Choose Data Structures

Introduction

This is lesson 2 of chapter 9 (domain interview). In lesson 1 you learned a method and the language of complexity. Most interview problems, and most real interface bugs, are solved by picking the right data structure: the shape in which data is stored so that the operations you need are cheap. In the official ninth course, data structures are one of the four topics (source: https://www.coursera.org/learn/coding-interview-preparation (opens in a new tab)). The material here is original and uses front-end scenarios from the Harbor Workshops project.

Learning objectives

By the end of this lesson you can:

1. Describe arrays, objects, Map, and Set and the cost of their common operations.
2. Choose between an array, an object, a Map, and a Set for a given need.
3. Implement and use stacks and queues with arrays and explain their order rules.
4. Explain a linked list and when it differs from an array.
5. Describe trees (including the DOM tree) and traverse them depth-first and breadth-first.
6. Explain hash-based lookup and why it is fast on average.
7. Use the frequency-counter, two-pointer, and normalization patterns.
8. Normalize nested data into lookup tables, as you do in React state.

1. Arrays

An array stores items in order at numeric indexes.

Use arrays when order matters and you mostly iterate or access by position: a list of sessions in display order, steps in a wizard.

const sessions = [
  { id: 's1', title: 'Pottery', seats: 4 },
  { id: 's2', title: 'Woodwork', seats: 0 },
  { id: 's3', title: 'Weaving', seats: 7 },
];

const open = sessions.filter((s) => s.seats > 0);
const titles = open.map((s) => s.title);   // ['Pottery', 'Weaving']

Pitfall: finding an item by id with sessions.find(...) inside another loop makes the algorithm quadratic. That is the signal to build a lookup table (section 4).

2. Objects, Map, and Set

Objects as dictionaries

A plain object maps string (or symbol) keys to values. Lookup by key is O(1) on average.

const byId = { s1: { title: 'Pottery' }, s2: { title: 'Woodwork' } };
byId['s1'].title;   // 'Pottery'

Limits: keys are converted to strings, the object inherits keys such as toString from its prototype (so byId['constructor'] is not undefined), and size must be counted manually with Object.keys(byId).length.

Map

A Map stores key/value pairs where keys can be any value, keeps insertion order, and has a size property.

const seatsLeft = new Map();
seatsLeft.set('s1', 4);
seatsLeft.set('s2', 0);
seatsLeft.get('s1');        // 4
seatsLeft.has('s9');        // false
seatsLeft.size;             // 2

get, set, has, and delete are O(1) on average. Prefer Map when keys are not known in advance, are not strings, or are added and removed often, and when user-controlled keys could collide with prototype names.

Set

A Set stores unique values and tests membership in O(1) on average.

const selected = new Set(['s1']);
selected.add('s3');
selected.add('s1');       // no effect, already present
selected.has('s3');       // true
[...selected];            // ['s1', 's3']

Use a Set for "have I seen this?", deduplication, and selected-item tracking.

Choosing

Important React note: React state should be treated as immutable. Mutating a Set with add and calling setState with the same instance will not re-render. Create a new one: setSelected(new Set(selected).add(id)).

3. Hashing in one paragraph

Objects, Map, and Set rely on hashing: a function converts the key into a number that indicates where to look, so the engine goes almost straight to the entry instead of scanning. Two keys can land on the same slot (a collision), which the engine resolves internally. That is why lookup is O(1) on average but could degrade in a pathological case. Interview answers should say "average O(1)".

4. The frequency counter and the lookup table

Frequency counter

Count occurrences with a Map, then answer questions from the counts.

function mostBooked(bookings) {
  const counts = new Map();
  for (const { workshopId } of bookings) {
    counts.set(workshopId, (counts.get(workshopId) ?? 0) + 1);
  }
  let bestId = null;
  let bestCount = 0;
  for (const [id, count] of counts) {
    if (count > bestCount) {
      bestId = id;
      bestCount = count;
    }
  }
  return bestId;
}

Time O(n + k) where k is the number of distinct ids (at most n), so O(n). Space O(k).

The lookup table (index by id)

Problem: join each booking with its workshop. The slow way calls workshops.find for each booking: O(b × w). The fast way builds a table once.

function attachWorkshops(bookings, workshops) {
  const byId = new Map(workshops.map((w) => [w.id, w]));      // O(w)
  return bookings.map((b) => ({ ...b, workshop: byId.get(b.workshopId) })); // O(b)
}

Total O(b + w). This pattern, "index once, look up many times", is among the most valuable in interviews and in front-end code.

5. Stacks and queues

A stack is last in, first out (LIFO). A queue is first in, first out (FIFO).

// Stack: use push and pop
const history = [];
history.push('/home');
history.push('/workshops');
history.pop();            // '/workshops' - like the browser Back stack

// Queue: use push and shift (shift is O(n) on a big array)
const jobs = [];
jobs.push('email-1');
jobs.push('email-2');
jobs.shift();             // 'email-1'

Stacks appear in undo features, the call stack, and checking balanced brackets. Queues appear in task scheduling, breadth-first search, and message processing. For a very large queue, shift costs O(n) per call, so a real implementation keeps a head index or uses a linked structure; in an interview, mention the cost and say you would use a head pointer if performance mattered.

Worked example: balanced brackets

Problem. Given a string made of (, ), [, ], {, }, return true when every opener is closed by the right closer in the right order. Example: "{[()]}" is balanced, "([)]" is not.

Reasoning. The most recent unclosed opener must be closed first. "Most recent first" is a stack.

1. For each character: if it is an opener, push it.
2. If it is a closer, the stack must be non-empty and its top must be the matching opener; pop it. Otherwise return false.
3. At the end the stack must be empty (no unclosed openers).

function isBalanced(text) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of text) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Trace "([)]": push (, push [; see ), pop gives [, which is not (, so return false. Trace "((": both pushed, stack not empty at the end, so false. Complexity: O(n) time, O(n) space for the stack.

Why other approaches are weaker. Counting each bracket type separately accepts "([)]" because the counts match even though the order is wrong. A stack is the structure whose rule (last in, first out) matches the nesting rule of the problem.

6. Linked lists

A linked list stores items in nodes; each node holds a value and a reference to the next node.

const list = {
  value: 'Pottery',
  next: { value: 'Woodwork', next: { value: 'Weaving', next: null } },
};

In JavaScript you rarely need a linked list, because arrays are very fast in practice, but interviews ask about them to see whether you can handle references.

function reverseList(head) {
  let previous = null;
  let current = head;
  while (current) {
    const next = current.next;   // remember the rest
    current.next = previous;     // flip the link
    previous = current;
    current = next;
  }
  return previous;
}

O(n) time and O(1) space. The classic bug is losing the rest of the list by overwriting current.next before saving it.

7. Trees and the DOM

A tree is a hierarchy of nodes with one root, where each node has zero or more children. The DOM is a tree; so is a React component tree, a folder structure, and a nested comment thread.

const menu = {
  label: 'Root',
  children: [
    { label: 'Workshops', children: [{ label: 'Pottery', children: [] }] },
    { label: 'About', children: [] },
  ],
};

Depth-first traversal (DFS)

Visit a node, then fully explore each child before the next. A recursive version is short:

function labels(node, out = []) {
  out.push(node.label);
  for (const child of node.children) labels(child, out);
  return out;
}
// ['Root', 'Workshops', 'Pottery', 'About']

Breadth-first traversal (BFS)

Visit level by level using a queue.

function levels(root) {
  const result = [];
  let queue = [root];
  while (queue.length > 0) {
    result.push(queue.map((n) => n.label));
    queue = queue.flatMap((n) => n.children);
  }
  return result;
}
// [['Root'], ['Workshops', 'About'], ['Pottery']]

Both are O(n) in the number of nodes. DFS uses stack (recursion) space proportional to the tree height; BFS uses space proportional to the widest level.

Front-end application: finding the nearest ancestor

function closestWithClass(el, className) {
  let node = el;
  while (node) {
    if (node.classList?.contains(className)) return node;
    node = node.parentElement;
  }
  return null;
}

This is what element.closest('.card') does natively; knowing the underlying walk helps you explain event delegation.

8. Normalizing nested data

API responses are often nested. Storing them as-is in React state forces deep updates. Normalization stores each entity once in a lookup table and refers to others by id.

// Nested
const response = [
  { id: 'c1', name: 'Crafts', workshops: [{ id: 's1', title: 'Pottery' }] },
];

// Normalized
const state = {
  categories: { c1: { id: 'c1', name: 'Crafts', workshopIds: ['s1'] } },
  workshops: { s1: { id: 's1', title: 'Pottery' } },
};

Updating s1 now touches one place, lookups are O(1), and components re-render less. This is the same idea as the lookup table in section 4.

9. Two pointers

Two indexes moving through the data often replace nested loops.

Problem. Given a sorted array of prices and a budget, find whether two different prices sum to exactly the budget.

function hasPairWithSum(sortedPrices, target) {
  let left = 0;
  let right = sortedPrices.length - 1;
  while (left < right) {
    const sum = sortedPrices[left] + sortedPrices[right];
    if (sum === target) return true;
    if (sum < target) left++;      // need a bigger sum
    else right--;                  // need a smaller sum
  }
  return false;
}

Input [5, 12, 20, 35, 50], target 55: 5+50=55, found immediately. Target 40: 5+50=55 too big, move right; 5+35=40, found. Time O(n), space O(1). Brute force is O(n²). A Set-based version is O(n) time but uses O(n) space and does not need sorted input. State both options and the assumption that decides between them.

10. Common pitfalls and exam tips

Exam tip: when you see "have I seen this before?", "count", or "find by id", think Set or Map first.

Exam tip: when you see "most recent first" or nested structure, think stack; "in order of arrival" or "level by level", think queue.

Pitfalls:

• Using an array with find inside a loop instead of building a lookup table.
• Using an object as a map with user-controlled keys (__proto__, constructor).
• Forgetting that Map and Set are not JSON-serializable and are awkward in React state.
• Mutating state structures in React and expecting a re-render.
• Using shift repeatedly on a huge array and calling it O(1).
• Writing a recursive tree traversal without a base case or on very deep input (stack overflow).
• Assuming sorted input when it was not stated.

11. Mini case study: group and rank the waiting list

Situation. Harbor Workshops stores waiting-list entries as { workshopId, email }. The same email might be added to the same workshop twice by double-clicking. Task: return, for each workshop, the number of unique emails, and the id of the workshop with the longest list.

Solution, commented.

1. Structure choice. We need unique emails per workshop, so a Map from workshopId to a Set of emails. The Set removes duplicate clicks automatically.
2. Code.

function waitlistSummary(entries) {
  const byWorkshop = new Map();
  for (const { workshopId, email } of entries) {
    if (!byWorkshop.has(workshopId)) byWorkshop.set(workshopId, new Set());
    byWorkshop.get(workshopId).add(email.trim().toLowerCase());
  }

  const counts = {};
  let longest = null;
  let longestSize = 0;
  for (const [id, emails] of byWorkshop) {
    counts[id] = emails.size;
    if (emails.size > longestSize) {
      longest = id;
      longestSize = emails.size;
    }
  }
  return { counts, longest };
}

3. Trace. Entries s1/A@x.com, s1/a@x.com , s2/b@x.com: the first two normalize to the same email, so s1 has size 1, s2 has size 1; longest is s1 because ties keep the first seen. State that tie rule aloud.
4. Complexity. O(n) time (each entry costs O(1) average plus the cost of trimming), O(n) space.
5. Alternatives rejected. An array of emails per workshop with includes would be O(n²) in the worst case. A sort-based approach would cost O(n log n) with no benefit.

Key terms

• Data structure: a way of organizing data for efficient operations.
• Hash table: a key-to-value structure using hashing for average O(1) lookup.
• Stack / queue: LIFO / FIFO collections.
• Linked list: nodes connected by references.
• Tree: a hierarchy with a root and children; the DOM is a tree.
• DFS / BFS: depth-first / breadth-first traversal.
• Normalization: storing entities once, referenced by id.
• Two pointers: moving two indexes to avoid a nested loop.

Summary checklist

• I know the cost of common array operations and avoid hidden O(n) calls in loops.
• I choose between array, object, Map, and Set for a stated need.
• I build lookup tables instead of repeated find.
• I recognize stack and queue problems and implement them.
• I traverse trees depth-first and breadth-first.
• I apply the frequency-counter and two-pointer patterns.
• I keep React state immutable when using Set or Map.

Sources

• Coding Interview Preparation (official course): https://www.coursera.org/learn/coding-interview-preparation (opens in a new tab)
• MDN Keyed collections (Map, Set): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Keyed_collections (opens in a new tab)
• MDN Using the DOM (the document as a tree): https://developer.mozilla.org/en-US/docs/Web/API/Document_Object_Model (opens in a new tab)