Collections for interviews

Costs to know

if x in big_list inside a loop is the classic accidental O(n²). Convert to a set once.

defaultdict and Counter

from collections import defaultdict, Counter
groups = defaultdict(list)
for word in words:
    groups[word[0]].append(word)     # no KeyError, no setdefault dance

counts = Counter(words)
counts.most_common(3)                # [('a', 5), ('b', 2), ('c', 2)]
counts["missing"]                    # 0, not KeyError

Careful: just reading groups[k] on a defaultdict inserts k.

deque for queues

from collections import deque
q = deque([start])
while q:
    node = q.popleft()               # O(1); list.pop(0) is O(n)

deque(maxlen=100) keeps only the last 100 items: perfect for "recent events".

heapq is a min-heap

import heapq, itertools
heap, tie = [], itertools.count()
heapq.heappush(heap, (priority, next(tie), task))   # tie-breaker avoids comparing tasks
priority, _, task = heapq.heappop(heap)

heapq.heappush(maxheap, -value)                     # negate for a max-heap
heapq.nlargest(k, items, key=lambda x: x.score)

Without the counter, two equal priorities make Python compare the tasks themselves: TypeError: '<' not supported for dicts.

bisect on sorted lists

from bisect import bisect_left, insort
i = bisect_left(sorted_times, t)     # first index with value >= t
insort(sorted_times, t)              # insert and stay sorted

LRU with OrderedDict

from collections import OrderedDict
class LRU:
    def __init__(self, cap): self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k)          # mark as most recent
        return self.d[k]
    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False) # evict least recent

functools.lru_cache does this for function results (arguments must be hashable).