﻿ # Google Coding Interview With A Competitive Programmer

Share
Embed
• Published on:  Saturday, September 28, 2019
• In this video, I conduct a mock Google coding interview with a competitive programmer, Errichto. As a Google Software Engineer, I interviewed dozens of candidates. This is exactly the type of coding interview that you would get at Google or any other big tech company.

Check out the video we made on Errichto's channel: https://www.viveos.net/video/Y8VeyLG3NhY/video.html

Prepping for coding interviews? Practice with 77 video explanations of popular interview questions and a full-fledged coding workspace on AlgoExpert: https://www.algoexpert.io (use "clem" promo code for a discount!)
• Source: https://youtu.be/EuPSibuIKIg

## Comment

• #### GaryChap

6 hours ago

Wow, this actually made me feel really good about my programming ability... for a problem I'd never encountered, under time pressure.

I had my own fast solution by the end of the video - and I actually preferred my solution! This immediately made me worry that I'd missed something super obvious. So, when I proved it for all the boundary cases, by stress testing against a generator, I was so impressed with myself. Such a confidence booster : )

I think I really need to learn to trust myself more... especially when there are more formidable voices in the room.

• #### Tuyến Nguyễn Văn

10 hours ago

I have a idea. Take two points (x1, y1) and (x2, y2) with (x1 != x2 and y1 != y2).
If there are both (x1, y2) and (x2, y1) exist in the list. They will make a rectangle.

• #### LoL_PerrY

13 hours ago

• #### LoL_PerrY

13 hours ago

If I ever get asked this question in any interview, I would just start searching for other jobs.

• #### Kristy Whalen

yesterday

0:39 are you related to Sylvester Stallone? :)

• #### Alon Wolf

yesterday

I think the diagonal direction was actually correct. For(a) for(c) check if b and d exist

• #### Nishant Sharma

yesterday

i learnt Java in 9th & 10th standard and C++ & SQL in 11th and 12th standard..thanks ICSE ..i can finally watch these videos

• #### john smith

yesterday

Search for telecommunication code in python... Ends up here...

• 3 days ago

"At 11 it gets complicated" is a reference to M-theory (superstring theory).

• #### Roberta Gallant

3 days ago

Everybody should now learn how to program / code computers for a change.

• #### Haroon Chughtai

3 days ago +1

Nick eh 30? Is that u?

• #### Ryan Joseph

3 days ago

60 seconds into interview I pull my internet cable out

• #### Juan Carlos

3 days ago

i dont watch the video, instead the comentaries LOL

• #### Miguel Hito

4 days ago

i dont understands

• #### SmileyMPV

4 days ago

I am surprised. I actually came up with a solution for the axis-aligned version that takes O(n*√n) time. I also came up with two O(n^2) algorithms for the general version.

For those interested, let me explain the algorithms. I will first explain the algorithms for the general version, because their explanations are a lot shorter. Although I do think that the algorithm for the axis-aligned version is the most elementary, because I assume almost no prior knowledge.

General version: Using slopes.

It is very hard to explain this solution without the assumption of basic linear algebra knowledge, so I am going to assume that. The basic idea is the following characterization of a rectangle. Four points A,B,C,D form a rectangle ABCD if and only if the following two properties hold.

B-A = C-D (This ensures opposite sides are parallel and equal length.)
(B-A)*A = (C-D)*D (Here * denotes the inner product. This ensures AD is perpendicular to AB.)

With this in mind, we can count all the rectangles very easily in quadratic time. We iterate through all pairs of points A,B and calculate B-A and (B-A)*A. We can encode this as a triplet of numbers, the x- and y-coordinates of B-A and the value (B-A)*A. For each triplet of numbers we encounter we keep track of the number of times we have seen this triplet. If we keep adding this number to our end total, by the same logic as the first algorithm in the video, we get the answer to the problem.

General version: Using center of rectangle.

I got this idea from the video, as he mentions you might be able to use the midpoint of the line segments. I am just confirming that you can. The basic idea is the following characterization of a rectangle. Four points A,B,C,D form a rectangle ABCD if and only if the following two properties hold.

