Interview DSA Crash Course

Week 1 — the vocabulary of the interview. A correct answer you cannot explain is a rejection.

1. Big-O without the fear

   Big-O describes how work grows as input grows. A loop inside a loop over the same list is O(n²) — that is most of what a fresher interview needs.

   The lesson

   Big-O is a way of saying how the work grows when the input grows, ignoring constants. Looking up a value in a list of n items takes up to n steps — that is O(n). Reading arr[5] takes one step whatever the size — O(1). A loop inside a loop is O(n²), and that is the one that quietly fails an interview.

   You do not need proofs. You need to look at your own code and count the loops: none or one pass is fine, a nested loop over the same input is a warning, and a nested loop over the WHOLE input inside another is usually the thing to fix. Say the number out loud in an interview and you have answered the question they were about to ask.

   The mistake is assuming a clever-looking solution is fast. list.index(x) reads as one call and is a hidden O(n) scan; sorting is O(n log n) and turns many O(n²) double loops into a single pass. Learn the cost of the five operations you actually use, and you will spot most bad solutions before you write them.

   PythonCopy

   # O(1) - one step, any size
   def first(items): return items[0]
   
   # O(n) - one pass
   def total(items): return sum(items)
   
   # O(n^2) - a loop inside a loop over the same input
   def has_pair(items):
       for a in items:
           for b in items:
               if a + b == 0:
                   return True
       return False
   
   # Hidden O(n): items.index(x) scans. Sorting is O(n log n).

   Example A single pass to find the maximum is O(n); checking whether a list has duplicates by comparing every pair is O(n²); a set makes it O(n) — same answer, different cost.

   Practice For five problems you have already solved, write the time and space complexity of each in one line.

2. The pattern-first method

   Interviews repeat patterns far more than they repeat problems. Naming the pattern is how a new question becomes a familiar one.

   The lesson

   Interview questions are not 500 different problems; they are about a dozen patterns wearing different clothes. Two pointers, sliding window, hash map, binary search, recursion, breadth-first search, and a handful more. Recognising the pattern is most of the work — the code is then short.

   The signals are in the question. "Sorted array" suggests two pointers or binary search. "Subarray" or "longest substring" suggests a window. "Have you seen this before", "count the frequency" or "find the pair" suggests a hash map. "Minimum number of steps in a grid" suggests BFS. Say which pattern you are considering and why — that sentence is worth more than typing.

   The mistake is starting to type while you are still deciding. Spend the first two minutes reading the example carefully and naming the pattern; the interviewer is scoring your approach, and a wrong approach written quickly scores nothing.

   Plain textCopy

   Signals in the question -> pattern:
     "sorted array", "pair sum"       -> two pointers / binary search
     "subarray", "longest substring"  -> sliding window
     "count frequency", "have I seen" -> hash map / set
     "minimum steps in a grid"        -> BFS
   
   Name the pattern and WHY before you type a line.

   Example "Find two numbers that add to a target" and "find a subarray with a given sum" are both the same two-pointer / hash-map family — recognising that is the whole skill.

   Practice Take ten problems you have solved and write the pattern name beside each one.

3. Explaining before writing

   Say the plan in plain language, get agreement, then code. Silent typing is the most common reason a technically correct candidate is rejected.

   The lesson

   The interview is a conversation about code, not a typing test. Say the plan before the code: "I will keep two pointers, one at each end, and move the one with the smaller value until they meet — that is O(n) time and O(1) extra space." Then write it, and they can follow every line.

   Work an example on the shared screen or on paper first, step by step, and let them correct you there rather than at line twenty. If you get stuck, say what you are stuck on — a candidate who says "I think the window contract breaks when the character repeats" is easier to help than one who stares silently.

   The mistake is silence. Silence reads as panic to an interviewer even when you are thinking clearly, and it removes the guidance they are allowed to give you. Narrate the choices — "I am using a set here because I need to know whether I have seen the character" — and the code becomes the easy part.

   Plain textCopy

   "I will keep two pointers, one at each end.
    Move the smaller one inward until they meet.
    That is O(n) time and O(1) extra space."
   
   Say it, THEN write it. Work the smallest example by hand first.
   Stuck? Say what you are stuck on - silence reads as panic.

   Example "I will use a hash map from value to index, so for each item I check whether target minus it is already in the map — that is O(n) time and O(n) space. Shall I write that?" is a full, close to winning answer.

   Practice Solve one problem out loud to a friend or a recorder, narrating every step, before writing a single line.

