亚麻 SDE2 西雅图挂经

Job Hunting Interview
, , , ,
1
  1. 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.
  2. Design an order tracking system.
  3. 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.

3 explanation:

inputs are:

  1. list of objects (call this platforms ). the order is (id, xcoord, ycoord) 
[
(0, 1, 2)
(1, 2, 3)
(2, 3, 4)
(3, 3, 5)
]
  1. list of tuple of ids (call this bridges ). (0,1) means there is an edge between platform 0 and platform 1.
[
(0,1)
(1,2)
(2,3)
]
  1. start id
0
  1. end id
2

output is:
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.
E.g.
Platforms [(0, 1, 2), (1, 1, 5), (2, 3, 5)]

Bridges [(1,2)]

start 0

end 2

j 3

Returns True

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 approaches:

  1. 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.
  2. Did some API designs, system diagrams, but the interviewer did not seem satisfied.
  3. 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.

2

For number 1, came up with O(n^2):

int numberOfRightAngles (Point[] coordinates) {

    HashMap<Integer, List<Integer>> yGivenX = new HashMap<>();
    HashMap<Integer, List<Integer>> xGivenY = new HashMap<>();

    for(Point coordinate : coordinates) {
        yGivenX.getOrDefault(coordinate.x,new ArrayList<Integer>()).add(coordinate.y);
        xGivenY.getOrDefault(coordinate.y,new ArrayList<Integer>()).add(coordinate.x);
    }

    int numberOfRightAngles = 0;
    for(Point coordinate : coordinates) {
        int numberOfPointsAboveCoordinate = yGivenX.getOrDefault(coordinate.x, Collections.emptyList())
                                            .stream()
                                            .filter(y -> y > coordinate.y)
                                            .collect(Collectors.toList())
                                            .size();
        int numberOfPointsBelowCoordinate = yGivenX.getOrDefault(coordinate.x, Collections.emptyList())
                                            .stream()
                                            .filter(y -> y < coordinate.y)
                                            .collect(Collectors.toList())
                                            .size();
        int numberOfPointsRightOfCoordinate = xGivenY.getOrDefault(coordinate.x, Collections.emptyList())
                                                .stream()
                                                .filter(x -> x > coordinate.x)
                                                .collect(Collectors.toList())
                                                .size();
        int numberOfPointsLeftOfCoordinate = xGivenY.getOrDefault(coordinate.x, Collections.emptyList())
                                                .stream()
                                                .filter(x -> x < coordinate.x)
                                                .collect(Collectors.toList())
                                                .size();
        //  |
        //  |
        //  |_____
        numberOfRightAngles+= numberOfPointsAboveCoordinate*numberOfPointsRightOfCoordinate;
        //        |
        //        |
        //   _____|
        numberOfRightAngles +=numberOfPointsAboveCoordinate*numberOfPointsLeftOfCoordinate;
        //   _____
        //  |
        //  |
        //  |
        numberOfRightAngles +=numberOfPointsBelowCoordinate*numberOfPointsRightOfCoordinate;
        //   _____
        //        |
        //        |
        //        |
        numberOfRightAngles +=numberOfPointsBelowCoordinate*numberOfPointsLeftOfCoordinate;
    }       
    return numberOfRightAngles;
}