2025 Coding Interview Prep

Overall principles.

All data structures are variants of arrays and linkedlists.

What kind of problem is this? Basically all coding problems can be boiled down to enumeration. To write a efficient enumeration algorithm, we need to make sure the code enumerates in a fashion where there is no leftovers and redundancies.

When encounters a problem, use the following thinking paradigm:

  1. How do we enumerate by brute-forcing?
    • DFS, BFS
    • Backtracing, Dynamic program
  2. Is it possible to enumerate or traverse more efficiently?
    • Sliding window
    • Greedy
    • Union Find

Linked List / Arrays

  1. Two pointers: fast/slow, left/right.
  2. Use DummyNode to simplify the edge cases.
  3. Make sure the tail is None and the constructed LinkedList has no cycles.

Sliding window

Problems related to Continuous sub-string, sub sequence.

def solution(array):
  l = r = 0
  # initialize window here using different data structures
  window = ...

  while r < len(array):
    item = array[r]
    r += 1

    # Update window status.
    window.add(item)

    while l < r and needs shrink:
      item = array[l]
      window.remove(item)
      l += 1

      # Check if result update is needed.

Binary Tree

Pre-order, in-order, post-order.

  1. Can we solve the problem by traversing the tree once? -> Use a void traverse() function and a external variable.
  2. Can we solve the problem by * breaking down* the problem into smaller ones? -> Define a recursive function and utilize the return value well.

搜索问题

本质上是图的遍历问题，每个state如何遍历以找到target state的问题。如何高效遍历：

  1. DFS/Backtracking
  2. BFS

BFS

本质是在一个图中求从start到end的最短距离。

from collections import deque


def bfs(start, end):
  q = deque([start])
  # Use set to achieve O(1) time complexity.
  # Sometimes the state need to be convert to data structures
  # that can be hashed and are immutable.
  visited = set([start])
  steps = 0

  while q:
    steps += 1
    # The following line can be substitute by appending depth to the element.
    for _ in range(len(q)):
      cur = q.popleft()
      if cur == end:
        return cur

      for next_node in get_next_steps(node):
        if next_node not in visited:
          q.append(next_node)
          visited.add(cur)
  # No path from start to end.
  return None
· Coding Interview