Uber Coding Interview: Expiring Element Counter

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Uber. We'll work through a coding problem together, so please think out loud as you code. If you need to step out or take a break, you can pause the interview any time with the Pause button at the top right.

The problem is about a counter whose entries expire after a set lifetime, a bit like tracking recent ride requests that go stale. It's in the Problem tab on the right, so please read it through, take your time, and ask me any questions before you start.

The problem

Build a counter whose elements each expire ttl seconds after being added.

• ttl: lifetime, in seconds, of every element.
• operations: chronological list of {kind, key, time}; kind is "put" or "count".

"put" adds one element under key at time. "count" asks how many elements under key are live at time: an element added at time s is live at time q when q < s + ttl. Times are non-decreasing. Return the answers to the "count" operations, in order.

Example: ttl = 10, operations = [put a@1, put a@5, put b@6, count a@8, count a@11, count b@16] → [2, 1, 0]

1 ≤ len(operations) ≤ 10^5; 1 ≤ ttl ≤ 10^9.