Small working systems: A Sample Coding Interview Solution

The coding question

Build a counter with put_element(key), get_element_count(key) and get_total_elements(). Each element expires t seconds after it was added.

Ask a few questions first

Ask	What we'll assume
Is an element that's exactly t seconds old still counted?	No, at t seconds it's gone.
Can the same key be added many times?	Yes, and each one counts and expires on its own.
Is the time real time?	Yes, but we'll let you pass in a clock, so tests can control it.
Do we need to handle threads?	Not for now. We'll mention it as a follow-up.

A couple of examples

Input	Output
t = 10. At time 0 put "a". At time 3 put "a" and "b". Then ask at time 3	count("a") = 2, count("b") = 1, total = 3
ask again at time 10	count("a") = 1, count("b") = 1, total = 2, since the first "a" just expired
ask again at time 13	count("a") = 0, count("b") = 0, total = 0

Start with brute force

Keep a list of every (time, key) ever added. For a count, go through the whole list and count the ones that match and haven't expired.

Cost: each read is O(n) over everything ever added, and memory grows forever.

A better way

Elements expire in the same order they were added, since everyone lives exactly t seconds. So the oldest one is always the next to go. A queue in time order means expiring is just popping from the front.

Keep a count per key and a total next to the queue. Whenever we pop an expired element, take one off its key's count and the total. Then every read is a quick lookup. This is the same sliding-window idea behind rate limiting, with a hash map for the counts.

Keep a queue of (time added, key), oldest first, a count per key, and a running total.
Before any operation, pop from the front while the oldest element is t or more seconds old, lowering its key's count and the total. Delete keys that hit zero.
put_element: expire, then add (now, key) to the back and bump the counts.
get_element_count: expire, then return the key's count, or 0.
get_total_elements: expire, then return the total.

The code

solution.pypython

import time
from collections import defaultdict, deque


class ExpiringCounter:
    def __init__(self, ttl_seconds, clock=time.monotonic):
        self.ttl = ttl_seconds
        self.clock = clock
        self.added = deque()  # (time added, key), oldest first
        self.counts = defaultdict(int)
        self.total = 0

    def put_element(self, key):
        self._expire()
        self.added.append((self.clock(), key))
        self.counts[key] += 1
        self.total += 1

    def get_element_count(self, key):
        self._expire()
        return self.counts.get(key, 0)

    def get_total_elements(self):
        self._expire()
        return self.total

    def _expire(self):
        cutoff = self.clock() - self.ttl
        while self.added and self.added[0][0] <= cutoff:
            _, key = self.added.popleft()
            self.counts[key] -= 1
            self.total -= 1
            if self.counts[key] == 0:
                del self.counts[key]

	Cost	Why
Each call	O(1) amortized	Every element is added once and popped once, so the expiring work averages out
Space	O(elements alive now)	Expired ones are removed as we go

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Asking about a key that was never added: returns 0, and doesn't create an empty entry.
An element exactly t seconds old: it's expired, because we pop when its time is at or before the cutoff.
Lots of puts at the same time: they all expire together.
Nothing called for a long time: the next call pops everything that's expired, and later calls are quick again.

Common mistakes

Calling time.time() directly everywhere, which makes the code really hard to test. Pass in a clock.
Adding up every key's count for get_total_elements. Keep a running total instead.
Forgetting to expire before a read, so counts include old elements.
Leaving keys with a count of zero in the map, so memory slowly grows with every key ever seen.

Follow-up questions

What if each element can have its own expiry time?

Then they don't expire in the order they were added. Swap the queue for a min-heap ordered by expiry time and pop from that.

What if millions of elements are added per second?

Group them into one-second buckets with a count per key, so the queue holds one entry per second instead of one per element. You lose a bit of precision at the edges.

How would you make it safe to call from several threads?

Put a lock around each public method, since they all change shared state through the expire step. Keep the lock short.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force and what it costs
10–15	Explain the better idea
15–30	Write the code
30–38	Test it out loud
38–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Uber.