I had two phone interviews (technical screens).
Round 1 was probably a new question from the interviewer — really hard. Given a set of node groups (e.g. [[1],[2,3],[4,5,6]]), connect all the groups into one connected graph. The way to connect: pick one node at random from each of two different groups and build an edge between them. The final graph needs to be connected, using the minimum number of edges (k groups need k-1 edges), and it has to be random.
Brute force is just enumeration, and it's suboptimal. Even a minimum spanning tree algorithm like Kruskal's isn't a uniform random spanning tree — some tree structures show up with higher probability than others, so you need a more advanced algorithm (not a standard one).
Input: groups = [[1], [2, 3], [4, 5, 6]]
Output: [(1, 3), (2, 5)] (one possible random result)
or [(1, 6), (3, 4)] (another possible result)
Round 2 was the classic type: a 2D grid (S = start, D = destination, X = obstacle, 1-4 represent Walk/Bike/Car/Train), plus cost[] and time[] matrices. You can only move horizontally/vertically, no diagonals. The base version restricts you to sticking with the same mode the whole way, and you find the fastest mode (tie-break on cheapest). The follow-up allows switching modes (with an extra penalty), then adds a limit on the number of switches.
Either run BFS 4 times, or do one BFS that also puts 1-4 into the queue state — both approaches work, though the interviewer probably wanted the second one. For the follow-up, they didn't make me actually write Dijkstra's — it was getting too complex, you'd already have to store several states — so I just talked through the approach at a high level.
In the end I passed, but there was no headcount. It's been on hold and can't move forward. They said they'd reach out when something opens up, but that was a while ago now...
Discussion
Loading comments…