В пантеоне структур данных кучи занимают особую нишу, особенно в алгоритмах, требующих операций с приоритетом, таких как приоритетные очереди. Эффективность куч признается на собеседованиях по разработке программного обеспечения в Meta (ранее известной как Facebook), где они служат пробным камнем для оценки алгоритмического мастерства кандидата. Здесь мы освещаем пять основных вопросов, связанных с кучей, которые часто возникают в процессе собеседований в Meta, и предлагаем решения на Python для каждого из них.
Не забудьте приобрести Проектирование приложений с интенсивным использованием данных, самую важную книгу, которую следует прочитать при подготовке к собеседованию по проектированию систем!
1. K-й самый большой элемент массива
Вопрос: Найдите k-й по величине элемент в несортированном массиве. Почему это задается. Это классическая задача о куче, которая проверяет умение кандидата использовать кучи для управления наборами данных и извлечения определенных элементов.
import heapq def findKthLargest(nums, k): return heapq.nlargest(k, nums)[-1]
2. Объединить K отсортированных списков
Вопрос: Объедините k отсортированных связанных списков и верните их как один отсортированный список. Почему это задается. Эта задача оценивает умение кандидата использовать кучи для сортировки и объединения структур данных.
Для вашего следующего собеседования рассмотрите популярный ByteByteGo» Курс для собеседований по системному дизайну!
import heapq class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeKLists(lists): dummy = ListNode() curr = dummy heap = [] for i, lst in enumerate(lists): if lst: heapq.heappush(heap, (lst.val, i, lst)) while heap: val, i, lst = heapq.heappop(heap) curr.next = ListNode(val) curr = curr.next if lst.next: heapq.heappush(heap, (lst.next.val, i, lst.next)) return dummy.next
Получите более высокую зарплату с помощью Grokking Comp Negotiation в сфере технологий.
3. Найдите медиану из потока данных.
Вопрос: Реализовать класс MedianFinder
, который обеспечивает функциональность сложения чисел и поиска текущего…