|C-A|^2 = |D-B|^2 (Here |P| denotes the length of a vector. This ensures the line segments AC and BD have the same length. The square is to avoid the need of a square root and floating point arithmetic.)
A+C = B+D (This ensures the line segments have the same midpoint. To see this, divide both sides by two.)

To prove this characterization is a basic application of Thales' theorem. The algorithm is the same as the previous. Only now we iterate through pairs of points A,C and we calculate A+C and |C-A|^2 to get a triplet of numbers.

Axis-aligned version

The algorithm for the axis-aligned version consists of two major parts. As preparation, we partition the given points on x-coordinate. Since we are only interested in axis-aligned rectangles, the only important thing about the x-coordinates of different points is whether they are the same or not. So at this point we can completely forget about the actual x-coordinates and only focus on the partition.

This means that we now have a list L of lists of y-coordinates. A rectangle would now correspond to a pair of y-coordinates (y1,y2) and a pair of lists (A,B) from L such that both y1 and y2 are contained in both A and B. To avoid double counting, let us add the restriction that y1
The first major part of the algorithm

Consider the following sub-problem. For a fixed list A from L, determine the number of rectangles that A is a part of. We can do this in linear time as follows.

First make a hashset (std::unordered_set in c++) of all y-coordinates in A. Then iterate through all the other lists B in L. For each list, count the number of y-coordinates in the list that are also in A. This can be done in constant time per element of B by using the hashset. Call this number x. Then there are (x choose 2) = x(x-1)/2 possible pairs of y-coordinates that are contained in both A and B. We simply sum this number over all lists B≠A. This gives us the number of rectangles that A is a part of.

Obviously, there can be a linear number of lists in L, so if we do this for each list in L, we will get quadratic time. So we have to do something more complicated than that. We are only going to do this for all the long lists in L. Let us define a list A in L to be long if its length is at least √n. If there are x long lists, then this step will take O(x*n) time. But note that there is a total of at least x*√n points in the long lists, so x*√n≤n, so x≤√n. This means that this step takes only O(n*√n) time.

One detail to consider is that this will double count all rectangles (y1,y2) (A,B) for which both A and B are long lists. To solve this problem, for each long list A, we only iterate through the other lists B that either are short (i.e. not long) or come after A in L. This concludes the first major part of the algorithm. We now have the total number of rectangles (y1,y2) (A,B) such that either A or B (or both) is a long list.

The second major part of the algorithm

We can start by removing all long lists from L and only focus on the short lists. This means we can now assume every list is at most √n long. This part is actually relatively simple.

We basically do the algorithm from the video. For each list, we consider every pair of y-coordinates. For each pair of y-coordinates, we keep track of how many times we have seen it before. If we keep adding this number to our end total, we will end up with the correct answer.

Note that each point is part of at most √n pairs, because it can only form a pair with another point in the same list. This means that the complexity of this step is indeed O(n*√n).

• #### Marc-Andre Rousseau

4 days ago

Would this be an impressive solution in an interview at google?

• #### Ammo MD

4 days ago

It bothers me that they didn't explore the midpoint as that is how I ended up tackling it. It seems the most intuitive to me as you can hash pairs of points by their midpoints and then just use the dot product to determine if 2 pairs of points that share a midpoint form a rectangle. It was nice giving my brain a bit of a workout when I was planning on going to bed.

• #### Jianhao Luo

5 days ago

Should be x*x2 + y*y2 =0 to determine 90degree angle its a mistake

• #### Laser Armor

5 days ago

Could you do more (fake) coding interview videos with Errichto? This was super-interesting to watch!

• #### 47Mortuus

5 days ago +1

The facial expressions of this interviewer man...

So much of what's inside of you is visible to the world - and we can see you're a spastic xD
Being interviewed by him in a real interview would lead me to thinking "can i please speak to someone who's qualified? This guy's asking me if a 2D coordinate system makes sense". 