P11 Merge intervals · P12 Hash join

FreeLesson 63 of 78

P11Merge intervalsDEMEDIUM

Sounds like: "merge overlapping bookings", "find busy periods", "total time covered by sessions"

Worked question: Merge each room's bookings into continuous occupied periods, then solve the classic numeric version.

Approach: 1. sort by start 2. if the next starts before the last ends, extend 3. otherwise start a new interval

SOLUTIONPYTHON 3.12

from collections import defaultdict

bookings = [(10, "05-01", "05-04"), (10, "05-03", "05-06"),
            (10, "05-06", "05-08"), (20, "05-02", "05-05"),
            (20, "05-04", "05-07")]

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:     # overlaps last
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

rooms = defaultdict(list)
for room, s, e in bookings:
    rooms[room].append((s, e))
for room, spans in rooms.items():
    print(room, merge(spans))
print(merge([(1, 3), (2, 6), (8, 10), (15, 18)]))

Output

10 [['05-01', '05-08']]
20 [['05-02', '05-07']]
[[1, 6], [8, 10], [15, 18]]

P12Hash joinDEMEDIUM

Sounds like: "join these two files without pandas", "enrich orders with customer data"

Worked question: Join orders to customers in plain Python, count orphan orders, and list customers who never ordered.

Approach: 1. load the small side into a dict 2. stream the big side and look up each row 3. a set of keys gives the anti join

SOLUTIONPYTHON 3.12

import csv, json

customers = {c["customer_id"]: c                 # build side: small
             for c in json.load(open("customers.json"))}

joined, orphans = [], 0
for o in csv.DictReader(open("orders.csv")):   # probe: streamed
    c = customers.get(int(o["customer_id"]))
    if c is None:
        orphans += 1
        continue
    city = (c["address"] or {}).get("city") or "Unknown"
    joined.append((o["order_id"], c["name"], city, o["amount"]))

print(len(joined), "joined,", orphans, "orphans")
for row in joined[8:11]:
    print(row)
seen = {int(r["customer_id"])
        for r in csv.DictReader(open("orders.csv"))}
print("anti join:",
      [c["name"] for i, c in customers.items() if i not in seen])

Output

15 joined, 0 orphans
('109', 'Kabir', 'Delhi', '747.00')
('110', 'Sana', 'Unknown', '1998.00')
('111', 'Diya', 'Mumbai', '1999.00')
anti join: ['Zoya']

Practice before you move on

Solve the two practice questions for P11 and P12 in Coding Practice, under Python.
Change P12 into a left join that keeps orphan orders with the name None.

In Coding Practice

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