dark

谷歌编码采访有竞争力的程序员

Total
0
Shares
0
0
0



在此视频中，我与竞争激烈的程序员Errichto进行了一次模拟Google编程采访。作为Google软件工程师，我采访了数十名候选人。这正是您将在Google或任何其他大型高科技公司获得的编码面试的类型。

观看我们在Errichto频道上制作的视频：https://www.youtube.com/watch?v=Y8VeyLG3NhY

准备编码面试吗？在AlgoExpert上使用77个有关热门访谈问题的视频解释和成熟的编码工作区进行练习：https：//www.algoexpert.io（使用“ clem”促销代码可享受折扣！）。

44 comments

  4. For the second half, my idea was to create a map<tuple<double, double, double>,int> where the doubles are line segment length, slope and x-intercept resp. where the slope is zero or more but not infinite (a vertical line). The x-intercept is where the perpendicular (to the line segment) through the left point in the pair hits the x-axis.

    If the slope is zero, the x-intercept is just x. Otherwise, it's y+x/m where m is the slope.

    Then you could use the similar count trick from the first half. I think that would be unique.

    That would have O(N^2 * (log N)^3) complexity and O(N) space used. To get down to O(N^2), maybe you could use an unordered map (hash table) and have constant lookup time with a hash function, perhaps based on the sum of the three doubles. Maybe Errichto could weigh on that idea.

  7. @errichto a solution could be taking the results of the first challenge and try to rotate them 90°. If all the four coordinates exist, then you'll find all the existing answers.

  10. For the second question why not just rotate all the points 45 degrees around the origin (so they have aligned x and y coordinates) and use the initial algorithm?

  17. Google's coding interviews are notoriously bullshit. Even Google has had to go back more than once to stop doing stupid shit that just a couple of years before they swore lead to better hires when data finally showed it didn't. Not sure why anyone would want to work for Google anyhow.

  19. I think these were soft balls given Errichto's history. Imagine being the interviewee but actually providing a much better solution than the interviewer and having to hand hold the solution.

  24. It could be done just with math.
    If you want to get the total number of squares, you could use X (for points at x axis) and Y (for points at y axis)
    Number_x = (x-1)+(x-2)+(x-3) … +1
    (Having in mind that you know the value of x and y)
    The same for y
    The number of squares is Number_x * Number_y

    More clear example, 4 by 3 points
    X = 3 +2 +1 => 6
    Y = 2 + 1 => 3
    It forms 6*3 => 18 squares.
    It is not calculating the horizontal possibilities, but do all the squares

  25. Now, it s clear why software crashes. So complicated solution for so simple task. 1. find all groups of four points (in our problem that is 126): 2. Make thee vectors AB, AC, AD: 3. Find the longest vector (presume that is AB): 4. Check is vect(AB)=vect(AC)+vect(AD): 5. If 4 is true that is paralelogram. 6. Check perpendicularity between vect(AC) and vect(AD). We need method for find all combination for 4 elements of N and override operator (+) to work with vectors in appropriate way.

  29. how about for the second task run algorithm once, then rotate all points coordinates by 45 degrees and run same algorithm second time. complexity will be still O(N^2)

  30. lol with the first two lines of summarising the problem, he pretty much solved it. Pretty trivial at that point. Fun to see people's thought processes when solving problems.

  31. Does counting the number of possible circles (without duplication) accommodating 4 points work? As in this case, if 4 points need to fall on a circle, the quadrilateral has to be cyclic … ???

  32. After reading through the comments I noticed a few "I feel so stupid" remarks. I understand why this video would produce those sorts of feelings – although I think they might be unjustified – if not simply myopic.

    Take into consideration the gaps in your knowledge. You simply don't have enough information to grasp what's going on – and neither do I. That's fine. It's not because you're stupid; it's because you're ignorant, which is entirely different matter altogether. If you can find a good starting point to start to fill in those gaps, there's a good chance you will develop the same ability – thus curing the malady of your ignorance.

    Another way of looking at it would be to consider your ability to tie your shoes. At this juncture of life, tying your shoes seems almost like an innate skill of sorts. However, trying your shoes is something EVERYONE struggled with at first. As time progressed, with enough instruction, and practice, you learned to literally do it with your eyes close. This is no different. Everyone starts 'tabula rasa', and everyone can work towards filling in those blanks.

    Kind regards.

  33. Solution with a middle point: for pair A, B points in addition to the middle point you record the length of AB. In that case, if there is C, D pair that has the same middle point and length, then ACBD will form a rectangle.
    The formula for the middle point is (A+B)/2, and formula for length is ||B-A||, where notice that (A+B) and ||B-A||^2 have integer values, thus it will be easy to store in the hashmap.
    Came up in <5 mins without a single note.

  34. competitive programming – how programming flops, how hackers steal your stuff, by his stupidity. How do you make a program FAIL. This fool can do so.

  41. I just solve fib problem and thinking wow i'm genius. But after seeing this video what the hell? I think i'm a kid in programmatic field.

  42. I haven't coded in 10+ years back in college so I might be far off here but can someone who's doing development please let me know why this approach wasn't taken?:

    1. Store all points
    2. Take set of 4 points
    3. Determine the cross point of the top right/bottom left and top left/bottom right
    4. If the cross point is equal, it's a rectangle.

    5. Iterate for all point combinations

Comments are closed.