Checkpoint: Data Structures
Published by Brayan K
A checkpoint is a consolidation lesson that ties an entire unit together, and this one combines everything from the data-structures stretch — dict methods, Counter, defaultdict, deque, heapq, bisect, numbers, strings, bytes, and iterators — into one build challenge and a quiz.
Part of the free Python course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.
Plan a report around the questions it must answer
You are building a small request desk. Each request has an ID, a topic, a numeric priority and a decimal charge. The desk needs arrival-order processing, counts by topic, names grouped by topic, a priority schedule, a short completion history and a charge-range report. Each view answers a different question; choosing one collection for every view makes some of those questions harder.
Keep a parsed record as the authoritative data. Derive the counts and ordered views from the same accepted records. This avoids a subtle reporting bug: accepting a record into one view but rejecting it from another. It also gives you a clear boundary between input validation and reporting.
The worked program uses a deliberately small, fixed input format with four fields separated by a vertical bar. It is a practice format, not a replacement for a general CSV parser. Names and topics in this task cannot contain that separator.
Trace one accepted set through several views
from collections import Counter, defaultdict, deque
from decimal import Decimal
from bisect import bisect_left, bisect_right
import heapq
payloads = [b"A|repair|2|1.20", b"B|setup|1|0.80", b"C|repair|1|1.20"]
records = []
for payload in payloads:
request_id, topic, priority, charge = payload.decode("utf-8").split("|")
records.append({"id": request_id, "topic": topic,
"priority": int(priority), "charge": Decimal(charge)})
counts = Counter(record["topic"] for record in records)
groups = defaultdict(list)
priority_queue = []
for sequence, record in enumerate(records):
groups[record["topic"]].append(record["id"])
heapq.heappush(priority_queue, (record["priority"], sequence, record["id"]))
arrival_queue = deque(records)
recent = deque(maxlen=2)
while arrival_queue:
recent.append(arrival_queue.popleft()["id"])
charges = sorted(record["charge"] for record in records)
start = bisect_left(charges, Decimal("0.80"))
stop = bisect_right(charges, Decimal("1.20"))
print("Counts:", sorted(counts.items()))
print("Repair IDs:", groups["repair"])
print("Priority order:", [heapq.heappop(priority_queue)[2] for _ in range(len(priority_queue))])
print("Recent arrivals processed:", list(recent))
print("Charges in range:", [str(charge) for charge in charges[start:stop]])
print("Total:", sum(charges, Decimal(0)))
# ✅ Expected output:
# Counts: [('repair', 2), ('setup', 1)]
# Repair IDs: ['A', 'C']
# Priority order: ['B', 'C', 'A']
# Recent arrivals processed: ['B', 'C']
# Charges in range: ['0.80', '1.20', '1.20']
# Total: 3.20Read the printed views separately. Arrival processing and priority scheduling are alternative orders over the same records; this demonstration does not claim both are the actual service order. The completion-history label makes its chosen order explicit. If your application serves by priority, record completion from that priority loop instead.
The heap contains a unique sequence number before the ID, so equal-priority requests retain arrival order. The range report uses the right boundary for its inclusive upper limit. No clock or external input is involved, allowing you to trace every result by hand and then compare it with the checked output.
Reject malformed records before updating any view
payload = b"A|repair|2"
fields = payload.decode("utf-8").split("|")
if len(fields) != 4:
raise ValueError("expected four fields")
# ✅ Expected error:
# ValueError: expected four fieldsThis error belongs at the parsing boundary, before a Counter or queue is changed. Otherwise a rejected request could still increase a count or occupy a place in a schedule. Decoding errors, invalid integers and invalid decimal strings also need an explicit policy in a real importer; this checkpoint’s accepted inputs are stated in the brief.
Strict decoding and the difference between text and byte positions are in Strings, Bytes & Unicode Encodings. Decimal construction and rounding decisions are in Numbers: int, float, Decimal & Fraction.
Explain the failure before changing the collection
from collections import Counter
topics = iter(["repair", "setup", "repair"])
print(Counter(topics).most_common())
print(list(topics))
# ✅ Expected output:
# [('repair', 2), ('setup', 1)]
# []The empty second report is caused by shared cursor state, not by Counter deleting a list. Save reusable records when several reports need separate passes, or compute the reports during one deliberate pass. Iterators: __iter__ & __next__ owns that cursor contract.
A bounded deque may discard old entries, so use it for retained history rather than unscheduled requests. deque & Queues covers that retention rule. For the schedule’s comparison key and tie handling, revisit Heaps with heapq (Priority Queues).
Count keys and group keys are another distinction: Counter counts occurrences, while defaultdict(list) stores the actual records for each group. Counter & defaultdict explains those behaviors; Dictionary Methods Deep Dive handles missing-key lookups and updates.
Repair the report without changing its meaning
Fill the grouping factory, FIFO removal method and upper range boundary. Both values equal to 20 must remain in the inclusive range. Completed history retains only two IDs, but pending requests must all be processed.
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
groups = defaultdict(___)
pending = deque([("A", "repair"), ("B", "setup"), ("C", "repair")])
completed = deque(maxlen=2)
while pending:
request_id, topic = pending.___()
groups[topic].append(request_id)
completed.append(request_id)
values = [10, 20, 20, 30]
start = bisect_left(values, 10)
stop = ___(values, 20)
print(dict(groups))
print(list(completed))
print(values[start:stop])
# 👉 replace ___ with list
# 👉 replace ___ with popleft
# 👉 replace ___ with bisect_right
# ✅ Expected output:
# {'repair': ['A', 'C'], 'setup': ['B']}
# ['B', 'C']
# [10, 20, 20]Build a priority desk and reconcile its reports
Use these records in arrival order: A/repair/2/1.20, B/setup/1/0.80, C/repair/1/1.20 and D/setup/3/2.00. Parse each slash-separated string into an ID, topic, integer priority and Decimal charge. Serve smaller priorities first, preserving arrival order for ties. Print each served ID, counts by topic in alphabetical order, the final two completed IDs, and all charges from 1.20 through 2.00 inclusive. Print the exact total of all charges. Unlike the worked example, completion history must now follow actual priority service.
from collections import Counter, deque
from decimal import Decimal
from bisect import bisect_left, bisect_right
import heapq
rows = ["A/repair/2/1.20", "B/setup/1/0.80", "C/repair/1/1.20", "D/setup/3/2.00"]
records = []
for row in rows:
request_id, topic, priority, charge = row.split("/")
records.append((request_id, topic, int(priority), Decimal(charge)))
pending = []
for sequence, record in enumerate(records):
heapq.heappush(pending, (record[2], sequence, record))
completed = deque(maxlen=2)
while pending:
priority, sequence, record = heapq.heappop(pending)
print("Served:", record[0])
completed.append(record[0])
counts = Counter(record[1] for record in records)
charges = sorted(record[3] for record in records)
start = bisect_left(charges, Decimal("1.20"))
stop = bisect_right(charges, Decimal("2.00"))
print("Counts:", sorted(counts.items()))
print("Last completed:", list(completed))
print("Range:", [str(charge) for charge in charges[start:stop]])
print("Total:", sum(charges, Decimal(0)))
# ✅ Expected output:
# Served: B
# Served: C
# Served: A
# Served: D
# Counts: [('repair', 2), ('setup', 2)]
# Last completed: ['A', 'D']
# Range: ['1.20', '1.20', '2.00']
# Total: 5.20If your range omits 2.00, check which side of that value your upper boundary selects. If history ends in arrival order instead of service order, inspect the loop where it is updated. If tied priorities swap, inspect the sequence field rather than sorting the finished history afterward. These are different causes and need different repairs.
For range boundaries and their costs, return to Binary Search with bisect. The checkpoint succeeds when you can explain why each view uses its particular collection and trace the same accepted requests through all of them; a correct final number alone can conceal an ordering bug.
Practice quiz
What does this program print? from collections import deque q = deque(["A", "B"], maxlen=2) q.append("C") print(list(q))
- ['A', 'B', 'C']
- ['B', 'C']
- ['A', 'B']
- ['A', 'C']
Answer: ['B', 'C']. A bounded pending queue would have discarded A before service.
What does this program print? import heapq h = [(2, 0, "A"), (1, 1, "B"), (1, 2, "C")] heapq.heapify(h) print([heapq.heappop(h)[2] for _ in range(len(h))])
- ['A', 'B', 'C']
- ['C', 'B', 'A']
- ['B', 'A', 'C']
- ['B', 'C', 'A']
Answer: ['B', 'C', 'A']. Priority chooses B and C first; arrival sequence orders their tie.
What does this program print? from bisect import bisect_left, bisect_right a = [10, 20, 20, 30] print(a[bisect_left(a, 20):bisect_right(a, 20)])
- [20, 20]
- [20]
- []
- [20, 20, 30]
Answer: [20, 20]. The left-to-right equal interval retains both duplicates.
What does this program print? from decimal import Decimal print(sum([Decimal("1.20"), Decimal("0.80")], Decimal(0)))
- 2
- 2.0000000000000004
- 2.00
- 1.200.80
Answer: 2.00. String construction keeps these decimal amounts exact.
What does this program print? from collections import Counter values = iter(["a", "b", "a"]) print(Counter(values)["a"]) print(list(values))
- 2 ["a", "b", "a"]
- 2 []
- 1 []
- 0 []
Answer: 2 []. Counter consumes the iterator, so a second pass has no values.
What does this program print? from collections import defaultdict groups = defaultdict(list) groups["repair"].append("A") print(groups.get("setup")) print("setup" in groups)
- [] True
- [] False
- None True
- None False
Answer: None False. get does not invoke the missing-key factory or insert the key.
Where should a malformed input record be rejected?
- Before it updates any derived count or queue
- After the total is printed
- Only when the queue becomes full
- After adding its topic count
Answer: Before it updates any derived count or queue. Validate the record before allowing reports to disagree about whether it exists.
The desk serves by priority. Which operation should update completed history?
- Parsing a new arrival
- Sorting the charge report
- Removing and serving the next priority entry
- Reading the topic count
Answer: Removing and serving the next priority entry. Completion order follows actual service, which may differ from arrival order.
Continue this course
- Previous: Iterators: __iter__ & __next__
- Next: Abstract Base Classes (abc) — Define and enforce interfaces with abc.ABC and @abstractmethod
- Quick reference: Python cheat sheet