Explain a Problem and Its Complexity

Introduction

This is lesson 1 of chapter 9, the last chapter of the pathway (domain interview). The official ninth course, Coding Interview Preparation, is organized around interview communication, pseudocode, data structures, and algorithms (source: https://www.coursera.org/learn/coding-interview-preparation (opens in a new tab)). This chapter is original OnLevelUp material that prepares you for those skills; it does not reproduce the course's graded work or any real interview question set.

Everything you built so far (components, hooks, forms, tests) showed that you can write code. A technical interview checks something slightly different: whether you can understand a problem, talk through a plan, write correct code under time pressure, and reason about its cost. This lesson gives you a repeatable method for the first three and the vocabulary for the fourth: time and space complexity.

Learning objectives

By the end of this lesson you can:

Restate a problem in your own words and ask clarifying questions about inputs, outputs, and constraints.
Work through concrete examples, including edge cases, before writing code.
Write pseudocode that separates the plan from language syntax.
Describe a brute-force solution first, then improve it deliberately.
Estimate time and space complexity using Big O notation for loops, nested loops, and halving strategies.
Test a solution by tracing it by hand.
Explain your reasoning aloud in a structured, calm way.

1. A repeatable method

Interview problems feel hard mostly because candidates start typing too early. A method turns a stressful moment into a checklist. A common five-step sequence is:

Step	What you do	Typical time
1. Understand	Restate the problem, ask questions, confirm inputs and outputs	2–3 min
2. Examples	Build 2–3 small examples plus edge cases	2–3 min
3. Plan	Describe brute force, then a better idea, in pseudocode	3–5 min
4. Code	Translate the plan into JavaScript, naming things clearly	10–15 min
5. Verify	Trace an example by hand, discuss complexity, mention tests	3–5 min

The times are editorial guidance, not an official rule. What matters is the order: no code until you and the interviewer agree on the problem and the plan.

Step 1: understand and clarify

Imagine the prompt: "Given a list of workshop bookings, return the names of customers who booked more than once."

Good clarifying questions:

What is the shape of a booking? An object { customer, workshopId }? Is customer a string?
Is the comparison case-sensitive? Is "Sam" the same as "sam"?
Can the list be empty? Can it be very large (thousands, millions of items)?
Should the result be unique names, in any order, or in order of first appearance?
Should the input be modified, or must it stay unchanged?

Asking questions is not a sign of weakness. In a real project you would never build a feature without these answers, and interviewers read the questions as evidence of engineering maturity.

Step 2: examples and edge cases

Write examples before code:

Input:  [{c:"Sam"}, {c:"Ana"}, {c:"Sam"}, {c:"Lee"}, {c:"Ana"}, {c:"Sam"}]
Output: ["Sam", "Ana"]            // unique, order of first repeat

Input:  []                        -> []
Input:  [{c:"Sam"}]               -> []        // one booking is not a repeat
Input:  [{c:"Sam"}, {c:"sam"}]    -> ?         // ask: case sensitivity

Typical edge cases to check every time:

Empty input.
A single element.
All elements identical.
Already sorted or reverse-sorted data.
Duplicates, negative numbers, zero, very large values.
Invalid input (null, wrong type), if the interviewer cares.

Step 3: plan with pseudocode

Pseudocode is a plain-language description of the steps, without exact syntax. It keeps you from getting lost in semicolons and lets the interviewer correct the plan cheaply.

function repeatedCustomers(bookings):
    counts = empty map
    result = empty list
    for each booking in bookings:
        add 1 to counts[booking.customer]
        if counts[booking.customer] is exactly 2:
            append booking.customer to result
    return result

Notice the detail "exactly 2": it prevents adding a name a third time. Writing the plan exposed that subtle point before any JavaScript existed.

Step 4: code

function repeatedCustomers(bookings) {
  const counts = new Map();
  const result = [];

  for (const { customer } of bookings) {
    const next = (counts.get(customer) ?? 0) + 1;
    counts.set(customer, next);
    if (next === 2) {
      result.push(customer);
    }
  }

  return result;
}

Output for the first example: ["Sam", "Ana"]. Sam reaches 2 at the third item, Ana at the fifth.

Step 5: verify

Trace with a small input and say each state out loud:

bookings: Sam, Ana, Sam
after Sam: counts {Sam:1}                result []
after Ana: counts {Sam:1, Ana:1}         result []
after Sam: counts {Sam:2, Ana:1}         result ["Sam"]

Then state the complexity (next sections) and name one or two additional tests.

2. Brute force first, then improve

A strong habit: describe the simplest correct solution first, even if slow. It proves you understand the problem and gives you a safe fallback.

Brute force for the same problem: for every booking, scan the whole list to count how many times that customer appears.

function repeatedCustomersSlow(bookings) {
  const result = [];
  for (const a of bookings) {
    let count = 0;
    for (const b of bookings) {
      if (a.customer === b.customer) count++;
    }
    if (count > 1 && !result.includes(a.customer)) {
      result.push(a.customer);
    }
  }
  return result;
}

This works, but for 10,000 bookings it performs about 10,000 × 10,000 = 100 million comparisons, plus includes scans. The Map version does one pass. Saying "the brute force is O(n²); I can use a Map to get it down to O(n)" is exactly the narration an interviewer wants.

3. Time complexity and Big O

Big O notation describes how the amount of work grows as the input size n grows. It ignores constants and lower-order terms because for large n the growth rate dominates.

Notation	Name	Typical example	Rough work for n = 1,000
O(1)	Constant	Read `array[i]`, `map.get(key)` (average)	1
O(log n)	Logarithmic	Binary search on sorted data	about 10
O(n)	Linear	One loop over the array	1,000
O(n log n)	Linearithmic	Efficient sorting (merge sort)	about 10,000
O(n²)	Quadratic	Loop inside a loop over the same data	1,000,000
O(2ⁿ)	Exponential	Naive recursive subsets or Fibonacci	astronomically large

How to read the cost of code

A single loop over n items with constant work inside: O(n).
Two sequential loops: O(n) + O(n) = O(2n), simplified to O(n).
A loop nested in a loop, both over n: O(n²).
A loop that halves the remaining range each time: O(log n).
A loop calling a linear method inside (such as includes, indexOf, slice, concat): the inner method adds a factor of n, so the total is O(n²).

That last rule is the one most front-end developers miss. This looks like one loop but is quadratic:

// O(n²): includes() scans the result array each time
function uniqueSlow(items) {
  const out = [];
  for (const x of items) {
    if (!out.includes(x)) out.push(x);
  }
  return out;
}

// O(n): Set lookup is O(1) on average
function unique(items) {
  return [...new Set(items)];
}

Worst, average, and best case

Big O normally states the worst case unless said otherwise. Searching an unsorted array for a value is O(n) in the worst case (value last or absent) even though it could be found at index 0. Mention the case you are describing when it matters.

Space complexity

Space complexity measures extra memory used as n grows, not counting the input itself.

repeatedCustomers stores a Map with up to n entries: O(n) space.
Reversing an array in place with two indices uses O(1) extra space.
Creating a new array with map or the spread operator uses O(n) space.
Recursion uses stack space: a recursive function that goes n levels deep uses O(n) stack.

Often you trade time for space. The Map solution uses more memory to save time. Naming the trade-off explicitly is a mark of a strong answer.

4. Worked example: from slow to fast

Problem. A booking page has a sorted-by-time list of n workshop session start times (in minutes since midnight, integers). Return true if any two sessions start at exactly the same minute.

Step 1: clarify. Are times sorted? The statement says sorted by time. Can n be 0 or 1? Yes. Is the list large? Assume up to 100,000.

Step 2: examples.

[540, 600, 600, 660] -> true
[540, 600, 660]      -> false
[]                   -> false
[540]                -> false

Step 3: plan.

Option A (brute force): compare every pair. O(n²) time, O(1) space. Option B (Set): store seen values, stop when one repeats. O(n) time, O(n) space. Option C (use the sorted property): duplicates in a sorted list are adjacent, so compare each element with its neighbor. O(n) time, O(1) space.

Option C is best because the sorted guarantee removes the need for extra memory.

Step 4: code.

function hasDuplicateStart(times) {
  for (let i = 1; i < times.length; i++) {
    if (times[i] === times[i - 1]) {
      return true;
    }
  }
  return false;
}

Step 5: verify. Trace [540, 600, 600, 660]: i=1 compares 600 and 540, no; i=2 compares 600 and 600, return true. For [] and [540] the loop never runs, so the result is false, as required.

Why the other choices are weaker. A is correct but needs about 5 billion comparisons for 100,000 items, too slow. B is correct and fast but wastes memory because the input already carries the structure we need. If the interviewer had said the list was not sorted, B would be the best answer, or sorting first at O(n log n). The correct choice depends on the guarantees you confirmed in step 1, which is why clarifying questions matter.

5. Naming and structure while you code

Interviewers read your code as they would in a code review. Small habits help:

Use descriptive names: seenIds, left, right, not a, b, tmp2.
Keep functions short and give them one job. Extract a helper if a block needs a comment to explain it.
Handle edge cases at the top with early returns.
Prefer const; use for...of or array methods when they read clearly.
Do not mutate input unless you agreed it is acceptable.
Say what you are about to do before you do it: "I'll keep two indices, one at each end."

// Clear: early return handles the empty case
function firstLongSession(sessions, minMinutes) {
  if (sessions.length === 0) return null;
  for (const session of sessions) {
    if (session.durationMin >= minMinutes) return session;
  }
  return null;
}

6. Communicating when you are stuck

Everyone gets stuck. Interviewers often care more about how you recover than whether you recover instantly.

Say what you know: "I have the brute force; it is quadratic."
Name the bottleneck: "The repeated scan inside the loop is the expensive part."
Ask a targeted question: "Can I assume the values fit in memory? Is the input sorted?"
Try a smaller case by hand and look for a pattern.
Consider a data structure that gives faster lookup (Map, Set), or sorting to expose adjacency.
If time is short, finish a correct but slower solution and discuss the improvement verbally.

Avoid long silences. Thinking aloud, in short sentences, lets the interviewer help you and see your reasoning.

7. Common pitfalls and exam tips

Exam tip: state the complexity of your final answer without being asked. One sentence: "This is O(n) time and O(n) space because of the Map."

Exam tip: when comparing options, compare on the same axes. Time, space, readability, and the assumptions each option needs.

Common pitfalls:

Starting to code before restating the problem, then solving a different problem.
Forgetting empty and single-element inputs.
Treating includes, indexOf, slice, splice, and string concatenation in a loop as free operations.
Calling a solution O(n) when it hides a nested linear call.
Claiming "O(1)" for hash lookups without saying "average case".
Optimizing too early; correct first, fast second.
Silently rewriting the whole solution when a one-line fix would do.
Memorizing solutions instead of the method; a small change to the prompt exposes memorization.

8. Mini case study: the slow search suggestion

Situation. Harbor Workshops has 20,000 workshop titles. A search box suggests titles that contain what the user typed. The developer wrote:

function suggestions(titles, query) {
  const results = [];
  for (const title of titles) {
    if (title.toLowerCase().includes(query.toLowerCase())) {
      if (!results.includes(title)) results.push(title);
    }
  }
  return results;
}

Users report lag on every keystroke. Analyze the cost and propose improvements.

Solution, commented.

Cost. The outer loop is O(n) with n = 20,000. Inside, toLowerCase() runs twice per title, each proportional to string length m, and includes is O(m). The results.includes(title) scan is O(r) where r is the number of matches so far. Worst case (query like "a", nearly everything matches) r approaches n, so that part is O(n²) ≈ 400 million comparisons.
Improvement 1. Lowercase the query once, outside the loop. This removes repeated work: constant-factor but free.
Improvement 2. Titles are unique already, or deduplicate once at load time with a Set. Remove the results.includes check entirely. The loop becomes O(n·m).
Improvement 3. Precompute lowercase titles once when data loads, store them next to the originals, so each keystroke only does the includes.
Improvement 4. In the React component, debounce the input or use useDeferredValue, and limit the displayed list (for example the first 8 results) so the render stays cheap.

function buildIndex(titles) {
  return [...new Set(titles)].map((title) => ({ title, lower: title.toLowerCase() }));
}

function suggestions(index, query, limit = 8) {
  const q = query.trim().toLowerCase();
  if (q === '') return [];
  const out = [];
  for (const entry of index) {
    if (entry.lower.includes(q)) {
      out.push(entry.title);
      if (out.length === limit) break;
    }
  }
  return out;
}

The early break means a common query stops after finding eight matches. In the interview you would also mention that a prefix tree (trie) or a server-side search could be better at far larger scale, but for 20,000 titles this simple approach is sufficient and easy to maintain.

Key terms

Pseudocode: a plain-language plan of steps without exact syntax.
Brute force: the simplest correct approach, often slow.
Big O notation: a description of how cost grows with input size, ignoring constants.
Time complexity: growth of the number of operations.
Space complexity: growth of extra memory.
Edge case: an unusual input at the boundary, such as empty or single-element.
Trade-off: gaining one benefit (speed) at the cost of another (memory).
Bottleneck: the part of the solution that dominates the cost.

Summary checklist

I restate the problem and ask about inputs, outputs, and constraints.
I write examples and edge cases before code.
I write pseudocode and agree the plan first.
I describe brute force, then improve it on purpose.
I can classify O(1), O(log n), O(n), O(n log n), O(n²).
I spot hidden linear calls inside loops.
I state both time and space complexity and name the trade-off.
I trace my solution by hand and think aloud when stuck.

Sources

Coding Interview Preparation (official ninth course of the pathway): https://www.coursera.org/learn/coding-interview-preparation (opens in a new tab)
Meta Front-End Developer Professional Certificate: https://www.coursera.org/professional-certificates/meta-front-end-developer (opens in a new tab)
MDN JavaScript reference (Map, Set, Array methods): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference (opens in a new tab)