Yahoo Interview Question
Software Engineer / Developersproblem 1: Create 3 lists, one for each dimension. Use the lists to store the indexs of the points in a sorted way. When sorting the nodes based on X, alwyas use |X|.
Next, try to find out the s points from these 3 lists in a parallel way, scan from the begining to the end. A hashmap is used to remove duplidated nodes.
The space is 3*N+S. the time is 3*N*(LogN)+3*S
Am I correct?
I will create a min heap with (0,0,0 ) as root and keep inserting data and this would be O(n log n). Every time I need to return s coordinates, I will do a breadth first search that will return the first s+1 closest coordinates to the origin (+1 is for origin and s for other coordinates). I have no idea how to do the second part :(
pls help
problem1: sorting X,Y and Z coordinates
- Anonymous September 23, 2009