Here's a coding interview problem from Amazon:
We have an array of tuples, or an array of arrays of two items each.
This represents points on a two-dimensional space
So for example this first item, (-2, 4) represents
this point right here because the x-coordinate of this point is -2 and the y-coordinate of this point is
4 and the problem is this:
given these points,
how would you find the K closest points to the origin? And of course the origin is at (0,0).
So for example, if the given K is 2, how would you find the two closest points
to the origin out of these points? The two closest points here are (-1,0) and (0,-2)
so you should be able to print these points and try solving this problem in a more general way
To practice pause the video right here
And think about how you would solve the problem and then come back to the video
the first natural step for solving this problem is to find the distance to each point from the origin and
of course we can use the Pythagorean theorem to do that so to find the distance to for example at this point, (-2,4)
We can just find the value of square root of
minus 2 squared plus 4 squared which
is equal to
square root of 4 plus 16 which is square root of 20 so that's
the distance from the origin to (-2,4) and we can go through the same procedure for
every other point to find the distance for every other point as well, and after that you can just
construct a new array with objects
containing the coordinates of each point as well as the distance to each point from the origin and
this new array might look like this
I'm calling this new array points_with_d as in points with distance and the first object of this
new array will correspond to the first item in the original array
with the coordinates (-2,4) and with this is square root of 20 of course,
and we're going to have the same type of object for every other point in the original points so the length of points_with_d
the new array will be the same as the length of the original array points,
and you can use dictionaries or hash tables to store this information
Instead of using objects as well
Once you have this array all you need to do is, you just need to find the K objects or the K points
with the shortest distance
So at this point this problem is actually equivalent to the problem of finding the K smallest
elements in a given array of numbers
for example if the given array is this array of integers, and if the given K is 3
We want to be able to find the three smallest items out of this array
Which are 1 2, and there are right here now
There are a few different approaches for solving this problem
The simplest approach is the one in which you sort this array in an ascending order so that the smallest items
come first and out of the sorted array take the K first items,
and that approach would take Big O of n log n in time if you use for example quick sort or merge sort
another approach is using a variation of something called selection sort and
I'm not going to go into detail here in this video
But this approach would take Big O of nk in time
Now my personal favourite approach is the one in which we use a max-heap and this one would take
Big O of (K + (n - k) log k) in time. Let me explain
how it works. First of all let's quickly go over what a heap is. In a sentence
It is an efficient way to keep track of the largest value in the given collection of numbers
Suppose as an example
You're given these three numbers
4, 1, 5. If you construct a max-heap with these three numbers, you can sort of visualise it as
a bag or a box of these three numbers,
and however many numbers you have in the max-heap
Retrieving the largest number out of it is very efficient. In fact, asking the heap what the largest number is
Without modifying the heap, so just examining what the number is without retrieving the number itself
will be done in Big O of 1 in time. Now, there are a few other operations
we're going to use on a heap for this particular problem. The first one is create
creating a heap, a max-heap, with K items
takes Big O of K in time the second operation is replace.
So for example, if we want to replace the current largest number in
the given heap, this one with a new number three,
then this heap will be rearranged so that the current largest number will be four, and they will have one and three
below it. This operation takes Big O of log K,
where K is the number of items in the heap, and the third operation is print all.
This prints all the items in the given heap in the order
that's not necessarily sorted. So for example, this operation on this particular heap
Might print 4, 1, 3, and this operation takes Big O of K in time.
Now, how can we use a max-heap and those operations on it to find the K smallest items in a given array of numbers?
Let's consider this array of numbers again and
Let's say we want to find the three smallest items.
Then the first step will be to construct a max-heap with the first K items, or with the first three items.
After that, for each item in the remainder of the array, ask ourselves, is this number
smaller than the current largest number in the heap? If it is smaller then replace it
with the current largest number.
So when we are examining this number right here, 2, the heap will look like this,
And the current largest number has become 4, and when we're examining this number 3,
4 will be replaced with 3.
We're going to keep going like that, and when we're examining this number, 10,
because this is not smaller than the current largest number in the max-heap,
we'll just ignore that number, and at the end of this process just print all items from this heap,
and we're done. We have the K smallest items from the given array. Now let's quickly recap our entire strategy
Using pseudocode we're going to define our function closest,
which takes the given points, and K, for finding the K closest points to the origin.
And from this function, we're not going to return anything,
but we're going to print the K closest points. And in this function, first of all using points, create
points_with_d for points with distance, an array of objects
containing the coordinates, as well as the distance to each point from the origin.
After that, using points_with_d
the array of objects, create a max-heap with the first
K items, and use the distance as the key when we create a max-heap.
Let's just call this max heap MH. After that,
run a for loop for each point in the remainder of the array,
and if this point's distance is less than the current max of MH,
then replace MH's current max with p, and once we're done with this for loop, then just print all points in
MH, and we're done. Now what about time complexity? Let's think about it line by line.
The first line here, using points creating points_with_d
takes Big O of n because we go through this array only once,
and creating a max-heap with K
items, as we discussed earlier, takes Big O of K in time, and here we're running n-k loops.
In each loop, replacing MH's current point with p takes Big O of log K,
and so the runtime for this entire for loop will be Big O of n-k times
log K in the worst case scenario.
After that, printing all points in MH will take Big O of K in time.
So adding them all up, Big O of n plus Big O of K
plus Big O of n - K times log K + Big O of K
We're going to have Big O of n
plus n - K times log K. And that would be the runtime for this entire solution.
Ok, thanks a lot for watching this video. If you liked this video I would also recommend
my course on Udemy, 11 Essential Coding Interview Questions, in which I cover
11 of the most essential coding interview questions to master with coding exercises in Python and Java.
In case you're interested in taking the course. I put a discount code below in the description. Alright,
I'll see you in the next video.