Dictionary Key Intersection

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Meta

Problem

A setting survives the reconciliation only if it appears in both config snapshots d1 and d2, and it keeps the value d1 gives it. Return the surviving settings as name/value pairs, alphabetical by setting name.

Two dictionaries. What do they share?

Example 1

Input:

d1 = {"a":1,"b":2,"c":3}, d2 = {"b":20,"c":30,"d":40}

Output:

[["b",2],["c",3]]

Example 2

Input:

d1 = {"x":10}, d2 = {"y":20}

Output:

[]

Worked solution and explanation

What this really is

Strip off the config-reconciliation costume and this is a filtered projection emitted in a controlled order: keep only the keys that live in BOTH snapshots, take each value from d1, and hand the pairs back sorted by name. Two things bite people. First, on a shared key the two snapshots almost always disagree, so reading from the wrong side reports the wrong value for every survivor. Second, dicts remember insertion order, not sort order, so walking d1 as-is returns the pairs in whatever order the snapshot was built. Neither mistake throws an error, which is exactly why they slip through.

The moves

Step 1: Order the names first

Walk d1's keys through sorted(d1). The visible examples happen to arrive already alphabetical, so they prove nothing about order; a snapshot built 'timeout', 'retries', 'batch_size' must still come back 'retries' then 'timeout', and only an explicit sort guarantees that.

Step 2: Filter to the shared names

Keep a key only when key in d2. That membership test is the whole intersection, and against a dict it costs O(1) per key.

Step 3: Take the value from d1

Emit d1[key] for each survivor. d2 only decides which names survive, never what they map to: in the third example d2 says 99 for both, and the answer still carries 1 and 2.

The solution

Sort, filter, then hand back the pairs
def dictionary_key_intersection(d1, d2):
    shared = {key: d1[key] for key in sorted(d1) if key in d2}
    return list(shared.items())

Build the ordered survivors once, then return them as name/value pairs.

Copy then hope
[(k, d1[k]) for k in d1 if k in d2] returns the right pairs in d1's build order, so a snapshot built 'c', 'a', 'b' comes back unsorted.
Sort then filter
sorted(d1) fixes the order up front, so the pairs are alphabetical no matter how d1 was assembled.

Common follow-up questions