Lists, maps and sets: pick by the question you ask

Almost every coding problem keeps a collection of things: books, orders, students, seats. The first choice you make is how to hold them. That choice decides how fast each question is answered. The hidden tests can send thousands of items, and the test runner stops a program that runs too long. An interviewer also reads your code for a loop that searches a list.

A weak answer puts everything in a list, because a list is the first tool most people think of. It works for 5 items and is much too slow for 100,000. A strong answer asks what the code must find out, and picks the structure that answers it in one step. It can also say the cost in numbers.

At SDE-1 level you should pick between a list and a dictionary for the simple cases. At SDE-2 level you should also count the steps, choose safe keys, and avoid the traps of sorting and copying. Interviewers often ask: "How fast is this search, and what if there are a million items?"

Think of a school office. There is a register where each student is written in the order they joined. That is a list: it keeps order, and finding one student means reading line after line. There is a wall of small boxes, one for each roll number. That is a dictionary: you say the roll number and go straight to the right box. There is also a tray of cards for "students who passed", with one card for each student. That is a set: it holds each thing once, and "is Asha in the tray?" is quick to answer.

So the choice depends on the question you ask, not on what the data is.

A dictionary keeps pairs of a key and a value, and you ask by key. A set keeps keys only, with no repeats. A list keeps items in a row, and you ask by position.

How fast: steps, and the letter n

To compare structures we count steps. Let n be the number of items. We ask how the steps grow when n grows. This is called big-O, and here we say it in words.

• 1 step. The work does not grow with n. A dictionary lookup takes about 1 step for 10 items and for 10 million items.
• n steps. The work grows in line with n. Looking for a value in a list means checking items one by one, so up to n steps.
• log n steps. The work grows very slowly. Think of a guessing game: I think of a number from 1 to 100,000. You ask "is it above 50,000?" and each answer halves the choices. After 17 questions you know it, because 2 to the power of 17 is 131,072, which is more than 100,000. So 17 steps for 100,000 items is log n.

Sorting takes about n x log n steps. These costs, from the Python documentation, are averages:

A dictionary and a set find the right place from the key itself, so the number of items does not matter. (If many keys land in the same place, the cost grows. This is rare with normal keys.)

A loop of lookups turns n into n x n

Suppose you have n students and, for each of n requests, you check if roll in students on a list. Each check is up to n steps. In the worst case, together that is n x n steps. With a dictionary, each check is 1 step, so the loop is n steps. Code that does this passes 5 items and fails the hidden tests.

Hashing and equality: which keys are safe

How does a dictionary find a place from a key? It computes a hash from the key: a number that works like a box number. The same key always gives the same hash. Two rules follow:

1. Two keys that are equal must have the same hash. Otherwise the dictionary would look in the wrong box.
2. A key must not change while it is in the dictionary. If it changed, its box number would change, and the dictionary could not find it.

So Python accepts only keys that have a hash. Numbers, text, tuples of such values and frozen dataclasses have one, and a value of that kind cannot change. A list and a dataclass that is not frozen have none. Python refuses them with a TypeError. A plain object is accepted, but it is hashed by identity. So two plain objects with the same data are two different keys, as the lesson on classes showed. A frozen dataclass gives you equality by content: two objects with the same fields are equal and have the same hash.

Order

A dictionary keeps the order in which keys were added. The Python documentation promises this from version 3.7. Changing the value of a key does not move it. Deleting a key and adding it again puts it at the end. A set promises no order. If you need the elements in order, write sorted(the_set), which gives a list.

Sorting: keys, tie-breaks and stable order

sorted(items, key=f) returns a new list in the order of f(item). The function f gives the value to sort by. If f returns a tuple (a fixed row of values), Python compares the first items. It uses the second items only when the first items are equal. So a tuple key is a tie-break. For "highest marks first, and if marks are equal, the smaller roll number first", the key is (-marks, roll). The minus sign turns "highest first" into "smallest first".

Python's sort is stable: items with equal keys stay in the order they had before. Do not depend on this when the problem gives a rule. Write the tie-break into the key.

Text order against number order

