round 1 & 2, https://leetcode.com/discuss/post/6678522/google-l4-interview-experience-usa-by-an-rcgo/

Googlyness - Standard questions. Expecting H.

Round 4

Warm up:

We receive a stream of tuples (timestamp, message) in non-decreasing timestamp order. We want to "show" a message only if we haven’t shown the same message in the last 10 seconds. Otherwise we suppress it.

Given:

(10, "solar panel activated") → show
(11, "low battery warning") → show
(12, "tire one: low air pressure")→ show
(13, "solar panel activated") → suppress (last shown at 10)
(14, "low battery warning") → suppress (last shown at 11)
(21, "solar panel activated") → show (21−10 ≥ 10)
(35, "solar panel activated") → show (35−21 ≥ 10)

Used HashMap to solve it in 10-13 min

Followup,

Now remove all messages that happened in past 10. secs.

(10, "solar panel activated") → supress, next shown at 11.
(11, "low battery warning") → suppress, next shown at 14.
(12, "tire one: low air pressure")→ show
(13, "solar panel activated") → suppress (last shown at 10)
(14, "low battery warning") → suppress (last shown at 11)
(21, "solar panel activated") → suppress (last shown at 13)
(35, "solar panel activated") → show (35−21 ≥ 10)

I funmbled this round. I intially went for creating a linkedlist of nodes where I delete the nodes that are in the timerange, using a HashMap<time, list> structure.

I gave a final TC of n^2 but could have been improved to O(n), which I have mentioned to the interviewer but just asked me to ignore it as we had less time. I always did not output the answer suitable for a stream. Once the interviewer asked me I had to change my code a bit to get the correct answer format.

Expect LNH - LH.

Clear explaination on the followup

If the input is as follows:

1 -> A
2 -> B
3 -> A
12 -> A
20 -> B
25 -> A

The output should be B,B,A.

If a string occurs more than once in a 10 sec window, then we would not print any occurance of that string in the block.

Update

The recuriter told me this round was positve.

updare 2
passed hc waiting for comp discussions.