Stufe 0·Komplexität & Problemlösung

Der Musterkatalog

Eine Karte der wiederkehrenden Muster - zwei Zeiger, Sliding Window, BFS/DFS, binäre Suche, dynamische Programmierung - und wie man erkennt, welches ein Problem verlangt.

13 Min. LesezeitFortgeschritten

Deutsche Übersetzung in Arbeit

Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.

Auf dieser Seite

Interview problems look infinitely varied, but they're not. Under the surface, the vast majority are instances of a small set of patterns. Once you can recognize which pattern a problem wants, you've done most of the work - the code follows. This lesson is the map; the rest of the path drills each pattern in depth.

The core patterns

Each pattern is a reusable technique with a tell - a signal in the problem that suggests it:

Two pointers — a sorted array or a pair/triplet to find; walk from both ends or at two speeds. Tell: "sorted," "pair that sums to," "remove duplicates in place."
Sliding window — the best/longest/shortest contiguous subarray or substring. Tell: "subarray," "substring," "consecutive."
Prefix sums — many range-sum or range-count queries. Tell: "sum of a range," "subarray sums to k."
Binary search — a sorted space, or a monotonic "is x feasible?" question. Tell: "sorted," "minimize the maximum," "find the boundary."
BFS / DFS — trees, graphs, grids, or anything with connectivity or levels. Tell: "shortest path," "connected," "levels," "islands."
Hashing — fast lookup, counting, or grouping. Tell: "seen before," "count of," "group by," "anagram."
Heap (top-k) — the k largest/smallest, or a running median. Tell: "k largest," "closest," "merge k."
Dynamic programming — overlapping subproblems and optimal substructure. Tell: "number of ways," "min/max cost," "can you reach," and a naive solution that recomputes the same subproblem.
Backtracking — build all combinations/permutations, pruning invalid branches. Tell: "generate all," "subsets," "permutations," "valid arrangements."

Recognize the tell, then reach for the pattern

   "longest substring without repeats"   → sliding window + a Set/Map
   "two numbers in a sorted array sum k"  → two pointers
   "number of ways to climb n stairs"     → dynamic programming
   "shortest path in an unweighted grid"  → BFS
   "k closest points to the origin"       → heap
   "all subsets of a set"                 → backtracking

The skill isn't memorizing solutions - it's pattern recognition. When you read a new problem, run through the tells and ask "which of these does this smell like?" Often two patterns combine (a sliding window with a hash map; DFS with memoization becoming DP).

When stuck, brute force then spot the waste

If no pattern jumps out, fall back to the method from the first lesson: write the brute force and look at what it recomputes. Repeated scanning of a range often means a window or prefix sum; recomputing the same subproblem means DP; re-searching a sorted space means binary search. The wasted work names the pattern.

A doctor recognizing a set of symptoms

An experienced doctor doesn't treat every patient as a brand-new mystery. They recognize patterns - this cluster of symptoms usually means that condition - and reach for the matching diagnosis, then confirm. Solving interview problems is diagnosis: the problem's 'symptoms' (sorted input, contiguous subarray, count of ways) point to a pattern you've seen before, and you apply it and verify. Building that catalog of recognized patterns is exactly what turns a hard problem into a familiar one.

Diagnose the pattern

For each problem, name the pattern its wording points to: (a) "find the length of the longest substring with at most two distinct characters"; (b) "given a sorted array, return all pairs that sum to a target"; (c) "count the number of distinct ways to make change for an amount."

What is the core skill the pattern catalog develops?

Key takeaways

Most interview problems are instances of a small set of patterns, each with a recognizable tell.
Core patterns: two pointers, sliding window, prefix sums, binary search, BFS/DFS, hashing, heap/top-k, DP, backtracking.
The key skill is pattern recognition - map the problem's wording to a technique, don't memorize solutions.
Patterns often combine (window + hash map, DFS + memoization).
When stuck, brute force and let the repeated work name the pattern (re-scanning→window, re-searching sorted→binary search, recomputed subproblems→DP).

War diese Lektion hilfreich?

Diese Seite auf GitHub bearbeiten