Когда дело доходит до собеседований по разработке программного обеспечения в Meta (ранее известной как Facebook), структуры данных, такие как приоритетные очереди, часто занимают центральное место. Очереди приоритетов имеют решающее значение для разработки и реализации алгоритмов для решения реальных задач, связанных с сортировкой, планированием и т. д. В этой статье рассматриваются 5 основных вопросов об очередях приоритетов, которые часто задают на собеседованиях по разработке программного обеспечения Meta, а также их решениях на Python.
Для вашего следующего собеседования рассмотрите популярный ByteByteGo» Курс для собеседований по системному дизайну!
1. K-й самый большой элемент массива
Вопрос:
Найдите k-й по величине элемент несортированного массива.
import heapq def kth_largest_element(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heapq.heappop(heap)
2. Объединить K отсортированных списков
Вопрос:
Имея k
отсортированных связанных списков, объедините их в один отсортированный связанный список.
import heapq class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_k_sorted_lists(lists): heap = [(l.val, l) for l in lists if l] heapq.heapify(heap) dummy = ListNode() curr = dummy while heap: val, node = heapq.heappop(heap) curr.next = node curr = curr.next node = node.next if node: heapq.heappush(heap, (node.val, node)) return dummy.next
Не забудьте приобрести экземпляр Проектирование приложений с интенсивным использованием данных, самой важной книги, которую следует прочитать при подготовке к собеседованию по проектированию систем!
3. Топ-K частых элементов
Вопрос:
Учитывая непустой массив целых чисел, найдите k
наиболее часто встречающихся элементов.
from collections import Counter def top_k_frequent(nums…