Amazon Interview Question Software Engineer / Developers
A little addition:
Finding Closest Point for a given (x,y):
1. Look for x JUST smaller then given x, look for y JUST smaller than given y, calculate the distance (say d1)
2. Look for x JUST smaller then given x, look for y JUST greater than given y, calculate the distance (say d2)
3. Look for x JUST greater then given x, look for y JUST smaller than given y, calculate the distance (say d3)
4. Look for x JUST greater then given x, look for y JUST greater than given y, calculate the distance (say d4)
5. Look for same x, look for y JUST greater than given y, calculate the distance (say d5)
6. Look for same x, look for y JUST smaller than given y, calculate the distance (say d6)
7. Look for same y, look for x JUST greater than given x, calculate the distance (say d7)
8. Look for same y, look for x JUST smaller than given x, calculate the distance (say d8)
9. point of MIN(d1,d2,d3,d4,d5,d6,d7,d8) is the closest point.
you can use a HASH Table for it.. like a array of pointers(structure pointer)and then from every index(use it as x coordinate) and store the y coordinate in the array[index]..and like wise for all those numbers whose x coordinate are same..just cr8 a link list from that index which will point to all points of same x coordinate..
struct *number[].
store only the y coordinate let say point (0,1) . cr8 a node .store 1 and store the address of the node in number[0]..and so on go on storing all those number having coordinates after the node which stored 1..as a single link list..
in this way we can store all points..
and then for searching first check X coordinate and then go to that number[x coordinate) to move to the starting node of that point and search for y coordinate in that link list...( u can get nearest point to it in this easily..)
How about k-d tree
Building a k-d tree: O(n log 2 n)
Insertion; O(logn)
Searching closest point: O(sqrt(n))
if k == 1, a kd-tree is nothing but a binary search tree (BST). A node has a single key (x) and for each node all the keys in the left-subtree of the node are less-than this key and all the keys in the right-subtree are greater-than or equal to this key.
if k == 2, a kd-tree is almost the same as BST except for a minor change. Note that each node now has two keys (x, y). Instead of using only one key we will try to use both of them. Let 'l' be the level/height/depth of a node 'n' in the tree. Assume that the root is at level 0. If ('l' mod 2 == 0), all the (x-keys) in the left sub-tree are less-than the x-key of 'n' and all the (x-keys) in the right-subtree are greater-than are equal to the x-key of 'n'. On the other hand if ('l' mod 2 == 1) the rule will be applied to thr y-keys. It is just a modified-BST with the comparison rule applied to the k-keys depending on the level of the node. This may sound confusing, but it helps to visualize the structure as follows. For the root (rx, ry), all the points in the left sub-tree are to the left of the vertical line X = rx and those in the right sub-tree are to its right.
Let the root of the left sub-tree be (lx, ly). For this node all the points in the left sub-tree are to the bottom of the horizontal line (Y = ly) and those in the right sub-tree are to its top. The same horizontal line logic goes for the root of the right sub-tree (rx, ry).
NOTE: Even though I said horizontal line (Y = ly), it is infact a line-segment (Y = ly && (X < rx)). See the article on wikipedia for a visual example.
The above logic can be extended to k-dimensions easily.
For calculating shortest distance we can use formula (squareroot of (x-x1)^2+(y-y1)^2). here x,y are the given points and x1,y1 can be iterated from hash map
you have to store the (x,y) in a structure and maintain the array of this structure for storing all the points...
a) We have to sort all the element based on x cooridinate
b) then we have to use divide and conquer to get the smallest distance..
For more info refer cormen or mark alen weiss
Not sure if this is best soln:
- Anonymous February 08, 20111. Store x co-ordinates in a BST (Say X BST)
2. For y co-ordinates , Design a Hash table where key will be corresponding x value
. Here many y can have same x, so store all such y in a BST, and slot for x key in Hash table will point to the root of this BST
Using these Data Structures, All x will be in one BST and All y will be in corresponding x key BSTs in Hash Table.
Searching a given (x,y):
1st look of x in X BST (log n), if not found, return -1, else look for y in Hash table, in x key BST(log n).
Seach Time: log n
Finding Closest Point for a given (x,y):
1. Look for x JUST smaller then given x, look for y JUST smaller than given y, calculate the distance (say d1)
2. Look for x JUST smaller then given x, look for y JUST greater than given y, calculate the distance (say d2)
3. Look for x JUST greater then given x, look for y JUST smaller than given y, calculate the distance (say d3)
4. Look for x JUST greater then given x, look for y JUST greater than given y, calculate the distance (say d4)
5. point of MIN(d1,d2,d3,d4) is the closest point.
Time: log n
This design looks scalable, Any number of new points can be added anytime.