Mock problems: design-style data structures

What a design-style question looks like

The interviewer describes a class and its methods: "Design a cache with get(key) and put(key, value), both O(1); when it is full, remove the least recently used key." You choose the data structures, write the class, and explain the cost of each method. No single structure does everything, so the answer is usually two structures working together.

LRU cache

A cache keeps recent answers so they can be returned quickly. When it is full, something must go. LRU (least recently used) removes the key that was used longest ago, because recently used data is likely to be used again. You need two things fast: find a key (a hash map does that in O(1)) and know the usage order, moving a key to "most recent" and removing the oldest (a doubly linked list does that in O(1), because a node can be unlinked when you hold a pointer to it).

The classic design is a dict from key to list node, plus a doubly linked list ordered from oldest to newest. get moves the node to the newest end. put inserts or updates at the newest end and, if over capacity, removes the node at the oldest end and its key from the dict. Python's collections.OrderedDict already combines both, so you can use it when the interviewer allows; be ready to explain the linked-list version too.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)          # now the most recent
        return self.data[key]

    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # remove the least recent

c = LRUCache(2)
c.put(1, "a"); c.put(2, "b"); c.get(1); c.put(3, "c")
print(list(c.data))   # Output: [1, 3]  (key 2 was least recently used)

Hit counter and rate limiter

"Count the hits in the last 300 seconds" and "allow at most 100 requests per user per minute" are sliding windows over time. Keep a deque of timestamps; when a request arrives, pop timestamps older than the window from the left, then check the length. Each timestamp is added and removed once, so the cost is O(1) amortised per call. If many hits share a second, store (timestamp, count) pairs to save memory.

Time-based key-value store

set(key, value, timestamp) stores a value at a time, and get(key, timestamp) returns the value set at the latest time ≤ timestamp. If timestamps for each key arrive in increasing order, keep, for each key, a list of times and a list of values. They stay sorted, so get can use bisect_right(times, timestamp) − 1 to find the answer in O(log n). set is O(1) (append).

Insert, delete and getRandom in O(1)

A list gives a random item in O(1) (random.choice) but deleting from the middle is O(n). A dict finds an item in O(1) but cannot pick a random one fairly in O(1). Use both: a list of values and a dict from value to its index in the list. To delete, move the LAST value into the deleted slot, update its index in the dict, then pop the end of the list. Every operation is O(1).

Common mistakes

• In LRU, forgetting that get also makes a key "recently used". Fix: move it to the newest end on every get that finds it.
• In LRU, evicting before updating an existing key, so a key is removed for no reason. Fix: if the key exists, update it in place; evict only when the size goes over capacity.
• In the time store, using bisect_left, which misses a value set exactly at the asked time. Fix: bisect_right(times, t) − 1, and check that the result is ≥ 0.
• In getRandom-set, deleting the last element and then writing it back into its own (now missing) slot. Fix: handle "the value is the last element" correctly, or do the swap before popping, as in the solution.
• Not stating the cost of every method. Fix: finish with a short table: get O(1), put O(1), space O(capacity).