Everything in coding interviews is built on two ideas: how to measure the cost of code (Big-O), and the data structure you'll use in 80% of problems (the array). Nail these in week one and every later pattern has something solid to stand on. No prior CS needed — we start from zero.
Look at a loop and instantly say "that's O(n)" (and defend it); explain why reading an array index is free but inserting at the front is expensive; and solve easy array problems in a single pass while narrating the time and space cost out loud — exactly what an interviewer is listening for.
Reading is not learning. This page is built to be used, not skimmed.
Big-O answers one question: as the input grows, how fast does the work grow?
It is not a stopwatch. "My laptop runs it in 3 milliseconds" tells an interviewer nothing — a faster machine changes that number, but it doesn't change whether your algorithm scales. Big-O throws away the hardware and the constants and keeps only the shape of the growth. That shape is the difference between code that handles a billion users and code that melts at a thousand.
Ask: "if the input doubles, what happens to the work?" Stays the same → O(1). Doubles too
→ O(n). Quadruples → O(n²). Goes up by a fixed step → O(log n). That single question
classifies almost everything.
You don't compute Big-O with math — you read it off the structure. The loops tell you almost everything:
# O(1) — constant. No loop over the input; one step regardless of size.
x = nums[0]
# O(n) — linear. One pass: work grows in lockstep with n.
for v in nums:
total += v
# O(n^2) — quadratic. A loop inside a loop over the same input.
for i in nums:
for j in nums:
print(i, j)
# O(log n) — logarithmic. The input is HALVED each step (n -> n/2 -> n/4 ...).
while n > 1:
n = n // 2
These shapes look similar near the origin and then diverge violently. Toggle each curve and read what it actually
costs at n = one million — the gap between O(n) and O(n²) is the whole game.
| Big-O | Name | Ops at n = 1,000,000 | Where you meet it |
|---|---|---|---|
| O(1) | constant | 1 | Array index, hash lookup, arithmetic |
| O(log n) | logarithmic | ~20 | Binary search (Week 5) |
| O(n) | linear | 1,000,000 | A single loop — your usual target |
| O(n log n) | linearithmic | ~20,000,000 | Good sorting (sorted()) |
| O(n²) | quadratic | 1,000,000,000,000 | Nested loops — optimise this away |
| O(2ⁿ) | exponential | too many to write | Brute-force "try every subset" (Week 6) |
O(2n + 5) is just O(n). Big-O cares about growth shape, not exact counts — doubling the work doesn't change how it scales.O(n² + n) is O(n²). For large n, the n² utterly dominates the n, so the small term is noise.
Big-O also measures extra memory your algorithm allocates as the input grows (not counting the input itself).
Solving a problem with a couple of variables is O(1) space; building a new list or a hash set of size n is
O(n) space. Interviewers grade both — the best answers state the time/space trade-off you chose.
"I loop through the array once, doing constant work each step, so it's O(n) time. I only keep a couple of variables, so O(1) space. I could trade space for speed with a hash set — O(n) space — but here one pass is enough."
Pick the tightest Big-O. (Answers reveal instantly, with the why.)
for v in nums:
if v == target:
return True
return Falsen elements, constant work each step → O(n). (It returns early on a match, but Big-O describes the worst case, where the target is absent or last.)for i in range(len(nums)):
for j in range(len(nums)):
if nums[i] + nums[j] == target:
return (i, j)while n > 1:
n = n // 2
steps += 1O(3n + 100) in the same class as O(n)? drillO(3n + 100), O(n/2), and O(n + 7) are all simply O(n).An array is a row of values laid out back-to-back in memory. That one physical fact explains all of its speed and all of its slowness.
Because the elements are contiguous and all the same size, the computer can find element i with pure
arithmetic: address = start + i × element_size. No searching. That's why reading or writing by index is
O(1) — instant, at any size. But it's also why inserting or deleting in the middle is O(n): to make room (or
close a gap) every element after the spot has to physically shuffle over.
Each box is a memory slot with its address. Try the three operations and watch the cost.
Index = O(1). Append to the end = O(1)* (amortised). Insert/delete at the front or middle = O(n). If a problem makes you repeatedly insert at the front, an array is the wrong tool — that's a hint to reach for a different structure later (a deque, a linked list).
* "Amortised O(1)": a dynamic array (Python list, Swift Array, Java ArrayList) occasionally
runs out of room and copies everything to a bigger block — an O(n) hiccup. But that's rare enough that averaged over many
appends, each one is effectively O(1). You can say "amortised constant" and sound exactly right.
A string is essentially an array of characters, so the same costs apply: indexing a character is O(1), scanning is O(n).
The one gotcha: in many languages (Python, Java, Swift) strings are immutable — every "edit" actually builds a new
string. So building a result character-by-character with s = s + c inside a loop is a sneaky O(n²).
The fix is to collect pieces in a list and join once at the end.
| Operation | Cost | Why |
|---|---|---|
Read / write arr[i] | O(1) | Direct address arithmetic — no searching |
| Append to end | O(1)* | Write the next free slot (amortised) |
| Insert / delete at front or middle | O(n) | Every later element must shift |
| Search for a value (unsorted) | O(n) | Must check each element |
| Search for a value (sorted) | O(log n) | Binary search — Week 5 |
| Scan the whole array | O(n) | One pass |
The fun part. Read the problem, actually try it for a few minutes, peek at the hint if stuck, then check the solution.
prices[i] is the stock price on day i. Buy on one day and sell on a later day to
maximise profit. Return the max profit, or 0 if no profit is possible.
Example: [7, 1, 5, 3, 6, 4] → 5 (buy at 1, sell at 6).
The brute force tries every (buy, sell) pair — O(n²). To do it in one pass: as you walk left to right, what's the only thing about the past you need to remember to know your best possible profit today?
Track the cheapest price seen so far. On each day, the best sale today is price − cheapest_so_far.
Keep the running maximum of that. One pass, two variables.
def max_profit(prices):
min_price = float('inf') # cheapest day we could have bought
best = 0 # best profit found so far
for p in prices:
min_price = min(min_price, p) # update cheapest buy
best = max(best, p - min_price) # best sale if we sell today
return bestO(n) time (one pass), O(1) space (two scalars). Pattern: one pass + a running value — here, "track the best so far". This single idea retires a whole shelf of O(n²) brute forces.
Find the contiguous subarray with the largest sum, and return that sum.
Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (the subarray [4, -1, 2, 1]).
Walk left to right keeping a "current running sum". At each element you face one decision: is it better to extend the current run, or throw it away and start fresh at this element? When does carrying the past hurt you?
If the running sum ever goes negative, it can only drag down whatever comes next — so drop it and restart at the current element. Track the best sum seen along the way.
def max_subarray(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # extend the run, or start over at x
best = max(best, cur) # remember the best run we've seen
return bestO(n) time, O(1) space. This is "Kadane's algorithm" — your first taste of dynamic programming (Week 11): the answer ending at each position is built from the answer at the previous one. The naive "sum every subarray" approach is O(n²) or worse.
Move all 0s to the end while keeping the order of the non-zero elements. Do it in place (no new array).
Example: [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0].
Use a second index — a "write pointer" — that marks where the next non-zero value should go. Sweep with a read pointer; every time you find a non-zero, write it at the write pointer and advance it. What's left to do once the sweep finishes?
Compact all the non-zeros to the front with a write pointer, then fill the remaining slots with zeros.
def move_zeroes(nums):
w = 0 # next position to write a non-zero
for x in nums: # read pointer sweeps the array
if x != 0:
nums[w] = x
w += 1
while w < len(nums): # fill the tail with zeros
nums[w] = 0
w += 1O(n) time, O(1) space. Pattern: read pointer + write pointer — the foundation of the "two pointers" family you'll meet properly in Week 3. "In place" is the signal to reach for pointers instead of a new array.
Return True if any value appears at least twice, else False.
Example: [1, 2, 3, 1] → True · [1, 2, 3, 4] → False.
The brute force compares every pair — O(n²). One option: sort first (O(n log n)), then duplicates sit next to each other. But can you do it in one pass if you're allowed to remember what you've already seen?
Keep a set of values you've seen. For each element, if it's already in the set you've found a duplicate; otherwise add it. Membership tests on a set are O(1).
def contains_duplicate(nums):
seen = set()
for x in nums:
if x in seen: # O(1) membership check
return True
seen.add(x)
return FalseO(n) time, O(n) space — we traded memory for speed. Pattern: hashing. This is the single most important trick in the whole interview, and it's all of Week 2. The sorting approach (O(n log n) time, O(1) extra space) is a great "here's the trade-off" line to mention.
Five questions. If you can ace these, the week's concepts are yours. The score tracks at the bottom.
Tick these off honestly. They're the bar for moving on — and they save in your browser.
Notice how Problem 4 itched for something faster than scanning or sorting? That "remember what I've seen in O(1)" instinct is the hash map — and it's the highest-leverage trick in the entire interview. That's Week 2.