Amazon Coding Interview Question - K Closest Points to the Origin

Amazon coding interview question and answer.

If you liked this video, I would also recommend my Udemy course, "11 Essential Coding Interview Questions":

(You'll get a discount through the link above.)

[kenhaley]

Two optimizations: (1) We don't need the actual distances, just relative distances. So, skip calculating the square roots (computationally heavy). just store the sum of squares as "distance". (2) No need to create the entire points_with_d array and storing it. Create the max heap right away and put/replace elements into the heap as you calculate the "distances". The heap still has points and distances, but only k of them.

[fasttorwa]

A bigger whiteboard might be a good investment. :)

[stumashaal]

is it just me or is this guy always solving questions that are easier than the ones I hear about my friends being asked in actual amazon interviews?

[ricardofranco]

Mathematician here. Intuitively, I went through it with the heap approach without knowing what it was called! Great vids! Thank you!

[denzillong]

Nice! This is a common real-world problem / solution used in video game development.

[joeliovl]

These videos are awesome. Dont stop making them pls !

[umarhn]

Sir, please continue with the videos, it's the best thing that happened to me on youtube !

[theyruinedyoutubeagain]

You can do it in O(N) easily by using the partitioning step in quicksort. You don't even need extra space since you can just compute the distance at each step since that's O(1), but that obviously invites the discussion about the tradeoff between space and time.

[ThunderBow]

Pre-explanation (1:04). I would approach this with a O(n) algorithm where I compute the euclidian distance of each coordinate and populate a new array with the values (unless its allowed to overwrite the original array). I would then do a quicksort, O(nlogn), on the list and return an array with the first k elements. Overall runtime is O(n+nlogn), which reduces to O(nlogn)

[pagrus]

The elegance of the heap solution sold me your udemy course

[melvin]

Wow, 1 month ago I couldn't solve this problem. But I just so have happened to watch 3Blue1Brown his videos and now this question was obvious. This is not a coding question at all, it is a math question disguised as a coding question.

[MrMLBson]

I have a 3 hour onsite java developing interview. If they ask me something like this, I'm just going to stand up, pack up my things and show myself out LOL

[Street_Food_Adventuress]

I just received an Amazon test assessment and i had exactly this question

[atrumluminarium]

√x is a strictly increasing function so a>b <=> √a>√b. Since we are only doing comparisons, the square root is a bit redundant

[smestre]

Aww thats a really neat solution. My solution using a sweep line was O(N+(N+K)logN)

I do have one question though: isn't building a heap with k elements a O(k logk) algorithm?

[jaimeduncan]

Hi very good video. Some details 1. Remove the square root, there is no need for it. If the sqrt(a) >sqrt(b) and both are positive numbers I know that a>b. (The reverse is also true, but it does not matter for this problem ). The second point is : you can merge both cycles, creating the heap once you reach k. But that will complicate the video and the explanation, so I agree with you: in an educational video is better than the ideas are clear than optimal. The sqrt removal, on the other hand is pretty easy to understand.

[CookieAvenger]

You can do it in O(n), so create points with distance which takes O(n), then a median of medians selection to find the kth smallest distance in O(n) time. Finally you can loop through all the distances printing out everything smaller than or equal to the kth smallest distance, which also takes O(n)!! Overall - O(n).

[juanuribe]

Nice video! I was actually asked this question by Facebook

[kittenhero]

You could get a better solution with min heap for O(n + k log n) by using heapify and remove min

[radekhladik]

This is actually a quite nice problem. It's solution can vary according to specific details a lot.
What metric should be used: euclidean, taxi(i.e. pixels on screen), maximum (i.e. number of pixels in line on screen), spherical (points are on earth)
What is the domain of x and y? For example integers are fast so one would do the sqrt as last as possible and only if needed. When calculating with floats it could be simpler to calculate it every time...
What is the distribution of input points? For example in case of Euclidean metric you could use simple optimalization. You can have variable for max x^2+y^2. If x>maxx2y2 or y>maxx2y2 then ignore point.
Can there be points with same distance?
Do you need to print out the points and/or their distance?
And some special cases for K=1, K=2. Small K can be done with simple array, large K with the use of linked lists...
And it would be really interesting when you would consider some sort of parallelism...