Text is sorted letter by letter. The text "O10" comes before "O2", because 1 comes before 2. So sorted(["O10", "O2", "O1"]) gives O1, O10, O2. If the ids carry a number, sort by the number. Use a key function that cuts the number out and turns it into an int.

Counting, grouping and keeping two dictionaries in step

Counter counts how many times each value appears. A defaultdict(list) is a dictionary that makes an empty list the first time you use a new key. So you can write groups[key].append(x) with no check.

Sometimes you keep the same facts in two dictionaries, for example students by roll number and roll numbers by branch. Then every change must update both, in one method. If two methods each update one dictionary, they drift apart.

Deleting and copying

If you remove items from a list while a for loop reads it, the loop skips items. Build a new list of the items you keep. A copy such as list(a) or a[:] makes a new list, but it is shallow: the items inside are shared. For nested data, copy each inner list, or use copy.deepcopy(a). The line b = a is not a copy. It gives the same list a second name.

Run with Python 3.11. Assumption: a few results from an exam, and the pass mark is 40. A Result is a frozen dataclass, so it can be a set member and a key.

from dataclasses import dataclass
from collections import defaultdict, Counter

@dataclass(frozen=True)
class Result:
    roll: int
    name: str
    branch: str
    marks: int

results = [
    Result(2, "Asha", "CS", 88), Result(10, "Ravi", "EC", 72),
    Result(7, "Meera", "CS", 35), Result(4, "Kiran", "ME", 72),
    Result(1, "Divya", "EC", 91), Result(9, "Farhan", "CS", 88),
]

Some code features that we use below:

• x for x in items builds a collection from a loop. This is a comprehension. {r.roll: r for r in results} builds a dictionary, {r.roll for ...} builds a set, and [... for ...] builds a list. Counter(r.branch for r in results) counts the values that the loop gives.
• d.get(k) gives the value of k, or None if k is missing.
• for a, b in pairs takes each pair and names its two parts.
• text[1:] is the text from position 1 to the end. a[:] is all of a, which is a copy.
• counts.most_common(1) gives the most frequent value and its count, as a list of one pair.
• list.remove(x) takes out the first x. d.pop(k) removes k and gives its value. s.discard(x) removes x, and does not fail if it is missing.

Find by roll number, and the set who passed.

by_roll = {r.roll: r for r in results}
print(by_roll[10].name, by_roll.get(99))
passed = {r.roll for r in results if r.marks >= 40}
print(sorted(passed), 7 in passed)

It prints Ravi None, then [1, 2, 4, 9, 10] False. Roll 99 does not exist, so get gives None. Roll 7 got 35 marks, below 40, so it is not in the set.

Group by branch, and count.

by_branch = defaultdict(list)
for r in results:
    by_branch[r.branch].append(r.name)
counts = Counter(r.branch for r in results)
print(dict(by_branch))
print(counts.most_common(1), counts["ME"], counts["XX"])

The call dict(by_branch) turns the defaultdict into a normal dictionary for printing. It prints {'CS': ['Asha', 'Meera', 'Farhan'], 'EC': ['Ravi', 'Divya'], 'ME': ['Kiran']}. The next line prints [('CS', 3)] 1 0. Three students are in CS. A branch that never appears has the count 0.

Top marks, ties broken by roll number.

def rank_key(result):
    return (-result.marks, result.roll)

top = sorted(results, key=rank_key)
print([(r.roll, r.marks) for r in top])

It prints [(1, 91), (2, 88), (9, 88), (4, 72), (10, 72), (7, 35)]. Asha (roll 2) and Farhan (roll 9) both have 88, and the smaller roll comes first. Kiran (roll 4) and Ravi (roll 10) both have 72, and roll 4 comes first. With a key of only -result.marks, the stable sort would keep the input order, and Ravi would come before Kiran. That depends on how the list was built, so put the tie-break in the key.

The order trap, the copy trap and the delete trap.

def order_number(text):
    return int(text[1:])

print(sorted(["O10", "O2", "O1"]))
print(sorted(["O10", "O2", "O1"], key=order_number))
rows = [[1], [2]]
shallow = list(rows)
shallow[0].append(9)
print(rows)

