I was asked this question in one of my technical onsites round for SWE 2 position at Google. This is actually a continuation of my previous post where I had mentioned about this question and some people wanted to know more about it.

We have this server which generates logs and we want to process the complete set of logs generated by this server. Each log entry has an ID, start and end time...but the log entries for start and end time are separate.

We need to find out what is the first log entry when we can say for sure that a certain log has taken more than K seconds to process. We need to return that time instant and the log ID. If there's no such log entry which exceeds K seconds, then we just return a pair {-1, -1}

Eg. with K = 3, for the below example we get the log ID as 2 and the timestamp when we know is 6.

Timestamp logID

The the above set of events look like

|-------|
    |-----------------------|
                        |-----------------------

0   1   2   3   4   5   6   7   8   9

Assumptions that I clarified:

1. Timestamps will be non-decreasing (i.e. two logs might arrive at the same instant)
2. It might never happen that a certain log is ending, but only that if there's a start event for some logID, that will surely be before its end event.

Solution:
We need to use a queue data structure but we also need to remove the elements which are getting ended.

I gave a "deque" based solution wherein the insertion would be at the end but the removal can happen in the middle too.
Then I told the interviewer that I'll augment this data structure to support O(1) insertions and deletions from the "queue"-like data structure.

I ended up with the following

1. list<pair<int, int>> - To store the (timestamp, id) pair
2. unordered_map<int, list<pair<int, int>::iterator>> - To map the id of the log to a certain entry which already exists in the above list.

Overally TC: O(N) for processing all the elements.

P.S. This is more like a Medium-hard problem which combines a bunch of different concepts but the interviewer had kept the question so vague that I had to clarify all the above assumptions and some more