Python Fundamentals for Interviews: Data Structures, Comprehensions, and Gotchas

Part 2 of 18 · ~4 min

The Four Core Collection Types

Split one of those log lines on whitespace and you get six strings. The first real decision is what to hold that parsed row in once you have it.

entry = ("203.0.113.42", "GET", "/api/search", 200, 118)  # a tuple — this row is done changing

A tuple, not a list. The request already happened; nothing about that row is ever going to need editing, and picking a tuple over a list is how you tell the next person reading this code exactly that, without a comment. There's a very concrete payoff waiting a few lines down, too: a tuple can be hashed, so it's allowed inside a set or as a dict key, and a list is permanently barred from both jobs no matter what it happens to contain.

seen_this_minute = {("198.51.100.7", "/api/login"), ("203.0.113.42", "/api/search")}  # a set of tuples — fine
seen_this_minute = {["198.51.100.7", "/api/login"]}  # TypeError: unhashable type: 'list'

Big-O cheat sheet for the built-ins

Go back to check_logs in the introduction. seen_ips was a list, and if ip not in seen_ips ran on every single line. in on a list means Python walks it from the front until it finds a match or runs out — a linear scan, O(n). On a gateway logging tens of thousands of distinct IPs a day, that one line turns an O(n)-line file into an O(n²) program, and the watcher gets slower every day the process stays up — not because the log grew, but because the list being scanned against grew.

Swap the list for a set and nothing else in the function has to change:

seen_ips = set()
# ...
if ip not in seen_ips:   # O(1) average — a hash lookup, not a scan
    seen_ips.add(ip)

That single substitution is most of what a "how would you make this faster" interview answer actually is: notice the collection being scanned repeatedly inside a loop, and change what kind of collection it is.

collections — the standard library's specialized containers

list, tuple, set, and dict handle nearly everything the watcher needs day to day, but three names imported from collections handle the handful of jobs those four are individually awkward at.

from collections import defaultdict, Counter, deque, namedtuple

# defaultdict — group every parsed entry by the IP that made it, no existence check needed
by_ip = defaultdict(list)
for entry in entries:
    by_ip[entry.ip].append(entry)          # by_ip[ip] auto-creates [] the first time this IP shows up

# Counter — which status codes are actually showing up, and how often
status_counts = Counter(entry.status for entry in entries)
status_counts.most_common(3)               # [(200, 8210), (401, 340), (500, 12)] — worst first

# deque — a sliding window of an IP's recent request timestamps, O(1) off either end
recent = deque()
recent.append(request_time)                # newest goes on the right
if recent and now - recent[0] > 60:
    recent.popleft()                        # drop anything older than 60s — O(1), not O(n)

# namedtuple — LogEntry.ip instead of entry[0]
LogEntry = namedtuple("LogEntry", ["ip", "method", "path", "status", "duration_ms"])
e = LogEntry("203.0.113.42", "GET", "/api/search", 200, 118)
e.ip, e.status                              # ("203.0.113.42", 200) — reads like an object, is a tuple

namedtuple is the one worth adopting immediately: reaching into a plain tuple by position (entry[0], entry[3]) is exactly the code smell it exists to remove, and from here on the watcher writes entry.ip and entry.status instead. Hold onto that deque, too — it isn't a throwaway example. A sliding window of recent timestamps is precisely the data structure a rate limiter needs, and the closures chapter builds one around exactly this deque, once there's a function to put it inside of.