The first line prints ['O1', 'O10', 'O2']. The second prints ['O1', 'O2', 'O10'], because the key cuts off the letter and makes a number. The copy shares the inner lists, so the last line prints [[1, 9], [2]]: the original changed. Copy each inner list with [row[:] for row in rows], and the original stays [[1], [2]].

Two outer lists, rows and shallow, each with two items. The first item of both lists points to the same inner list, which holds 1 and 9 after the append. The second item of both lists points to the same inner list, which holds 2. Copying the outer list does not copy the inner lists.

marks = [30, 35, 40, 28, 90]
for m in marks:
    if m < 40:
        marks.remove(m)
print(marks)

We wanted only the marks of 40 or more, so the answer should be [40, 90]. It prints [35, 40, 90]. After the loop removes 30, every item moves one place to the left, and the loop skips 35. Build a new list instead: marks = [m for m in marks if m >= 40] gives [40, 90].

One source of truth. The first half of a class that keeps two dictionaries in step:

class ResultBook:
    def __init__(self):
        self._by_roll = {}
        self._rolls_by_branch = defaultdict(set)

    def add(self, result):
        if result.roll in self._by_roll:
            raise ValueError(f"roll {result.roll} already exists")
        self._by_roll[result.roll] = result
        self._rolls_by_branch[result.branch].add(result.roll)

    def remove(self, roll):
        if roll not in self._by_roll:
            raise ValueError(f"unknown roll: {roll}")
        result = self._by_roll.pop(roll)
        self._rolls_by_branch[result.branch].discard(roll)

    def rolls_in(self, branch):
        return sorted(self._rolls_by_branch.get(branch, ()))

Both methods check first and change last, as in the lesson on bad input and errors. Each one updates both dictionaries, so they cannot drift apart. Now use it:

book = ResultBook()
for roll, name in [(2, "Asha"), (7, "Meera"), (9, "Farhan")]:
    book.add(Result(roll, name, "CS", 60))
book.remove(2)
print(book.rolls_in("CS"))
try:
    book.remove(2)
except ValueError as error:
    print(error)

It prints [7, 9], then unknown roll: 2. The second remove(2) is refused, and nothing changes.

The cost at scale (the predict box). With a list, one check is up to 100,000 steps in the worst case. A loop of 100,000 checks is:

100,000 x 100,000 = 10,000,000,000 steps.

At 10 million steps a second, that is 10,000,000,000 / 10,000,000 = 1,000 seconds, about 17 minutes. With a dictionary, one check is about 1 step, so the loop is 100,000 steps. That is 100,000 / 10,000,000 = 0.01 seconds. A real computer differs from our assumed 10 million, but the gap stays huge.

A dictionary or a set solves the slow lookup: about 1 step for any size, so a loop of lookups stays fast. It costs extra memory, a key that cannot change, and care when you keep two dictionaries in step. A list solves order and the simple case, and costs n steps for a search. I would change from a list to a dictionary or a set when the code looks things up inside a loop. I would also change when the input can be large.

"The in check is fast on a list too." It is not. On a list it goes through items one by one, up to n steps. On a set or a dictionary it is about 1 step. In a loop of 100,000 checks the difference is 1,000 seconds against 0.01 seconds.

"A set keeps the order in which I add things." A set promises no order. A dictionary does keep insertion order. If you need a sorted view of a set, call sorted.

"Sorting the ids as text gives the right order." Text order puts O10 before O2. Sort by a number, with a key function, when ids carry a number.

1. Name the structure you would use for each question. (a) "Is roll 5 already registered?" (b) "List the names in each branch." (c) "In what order did the requests arrive?"
2. A college has 50,000 students. A loop makes 50,000 checks with roll in students_list, in the worst case. How many steps is that? At 10 million steps a second, how many seconds? How many seconds if the students are in a set?
3. A teammate sorts order ids ["O1", "O2", "O10", "O11", "O12"] with sorted(ids) and shows them to the user. What list does the user see, and how do you fix it?