Die Vorbereitung auf Coding-Interviews kann eine echte Herausforderung sein, da Entwickler oft mehrere Wochen damit verbringen, neues Material zu überprüfen und zu lernen.
Die Wahrheit ist, dass sich die meisten Entwickler nie ganz auf ihre Programmiergespräche vorbereitet fühlen. Es ist nicht ungewöhnlich, dass Entwickler wochenlang Probleme mit LeetCode lösen und sich dennoch unvorbereitet fühlen. Offensichtlich gibt es bei diesem Ansatz Probleme.
Werfen wir einen genaueren Blick auf einige Probleme, die mit der herkömmlichen Vorbereitung von Codierungsinterviews verbunden sind.
Eine der häufigsten Fallstricke bei der herkömmlichen Vorbereitung auf Vorstellungsgespräche ist das „Grinding“. Bei diesem Ansatz geht es darum, möglichst viele LeetCode- Probleme ohne einen klaren Plan oder eine klare Strategie zu lösen. Obwohl dies wie eine produktive Strategie erscheint, hat sie mehrere Nachteile.
Wenn Sie Probleme ohne strukturierten Ansatz lösen, erkennen Sie möglicherweise Ihre Schwächen nicht. Es gibt keinen bewussten Plan für Ihr Studium; Das Ziel besteht einfach darin, so viele Probleme wie möglich zu lösen. Dadurch haben Sie möglicherweise das Gefühl, viel gelernt zu haben, es könnten jedoch erhebliche Wissenslücken bestehen.
Darüber hinaus besteht das Problem darin, dass es im Wesentlichen darum geht, Lösungen für eine Vielzahl von Problemen auswendig zu lernen. Der Versuch, sich Lösungen für hundert verschiedene Codierungsprobleme zu merken, erweist sich als wirkungslos, wenn Interviewer Fragen stellen, die auch nur geringfügig von denen abweichen, denen Sie zuvor begegnet sind. Dies kann dazu führen, dass Sie das Gefühl haben, nicht auf die Bewältigung von Problemvarianten vorbereitet zu sein.
Mein letztes Problem mit dieser Strategie ist, dass sie auf lange Sicht mehr Stress und Kopfschmerzen verursacht. Wenn Sie jedes Mal, wenn Sie den Job wechseln möchten, die gleiche mehrwöchige Pauksitzung absolvieren müssen, werden Sie jedes Mal Schwierigkeiten haben. Sie werden Wochen damit verbringen, Dinge neu zu lernen und die gleichen Probleme wie zuvor zu lösen.
Angesichts dieser Herausforderungen muss es einen besseren Weg geben.
Gibt es also einen effektiveren und nachhaltigeren Ansatz zur Codierung der Interviewvorbereitung? Die Antwort liegt im Verstehen und Nutzen von Codierungsmustern.
Wenn ich mich auf Codierungsinterviews vorbereite, lege ich Wert darauf, die zugrunde liegenden Problemmuster zu erfassen. Diese Muster, zu denen Techniken wie Two-Pointers , Sliding Window , Modified Binary Search , Topological Sort und viele mehr gehören, bieten einen vielseitigen und leistungsstarken Rahmen für die Bewältigung einer Vielzahl von Codierungsproblemen. Der Schwerpunkt verlagert sich vom Auswendiglernen von Lösungen hin zu bewährten Problemlösungstechniken.
Indem Sie sich auf Codierungsmuster konzentrieren, können Sie Ihre Vorbereitung auf Vorstellungsgespräche deutlich rationalisieren und effizienter machen.
Denken Sie daran: Bereiten Sie sich intelligenter vor, nicht härter.
In diesem Artikel habe ich das zusammengestellt
Obwohl ich in diesem Artikel viel behandele, können Sie sich unseren umfassenden Vorbereitungskurs für Coding-Interviews auf Techinterviews.io ansehen, wenn Sie tiefergehende Schulungen, Erklärungen und Programmierübungen wünschen. Wir behandeln auch wichtige Themen wie Datenstrukturen , Verhaltensinterviews und sogar Gehaltsverhandlungen .
Lassen Sie uns nun in diese Codierungsmuster eintauchen.
Bei der Umkehrung verknüpfter Listen wird die Richtung von Zeigern in einer verknüpften Liste geändert, um die Reihenfolge der Elemente umzukehren. Es handelt sich um eine grundlegende Operation in Datenstrukturen, die häufig eine sorgfältige Manipulation der Knotenreferenzen erfordert.
Dies ist nützlich, wenn es sich um eine verknüpfte Liste handelt und die Einschränkung darin besteht, sie an Ort und Stelle umzukehren.
Der Prozess zum Umkehren einer verknüpften Liste an Ort und Stelle ist wie folgt:
Beginnen Sie mit der Definition von drei Variablen: current , previous und next . Legen Sie current als Kopf der verknüpften Liste fest und initialisieren Sie previous und next als None.
Während die aktuelle Variable nicht None ist, gehen Sie wie folgt vor:
Setzen Sie abschließend den Kopf der umgekehrten Liste auf den zuletzt erreichten Knoten, der in der vorherigen Variablen gespeichert ist.
Schlüsselindikatoren:
Vorlagencode:
Python
def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev
JS
function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }
Java
public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }
Die modifizierte binäre Suche passt den klassischen binären Suchalgorithmus an, um verschiedene Probleme zu lösen. Zu den Variationen gehören die Suche nach dem ersten/letzten Vorkommen eines Elements oder die Suche in gedrehten Arrays. Es erfordert einen sorgfältigen Umgang mit Mittelpunkten und Bedingungen.
Wenn Sie jemals ein sortiertes Array, eine verknüpfte Liste oder eine Matrix erhalten, sollten Sie die Verwendung einer modifizierten binären Suche in Betracht ziehen.
Hier ist eine Aufschlüsselung, wie dieses Muster auf eine sortierte Datenstruktur angewendet wird:
middle = start + (end - start) / 2
.
Schlüsselindikatoren:
Vorlagencode:
Python
def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index
JS
function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }
Java
public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }
Die Zwei-Zeiger-Technik beinhaltet die Verwaltung von zwei Zeigern, die eine Datenstruktur durchlaufen, typischerweise Arrays oder verknüpfte Listen, die häufig für Probleme mit Paaren oder Unterarrays verwendet werden. Es optimiert Probleme, die einen Vergleich zwischen Elementen an verschiedenen Positionen erfordern.
Der Vorteil dieser Technik liegt in ihrer Einfachheit und Effizienz, insbesondere beim Umgang mit linearen Datenstrukturen wie Arrays oder Strings, bei denen Sie zunächst möglicherweise nur einen Zeiger verwenden. Durch die Verwendung von zwei Zeigern können Sie redundante Vorgänge umgehen und die Laufzeiteffizienz erheblich steigern, indem Sie sie möglicherweise von O(n^2) auf O(n) reduzieren.
Das „Two Pointers“ -Muster umfasst mehrere Variationen, die jeweils auf bestimmte Szenarien zugeschnitten sind. Zu diesen Variationen gehören die gleiche Richtung , die entgegengesetzte Richtung und eine einzigartige Methode, die als „schnell und langsam“ bekannt ist und oft als „Schildkröten-und-Hase“ -Technik bezeichnet wird, bei der sich zwei Zeiger mit unterschiedlichen Geschwindigkeiten durch eine Datenstruktur bewegen, was besonders für die Erkennung nützlich ist Fahrräder.
Wenn Sie zum Durchlaufen einer Datenstruktur mehrere Zeiger verwenden, können Sie Ihren Ansatz nach dem Muster „Zwei Zeiger“ kategorisieren.
Schlüsselindikatoren:
Vorlagencode:
Vorlage für die Variante „entgegengesetzte Richtung“.
Python
def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans
JS
function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }
Java
public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }
Bei der Sliding-Window-Technik wird ein dynamisches Fenster über einer linearen Datenstruktur wie Arrays, Strings oder verknüpften Listen verwaltet. Die Größe des Fensters kann je nach Implementierung variieren und kann auch als fester Wert festgelegt werden. Das Hauptziel dieses Fensters ist die kontinuierliche Überwachung und Erfassung von Daten, die bestimmte Kriterien erfüllen, was es besonders wertvoll für die effiziente Lösung von Subarray- oder Substring-Problemen macht.
Dieses Muster verwendet häufig eine Hash-Map, um die Verfolgung einzelner Daten innerhalb des Fensters zu erleichtern. Es ist jedoch wichtig zu beachten, dass dieser Ansatz zu einer Raum-Zeit-Komplexität von O(n) führen kann.
Schlüsselindikatoren:
Vorlagencode:
Python
def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans
JS
function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }
Java
public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }
Bei diesem Muster geht es darum, die K größten oder kleinsten Elemente in einer Sammlung zu finden, was häufig mithilfe von Datenstrukturen wie Heaps oder Prioritätswarteschlangen implementiert wird. Dies ist nützlich, um eine Teilmenge von Elementen basierend auf ihrem Wert oder ihrer Häufigkeit auszuwählen.
Immer wenn wir aufgefordert werden, die häufigsten, kleinsten oder obersten „K“-Elemente in einem bestimmten Datensatz zu finden, können wir die Verwendung dieses Musters in Betracht ziehen.
Die Funktionsweise ist einfach:
Das Schöne an diesem Ansatz liegt in seiner Effizienz; Sie müssen nicht auf Sortieralgorithmen zurückgreifen, da der Heap selbst natürlich die erforderliche Reihenfolge für Sie aufrechterhält.
Schlüsselindikatoren:
Vorlagencode:
Python
import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]
JS
function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }
Java
import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }
Zwei Heaps nutzen zwei Heaps (einen Max-Heap und einen Min-Heap), um bestimmte Probleme zu optimieren, beispielsweise das Finden von Medianwerten in einem Datensatz. Dieses Muster ist besonders nützlich, um eine ausgewogene Struktur aufrechtzuerhalten.
So funktioniert das:
Schlüsselindikatoren:
Vorlagencode:
Python
import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)
JS
class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);
Java
import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);
Monoton – (einer Funktion oder Größe), die so variiert, dass sie entweder nie abnimmt oder nie zunimmt.
Der monotone Stapel verwaltet einen Stapel von Elementen in nicht aufsteigender oder nicht absteigender Reihenfolge und wird häufig zum Auffinden der nächsten kleineren/größeren Elemente in einem Array verwendet. Es ist ein leistungsstarkes Tool zur Optimierung bestimmter Probleme.
Die Reihenfolge ist streng: Immer wenn wir auf ein Element stoßen, das kleiner (oder größer) ist als das, was sich oben im Stapel befindet, müssen wir aus dem monotonen Stapel herausspringen, bis das Element, das wir hinzufügen möchten, das kleinste (oder größte) Element ist ihnen.
Schlüsselindikatoren:
Vorlagencode:
Python
def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)
JS
function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }
Java
import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }
DFS oder Depth-First Search ist eine Traversal-Methode, bei der Sie einen Zweig so tief wie möglich erkunden, bevor Sie ihn zurückverfolgen. Es wird häufig bei Problemen mit Bäumen und Graphen eingesetzt, insbesondere bei Traversierungs- und Suchoperationen.
Um DFS für einen Baum auszuführen, müssen Sie im Stammverzeichnis beginnen. Befolgen Sie dann die folgenden Schritte:
Unterschied zu DFS in einem Diagramm: Der Hauptunterschied zwischen Baum-DFS und Diagramm-DFS liegt im Vorhandensein von Zyklen. In einem Baum gibt es per Definition keine Zyklen, daher stellt das Baum-DFS sicher, dass jeder Knoten genau einmal besucht wird, und endet auf natürliche Weise, wenn der gesamte Baum durchlaufen wird. Im Gegensatz dazu muss Graph-DFS zusätzliche Maßnahmen zur Handhabung zyklischer Strukturen innerhalb eines Graphen integrieren. Um zu vermeiden, dass Knoten in einem Zyklus auf unbestimmte Zeit erneut besucht werden, erfordert Graph DFS Mechanismen wie das Markieren besuchter Knoten und die entsprechende Handhabung des Backtrackings . Diese Unterscheidung macht Graph-DFS komplexer als Baum-DFS, da bei Vorhandensein von Zyklen die Möglichkeit von Endlosschleifen besteht.
Schlüsselindikatoren:
Vorlagencode:
Python
def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree
JS
function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }
Java
public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }
BFS ist eine Traversierungstechnik für Bäume und Diagramme, die alle Knoten in der aktuellen Tiefe untersucht, bevor sie zur nächsten Ebene übergeht.
Um BFS für einen Baum durchzuführen, müssen Sie im Stammverzeichnis beginnen. Befolgen Sie dann die folgenden Schritte:
Initialisieren Sie eine leere Warteschlangendatenstruktur, um den Überblick über die zu besuchenden Knoten zu behalten.
Stellen Sie den Root-Knoten in die Warteschlange.
Geben Sie eine Schleife ein, bis die Warteschlange leer ist:
Wiederholen Sie die Schritte 3a–3c , bis die Warteschlange leer ist.
Der BFS-Durchlauf ist abgeschlossen, wenn alle Knoten im Baum stufenweise von links nach rechts besucht wurden.
Im Wesentlichen untersucht BFS in einem Baum Knoten Ebene für Ebene , beginnend bei der Wurzel und zu den untergeordneten Knoten, bevor zur nächsten Ebene übergegangen wird. Dadurch wird sichergestellt, dass Knoten auf jeder Ebene besucht werden, bevor zur nächsten Ebene gewechselt wird. Dies macht es besonders nützlich für Aufgaben wie das Finden des kürzesten Pfads in einem ungewichteten Baum oder das Erkunden eines Baums Ebene für Ebene.
Unterschied zu BFS in einem Diagramm: Ähnlich wie DFS passt sich Diagramm-BFS an das Vorhandensein von Zyklen und mehreren Pfaden zwischen Knoten an. Es nutzt Mechanismen wie die Markierung besuchter Knoten und spezielle Beendigungsbedingungen, um effizient durch das komplexe Beziehungsnetzwerk innerhalb von Diagrammen zu navigieren.
Schlüsselindikatoren:
Vorlagencode:
Python
from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND
JS
function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }
Java
import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }
Die Union-Find- Datenstruktur, auch bekannt als Disjoint Set Union (DSU) , wird verwendet, um Probleme mit disjunkten Mengen oder verbundenen Komponenten effizient zu verwalten und zu lösen. Es bietet Operationen zum Zusammenführen von Mengen (Vereinigung) und zum Bestimmen der Menge, zu der ein Element gehört (Suchen). Union-Find wird häufig in Algorithmen wie Kruskals Minimum Spanning Tree und der Zykluserkennung in Diagrammen verwendet.
Union Find wird wie folgt implementiert:
Vorlagencode:
Python
class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)
JS
class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }
Java
import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }
Ein gerichteter azyklischer Graph (DAG) ist ein gerichteter Graph ohne gerichtete Zyklen.
Topologische Sortierung ist ein Algorithmus zum Anordnen der Knoten eines gerichteten azyklischen Graphen ( DAG ) in einer linearen Reihenfolge, wobei jeder Knoten vor seinen Nachfolgern erscheint. Es ist von entscheidender Bedeutung für Aufgaben wie das Planen von Abhängigkeiten, das Kompilieren von Code und das Analysieren der Priorität von Aufgaben in verschiedenen Anwendungen.
Hier ist eine schrittweise Aufschlüsselung der topologischen Sortierung:
Initialisierung: Beginnen Sie mit einem gerichteten azyklischen Graphen ( DAG ), der Aufgaben oder Knoten mit Abhängigkeiten darstellt. Initialisieren Sie eine Warteschlange, um die sortierten Knoten aufzunehmen.
In-Grad-Berechnung: Berechnen Sie den In-Grad (die Anzahl der eingehenden Kanten) für jeden Knoten im Diagramm. Knoten mit einem In-Grad von 0 haben keine Abhängigkeiten und eignen sich als Ausgangspunkt der topologischen Sortierung.
Anfängliches Füllen der Warteschlange: Alle Knoten mit einem In-Grad von 0 werden in die Warteschlange gestellt. Diese Knoten können zuerst bearbeitet werden.
Topologische Sortierschleife: Führen Sie die folgenden Schritte aus, während die Warteschlange nicht leer ist:
Abschluss: Sobald die topologische Sortierschleife abgeschlossen ist, ist die Warteschlange leer und die sortierte Liste enthält alle Knoten in einer gültigen topologischen Reihenfolge.
Zykluserkennung: Wenn zu irgendeinem Zeitpunkt während des topologischen Sortiervorgangs keine Knoten mit einem In-Grad von 0 in der Warteschlange mehr vorhanden sind, weist dies auf das Vorhandensein von Zyklen im Diagramm hin, wodurch eine topologische Sortierung unmöglich wird.
Das Ergebnis der topologischen Sortierung ist eine lineare Reihenfolge der Knoten, die ihre Abhängigkeiten berücksichtigt, wodurch sie sich für die Planung von Aufgaben oder die Analyse der Ausführungsreihenfolge in verschiedenen Anwendungen eignet.
Schlüsselindikatoren:
Vorlagencode:
Python
from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None
JS
/** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }
Java
import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }
Ein Trie ist eine baumartige Datenstruktur, die für den effizienten String-Abgleich und die Speicherung von Wörtern verwendet wird. Es eignet sich hervorragend für Probleme, bei denen Sie Zeichenfolgen mit gemeinsamen Präfixen speichern und suchen müssen.
So implementieren Sie einen Trie:
Initialisierung: Beginnen Sie mit einem leeren Trie, der normalerweise aus einem Wurzelknoten ohne zugehöriges Zeichen besteht.
Einfügen: Um ein Wort in den Trie einzufügen, beginnen Sie am Wurzelknoten und durchlaufen Sie den Baum zeichenweise nach unten. Für jedes Zeichen im Wort:
Wortvervollständigung: Um zu überprüfen, ob ein Wort im Trie vorhanden ist, durchlaufen Sie es auf ähnliche Weise wie beim Einfügen. Stellen Sie sicher, dass jedes Zeichen im Wort einem untergeordneten Knoten des aktuellen Knotens entspricht. Wenn der Durchlauf das Ende des Wortes erreicht und am letzten Zeichenknoten eine gültige Endmarkierung (z. B. ein boolesches Flag) vorhanden ist, existiert das Wort im Trie.
Präfixsuche: Trie zeichnet sich durch die Präfixsuche aus. Um alle Wörter mit einem bestimmten Präfix zu finden, beginnen Sie die Durchquerung am Wurzelknoten und bewegen Sie sich entlang der Baumstruktur nach unten, indem Sie den Zeichen des Präfixes folgen. Sobald Sie das letzte Zeichen des Präfixes erreicht haben, können Sie von diesem Knoten aus eine Tiefensuche (DFS) durchführen, um alle Wörter zu finden, die dasselbe Präfix haben.
Löschen: Um ein Wort aus dem Trie zu löschen, führen Sie eine Suche nach dem Wort durch. Wenn Sie das Ende des Wortes erreicht haben, entfernen Sie die Endmarkierung (falls vorhanden). Wenn der Knoten keine anderen untergeordneten Knoten hat, können Sie den gesamten Zweig des Trie, der das Wort darstellt, sicher entfernen.
Versuche können speicherintensiv sein, insbesondere bei großen Vokabularien. Um den Speicher zu optimieren, können Techniken wie Komprimierung (z. B. Verwendung einer Karte anstelle eines Zeichenarrays in jedem Knoten) und Bereinigung (Entfernen von Knoten ohne Nachkommen) angewendet werden.
Versuche sind besonders nützlich für den effizienten String-Abgleich, Vorschläge zur automatischen Vervollständigung, Rechtschreibprüfung und die Indizierung von Wörtern mit gemeinsamen Präfixen. Sie bieten eine schnelle und platzsparende Möglichkeit, Wörter oder Zeichenfolgen mit gemeinsamen Präfixen in einer baumartigen Struktur zu speichern und zu suchen.
Schlüsselindikatoren:
Vorlagencode:
Python
class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)
JS
class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }
Java
import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }
Dynamische Programmierung ist eine leistungsstarke Problemlösungstechnik, die in der Informatik und Mathematik zur effizienten Lösung einer Vielzahl komplexer Probleme eingesetzt wird. Besonders wertvoll ist es, wenn ein Problem in einfachere Teilprobleme zerlegt werden kann und die Lösungen dieser Teilprobleme zur Lösung des Gesamtproblems kombiniert werden können.
Hier sind seine Hauptmerkmale und seine Funktionsweise:
Optimaler Unterbau:
Überlappende Teilprobleme:
So funktioniert dynamische Programmierung:
Dynamische Programmierung wird auf eine Vielzahl von Problemen angewendet, darunter das Finden der kürzesten Pfade in Diagrammen, das Optimieren der Ressourcenzuweisung, das Zählen von Kombinationen, das Lösen von Rucksackproblemen und vieles mehr. Seine Fähigkeit, Lösungen zu optimieren, indem komplexe Probleme in einfachere Teile zerlegt und redundante Berechnungen vermieden werden, macht es zu einer grundlegenden Technik beim Entwurf und der Optimierung von Algorithmen.
Wichtige Konzepte: Bottoms-Up-Ansatz, Top-Down, Auswendiglernen, Tabellierung
Schlüsselindikatoren:
Vorlagencode:
Eine Vorlage für die Top-Down-Memoisierung ist eine von vielen Möglichkeiten, dynamische Programmierung zu implementieren.
Python
def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)
JS
function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }
Java
import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }
Backtracking ist eine allgemeine algorithmische Technik zur schrittweisen Lösung von Problemen, indem verschiedene Möglichkeiten ausprobiert und rückgängig gemacht werden, wenn sie nicht zu einer Lösung führen. Es wird verwendet, wenn eine umfassende Suche erforderlich ist.
Hier finden Sie einen detaillierten Einblick in die Funktionsweise von Backtracking:
Anwendungen von Backtracking:
Backtracking wird in verschiedenen Problembereichen eingesetzt, darunter:
Schlüsselindikatoren:
Vorlagencode:
Python
def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans
JS
function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }
Java
public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }
Beim Zusammenführen von Intervallen werden überlappende oder benachbarte Intervalle zu einem konsolidierten Satz zusammengefasst. Dies wird häufig bei Problemen mit Zeitintervallen oder der Planung verwendet. Es vereinfacht intervallbasierte Vorgänge.
Hier sehen Sie genauer, wie das Zusammenführen von Intervallen funktioniert:
Anwendungen von Zusammenführungsintervallen:
Zusammenführungsintervalle werden häufig verwendet in:
Durch die Zusammenführung überlappender Intervalle vereinfacht diese Technik intervallbasierte Vorgänge und steigert die Effizienz in verschiedenen Anwendungen.
Schlüsselindikatoren:
Vorlagencode:
Python
def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals
JS
function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }
Java
public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }
Wenn Sie mehr über diese Muster erfahren möchten und erfahren möchten, wie Sie sie bei Ihrem nächsten Coding-Interview effektiver umsetzen können, dann schauen Sie sich noch heute techinterviews.io an! Wir bieten einen umfassenden Lehrplan, um Sie auf Ihr nächstes Programmiergespräch vorzubereiten und Themen wie Datenstrukturen , Algorithmen , Verhaltensinterviews und sogar Gehaltsverhandlungen abzudecken. Wir haben sogar einen integrierten Codierungsarbeitsbereich, in dem Sie üben können.
Verbessern Sie Ihre Vorbereitung auf Programmiergespräche noch heute mit unserem Aktionscode TECH30 für 30 $ Rabatt!
Ausgewähltes Bild „Ein Entwickler schreibt Code“ von @Limarc
Grafiken erstellt mit Okso.app