4. Numbers you should know cold

   Base cases exist for a reason: for n up to 10, a nested loop is fine; for n up to 100,000 it is not. The n bound in the question tells you which solution is acceptable.

   The lesson

   A few facts save time and make you look prepared. An array index is O(1); searching a sorted array with binary search is O(log n) — about 20 steps for a million items. A hash map lookup is O(1) on average. Sorting is O(n log n). Counting from 1 to 10⁷ in a loop is about a second in Python.

   Also worth knowing: 10⁶ operations is comfortable, 10⁸ is not, and that is why an O(n²) solution over 100,000 items cannot pass a time limit no matter how clean it is. When you propose an approach, mention the size of the input it must handle — the constraints are printed in the question and interviewers expect you to read them.

   The mistake is proposing a solution the constraints cannot support and discovering it at the end. Read the limits first, sanity-check the complexity against them, then choose the approach. Three seconds of arithmetic saves the round.

   Plain textCopy

   arr[i]                  O(1)
   binary search           O(log n)   ~20 steps for 1,000,000 items
   hash map lookup         O(1) average
   sort                    O(n log n)
   loop to 10^7 in Python  ~1 second
   
   10^6 ops = comfortable.  10^8 ops = too slow.  Read the constraints FIRST.

   Example A question with n up to 10⁵ rules out anything O(n²) before you write it — knowing that saves the interview.

   Practice For each of your ten problems, write the largest n that could be accepted with your solution.

Week 2 — the highest-frequency patterns in fresher interviews, and the easiest to practise.

1. Two pointers

   Two positions moving through one sequence, usually from both ends or at different speeds. It turns a nested loop into a single pass.

   The lesson

   Two pointers is one loop with two moving positions instead of two nested loops. Starting at both ends is for a sorted array and a target sum: if the sum is too small, move the left pointer up; too big, move the right one down. Running one behind the other is for removing duplicates in place or reversing part of a sequence.

   The reason it works is that each pointer only moves forward, so the whole thing is one pass — O(n) time and no extra memory. The trick to explaining it is the invariant: "everything to the left of the slow pointer is processed, and the fast one is looking for the next item to keep".

   The mistakes are forgetting the pointers may cross — the loop condition is usually while (left < right) — and trying to use the two-ended version on an unsorted array, where moving a pointer tells you nothing. Sort first if the question allows it, and say that you did.

   PythonCopy

   def two_sum_sorted(nums, target):
       left, right = 0, len(nums) - 1
       while left < right:
           s = nums[left] + nums[right]
           if s == target: return [left, right]
           if s < target:  left += 1      # need bigger -> move left up
           else:           right -= 1     # need smaller -> move right down
       return []
   
   # Sorted input required. One pass: O(n) time, O(1) extra space.

   Example Sorted array, find a pair summing to a target: move the left pointer up when the sum is too small and the right pointer down when it is too large — O(n), and it is O(n²) if you look at every pair.

   Practice Solve reverse-a-string-in-place, check-for-palindrome and pair-sum with two pointers, and write the complexity under each.

2. Hash maps and sets

   A map trades memory for speed: remembering what you have seen makes "have I seen this before" a constant-time question.

   The lesson

   A hash map stores values by key, and a set stores just the keys, both with an average lookup of O(1). That single property turns an O(n²) double loop into one pass in dozens of interview questions: "find two numbers that add to a target", "the first non-repeating character", "is there a duplicate", "group the anagrams".

   The moving parts: adding a key, checking whether a key exists, reading one back, and counting with counts[x] = counts.get(x, 0) + 1. For a duplicate check a set is enough; for counting or grouping you need the map. In JavaScript a Map is safer than an object when the keys are numbers or come from user input.

   The mistake is using a map when the array is sorted and pointers would do with less memory, or using a set when the question asks for the INDEX of the pair — a set tells you the value exists, not where it was. Read what the question wants returned before choosing the structure.

   PythonCopy

   def two_sum(nums, target):
       seen = {}                          # value -> index
       for i, n in enumerate(nums):
           if target - n in seen:
               return [seen[target - n], i]
           seen[n] = i
       return []
   
   # "Is there a duplicate?" needs only a set:
   def has_duplicate(nums):
       return len(set(nums)) != len(nums)
   
   # A set tells you a value EXISTS; a map tells you WHERE.

   Example Counting the frequency of each character in a string in one pass with a map is the same building block used by anagrams, duplicates and most "find the first non-repeating" questions.

   Practice Solve three frequency problems and one "first non-repeating character" problem, each in a single pass.

3. Sliding window

   A moving window over a sequence is the standard answer to "longest/shortest subarray with some property" — including at non-coding companies that ask only this.

   The lesson

   A sliding window is a range that grows on the right and shrinks on the left while you keep a running answer. "Longest substring without repeating characters" and "smallest subarray with sum at least k" are the same technique: extend until a rule breaks, then move the left edge in until it holds again.

   The window needs a small piece of state — a set of characters, a sum, a count map — and the loop looks the same each time: add the new item, fix the violation by moving left, update the best answer. Written that way it is O(n) with two pointers that never move backwards.

   The mistakes are updating the best answer after shrinking instead of before, and forgetting to remove the item you left behind when the window moves — which produces an answer that is too long and looks almost right in a test. Trace one small example by hand before you run it.

   PythonCopy

   def longest_unique(s):
       seen, left, best = set(), 0, 0
       for right, ch in enumerate(s):
           while ch in seen:              # shrink until the rule holds again
               seen.remove(s[left])
               left += 1
           seen.add(ch)
           best = max(best, right - left + 1)
       return best
   
   # O(n): each index is added and removed at most once.

   Example Longest substring without repeating characters: grow the window on the right, shrink from the left while a duplicate exists, remember the largest size. One pass, O(n).

   Practice Implement the longest-substring window and a fixed-size maximum-sum window, and compare both against a brute-force version.

Weeks 3–4 — the shapes that appear in a second technical round, plus the recovery skills nobody teaches.

1. Recursion and the call stack

   A recursive function calls itself on a smaller input. Every recursion needs a base case or it never stops — the single most common failure in a live interview.

   The lesson

   A recursive function calls itself on a smaller version of the problem, with a base case that stops. Factorial, the sum of a list, a tree walk and binary search all have the same three parts: the base case, the smaller call, and what you do with the result. Every call sits on the stack until the innermost one returns.

   The useful skill is converting between the two. Every recursive function can be written with an explicit stack or a loop, and interviewers ask for it when recursion depth would overflow. Practise factorial and Fibonacci both ways — it is the same reasoning applied twice and it comes up constantly.

   The mistake is a base case that never triggers: if n == 0 when n can go negative, or a recursive call with the same argument. If you see a recursion error, print n on each call and the missing step is almost always visible in three lines of output.

   PythonCopy

   def factorial(n):
       if n <= 1:                 # base case - stops the recursion
           return 1
       return n * factorial(n - 1)
   
   # The same thing with a loop
   def factorial_loop(n):
       result = 1
       for i in range(2, n + 1):
           result *= i
       return result
   
   # A base case that never triggers -> RecursionError. Print n to debug.

   Example factorial(n) = n * factorial(n - 1) with factorial(0) = 1 is complete; omit the base case and the answer is a stack overflow in front of the interviewer.

   Practice Write three recursive solutions by hand, each with the base case written FIRST, then verify on paper for n = 0 and n = 1.

2. Binary trees, traversals and search

   Trees and their traversals — depth-first and breadth-first — cover a large share of second-round fresher questions.

   The lesson

   A binary tree is a node with a left child, a right child, and a value. Traversals are just orders of visiting: pre-order is node, left, right; in-order is left, node, right and prints a binary SEARCH tree in sorted order; post-order is left, right, node and is how you free or compute upwards. Breadth-first uses a queue and goes level by level.

   Three interview problems cover most of what is asked: how deep is the tree (recursion on both children, take the larger), is it balanced, and is a given tree a binary search tree (an in-order traversal comes out sorted). Search in a BST is a loop: go left if the target is smaller, right if larger, stop when you reach it.

   The mistake is writing a traversal that returns nothing because the recursive call was made without return. And on the BST question, checking only parent against child is not enough — the value must be inside an allowed RANGE from every ancestor, which is why in-order traversal is the safe answer.

   PythonCopy

   class Node:
       def __init__(self, val, left=None, right=None):
           self.val, self.left, self.right = val, left, right
   
   def depth(node):
       if node is None: return 0
       return 1 + max(depth(node.left), depth(node.right))
   
   def inorder(node, out):
       if node is None: return out
       inorder(node.left, out); out.append(node.val); inorder(node.right, out)
       return out
   
   # In a binary SEARCH tree, the in-order traversal comes out sorted.

   Example A breadth-first traversal with a queue prints level by level; depth-first with recursion prints all of one branch before the next. The output order is the difference, and interviewers ask for both.

   Practice Implement a tree insertion and all three depth-first traversals without looking anything up, then check against a written example.

3. When you go blank

   The recovery routine: restate the question, name the pattern family, start with the brute force, then improve it. Most candidates who are rejected went silent instead of doing this.

   The lesson

   Going blank happens to everyone, including people who have solved three hundred problems, because the interview is a different task from practising. The recovery is a procedure, not a mood: restate the question in your own words, work the smallest example by hand, then describe the brute-force solution out loud.

   Naming the brute force is not giving up; it is a floor to stand on. Say "the straightforward way is O(n²) — let me write the skeleton and then improve it", and you are talking, the interviewer can steer you, and partial credit is on the table. Many candidates then spot the improvement while writing the slow version.

   The mistake is going quiet and waiting for inspiration, or worse, starting to write code you cannot explain. Ask a clarifying question about the input instead — size, duplicates, empty cases — the answer usually hands you the pattern.

   Plain textCopy

   Recovery procedure:
     1. Restate the question in your own words.
     2. Work the SMALLEST example by hand.
     3. Say the brute force out loud: "the simple way is O(n^2)...".
     4. Ask about the input: size? duplicates? empty?
   
   Naming the brute force is a floor to stand on, not giving up.

   Example "I do not have the optimal answer yet. A brute-force version is O(n²) and would work; may I describe that and then improve it?" is a strong answer, not a confession.

   Practice Practise two problems you cannot solve: spend ten minutes narrating the brute force and the path you would explore, and never say only "I do not know".

4. A 4-week practice plan, condensed

   Four weeks is enough for patterns, not for hundreds of problems. Two problems a day, narrated out loud, beats twenty problems read.

   The lesson

   Four weeks, one topic a week, two problems a day of which one is new and one is a repeat from three days ago. Week 1 arrays, strings and hashing. Week 2 two pointers, sliding window and sorting. Week 3 recursion, trees and BFS. Week 4 revision of everything you got wrong, typed again from scratch.

   Keep a file per problem with three lines: the pattern, the complexity, and the specific mistake you made. That file is what you revise from, not the solutions — reading a solution you have already understood teaches almost nothing. Before an interview, read only your mistake file.

   The mistake is grinding new problems for hours a day and never repeating. Fluency comes from the second and third attempt at the same problem a few days apart, and that is exactly what most candidates skip because a new problem feels more productive.

   Plain textCopy

   Wk1 arrays, strings, hashing
   Wk2 two pointers, sliding window, sorting
   Wk3 recursion, trees, BFS
   Wk4 redo everything you got wrong, typed from scratch
   
   2 problems a day: 1 new + 1 repeat from three days ago.
   Keep a file: the pattern . the complexity . the mistake you made.

   Example A day of ten problems read and not solved is worth less than two solved on paper with the complexity written underneath.

   Practice Book 28 daily slots in your calendar, two problems each, and mark each one solved-on-paper-yes-or-no.

