Foundations · pattern 10 of 10

Purpose-built data structure

Some tasks give you no list to work through. They name a few operations, such as add, remove and find, and call them many times. You build a small store from simple parts and keep a little extra, so that every operation is fast.

Watch it run in the app

When to use it

Use it when the task lists operations to support and wants each one fast, and no single ready-made structure answers all of them.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A school records which student has which locker. A "move" gives a student a free locker and frees the one that student had. A "where" asks for a student's locker, or -1 for none. A "who" asks which student has a locker, or "nobody". Return the answers, in order.

Input
ops = [["move", "Ana", 7], ["move", "Ben", 4], ["who", 7], ["move", "Ana", 2], ["who", 7], ["where", "Ana"], ["who", 2]]

Output
["Ana", "nobody", 2, "Ana"]

The method

Keep two maps: student to locker, and locker to student
A move first frees the locker the student had, if any
Then it writes the new pair into both maps
A question is one lookup in the map that has its key
Return the answers in the order they were asked

The run, one moment at a time

Step 1. Two empty maps, each a table that finds a value by its key. "lockers" answers the "where" questions. With it alone, each "who" question would be a search through every student, so "owners" is kept too.
```
op: empty
lockers: empty
owners: empty
answers: empty
```
Step 3. Ana has no locker yet, so nothing is freed. Write Ana to 7 in lockers and 7 to Ana in owners.
```
op: move Ana 7
lockers: Ana:7
owners: 7:Ana
answers: empty
```
Step 3. Ben has no locker yet, so nothing is freed. Write Ben to 4 in lockers and 4 to Ben in owners.
```
op: move Ben 4
lockers: Ana:7 Ben:4
owners: 7:Ana 4:Ben
answers: empty
```
Step 4. "who 7" is one lookup in owners, with no search through the students: Ana.
```
op: who 7
lockers: Ana:7 Ben:4
owners: 7:Ana 4:Ben
answers: Ana
```
Step 2. Ana already has locker 7. Take 7 out of owners first, or that map would still say Ana has it.
```
op: move Ana 2
lockers: Ana:7 Ben:4
owners: 7:Ana 4:Ben
answers: Ana
```
Step 3. Now write the new pair: Ana to 2 in lockers and 2 to Ana in owners. The two maps agree again.
```
op: move Ana 2
lockers: Ana:2 Ben:4
owners: 4:Ben 2:Ana
answers: Ana
```
Step 4. "who 7" finds no entry for 7 in owners, so the answer is "nobody". The move took that entry out.
```
op: who 7
lockers: Ana:2 Ben:4
owners: 4:Ben 2:Ana
answers: Ana nobody
```

Step 4. "where Ana" is one lookup in lockers: 2.

op: where Ana
lockers: Ana:2 Ben:4
owners: 4:Ben 2:Ana
answers: Ana nobody 2

Step 4. "who 2" is one lookup in owners, with no search through the students: Ana.

op: who 2
lockers: Ana:2 Ben:4
owners: 4:Ben 2:Ana
answers: Ana nobody 2 Ana

Step 5. 4 questions were asked and each took a single lookup. The answers are Ana, nobody, 2, Ana.
```
op: empty
lockers: Ana:2 Ben:4
owners: 4:Ben 2:Ana
answers: Ana nobody 2 Ana
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(ops) {
  // 1. Keep two maps: student to locker, and locker to student
  const lockers = new Map();
  const owners = new Map();
  const answers = [];
  for (const op of ops) {
    if (op[0] === "move") {
      const student = op[1];
      const locker = op[2];
      // 2. A move first frees the locker the student had, if any
      if (lockers.has(student)) {
        owners.delete(lockers.get(student));
      }
      // 3. Then it writes the new pair into both maps
      lockers.set(student, locker);
      owners.set(locker, student);
    } else if (op[0] === "where") {
      // 4. A question is one lookup in the map that has its key
      answers.push(lockers.has(op[1]) ? lockers.get(op[1]) : -1);
    } else {
      answers.push(owners.has(op[1]) ? owners.get(op[1]) : "nobody");
    }
  }
  // 5. Return the answers in the order they were asked
  return answers;
}

Python

def solve(ops):
    # 1. Keep two maps: student to locker, and locker to student
    lockers = {}
    owners = {}
    answers = []
    for op in ops:
        if op[0] == "move":
            student = op[1]
            locker = op[2]
            # 2. A move first frees the locker the student had, if any
            if student in lockers:
                del owners[lockers[student]]
            # 3. Then it writes the new pair into both maps
            lockers[student] = locker
            owners[locker] = student
        elif op[0] == "where":
            # 4. A question is one lookup in the map that has its key
            answers.append(lockers.get(op[1], -1))
        else:
            answers.append(owners.get(op[1], "nobody"))
    # 5. Return the answers in the order they were asked
    return answers

How to spot it

Given: A list of operations to carry out, each with its arguments: There is no single input to scan. You decide what to store so that each operation finds what it needs.
Asked: Design a structure that supports these operations: The work is choosing the parts. For each operation, ask which simple structure would answer it in one step.
Asked: The same data must be found in two different ways: One structure is fast for one way of asking. Keep a second one for the other way, and update both together.
Limits: Every operation must take constant time: Constant time means a few steps however much is stored. A search through everything is ruled out, so something extra must be kept ready.

Looks like it, but is not

You get one finished list and must find, for each item, its partner in the list. Use Hash map lookup. One map filled in a single pass is enough. Nothing changes afterwards, so there are no operations to design for.
The only operations are add a value and take out the smallest value. Use Heap as a priority queue. A heap alone does both in a few steps. A design of your own is needed only when no single structure is enough.
The only operations are put an item on top and take the top item off. Use Last-in, first-out stack. A plain stack already does both in one step. It becomes a design task when another question is added.

Cost and mistakes

Each operation is a fixed number of map steps, written O(1), however many students there are. Extra space is two map entries for each student who has a locker, written O(n).

Watch out

Every operation that changes one part must change the others in the same call. If a move wrote to one map only, the two maps would give different answers from then on.
Do not choose the storage first and then search it for every question. List the operations, ask what would make each one a single step, and store that.

In the 150

4 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 4

Min StackMedium · Stack
LRU CacheMedium · Linked List
Design TwitterMedium · Heap / Priority Queue
Detect SquaresMedium · Math & Geometry