В пантеоне структур данных кучи занимают особую нишу, особенно в алгоритмах, требующих операций с приоритетом, таких как приоритетные очереди. Эффективность куч признается на собеседованиях по разработке программного обеспечения в 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, который обеспечивает функциональность сложения чисел и поиска текущего…