Core interview toolkit

These topics are small enough to hide inside larger problems. Choose them from the operation and proof you need, not from the nouns in the story.

Thinking flow · recognize the missing primitive

flowchart TD
  accTitle: Choosing a core interview technique
  accDescr: Pointer rewiring suggests linked lists, a locally safe irreversible choice suggests greedy, flags and subsets packed into integers suggest bit operations, and repeated prefix fallback suggests a string matching algorithm.
  A{"What operation dominates?"}
  A -->|"rewire nodes without shifting data"| B["Linked-list pointers"]
  A -->|"commit one choice and discard alternatives"| C{"Can an exchange argument prove safety?"}
  C -->|yes| D["Greedy"]
  C -->|no| E["DP, search, or flow"]
  A -->|"pack flags, masks, or subsets"| F["Bit manipulation"]
  A -->|"match a pattern while reusing prefix work"| G["KMP or another string index"]

One pointer invariant to memorize

When reversing a singly linked list, the list is split into a reversed prefix and an unread suffix. Save the suffix before overwriting next.

PythonC++17C++11

@dataclass
class ListNode:
    value: int
    next: ListNode | None = None


def reverse_linked_list(head: ListNode | None) -> ListNode | None:
    """Reverse a singly linked list in place and return its new head."""
    previous: ListNode | None = None
    current = head
    while current is not None:
        # Save the unread suffix before changing the only forward link.
        following = current.next
        current.next = previous
        # Advance both boundaries of the reversed prefix.
        previous, current = current, following
    return previous

struct ListNode {
  explicit ListNode(int node_value, ListNode* next_node = nullptr)
      : value(node_value), next(next_node) {}

  int value;
  ListNode* next;
};

inline ListNode* reverse_linked_list(ListNode* head) {
  ListNode* previous = nullptr;
  ListNode* current = head;
  while (current != nullptr) {
    // Save the unread suffix before changing the only forward link.
    ListNode* following = current->next;
    current->next = previous;
    // Advance both boundaries of the reversed prefix.
    previous = current;
    current = following;
  }
  return previous;
}

struct ListNode {
  explicit ListNode(int node_value, ListNode* next_node = nullptr)
      : value(node_value), next(next_node) {}

  int value;
  ListNode* next;
};

inline ListNode* reverse_linked_list(ListNode* head) {
  ListNode* previous = nullptr;
  ListNode* current = head;
  while (current != nullptr) {
    // Save the unread suffix before changing the only forward link.
    ListNode* following = current->next;
    current->next = previous;
    // Advance both boundaries of the reversed prefix.
    previous = current;
    current = following;
  }
  return previous;
}

Reading path

1. Linked lists: draw ownership before changing pointers.
2. Greedy algorithms: prove a local choice with exchange or stay-ahead reasoning.
3. Bit manipulation: use masks only when the representation simplifies state.
4. String matching: choose KMP, Z, Trie, or rolling hash from the query shape.

Continue to the problem catalog to practice by recognition signal instead of random difficulty.