# Birds of a Feather > Every record finds its kin; keep them in the order they arrived. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L4 ## Problem An ingestion step hands you a list of record dicts in `records` and the name of a field in `key`. Return a dict mapping each value found under that field to the list of records carrying it, with each bucket keeping its records in the order they arrived. ## Worked solution and explanation ### What this really is Strip the costume and this is GROUP BY, run in Python instead of SQL. The whole problem is 'append each record to the bucket named by its key value, making the bucket the first time you see that value.' Everyone gets the loop. What separates candidates is the two quiet decisions around it: which container avoids the if-key-not-in-dict dance, and whether the per-bucket order survives. Reach for itertools.groupby out of muscle memory and you walk straight into the trap, because groupby only groups CONSECUTIVE equal keys, so on unsorted input you get one group per run, not per value, and your buckets come out fragmented. --- ### The build #### Step 1: Pick the container that creates buckets for you defaultdict(list) hands you an empty list the first time you touch a key, so you can append without ever checking whether the bucket exists. That is exactly the 'create bucket on first sight, extend it after' shape this needs. A plain dict with setdefault(value, []).append(record) is identical in cost and just reads noisier. #### Step 2: One in-order pass Walk records once, in order. Pull record[key], append the record to its bucket. Order is preserved for free: list.append goes to the end, and dicts keep insertion order since 3.7, so both the keys and the lists reflect the order things arrived. No sort, no second pass. #### Step 3: Hand back a plain dict Convert to dict(buckets) on the way out. A defaultdict that escapes the function is a footgun: a caller that does partitions[some_value] to check membership silently materializes an empty list and mutates your result. Returning a plain dict makes the absent key raise, which is what a caller expects. --- ### The solution **defaultdict(list), one pass, return dict** ```python from collections import defaultdict def partition_by(records, key): buckets = defaultdict(list) for record in records: buckets[record[key]].append(record) return dict(buckets) ``` > **Cost analysis** > > One pass over n records, O(1) average per dict lookup and list append, so O(n) time and O(n) space for the output (every record ends up in exactly one bucket). defaultdict resolves the missing-key case in C, shaving the Python-level branch that setdefault costs, though in practice the two are a wash. > **Interviewers watch for** > > Whether you reach for the append idiom instead of sort-then-groupby, whether you notice that per-bucket order is a requirement and not an accident, and whether you say out loud what record[key] does when the field is absent. A strong candidate pauses on the missing-key case and asks whether to skip, default, or let it raise rather than assuming. **groupby (wrong here)** itertools.groupby only merges adjacent equal keys, so you must sorted(records, key=lambda r: r[key]) first. That is O(n log n) AND it destroys the original within-bucket order the spec demands. **defaultdict (correct)** A single O(n) pass appends in arrival order. Buckets are correct on unsorted input and each list stays in the order records came in. --- ## Common follow-up questions - What changes if some records are missing the field entirely? _(record.get(key, DEFAULT) to bucket missing-key records together, or try/except KeyError to skip them. Talk through the product decision.)_ - How would you return just the count per bucket instead of the records? _(Counter(r[key] for r in records); one line, still O(n). Compare to the defaultdict(int) idiom.)_ - How would you scale this to a billion records? _(Hash-partition by r[key] across workers, each builds a local map, then merge. Mention Spark/Beam groupByKey as the production version.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/birds_of_a_feather) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.