The two patterns left, and the debrief that makes practice actually stick.

1. Graphs: BFS and DFS

   A graph is nodes and edges; BFS explores level by level and finds the shortest number of steps, while DFS goes deep and is the base for many recursive answers.

   The lesson

   Keep a visited set from the start, or a graph with a cycle loops forever - the single most common bug in a first BFS.

   Grid problems are graphs in disguise: each cell is a node and its four neighbours are edges. Seeing that turns a scary question into BFS you already know.

   PythonCopy

   from collections import deque
   
   def shortest(graph, start, goal):
       q = deque([(start, 0)])
       seen = {start}
       while q:
           node, dist = q.popleft()
           if node == goal:
               return dist
           for nxt in graph[node]:
               if nxt not in seen:
                   seen.add(nxt)
                   q.append((nxt, dist + 1))
       return -1

   Example Shortest path in a grid, or "fewest changes to reach a state", is BFS with a queue; "does a path exist" or "count the islands" can be DFS.

   Practice Write BFS that returns the shortest distance between two nodes in an unweighted graph.

2. Greedy and intervals

   A greedy solution takes the locally best choice and never reconsiders. It is right when the problem has that property - intervals sorted by end time is the classic case.

   The lesson

   Greedy is easy to code and easy to get wrong; before trusting it, try to build a small counterexample. If you cannot, say why the greedy choice is safe.

   Its tell is an exchange argument: swapping your choice for any other never improves the answer. Saying that sentence is worth as much as the code.

   PythonCopy

   def max_meetings(intervals):
       intervals.sort(key=lambda iv: iv[1])   # by END time
       count, last_end = 0, float("-inf")
       for start, end in intervals:
           if start >= last_end:              # fits after the last one
               count += 1
               last_end = end
       return count
   
   # [[1,3],[2,4],[3,5]] -> 2   (take [1,3] then [3,5])

   Example The maximum number of meetings in one room is greedy: sort by end time and take each meeting that starts after the last one ends.

   Practice Solve the meeting-room problem and write one sentence on why sorting by end time is the correct greedy choice.

3. Binary search on the answer

   When the answer is a number and "is X good enough" is easy to check, binary search the answer instead of trying every value. It turns a linear scan into a logarithm.

   The lesson

   The hard part is the check, not the search. Write a plain function that answers yes or no for one value; the binary search around it is five lines.

   Off-by-one is the classic bug - decide once whether the answer is the low or the high end, and keep that convention through the loop.

   PythonCopy

   def ship_within(capacity, weights, days):
       used, current = 1, 0
       for w in weights:
           if current + w > capacity:
               used += 1
               current = 0
           current += w
       return used <= days
   
   lo, hi = max(weights), sum(weights)
   while lo < hi:
       mid = (lo + hi) // 2
       if ship_within(mid, weights, days):
           hi = mid
       else:
           lo = mid + 1
   print(lo)

   Example "Smallest ship capacity to move all packages in D days" is checked by a simple simulation at each candidate capacity, then binary-searched.

   Practice Solve "minimum capacity to ship in D days" and write the check function separately from the search.

4. The mock interview and the debrief

   A mock interview is worth ten more practice problems if you debrief it. Record it, then write down the pattern you missed and the sentence you fumbled.

   The lesson

   Practise out loud with a person or a recording; thinking you can explain it and explaining it under time pressure are different skills, and only one is tested.

   Read your debrief file before the next interview, not your solution file. The mistakes repeat; the solutions you already know do not need revising.

   Plain textCopy

   Mock interview debrief (3 lines)
   
   Went well:  talked through the two-pointer plan before coding
   Went wrong: blanked on "longest subarray with sum <= k" - missed the window
   Change:     keep a pattern checklist; say the pattern out loud first
   
   Read this before the next interview, not the solutions.

   Example If you blanked on a "subarray" question, the debrief note is "did not connect subarray to a sliding window" - the fix is a checklist, not more problems.

   Practice Do one timed mock interview, then write a three-line debrief: what went well, what went wrong, what you will change.