Подготовка к собеседованиям по программированию может стать настоящей проблемой, поскольку разработчики часто тратят несколько недель на просмотр и изучение нового материала.
Правда в том, что большинство разработчиков никогда не чувствуют себя полностью готовыми к собеседованиям по программированию. Разработчики нередко тратят недели на решение проблем в LeetCode и при этом чувствуют себя неподготовленными. Очевидно, что с этим подходом есть проблемы.
Давайте подробнее рассмотрим некоторые проблемы, связанные с традиционной подготовкой к собеседованию по программированию.
Одной из наиболее распространенных ошибок при традиционной подготовке к собеседованию является практика «притирки». Этот подход предполагает решение как можно большего количества проблем LeetCode без четкого плана или стратегии. Хотя это может показаться продуктивной стратегией, у нее есть несколько недостатков.
Когда вы решаете проблемы без структурированного подхода, вы можете не распознать свои слабости. У вашего обучения нет продуманного плана; цель состоит в том, чтобы просто решить как можно больше проблем. В результате у вас может возникнуть ощущение, что вы многому научились, но в ваших знаниях могут быть значительные пробелы.
Более того, проблема в том, что по сути это вращается вокруг запоминания решений множества проблем. Попытка запомнить решения сотни различных задач по кодированию оказывается неэффективной, когда интервьюеры задают вопросы, которые хоть немного отличаются от тех, с которыми вы сталкивались раньше. Это может привести к тому, что вы почувствуете себя неподготовленным к решению проблемных вариантов.
Моя последняя проблема с этой стратегией заключается в том, что в долгосрочной перспективе она создает еще больше стресса и головных болей. Если вам приходится проходить одну и ту же зубрежку продолжительностью в несколько недель каждый раз, когда вы хотите сменить работу, вам каждый раз придется бороться. Вы потратите недели на то, чтобы заново учиться и решать те же проблемы, что и раньше.
Учитывая эти проблемы, должен быть лучший путь.
Итак, существует ли более эффективный и устойчивый подход к подготовке к собеседованию по кодированию? Ответ заключается в понимании и использовании шаблонов кодирования.
Когда я готовлюсь к собеседованиям по программированию, я уделяю первоочередное внимание выявлению основных закономерностей проблем. Эти шаблоны, включающие в себя такие методы, как «Два указателя », «Скользящее окно» , «Модифицированный двоичный поиск », «Топологическая сортировка » и многие другие, обеспечивают универсальную и мощную основу для решения широкого спектра проблем кодирования. Акцент смещается с запоминания решений на проверенные методы решения проблем.
Сосредоточив внимание на шаблонах кодирования, вы можете значительно упростить подготовку к собеседованию, сделав ее более эффективной.
Помните, готовьтесь умнее, а не усерднее.
В этой статье я собрал
Хотя я многое рассказываю в этой статье, если вам нужно более углубленное обучение, объяснения и практика кодирования, вы можете посетить наш Комплексный курс подготовки к собеседованию по программированию на Techinterviews.io. Мы также освещаем такие важные темы, как структуры данных , поведенческие интервью и даже переговоры о зарплате .
Теперь давайте углубимся в эти шаблоны кодирования.
Обращение связанного списка предполагает изменение направления указателей в связанном списке для изменения порядка элементов. Это фундаментальная операция в структурах данных, которая часто требует тщательного манипулирования ссылками на узлы.
Это полезно при работе со связанным списком, и ограничение состоит в том, чтобы перевернуть его на месте.
Процесс отмены связанного списка на месте выглядит следующим образом:
Начните с определения трех переменных: current , previous и next . Установите текущий в качестве главы связанного списка и инициализируйте предыдущий и следующий как None.
Пока текущая переменная не None , действуйте следующим образом:
Наконец, установите заголовок перевернутого списка на последний достигнутый узел, который хранится в предыдущей переменной.
Ключевые показатели:
Код шаблона:
Питон
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; }
Джава
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; }
Модифицированный двоичный поиск адаптирует классический алгоритм двоичного поиска для решения различных задач. Варианты включают поиск первого/последнего вхождения элемента или поиск во вращающихся массивах. Это требует тщательного обращения со средними точками и условиями.
Если вам когда-либо предоставлялся отсортированный массив, связанный список или матрица, рассмотрите возможность использования модифицированного двоичного поиска .
Вот описание того, как применить этот шаблон к отсортированной структуре данных:
middle = start + (end - start) / 2
.
Ключевые показатели:
Код шаблона:
Питон
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; }
Джава
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; }
Метод двух указателей предполагает поддержку двух указателей, которые пересекают структуру данных, обычно массивы или связанные списки, часто используемые для решения задач, связанных с парами или подмассивами. Он оптимизируется для задач, требующих сравнения элементов в разных позициях.
Преимущество этого метода заключается в его простоте и эффективности, особенно при работе с линейными структурами данных, такими как массивы или строки, где изначально можно использовать только один указатель. Используя два указателя, вы можете обойти избыточные операции и значительно повысить эффективность выполнения, потенциально снижая ее с O(n^2) до O(n) .
Шаблон «Два указателя» включает в себя несколько вариантов, каждый из которых адаптирован к конкретным сценариям. Эти варианты включают в себя одно и то же направление , противоположное направление и уникальный метод, известный как «быстрый и медленный», часто называемый методом «черепахи и зайца» , который предполагает перемещение двух указателей с разной скоростью через структуру данных, что особенно полезно для обнаружения циклы.
Если вы используете несколько указателей для обхода структуры данных, вы можете классифицировать свой подход как следующий шаблону «Два указателя» .
Ключевые показатели:
Код шаблона:
Шаблон для варианта «в противоположном направлении»
Питон
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; }
Джава
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; }
Метод скользящего окна предполагает сохранение динамического окна над линейной структурой данных, такой как массивы, строки или связанные списки. Размер окна может варьироваться в зависимости от конкретной реализации, а также может быть установлен как фиксированное значение. Основная цель этого окна — непрерывный мониторинг и сбор данных, удовлетворяющих определенным критериям, что делает их особенно ценными для эффективного решения проблем с подмассивами или подстроками.
В этом шаблоне часто используется хеш-карта для облегчения отслеживания отдельных данных в окне. Однако важно отметить, что этот подход может привести к пространственно-временной сложности O(n) .
Ключевые показатели:
Код шаблона:
Питон
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; }
Джава
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; }
Этот шаблон включает в себя поиск K крупнейших или наименьших элементов в коллекции, часто реализуемый с использованием структур данных, таких как кучи или очереди с приоритетами. Это полезно для выбора подмножества элементов на основе их значения или частоты.
Каждый раз, когда нас просят найти наиболее частые, наименьшие или самые популярные элементы «K» в заданном наборе данных, мы можем рассмотреть возможность использования этого шаблона.
Принцип работы прост:
Красота этого подхода заключается в его эффективности; вам не нужно прибегать к каким-либо алгоритмам сортировки, поскольку куча сама естественным образом поддерживает необходимый порядок.
Ключевые показатели:
Код шаблона:
Питон
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); }
Джава
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; }
Две кучи используют две кучи (максимальную и минимальную кучи) для оптимизации определенных задач, например поиска медианных значений в наборе данных. Этот шаблон особенно полезен для поддержания сбалансированной структуры.
Вот как это работает:
Ключевые показатели:
Код шаблона:
Питон
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);
Джава
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);
Монотонный - (функции или величины), изменяющийся таким образом, что он либо никогда не уменьшается, либо никогда не увеличивается.
Монотонный стек поддерживает стек элементов в неубывающем или неубывающем порядке, часто используемый для поиска ближайших меньших/больших элементов в массиве. Это мощный инструмент для оптимизации определенных задач.
Порядок строгий: всякий раз, когда мы сталкиваемся с элементом, который меньше (или больше), чем тот, что находится на вершине стека, мы должны извлечь из монотонного стека до тех пор, пока элемент, который мы хотим добавить, не станет наименьшим (или наибольшим) из их.
Ключевые показатели:
Код шаблона:
Питон
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; }
Джава
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 или поиск в глубину — это метод обхода, при котором вы как можно глубже исследуете ветвь перед возвратом; он широко применяется в задачах, связанных с деревьями и графами, особенно для операций обхода и поиска.
Чтобы выполнить DFS в дереве, вам нужно начать с корня. Затем выполните следующие действия:
Разница с DFS на графе. Ключевое различие между DFS дерева и DFS графа заключается в наличии циклов. В дереве циклов нет по определению, поэтому DFS дерева гарантирует, что каждый узел посещается ровно один раз, и естественным образом завершается при обходе всего дерева. Напротив, графовая DFS должна включать дополнительные меры для обработки циклических структур внутри графа. Чтобы избежать бесконечного повторного посещения узлов в цикле, графовая DFS требует таких механизмов, как маркировка посещенных узлов и соответствующая обработка обратного отслеживания . Это различие делает графовую DFS более сложной, чем древовидную DFS из-за возможности возникновения бесконечных циклов при наличии циклов.
Ключевые показатели:
Код шаблона:
Питон
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 }
Джава
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 — это метод обхода деревьев и графов, который исследует все узлы на текущей глубине перед переходом на следующий уровень.
Чтобы выполнить BFS на дереве, вам нужно начать с корня. Затем выполните следующие действия:
Инициализируйте структуру данных пустой очереди, чтобы отслеживать узлы, которые необходимо посетить.
Поставьте корневой узел в очередь.
Введите цикл, пока очередь не станет пустой:
Повторяйте шаги 3a–3c, пока очередь не станет пустой.
Обход BFS завершается, когда все узлы дерева посещены по уровням, слева направо.
По сути, BFS в дереве исследует узлы уровень за уровнем , начиная с корня и переходя к дочерним узлам, прежде чем перейти к следующему уровню. Это гарантирует, что узлы на каждом уровне будут посещены перед переходом на следующий уровень, что делает его особенно полезным для таких задач, как поиск кратчайшего пути в невзвешенном дереве или исследование дерева уровень за уровнем.
Разница с BFS на графе. Подобно DFS, Graph BFS адаптируется к наличию циклов и нескольких путей между узлами. Он использует такие механизмы, как маркировка посещенных узлов и специальные условия завершения, чтобы эффективно перемещаться по сложной сети отношений внутри графов.
Ключевые показатели:
Код шаблона:
Питон
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 }
Джава
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 }
Структура данных Union-Find , также известная как объединение непересекающихся множеств (DSU) , используется для эффективного управления и решения проблем, связанных с непересекающимися множествами или связанными компонентами. Он предоставляет операции по слиянию множеств (объединение) и определению множества, к которому принадлежит элемент (поиск). Union-Find обычно используется в таких алгоритмах, как минимальное остовное дерево Крускала и обнаружение циклов на графах.
Union Find реализован следующим образом:
Код шаблона:
Питон
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); } }
Джава
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)); } }
Ориентированный ациклический граф (DAG) — это ориентированный граф без ориентированных циклов.
Топологическая сортировка — это алгоритм расположения узлов ориентированного ациклического графа ( DAG ) в линейном порядке, где каждый узел появляется раньше своих преемников. Это крайне важно для таких задач, как планирование зависимостей, компиляция кода и анализ приоритета задач в различных приложениях.
Вот пошаговое описание топологической сортировки:
Инициализация. Начните с направленного ациклического графа ( DAG ), который представляет задачи или узлы с зависимостями. Инициализируйте очередь для хранения отсортированных узлов.
Расчет в степени: вычисление степени (количества входящих ребер) для каждого узла графа. Узлы с входной степенью 0 не имеют зависимостей и подходят в качестве отправной точки топологической сортировки.
Начальное заполнение очереди: поместите в очередь все узлы со степенью входа 0. Эти узлы можно обработать в первую очередь.
Цикл топологической сортировки: пока очередь не пуста, выполните следующие действия:
Завершение: после завершения цикла топологической сортировки очередь станет пустой, а отсортированный список будет содержать все узлы в допустимом топологическом порядке.
Обнаружение циклов: если в какой-либо момент процесса топологической сортировки в очереди не осталось узлов с нулевой степенью, это указывает на наличие циклов в графе, что делает топологическую сортировку невозможной.
Результатом топологической сортировки является линейное упорядочение узлов с учетом их зависимостей, что делает ее пригодной для планирования задач или анализа порядка выполнения в различных приложениях.
Ключевые показатели:
Код шаблона:
Питон
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; } }
Джава
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; } }
Trie — это древовидная структура данных, используемая для эффективного сопоставления строк и хранения слов. Он отлично подходит для решения задач, связанных с хранением и поиском строк с общими префиксами.
Вот как реализовать Trie:
Инициализация: начните с пустого элемента Trie, который обычно состоит из корневого узла без связанного символа.
Вставка. Чтобы вставить слово в дерево, начните с корневого узла и перемещайтесь вниз по дереву, по одному символу за раз. Для каждого символа в слове:
Завершение слов. Чтобы проверить, существует ли слово в Trie, пройдите по нему аналогично вставке. Убедитесь, что каждый символ в слове соответствует дочернему узлу текущего узла. Если обход достигает конца слова и в последнем символьном узле имеется действительный маркер конца (например, логический флаг), слово существует в Trie.
Поиск по префиксам: Trie превосходно справляется с поиском по префиксам. Чтобы найти все слова с заданным префиксом, начните обход с корневого узла и двигайтесь вниз по дереву, следуя за символами префикса. Достигнув последнего символа префикса, вы можете выполнить поиск в глубину (DFS) из этого узла, чтобы найти все слова, имеющие один и тот же префикс.
Удаление: Чтобы удалить слово из списка, выполните поиск этого слова. Когда вы дойдете до конца слова, удалите маркер конца (если он существует). Если у узла нет других дочерних элементов, вы можете безопасно удалить всю ветвь дерева Trie, представляющую это слово.
Попытки могут потребовать много памяти, особенно для больших словарей. Для оптимизации памяти можно применять такие методы, как сжатие (например, использование карты вместо массива символов в каждом узле) и обрезка (удаление узлов без потомков).
Попытки особенно полезны для эффективного сопоставления строк, предложений автозаполнения, проверки орфографии и индексации слов с общими префиксами. Они обеспечивают быстрый и экономичный способ хранения и поиска слов или строк с общими префиксами в древовидной структуре.
Ключевые показатели:
Код шаблона:
Питон
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); } } }
Джава
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); } } }
Динамическое программирование — это мощный метод решения проблем, используемый в информатике и математике для эффективного решения широкого спектра сложных задач. Это особенно ценно, когда проблему можно разбить на более простые подзадачи, а решения этих подзадач можно объединить для решения общей проблемы.
Вот его основные характеристики и принцип работы:
Оптимальная подструктура:
Перекрывающиеся подзадачи:
Как работает динамическое программирование:
Динамическое программирование применяется для решения широкого спектра задач, включая поиск кратчайших путей в графах, оптимизацию распределения ресурсов, подсчет комбинаций, решение задач о рюкзаке и многое другое. Его способность оптимизировать решения, разбивая сложные проблемы на более простые части и избегая избыточных вычислений, делает его фундаментальным методом разработки и оптимизации алгоритмов.
Важные понятия: подход «снизу вверх», «сверху вниз», мемоизация, табуляция.
Ключевые показатели:
Код шаблона:
Шаблон для нисходящего запоминания — один из многих способов реализации динамического программирования.
Питон
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); }
Джава
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; }
Возврат — это общий алгоритмический метод постепенного решения проблем путем проверки различных возможностей и отмены их, если они не приводят к решению. Он используется, когда требуется исчерпывающий поиск.
Вот подробный обзор того, как работает возврат:
Применение обратного отслеживания:
Обратное отслеживание используется в различных проблемных областях, в том числе:
Ключевые показатели:
Код шаблона:
Питон
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; }
Джава
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; }
Объединение интервалов предполагает объединение перекрывающихся или соседних интервалов в единый набор, который часто используется в задачах, связанных с временными интервалами или планированием. Это упрощает интервальные операции.
Вот более детальный взгляд на то, как работает объединение интервалов:
Применение интервалов слияния:
Интервалы слияния обычно используются в:
За счет объединения перекрывающихся интервалов этот метод упрощает операции на основе интервалов и повышает эффективность различных приложений.
Ключевые показатели:
Код шаблона:
Питон
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; }
Джава
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()][]); } }
Если вы хотите узнать больше об этих шаблонах и о том, как их можно более эффективно реализовать во время следующего собеседования по программированию, посетите techinterviews.io сегодня! Мы предлагаем комплексную учебную программу, которая подготовит вас к следующему собеседованию по программированию, охватывающую такие темы, как структуры данных , алгоритмы , поведенческие собеседования и даже переговоры о зарплате . У нас даже есть встроенное рабочее пространство для кодирования, где вы можете попрактиковаться.
Улучшите свою подготовку к собеседованию по программированию сегодня с помощью нашего промокода TECH30 на скидку 30 долларов!
Рекомендованное изображение «разработчик, пишущий код», автор @Limarc
Графика сделана с помощью Okso.app