Шаблоны кодирования: более разумный подход к подготовке к собеседованию по программированию

Подготовка к собеседованиям по программированию может стать настоящей проблемой, поскольку разработчики часто тратят несколько недель на просмотр и изучение нового материала. Правда в том, что большинство разработчиков никогда не чувствуют себя полностью готовыми к собеседованиям по программированию. Разработчики нередко тратят недели на решение проблем в LeetCode и при этом чувствуют себя неподготовленными. Очевидно, что с этим подходом есть проблемы. Давайте подробнее рассмотрим некоторые проблемы, связанные с традиционной подготовкой к собеседованию по программированию. Ловушки традиционной подготовки к собеседованию Одной из наиболее распространенных ошибок при традиционной подготовке к собеседованию является практика Этот подход предполагает решение как можно большего количества проблем без четкого плана или стратегии. Хотя это может показаться продуктивной стратегией, у нее есть несколько недостатков. «притирки». LeetCode Когда вы решаете проблемы без структурированного подхода, вы можете не распознать свои слабости. У вашего обучения нет продуманного плана; цель состоит в том, чтобы просто решить как можно больше проблем. В результате у вас может возникнуть ощущение, что вы многому научились, но в ваших знаниях могут быть значительные пробелы. Более того, проблема в том, что по сути это вращается вокруг запоминания решений множества проблем. Попытка запомнить решения сотни различных задач по кодированию оказывается неэффективной, когда интервьюеры задают вопросы, которые хоть немного отличаются от тех, с которыми вы сталкивались раньше. Это может привести к тому, что вы почувствуете себя неподготовленным к решению проблемных вариантов. Моя последняя проблема с этой стратегией заключается в том, что в долгосрочной перспективе она создает еще больше стресса и головных болей. Если вам приходится проходить одну и ту же зубрежку продолжительностью в несколько недель каждый раз, когда вы хотите сменить работу, вам каждый раз придется бороться. Вы потратите недели на то, чтобы заново учиться и решать те же проблемы, что и раньше. Учитывая эти проблемы, должен быть лучший путь. Лучший способ: использование шаблонов кодирования Итак, существует ли более эффективный и устойчивый подход к подготовке к собеседованию по кодированию? Ответ заключается в понимании и использовании шаблонов кодирования. Когда я готовлюсь к собеседованиям по программированию, я уделяю первоочередное внимание выявлению основных закономерностей проблем. Эти шаблоны, включающие в себя такие методы, как », , », » и многие другие, обеспечивают универсальную и мощную основу для решения широкого спектра проблем кодирования. Акцент смещается с запоминания решений на проверенные методы решения проблем. «Два указателя «Скользящее окно» «Модифицированный двоичный поиск «Топологическая сортировка Сосредоточив внимание на шаблонах кодирования, вы можете значительно упростить подготовку к собеседованию, сделав ее более эффективной. Помните, готовьтесь умнее, а не усерднее. Что ожидать? В этой статье я собрал что вам нужно знать, чтобы ответить на любой вопрос по кодированию. Я расскажу, что представляет собой каждый шаблон и как он работает. Поделитесь ключевыми индикаторами, которые помогут вам определить закономерность, и, наконец, предложите подробные графики с кодом шаблона, которые помогут вам закрепить свое понимание. 15 лучших шаблонов кодирования Хотя я многое рассказываю в этой статье, если вам нужно более углубленное обучение, объяснения и практика кодирования, вы можете посетить наш на Мы также освещаем такие важные темы, как , и даже . Комплексный курс подготовки к собеседованию по программированию Techinterviews.io. структуры данных поведенческие интервью переговоры о зарплате Теперь давайте углубимся в эти шаблоны кодирования. 1. Обращение связанного списка Обращение связанного списка предполагает изменение направления указателей в связанном списке для изменения порядка элементов. Это фундаментальная операция в структурах данных, которая часто требует тщательного манипулирования ссылками на узлы. Это полезно при работе со связанным списком, и ограничение состоит в том, чтобы перевернуть его на месте. Процесс отмены связанного списка на месте выглядит следующим образом: Начните с определения трех переменных: , и . Установите текущий в качестве главы связанного списка и инициализируйте предыдущий и следующий как None. current previous next Пока текущая переменная не , действуйте следующим образом: 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; } 2. Модифицированный двоичный поиск адаптирует классический алгоритм двоичного поиска для решения различных задач. Варианты включают поиск первого/последнего вхождения элемента или поиск во вращающихся массивах. Это требует тщательного обращения со средними точками и условиями. Модифицированный двоичный поиск Если вам когда-либо предоставлялся отсортированный массив, связанный список или матрица, рассмотрите возможность использования . модифицированного двоичного поиска Вот описание того, как применить этот шаблон к отсортированной структуре данных: Начните с определения средней точки между и позициями. Чтобы избежать потенциального целочисленного переполнения, безопаснее вычислять середину следующим образом: . начальной конечной middle = start + (end - start) / 2 Проверьте, соответствует ли ключ элементу по индексу. Если это так, верните индекс в качестве результата. среднему средний Если ключ не соответствует элементу по индексу, перейдите к следующим шагам. среднему Оцените, меньше ли ключ, чем элемент в индекса. Если это так, сузьте диапазон поиска, обновив до . середине конец среднего - 1 И наоборот, если ключ больше, чем элемент в индексе , измените диапазон поиска, обновив до . middle start middle + 1 Ключевые показатели: Вы работаете с отсортированной структурой данных. Вам необходимо эффективно находить конкретные элементы, границы или опорные точки. Проблемы связаны с поиском в повернутых отсортированных массивах. Код шаблона: Питон 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; } 3. Два указателя предполагает поддержку двух указателей, которые пересекают структуру данных, обычно массивы или связанные списки, часто используемые для решения задач, связанных с парами или подмассивами. Он оптимизируется для задач, требующих сравнения элементов в разных позициях. Метод двух указателей Преимущество этого метода заключается в его простоте и эффективности, особенно при работе с линейными структурами данных, такими как массивы или строки, где изначально можно использовать только один указатель. Используя два указателя, вы можете обойти избыточные операции и значительно повысить эффективность выполнения, потенциально снижая ее с до . O(n^2) O(n) Шаблон включает в себя несколько вариантов, каждый из которых адаптирован к конкретным сценариям. Эти варианты включают в себя , и уникальный метод, известный как часто называемый методом , который предполагает перемещение двух указателей с разной скоростью через структуру данных, что особенно полезно для обнаружения циклы. «Два указателя» одно и то же направление противоположное направление «быстрый и медленный», «черепахи и зайца» Если вы используете несколько указателей для обхода структуры данных, вы можете классифицировать свой подход как следующий шаблону . «Два указателя» Ключевые показатели: Вам нужно сравнивать элементы, находящиеся в разных позициях, или работать с ними. Проблемы требуют поиска пар элементов в отсортированном массиве. Вы хотите эффективно удалить дубликаты из отсортированного массива. Когда вы имеете дело с линейными структурами данных (массивами, строками или связанными списками) и сталкиваетесь с квадратичной временной сложностью (решение методом грубой силы ), рассмотрите возможность использования двух указателей. O(n^2) Код шаблона: Шаблон для варианта «в противоположном направлении» Питон 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; } 4. Раздвижное окно предполагает сохранение динамического окна над линейной структурой данных, такой как массивы, строки или связанные списки. Размер окна может варьироваться в зависимости от конкретной реализации, а также может быть установлен как фиксированное значение. Основная цель этого окна — непрерывный мониторинг и сбор данных, удовлетворяющих определенным критериям, что делает их особенно ценными для эффективного решения проблем с подмассивами или подстроками. Метод скользящего окна В этом шаблоне часто используется хеш-карта для облегчения отслеживания отдельных данных в окне. Однако важно отметить, что этот подход может привести к пространственно-временной сложности . 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 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; } 5. Топ-K элементов Этот шаблон включает в себя поиск K крупнейших или наименьших элементов в коллекции, часто реализуемый с использованием структур данных, таких как кучи или очереди с приоритетами. Это полезно для выбора подмножества элементов на основе их значения или частоты. Каждый раз, когда нас просят найти наиболее частые, наименьшие или самые популярные элементы «K» в заданном наборе данных, мы можем рассмотреть возможность использования этого шаблона. Принцип работы прост: Мы вставляем элементы «K» в нашу минимальную или максимальную кучу (это зависит от реализации). Каждый раз, когда мы добавляем в нашу кучу, мы должны настроить так, чтобы всегда сохранялись частые/наименьшие/верхние элементы «K». Красота этого подхода заключается в его эффективности; вам не нужно прибегать к каким-либо алгоритмам сортировки, поскольку куча сама естественным образом поддерживает необходимый порядок. Ключевые показатели: Вам необходимо определить 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 topKElements(int[] arr, int k) { PriorityQueue 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 topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; } 6. Две кучи Две кучи используют две кучи (максимальную и минимальную кучи) для оптимизации определенных задач, например поиска медианных значений в наборе данных. Этот шаблон особенно полезен для поддержания сбалансированной структуры. Вот как это работает: максимальную кучу для определения самого большого элемента и минимальную кучу для поиска наименьшего. Используйте две кучи: Заполните максимальную кучу первой половиной чисел, стремясь найти среди них наибольшее. Заполните минимальную кучу второй половиной чисел, чтобы определить наименьшее из этой части. Медиану текущего набора чисел можно вычислить в любой момент, исследуя верхние элементы обеих куч. Ключевые показатели: Вам необходимо поддерживать сбалансированную структуру для эффективного поиска медианы. Проблемы связаны с решением проблем скользящего окна с динамическими медианами. Вы хотите расставить приоритеты элементов в коллекции на основе их значений. Код шаблона: Питон 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 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.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 minHeap; // Right heap to store larger half private PriorityQueue 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 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); 7. Монотонный стек Монотонный - (функции или величины), изменяющийся таким образом, что он либо никогда не уменьшается, либо никогда не увеличивается. Монотонный стек поддерживает стек элементов в неубывающем или неубывающем порядке, часто используемый для поиска ближайших меньших/больших элементов в массиве. Это мощный инструмент для оптимизации определенных задач. Порядок строгий: всякий раз, когда мы сталкиваемся с элементом, который меньше (или больше), чем тот, что находится на вершине стека, мы должны извлечь из монотонного стека до тех пор, пока элемент, который мы хотим добавить, не станет наименьшим (или наибольшим) из их. Ключевые показатели: Вам необходимо поддерживать элементы в неубывающем или неубывающем порядке. Проблемы заключаются в поиске ближайшего меньшего или большего элемента. Вы хотите оптимизировать операции на основе стека, сохраняя при этом порядок. Код шаблона: Питон def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] 0 && stack[stack.length - 1] 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; } 8. Поиск в глубину или — это метод обхода, при котором вы как можно глубже исследуете ветвь перед возвратом; он широко применяется в задачах, связанных с деревьями и графами, особенно для операций обхода и поиска. DFS поиск в глубину Чтобы выполнить DFS в дереве, вам нужно начать с корня. Затем выполните следующие действия: Исследуйте текущий узел, посещая его дочерние узлы, обычно . слева направо к каждому дочернему узлу, углубляясь в дерево. Рекурсивно примените процесс DFS После посещения всех дочерних узлов к родительскому узлу. вернитесь для каждого непосещенного дочернего элемента текущего узла, пока не будут посещены все узлы в дереве. Повторяйте шаги 1–3 Ключевое различие между 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 } 9. Поиск в ширину BFS — это метод обхода деревьев и графов, который исследует все узлы на текущей глубине перед переходом на следующий уровень. Чтобы выполнить BFS на дереве, вам нужно начать с корня. Затем выполните следующие действия: Инициализируйте структуру данных пустой очереди, чтобы отслеживать узлы, которые необходимо посетить. корневой узел в очередь. Поставьте Введите цикл, пока очередь не станет пустой: Удалить из очереди узел в начале очереди. Обработать узел, выведенный из очереди (например, посетить его или выполнить над ним какую-либо операцию). Поместите в очередь всех дочерних узлов узла (если таковые имеются). пока очередь не станет пустой. Повторяйте шаги 3a–3c, Обход BFS завершается, когда все узлы дерева посещены по уровням, слева направо. По сути, BFS в дереве исследует узлы , начиная с корня и переходя к дочерним узлам, прежде чем перейти к следующему уровню. Это гарантирует, что узлы на каждом уровне будут посещены перед переходом на следующий уровень, что делает его особенно полезным для таких задач, как поиск кратчайшего пути в невзвешенном дереве или исследование дерева уровень за уровнем. уровень за уровнем Подобно DFS, Graph BFS адаптируется к наличию циклов и нескольких путей между узлами. Он использует такие механизмы, как маркировка посещенных узлов и специальные условия завершения, чтобы эффективно перемещаться по сложной сети отношений внутри графов. Разница с 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 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 } 10. Поиск объединения (объединение непересекающихся наборов) Структура данных , также известная как , используется для эффективного управления и решения проблем, связанных с непересекающимися множествами или связанными компонентами. Он предоставляет операции по слиянию множеств (объединение) и определению множества, к которому принадлежит элемент (поиск). Union-Find обычно используется в таких алгоритмах, как минимальное остовное дерево Крускала и обнаружение циклов на графах. 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 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)); } } 11. Топологическая сортировка Ориентированный ациклический граф (DAG) — это ориентированный граф без ориентированных циклов. — это алгоритм расположения узлов ориентированного ациклического графа ( ) в линейном порядке, где каждый узел появляется раньше своих преемников. Это крайне важно для таких задач, как планирование зависимостей, компиляция кода и анализ приоритета задач в различных приложениях. Топологическая сортировка DAG Вот пошаговое описание топологической сортировки: Начните с направленного ациклического графа ( ), который представляет задачи или узлы с зависимостями. Инициализируйте очередь для хранения отсортированных узлов. Инициализация. DAG вычисление степени (количества входящих ребер) для каждого узла графа. Узлы с входной степенью 0 не имеют зависимостей и подходят в качестве отправной точки топологической сортировки. Расчет в степени: поместите в очередь все узлы со степенью входа 0. Эти узлы можно обработать в первую очередь. Начальное заполнение очереди: пока очередь не пуста, выполните следующие действия: Цикл топологической сортировки: Удалить узел из начала очереди. Обработать узел (например, добавить его в отсортированный список). Для каждого из соседей узла (узлов, на которые он указывает) уменьшите их входную степень на 1. Если в результате декремента степень входа соседа становится равной 0, поставьте его в очередь. после завершения цикла топологической сортировки очередь станет пустой, а отсортированный список будет содержать все узлы в допустимом топологическом порядке. Завершение: если в какой-либо момент процесса топологической сортировки в очереди не осталось узлов с нулевой степенью, это указывает на наличие циклов в графе, что делает топологическую сортировку невозможной. Обнаружение циклов: Результатом топологической сортировки является линейное упорядочение узлов с учетом их зависимостей, что делает ее пригодной для планирования задач или анализа порядка выполнения в различных приложениях. Ключевые показатели: Проблема связана с планированием или упорядочиванием задач с зависимостями. Вы работаете с ориентированным ациклическим графом (DAG). Задачи должны выполняться в определенном порядке с соблюдением их зависимостей. Код шаблона: Питон 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 findIndegree(Map > graph) { Map 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 topologicalSort(Map > graph) { List result = new ArrayList<>(); Queue queue = new LinkedList<>(); Map 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; } } 12. Попытки (префиксное дерево) — это древовидная структура данных, используемая для эффективного сопоставления строк и хранения слов. Он отлично подходит для решения задач, связанных с хранением и поиском строк с общими префиксами. 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 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); } } } 13. Динамическое программирование — это мощный метод решения проблем, используемый в информатике и математике для эффективного решения широкого спектра сложных задач. Это особенно ценно, когда проблему можно разбить на более простые подзадачи, а решения этих подзадач можно объединить для решения общей проблемы. Динамическое программирование Вот его основные характеристики и принцип работы: Оптимальная подструктура: Эта характеристика относится к тому свойству, что оптимальное решение более крупной проблемы может быть построено из оптимальных решений ее меньших подзадач. Другими словами, проблемы DP имеют рекурсивную структуру, где оптимальное решение проблемы зависит от оптимальных решений ее подзадач. Например, при поиске кратчайшего пути между двумя точками на графе оптимальным должен быть также кратчайший путь между любыми двумя промежуточными точками. Перекрывающиеся подзадачи: Перекрывающиеся подзадачи возникают, когда одни и те же подзадачи решаются несколько раз в ходе вычислений, что приводит к избыточной работе. Динамическое программирование направлено на решение этой проблемы путем сохранения решений подзадач в структуре данных (часто в таблице или массиве мемоизации), чтобы избежать их повторного расчета. Такое хранение и повторное использование решений подзадач значительно сокращают временную сложность алгоритма. Как работает динамическое программирование: Первым шагом в решении проблемы с использованием DP является идентификация подзадач. Разбейте проблему на более мелкие, управляемые подзадачи, решение которых будет способствовать решению основной проблемы. Идентификация подзадач. Разработайте рекурсивное решение, выражающее решение более крупной проблемы через решения более мелких подзадач. Эта рекурсивная формулировка фиксирует оптимальную подструктуру. Рекурсивное решение. Для решения пересекающихся подзадач вы можете выбрать один из двух распространенных методов: Мемоизация или табуляция. сохранение результатов подзадач в структуре данных (обычно массиве или хеш-таблице) по мере их вычисления. Когда подзадача встречается снова, извлеките ее решение из хранилища вместо того, чтобы пересчитывать его. Этот подход также известен как подход . Мемоизация: «сверху вниз» создайте таблицу (часто двумерный массив) для хранения решений подзадач способом. Начните с решения самых маленьких подзадач и постепенно приближайтесь к основной проблеме. Табуляция: восходящим как только все подзадачи решены, решение основной проблемы может быть получено путем объединения решений ее подзадач в соответствии с рекурсивной структурой задачи. Оптимальное решение: Динамическое программирование применяется для решения широкого спектра задач, включая поиск кратчайших путей в графах, оптимизацию распределения ресурсов, подсчет комбинаций, решение задач о рюкзаке и многое другое. Его способность оптимизировать решения, разбивая сложные проблемы на более простые части и избегая избыточных вычислений, делает его фундаментальным методом разработки и оптимизации алгоритмов. подход «снизу вверх», «сверху вниз», мемоизация, табуляция. Важные понятия: Ключевые показатели: Проблему можно разбить на более мелкие перекрывающиеся подзадачи. Необходимо оптимизировать, сохраняя и повторно используя решения подзадач. Вы хотите решить задачи, связанные с оптимизацией или подсчетом. Код шаблона: Шаблон для нисходящего запоминания — один из многих способов реализации динамического программирования. Питон 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 memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map 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; } 14. Возврат — это общий алгоритмический метод постепенного решения проблем путем проверки различных возможностей и отмены их, если они не приводят к решению. Он используется, когда требуется исчерпывающий поиск. Возврат Вот подробный обзор того, как работает возврат: возвратное отслеживание исследует проблемное пространство путем постепенного построения решения по одному фрагменту за раз. На каждом этапе он принимает решение и движется вперед. Исследование проблемного пространства: Обратное отслеживание часто включает в себя рекурсию. Он начинается с первоначального частичного решения и исследует все возможные способы его расширения. Этот процесс продолжается рекурсивно до тех пор, пока не будет найдено полное решение или пока не станет очевидно, что допустимого решения не существует. Рекурсивная структура. На каждом этапе существуют точки принятия решения, в которых алгоритм должен выбирать из доступных вариантов. Этот выбор приводит к разветвлению процесса разведки. Точки принятия решения. после выбора алгоритм проверяет, является ли текущее частичное решение допустимым. Если это действительно так, алгоритм переходит к следующему шагу. Если нет, он возвращается назад, отменяя предыдущий выбор и изучая другие варианты. Проверка решения: возврат продолжается до тех пор, пока не будет выполнено одно из двух условий: Условия завершения: Находится допустимое решение, и в этом случае алгоритм останавливается и возвращает решение. Определяется, что допустимого решения не существует, после чего алгоритм возвращается к предыдущей точке принятия решения и исследует различные варианты. Чтобы оптимизировать поиск, возврат часто включает в себя стратегии сокращения. Сокращение предполагает избегание исследования путей, которые гарантированно приведут к неверным решениям, что значительно сокращает пространство поиска. Сокращение. Применение обратного отслеживания: Обратное отслеживание используется в различных проблемных областях, в том числе: Решение головоломок, таких как судоку и N-Queens. Создание перестановок и комбинаций. Поиск путей в графах и деревьях. Проблемы удовлетворения ограничений (например, задача коммивояжера). Игровые алгоритмы (например, шахматный ИИ). Ключевые показатели: Проблема заключается в постепенном изучении множества возможностей. Существуют точки принятия решения или ограничения, которые требуют опробовать разные варианты. Вам необходимо найти все возможные решения или удовлетворить конкретные условия путем перебора. Код шаблона: Питон 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; } 15. Объединение интервалов Объединение интервалов предполагает объединение перекрывающихся или соседних интервалов в единый набор, который часто используется в задачах, связанных с временными интервалами или планированием. Это упрощает интервальные операции. Вот более детальный взгляд на то, как работает объединение интервалов: Интервалы обычно представляются как пары и точек (например, ). Представление интервалов. начальной конечной [start, end] Чтобы эффективно объединить интервалы, начните с их сортировки по начальным точкам. Это гарантирует, что перекрывающиеся или соседние интервалы будут соседними в отсортированном списке. Сортировка. инициализируйте пустой список для хранения объединенных интервалов. Затем выполните итерацию по отсортированным интервалам один за другим: Процесс слияния: Если текущий интервал не перекрывается с предыдущим, добавьте его в список объединенных интервалов. Если есть перекрытие, обновите конечную точку предыдущего объединенного интервала, чтобы он охватывал как текущий, так и предыдущий интервалы, эффективно объединяя их. После обработки всех интервалов список объединенных интервалов будет содержать непересекающиеся и консолидированные интервалы. Завершение: Применение интервалов слияния: Интервалы слияния обычно используются в: Приложения для планирования и управления временем. Обнаружение перекрывающихся событий в календарных системах. Интервальный анализ данных, например, в запросах к базе данных. Решение проблем, связанных с распределением ресурсов и планированием встреч. За счет объединения перекрывающихся интервалов этот метод упрощает операции на основе интервалов и повышает эффективность различных приложений. Ключевые показатели: Вы имеете дело с интервалами или данными, основанными на времени. Проблемы связаны с объединением перекрывающихся или соседних интервалов. Вы хотите упростить интервальные операции или оптимизировать планирование событий. Код шаблона: Питон 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 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 структуры данных алгоритмы поведенческие собеседования переговоры о зарплате Улучшите свою подготовку к собеседованию по программированию сегодня с помощью нашего промокода на скидку 30 долларов! TECH30 Рекомендованное изображение автор @Limarc «разработчик, пишущий код», Графика сделана с помощью Okso.app