- Given an array of coordinates, return the number of right angles (composed of 3 points) e that the coordinates can form (lines should be paralell to the x or y axis) . (0,0), (2,0) (0,2) is an example of a right angle.
- Design an order tracking system.
- Given a list of object (id, coordinates) and a list of (id1, id2) which indicates a bidirectional bridge, and start id and end id, return True if there is a way to get from start to end
3b. Take an extra input j, which denotes the amount of jumps that can be made ( from (0,0) to (0,2) is possible if j =2 ), and figure out if its still possible to get from start to end.
- list of objects (call this
platforms). the order is
(id, xcoord, ycoord)
[ (0, 1, 2) (1, 2, 3) (2, 3, 4) (3, 3, 5) ]
- list of tuple of ids (call this
(0,1)means there is an edge between platform 0 and platform 1.
[ (0,1) (1,2) (2,3) ]
- start id
- end id
True/False (depending on getting from start platform to end platform is possible)
for the next question, Take an extra input
j that indicates number of jumps that can be made from any platform. This jump can span either x axis or y axis.
[(0, 1, 2), (1, 1, 5), (2, 3, 5)]
Because from platform 0, there are no bridges but j is 3, so you can jump to platform 1. From platform 1 to 2, there is a bridge so you can go to platform 2.
- My approach was a n^2 time, n^2 space complexity solution. Traverse every point to all points with same x axis, then from the second point, traverse every point to all points with same y axis. Do the same but the axises flipped. Definitely was not the optimal solution.
- Did some API designs, system diagrams, but the interviewer did not seem satisfied.
- Solved the first part with DFS. Verbally talked about the solution for the follow up question but no time to code it. Definitely was not an optimized solution
Overall I did not expect to get these kind of questions; I thought i was prepared on most algorithms like string, arrays, dp, trees, and graphs, but obviously not enough to comfortably solve these kind of questions.