Deze les is automatisch vertaald naar het Nederlands en is nog niet door een mens nagekeken. Klinkt iets vreemd, dan is de Engelse versie leidend.
Hier is een geheim dat topinterviewcoaches je geen $ 500 vragen om te leren: ruwweg 90% van de codeerinterviewproblemen draait om slechts zeven datastructuren. Als je goed begrijpt wanneer en waarom je ze allemaal moet bereiken, heb je de helft van de strijd al gewonnen. De andere helft is oefenen – maar zonder de juiste mentale modellen is oefenen slechts memoriseren. Deze les geeft je de kaart, zodat elk probleem dat je tegenkomt als bekend terrein aanvoelt.
Elk technisch interview put uit dezelfde bron. Hier zijn de structuren die je tegenkomt, gerangschikt op frequentie:
| Gegevensstructuur | Interviewfrequentie | Kernactiviteiten | Wanneer interviewers het verwachten | |---|---|---|---| | Matrices/tekenreeksen | ★★★★★ | Toegang tot O(1), zoeken naar O(n), invoegen van O(n) | Bijna elk probleem begint hier | | Hash-kaarten / sets | ★★★★★ | O(1) invoegen, O(1) opzoeken, O(1) verwijderen | "Optimaliseer dit van O(n²) naar O(n)" | | Gekoppelde lijsten | ★★★★☆ | O(1) invoegen, O(1) verwijderen, O(n) openen | Aanwijzermanipulatie, cyclusdetectie | | Stapels en wachtrijen | ★★★★☆ | Push/Pop O(1), Enqueue/Dequeue O(1) | Parseren, BFS, bewerkingen ongedaan maken | | Bomen (binair, BST) | ★★★★☆ | Zoek O(log n), voeg O(log n) in | Hiërarchische gegevens, gesorteerde bewerkingen | | Grafiek | ★★★☆☆ | Afhankelijk van vertegenwoordiging | Relaties, paden, connectiviteit | | Hopen | ★★★☆☆ | Voeg O(log n) in, extraheer-min O(log n) | "Vind de k grootste/kleinste" |
Arrays vormen het startpunt voor bijna elk interviewprobleem. Het belangrijkste inzicht is dat de meeste array-problemen niet echt over arrays gaan, maar over het herkennen van patronen zoals twee pointers, een schuifvenster of prefix-sommen.
# 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
Merk op dat zelfs dit "array"-probleem in werkelijkheid een hashmap-probleem is. Dat patroon herhaalt zich voortdurend: de brute kracht maakt gebruik van geneste lussen over een array, en de optimale oplossing introduceert een hash-map.
Meld je aan om deel te nemen aan de discussie
Als je met een probleem vastzit en de brute kracht O(n²) is, vraag jezelf dan af: "Kan een hashmap dit terugbrengen tot O(n)?" Het antwoord is verrassend vaak ja.
Hash-kaarten schitteren wanneer u:
// 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());
}
Problemen met gekoppelde lijsten testen uw vermogen om wijzers te manipuleren zonder knooppunten uit het oog te verliezen. De drie technieken die je nodig hebt zijn:
# 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
Stapels (LIFO) en wachtrijen (FIFO) zijn eenvoudiger structuren, maar ze ontsluiten hele categorieën problemen:
# 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
Bij boomproblemen gaat het doorgaans om recursie en een van de drie traversal-orders (in-order, pre-order, post-order). Het mentale model dat moet worden ontwikkeld is: "Wat heb ik nodig van de linker subboom, de rechter subboom, en hoe combineer ik ze op het huidige knooppunt?"
# 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-problemen (Binary Search Tree) voegen één cruciale eigenschap toe: het in volgorde doorlopen levert gesorteerde elementen op. Als u in hetzelfde probleem "gesorteerd" en "boom" ziet, denk dan onmiddellijk aan BST.
Grafiekproblemen voelen intimiderend aan, maar de meeste reduceren zich tot BFS of DFS zodra je de lijst met aangrenzende gebieden hebt samengesteld. De belangrijkste vaardigheden zijn:
# 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
Wanneer een probleem zegt: "vind de K grootste", "K dichtstbijzijnde", of "voeg K gesorteerde lijsten samen", is een heap (prioriteitwachtrij) vrijwel zeker het antwoord. In Python biedt heapq een min-heap; voor een max-heap negeert u de waarden.
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
Je moet de mediaan van een stroom getallen in O(log n) per invoeging vinden. Welke datastructuurcombinatie is het meest geschikt?
| Structuur | Toegang | Zoeken | Invoegen | Verwijder | Ruimte | |---|---|---|---|---|--| | Array | O(1) | O(n) | O(n) | O(n) | O(n) | | Hash-kaart | — | O(1)* | O(1)* | O(1)* | O(n) | | Gekoppelde lijst | O(n) | O(n) | O(1) | O(1) | O(n) | | Stapel/wachtrij | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (evenwichtig) | O(logboek n) | O(logboek n) | O(logboek n) | O(logboek n) | O(n) | | Hoop | — | O(n) | O(logboek n) | O(logboek n) | O(n) |
* Gemiddeld geval; in het slechtste geval is O(n) als gevolg van hash-botsingen.
Ontwikkel deze mentale checklist bij het lezen van een probleem: