So I had an onsite round today with Google, where I was asked the following question.

Given a really large log file where each row contains id, timestamp and an event for a service.

Something like this,

And given a integer value, TIMEOUT = 3

We need to find the ids of services that have timed out.

A service is said to have been timed out if the time between end and start of the service >= TIMEOUT

There can be multiple starts and ends for the same id and there might also be the case that one of the entries is missing from the file because of some I/O error. For eg, it is possible that there are two entries corresponding to START for the same id.

I was able to provide a couple of solutions with T.C. - O(n^2), O(n) and S.C. O(1), O(n) respectively.

But the interviewer was looking for something in between for both T.C. and S.C.

I was just wondering what is the solution that he was looking for.