Diese Lektion wurde automatisch ins Deutsche übersetzt und noch nicht von einem Menschen geprüft. Falls etwas seltsam klingt, gilt die englische Fassung.
Hier ist ein Geheimnis, für dessen Erlernen Top-Interview-Coaches keine 500 US-Dollar verlangen: Ungefähr 90 % der Codierungsprobleme bei Interviews drehen sich um nur sieben Datenstrukturen. Wenn Sie genau verstehen, wann und warum Sie nach jedem einzelnen greifen müssen, haben Sie bereits die halbe Miete gewonnen. Die andere Hälfte ist Übung - aber ohne die richtigen mentalen Modelle ist Übung nur Auswendiglernen. In dieser Lektion erhalten Sie eine Übersicht, sodass sich jedes Problem, auf das Sie stoßen, wie vertrautes Terrain anfühlt.
Jedes technische Interview schöpft aus derselben Quelle. Hier sind die Strukturen, denen Sie begegnen werden, sortiert nach Häufigkeit:
| Datenstruktur | Interviewhäufigkeit | Kernbetrieb | Wenn Interviewer es erwarten | |---|---|---|---| | Arrays / Strings | ★★★★★ | Auf O(1) zugreifen, O(n) durchsuchen, O(n) einfügen | Fast jedes Problem beginnt hier | | Hash-Maps/Sets | ★★★★★ | O(1) einfügen, O(1) suchen, O(1) löschen | „Optimieren Sie dies von O(n²) auf O(n)“ | | Verknüpfte Listen | ★★★★☆ | O(1) einfügen, O(1) löschen, auf O(n) zugreifen | Zeigermanipulation, Zykluserkennung | | Stapel und Warteschlangen | ★★★★☆ | Push/Pop O(1), Enqueue/Dequeue O(1) | Parsen, BFS, Rückgängigmachen von Vorgängen | | Bäume (Binär, BST) | ★★★★☆ | O(log n) suchen, O(log n) einfügen | Hierarchische Daten, sortierte Operationen | | Grafiken | ★★★☆☆ | Hängt von der Darstellung ab | Beziehungen, Wege, Konnektivität | | Haufen | ★★★☆☆ | O(log n) einfügen, min O(log n) extrahieren | „Finde die k größten/kleinsten“ |
Arrays sind der Ausgangspunkt für fast jedes Interviewproblem. Die wichtigste Erkenntnis ist, dass es bei den meisten Array-Problemen nicht wirklich um Arrays geht, sondern um das Erkennen von Mustern wie zwei Zeigern, Schiebefenstern oder Präfixsummen.
# Two Sum - the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) - trading space for time
Beachten Sie, dass selbst dieses „Array“-Problem in Wirklichkeit ein Hash-Map-Problem ist. Dieses Muster wiederholt sich ständig: Die Brute-Force-Methode verwendet verschachtelte Schleifen über ein Array, und die optimale Lösung führt eine Hash-Map ein.
Anmelden um an der Diskussion teilzunehmen
Wenn Sie bei einem Problem nicht weiterkommen und die rohe Gewalt O(n²) ist, fragen Sie sich: „Kann eine Hash-Map dies auf O(n) reduzieren?“ Die Antwort lautet überraschend oft „Ja“.
Hash-Maps glänzen, wenn Sie Folgendes benötigen:
// Group Anagrams - a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
Probleme mit verknüpften Listen testen Ihre Fähigkeit, Zeiger zu manipulieren, ohne den Überblick über Knoten zu verlieren. Die drei Techniken, die Sie benötigen, sind:
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Stapel (LIFO) und Warteschlangen (FIFO) sind einfachere Strukturen, aber sie erschließen ganze Problemkategorien:
# Valid Parentheses - classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
Baumprobleme beinhalten typischerweise Rekursion und eine von drei Durchlaufreihenfolgen (in-order, pre-order, post-order). Das zu entwickelnde mentale Modell lautet: „Was benötige ich vom linken Teilbaum, vom rechten Teilbaum und wie kombiniere ich sie am aktuellen Knoten?“
# Maximum depth of a binary tree - the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
BST-Probleme (Binary Search Tree) fügen eine entscheidende Eigenschaft hinzu: Das Durchlaufen in der richtigen Reihenfolge liefert sortierte Elemente. Wenn Sie „sortiert“ und „Baum“ im selben Problem sehen, denken Sie sofort an BST.
Diagrammprobleme wirken einschüchternd, aber die meisten lassen sich auf BFS oder DFS reduzieren, sobald Sie die Adjazenzliste erstellt haben. Die Schlüsselkompetenzen sind:
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
Wann immer ein Problem lautet: „Finde die K größten“, „K nächsten“ oder „K sortierte Listen zusammenführen“, ist ein Heap (Prioritätswarteschlange) mit ziemlicher Sicherheit die Antwort. In Python stellt heapq einen Min-Heap bereit; Negieren Sie für einen Max-Heap die Werte.
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
Sie müssen den Median eines Zahlenstroms in O(log n) pro Einfügung ermitteln. Welche Datenstrukturkombination ist am besten geeignet?
| Struktur | Zugriff | Suchen | Einfügen | Löschen | Raum | |---|---|---|---|---|---| | Array | O(1) | O(n) | O(n) | O(n) | O(n) | | Hash-Karte | - | O(1)* | O(1)* | O(1)* | O(n) | | Verlinkte Liste | O(n) | O(n) | O(1) | O(1) | O(n) | | Stapel/Warteschlange | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (ausgeglichen) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | Haufen | - | O(n) | O(log n) | O(log n) | O(n) |
* Durchschnittlicher Fall; Der schlimmste Fall ist O(n) aufgrund von Hash-Kollisionen.
Entwickeln Sie diese mentale Checkliste, wenn Sie ein Problem lesen: