Looking at the recent interview reports on 1point3acres, they're mostly the shortest-path problem — I specifically prepared for that for a long time, but it turned out not to be that. It was an uncommon, old question.
There were several event objects (sim id, type, timestamp) representing various events for a simulation's state. Type is one of start, ping, end. start means the sim starts, ping means the sim is still running and updates the sim's last timestamp, end means the sim ends. Now given a timeout limit, say 3 seconds — if a sim's last timestamp is more than 3 seconds behind the current timestamp, the sim automatically times out. I needed to write a function that can receive a new event and return all sims that are currently timed out.
The trick is to use a heap and a map. The heap sorts events by timestamp, and the map is sim id -> last timestamp. The reason you need the map is that the sim corresponding to the event at the top of the heap might have already ended long ago, or it might still be pinging.
Once I figured it out, it wasn't that hard. But I hadn't interviewed in a long time, so I was really rusty. I completely forgot the heap syntax and its time complexity — I actually said it was O(n log n), and I laughed at myself for being so dumb.
Discussion
Loading comments…