Hashmap State Modeling: Aggregates and Composite Keys

Many "design" problems are about choosing what state to keep. The first draft usually stores every event and computes answers by scanning. The better design asks what each query needs, then keeps only that, usually in a dict with a well-chosen key. The result is $O(1)$ queries and memory that grows with the number of distinct keys, not the number of events.

The idea#

Three habits cover most of these problems.

Store aggregates, not history. If the query is an average, keep [total, count] and update it on each event. Scanning past events is never needed.
Key on exactly what the query asks for. If the query names a pair (start, end), make the tuple the key. Then the answer is one lookup instead of a filter over everything under start.
Separate transient state from permanent state. A check-in only matters until its check-out. Remove it (pop) as soon as it has been folded into the aggregate.

This works because an average, total or count can be updated one event at a time. So the aggregate after each event already holds the answer, and no query ever needs the events again.

Counters instead of a grid#

The same thinking works on a board game, where the aggregate becomes a set of counters. A win means one player owns a whole line. Keep a running signed sum per line instead of a grid: one player adds +1, the other -1, and mixed lines cancel out. Each move then updates only the lines through that cell.

Here is a trace on a 3 x 3 board, with player 1 adding +1 and player 2 adding -1:

Move	Player	`rows`	`cols`	`diag`	`anti`	Winner
(0, 0)	1	[1, 0, 0]	[1, 0, 0]	1	0	none
(0, 2)	2	[0, 0, 0]	[1, 0, -1]	1	-1	none
(1, 1)	1	[0, 1, 0]	[1, 1, -1]	2	0	none
(2, 0)	2	[0, 1, -1]	[0, 1, -1]	2	-1	none
(2, 2)	1	[0, 1, 0]	[0, 1, 0]	3	-1	player 1 (`diag`)

For contrast, the Connect Four LLD note scans the board for a win instead of keeping counters.

How to spot it#

These cues point to dict-based state modeling.

the query is an average, total or count over a group ("average time from A to B")
the first idea scans a list on every query
an entity has a start and an end event (check-in and check-out, open and close)
"after each move, did someone win?" on an n x n board
a fixed set of resource types with counts (spots, seats, stock)

Template#

Here is the shape of a design with a start event, an end event and an aggregate query. One transient map holds open entities; one aggregate map holds totals per query key.

init():
    open = empty dict             # entity id -> start info (transient)
    stats = empty dict            # query key -> [total, count] (aggregate)
start_event(id, info, t):
    open[id] = (info, t)
end_event(id, info, t):
    start_info, t0 = pop id from open      # done once it is counted
    key = (start_info, info)               # exactly what the query names
    stats[key] = stats.get(key, [0, 0])
    add the measurement (t - t0) to total; add 1 to count
query(key):
    total, count = stats[key]
    return total / count                   # O(1): no scan over history

Pitfalls#

Each of these costs you memory or correctness.

Keeping history you never query. If no question needs individual events, store the aggregate.
A key that is too coarse. start -> list of events forces a filter on every query; a tuple key doesn't.
Forgetting to drop transient state. Open entries that are never removed are a slow memory leak.
defaultdict(int) for list values. The default must match what you store, for example setdefault(key, [0, 0]).
One cell, several groups. A cell can belong to more than one counter group. Test each group independently, never with elif.
All-time aggregates for windowed questions. "Last 24 hours" needs buckets, not one running total.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Design Underground System.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Design Underground System

A first version keeps start -> [(end, duration), ...] and averages by scanning, which is $O(\text{trips})$ per query. Key on the tuple (start, end) with a running [total, trips] instead. A rider has at most one open check-in at a time, so a transient map keyed by rider id is enough.

Hint: Design Underground System: follow-ups

