Arrays and Hashing
9 / 170Arrays and HashingLesson 4 of 10About 52 min
Design a key so that everything which belongs together produces the same key, and nothing else does.
The grouping loop itself is three lines and is always the same. Choosing the key is the entire problem.
from collections import defaultdict def group_by_digits(numbers): groups = defaultdict(list) for number in numbers: key = "".join(sorted(str(number))) # canonical form groups[key].append(number) return list(groups.values()) print(group_by_digits([123, 231, 45, 312, 54, 9]))Any hashable value works, and a tuple is the usual choice when the signature is naturally several numbers. Here the canonical form of a word is its shape: which positions repeat, ignoring the actual letters. "noon" and "baab" have the same shape.
def shape_of(word): first_seen = {} shape = [] for ch in word: if ch not in first_seen: first_seen[ch] = len(first_seen) shape.append(first_seen[ch]) return tuple(shape) # tuple, because lists are not hashable print(shape_of("noon"), shape_of("baab"), shape_of("abcd"))Three ways to append into a bucket that might not exist yet. They behave identically here, and the first is the one to write.
groups = defaultdict(list)groups[key].append(word) # the missing key becomes [] automatically groups = {}groups.setdefault(key, []).append(word) # works on a plain dict groups = {}if key not in groups: # explicit, and noisier groups[key] = []groups[key].append(word)You want to group points with positive coordinates that lie on the same line through the origin. Which key is a correct canonical form?
Two grouping problems where the only real work is picking the key. group_by_length buckets words by their length. group_shifted is harder: group strings that are the same sequence of gaps between consecutive letters, so "abc" and "xyz" belong together, and so do "az" and "ba" because the gap wraps around 26.
Tests
print(group_by_length(["a", "bb", "cc", "ddd"]))print(group_shifted(["abc", "bcd", "xyz", "az", "ba", "a", "z"]))Output
Run tests to see output.
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.