Когда дело доходит до собеседований по разработке программного обеспечения в 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…