P1 Frequency count · P2 Top-K

FreeLesson 57 of 78

P1Frequency countDEEASY

Sounds like: "how many of each status", "most common error message", "count events per page"

Worked question: Count orders per status and per (customer, status), then the two most visited pages from the event stream.

Approach: 1. pick the key, a tuple if it is two columns 2. Counter over a generator 3. most_common for the top

SOLUTIONPYTHON 3.12

import csv, json
from collections import Counter

orders = list(csv.DictReader(open("orders.csv")))
by_status = Counter(r["status"] for r in orders)
pairs = Counter((r["customer_id"], r["status"]) for r in orders)
print(by_status)
print(by_status.most_common(1), pairs[("1", "delivered")])

with open("events.jsonl") as f:
    pages = Counter(json.loads(line)["props"]["page"] for line in f)
print(pages.most_common(2))

counts = {}                                   # by hand
for r in orders:
    counts[r["status"]] = counts.get(r["status"], 0) + 1
print(counts == dict(by_status))

Output

Counter({'delivered': 12, 'cancelled': 2, 'returned': 1})
[('delivered', 12)] 3
[('/cart', 3), ('/checkout', 2)]
True

P2Top-KDEMEDIUM

Sounds like: "top 3 customers by spend", "10 largest files", "k most frequent words"

Worked question: The top 3 customers by delivered spend, first with the library, then with a heap you write yourself.

Approach: 1. aggregate first (P1/P3) 2. keep only k items in a min-heap 3. sort the k survivors at the end

SOLUTIONPYTHON 3.12

import csv, heapq
from collections import defaultdict

spend = defaultdict(float)
for r in csv.DictReader(open("orders.csv")):
    if r["status"] == "delivered":
        spend[r["customer_id"]] += float(r["amount"])

print(heapq.nlargest(3, spend.items(), key=lambda kv: kv[1]))

def top_k(pairs, k):              # size-k min-heap: O(n log k)
    heap = []
    for cid, amt in pairs:
        if len(heap) < k:
            heapq.heappush(heap, (amt, cid))
        elif amt > heap[0][0]:     # beats the smallest kept
            heapq.heapreplace(heap, (amt, cid))
    return sorted(heap, reverse=True)

print(top_k(spend.items(), 3))

Output

[('5', 5096.0), ('1', 5094.0), ('2', 4143.0)]
[(5096.0, '5'), (5094.0, '1'), (4143.0, '2')]

Follow-ups interviewers ask

They ask	You answer
"Count words in a 30 GB log."	Stream lines (P13), Counter per batch, then add the batch Counters: Counter supports +. Or split the file across processes and merge.
"Top 10 with ties at the cut-off?"	nlargest drops ties at the boundary. Find the 10th value, then keep everything at or above it.
"The data does not fit in memory."	Keep a size-k heap while streaming (above): memory is O(k) no matter how big the input is.

Practice before you move on

Solve the two practice questions for P1 and P2 in Coding Practice, under Python.
Change P1 to count events per device from events.jsonl.
Change P2 to return the two products with the most units sold from order_items.csv.

In Coding Practice

Solve this pattern on fresh data, under Python. Hidden tests grade it.