A check-out with no check-in makes pop(rider) raise KeyError: check membership first or use pop(rider, None). Route stats grow with station pairs (1,000 stations means up to 1,000,000 routes), so expire unused routes with a TTL or LRU. Concurrent += on one route can lose an update, so use a lock or an atomic update. "Last 24 hours only" needs per-hour buckets per route, as in Sliding Time Window.

Hint: Design Tic-Tac-Toe

Keep rows[n], cols[n], one diag and one anti sum. Add the player's value to diag if r == c and to anti if r + c == n - 1; test these independently, because the center of an odd board is on both. A line belongs to one player exactly when abs(sum) == n. Each move is $O(1)$ and memory is $O(n)$ instead of $O(n^2)$ .

Hint: Design Tic-Tac-Toe: after a win

LeetCode guarantees no moves after a win, so remembering the winner is optional.

Hint: Design Parking System

Use a dict {car_type: free_spots} instead of three variables, so a new type is a new key, not a new branch. The concurrency follow-up (two cars, one spot) is in Concurrency Primitives, and the full design is in the Parking Lot LLD.

Hint: Insert Delete GetRandom O(1)

Use a list for random access plus a dict value -> index. To delete, move the last element into the deleted slot, update its index, and pop the end. The dict makes lookups $O(1)$ , and the list makes random.choice $O(1)$ .

Hint: Detect Squares

Count points in a map keyed by (x, y). For a query point, treat every stored point with abs(dx) == abs(dy) > 0 as the opposite corner, then multiply the counts of the two remaining corners.

Hint: Design HashSet

Pick a fixed number of buckets (a prime like 769 spreads keys well) and store a small list in each. add, remove and contains hash the key to a bucket and only scan that bucket's list.

Hint: Design HashMap

Same buckets as Design HashSet, but each bucket holds [key, value] pairs. put updates the pair if the key is already in its bucket, otherwise appends a new one.

Key takeaways#

Ask what each query needs, and store only that.
Running [total, count] per key gives $O(1)$ averages; tuple keys match multi-part queries.
Remove transient state the moment it has been folded into an aggregate.
Signed counters per line turn "did someone win?" into an $O(1)$ check.
Running totals are all-time; windowed questions need time buckets.

Core idea#

Many design problems are about choosing what state to keep. Ask what each query needs, then keep only that, usually in a dict with a well-chosen key.

Key points#

Store aggregates, not history. For an average, keep [total, count] per key.
Key on exactly what the query names. A query on (start, end) uses that tuple as the key.
Drop transient state (pop) once it is folded into the aggregate.
Memory then grows with distinct keys, not with events.
Tic-Tac-Toe: player 1 adds +1, player 2 adds -1 to rows[r], cols[c], diag and anti. abs(sum) == n means a win.
Parking System: a dict {car_type: free_spots}. A new type is a new key, not a new branch.
Insert Delete GetRandom: a list plus value -> index. Delete by moving the last element into the gap.

Underground System follow-ups#

Follow-up	Answer
Check-out without check-in	Check `rider in active_trips`, or `pop(rider, None)`
Memory	Up to 1,000,000 routes for 1,000 stations; expire old routes (TTL or LRU)
Concurrent check-outs	`+=` can lose an update; use a lock or atomic update
Last 24 hours only	Per-hour buckets per route

Template#

check_in(rider, station, t):
    active_trips[rider] = (station, t)
check_out(rider, station, t):
    start, t0 = pop rider from active_trips   # transient state
    stats = route_stats[(start, station)], default [0, 0]
    add t - t0 to stats total; add 1 to stats trips
average(start, end):
    total, trips = route_stats[(start, end)]
    return total / trips                      # O(1), no scan

Pitfalls#

Keeping history that no query needs.
A key that is too coarse. start -> list of trips forces a filter.
Forgetting to drop transient state. That is a slow memory leak.
Tic-Tac-Toe diagonals with elif. The center is on both.
All-time totals for windowed questions.

Say it in an interview#

"A running total and count per route make every query O(1)."
"Signed counters per line turn a win check into O(1)."