Модели за интервюта за кодиране

Успейте с всяко интервю за кодиране, като научите модели на алгоритми

Въведение

Моделът на горните K елементи е техника, която има за цел да върне даден брой от най-честите/най-големите/най-малките елементи в даден набор.

Ключовата структура на данните за решаване на проблеми с най-добрите K елементи е купчина. Като характеристика на max heap и min heap, винаги можем да получим най-големия и най-малкия елемент ефективно, т.е. O(logN).

Приближаване

Нека да видим някои примери. Първо ще разгледаме среден проблем на LeetCode — K-тият най-голям елемент в масив. Това изисква от нас да намерим даден номер на най-големия елемент в набор от цели числа.

Ето няколко примера:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Решение с груба сила е просто да сортирате масива и да откриете елемента на K-то място. Този метод обаче ще доведе до O(NlogN) поради функцията за сортиране на алгоритъма.

Можем ли да подобрим времевата сложност на този алгоритъм?

Определено. Вместо да сортираме и търсим поотделно, можем да поддържаме куп с размер K, което позволява съхраняване и сортиране на посетените елементи едновременно.

Но какъв вид купчина трябва да използваме? По принцип min heap и max heap могат да постигнат правилното решение. Тук ще обясним как можем да разрешим този проблем с min heap.

След като решихме структурата на данните, вече можем да влезем в основния процес. Идеята за решаване на този проблем чрез модела на най-горните K елементи е да запазим дадения размер на нашия min heap.

Тъй като коренният елемент винаги ще бъде най-малкият в рамките на min heap, ако размерът на heap е по-голям от K, root елементът трябва да бъде изхвърлен, тъй като е (K+1)-ият най-голям елемент досега.

В резултат на това процесът на алгоритъма ще изглежда като:

Обходете елементите на масива и ги поставете в купчина с мин. размер K. Ако размерът на купчината е по-голям от K, извадете основния елемент. Повторете този процес до края на масива.
Върнете коренния елемент на min heap, тъй като той е K-тият най-голям елемент от целия масив.

По-долу е дадена визуализация на алгоритъма:

Сега можем лесно да напишем имплементацията на кода:

Чрез прилагане на модела на най-горните K елементи можем да подобрим времевата сложност на решението за O(NlogK), в което извличането на коренния елемент е O(logK) и трябва да обходим целия масив.

След това ще разгледаме друг среден проблем на LeetCode — K най-близки точки до произход. Това е малко по-различно от горния проблем, който изисква от нас да намерим K най-големите елемента, докато този изисква K най-малките елемента.

Ето няколко примера:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]

Както правехме преди, всички знаем, че можем да решим проблема чрез купчина, но какъв вид купчина трябва да използваме?

Отново, за проблеми с топ k елемента винаги можем да ги решим чрез max heap или min heap. Просто е малко по-различно от начина, по който се справят с проблема. За този ще използваме максимална купчина, за да ви покажем как да се справите с K най-малките проблеми.

Начинът, по който дефинираме максимална купчина, също трябва да бъде внимателен. Вместо да сравняваме директно всяко цяло число, този път ще сравним разстоянието до началото между всяка точка.

Така че нашата максимална купчина трябва да се дефинира като:

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]))

(b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]) означава сравнението между разстоянието от b до началото и разстоянието от a до началото.

Останалата част от решението ще бъде същата като последния проблем, който ще поддържаме куп с максимален размер K. Елементите в тази купчина ще бъдат K най-близките точки до началото. Така че процесът ще бъде като:

Преминете и вмъкнете тези точки в максималния куп. Ако максималния размер на купчината надвишава K, извадете основния елемент, тъй като това е (K+1)-та най-близка точка до началото досега, която не ни е необходима.
Върнете крайната максимална купчина като резултат.

Визуализацията е показана по-долу:

Така вече можем да приложим решението:

Времевата сложност на този алгоритъм е O(NlogK), а пространствената сложност е O(K).

Заключение

В крайна сметка видяхме два вида решаване на проблеми с най-добрите K елементи съответно чрез min heap и max heap. В обобщение, моделът на горните K елементи може да бъде разделен на две стъпки:

Решете какъв вид купчина искате да използвате. Внимавайте с инициализацията на купчината, особено с начина за сравнение между елементите.
Поддържайте размера на купчината по-малък от K. Ако е по-голям от K, извлечете коренния елемент. Повторете този процес до края.

Свързани проблеми

Препратки

„Grokking the Coding Interview: Patterns for Coding Questions“
LeetCode — водещата в света платформа за онлайн обучение по програмиране

Модели за интервюта за кодиране — Топ „K“ елементи