Полезное видео, но касательно практической части хотелось бы все-таки более реалистичного сценария решения задач на том же leetcode-е: я имею ввиду моделирование реального технического интервью, где нужно написать код за ограниченное количество времени с проговариванием хода мыслей вслух как-будто бы зритель является своеобразным абстрактным интервьювером. Я ожидал нечто похожее. Как вариант, можно было бы выбрать категорию Heap (Priority Queue), где на данный момент насчитывается 169 задач и выбрать какую-то случайную, когда заранее неизвестно описание, в моем понимании большую роль играет насколько быстро интервьюируемый способен понять описание задачи и какой результат требуется на выходе. Я конечно понимаю, что автор канала возможно все их уже решил, но даже если это так, то все равно было бы интересно понаблюдать за ходом мыслей: как вариант, можно поставить таймер минут на 40 для medium задач и придерживаться его. P.S.: В любом случае очень полезный теоретический материал, было интересно.
Отличное объяснение! Спасибо за труды. Правда не понял восторга от применения heap-а в задаче с k-ым максимальным. Сложность будет сложность вроде таже, что и сортировкой, nlog(n). Поправьте, если ошибаюсь
Привет! Хороший вопрос. У нас есть n элементов и окно размера k. И оно так и останется максимального размера k в течение работы. Каждый новый элемент добавляется в окно и если инвариант нарушается в окне (window size == k + 1), мы убираем лишний (снова k). То есть глубина нашего дерева будет всегда log(k). Для каждого элемента мы свапнем его максимум log(k) раз. В целом тут k может быть равно n и тогда в крайнем случае действительно будет nlog(n). В среднем случае (считаем, что k чаще не очень большая) будет nlog(k). Например, если log(k) == 2 - мы рядом с "линейной сложностью" с константой C == 2. Тут есть еще один ньюанс. Heap на массиве - чрезвычайно cache friendly data structure и может при не большом k (
Спасибо за понятное и доступное объяснение работы Heap алгоритма! Подскажи плз - есть ли у тебя в каком нибудь видео рекомендация какой 📝список базовых алгоритмов необходимо изучить, чтобы начать видеть паттерны по твоему фрэймворку ? ❓Кстати, как ты считаешь - верно ли понимаю что данное решение чуть быстрее будет работать (нашел на литкоде): 📌# 1 - это твое решение с учетом переработки с С++ на Python и ипортом heapq (готовой реализации) # где ❗всегда для каждого элемента в цикле мы используем операцию heapq.heappush(heap, num) # class Solution: # def findKthLargest(self, nums: List[int], k: int) -> int: # heap = [] # for num in nums: # heapq.heappush(heap, num) # if len(heap) > k: # heapq.heappop(heap) # return heap[0] 📌# 2 - решение от leetcode.com/problems/kth-largest-element-in-an-array/solutions/3906260/100-3-approaches-video-heap-quickselect-sorting # где ⁉НЕ всегда для каждого элемента в цикле мы используем операцию heapq.heappush(heap, num), а тока когда num > heap[0] class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap = nums[:k] heapq.heapify(heap) for num in nums[k:]: if num > heap[0]: heapq.heappop(heap) heapq.heappush(heap, num) return heap[0]
Можно да. Я специально вставлял там наше решение с нуля, чтобы протестировать, что оно проходит на самых разных наборах данных. В реальности, мы так не делаем обычно :) А про паттерны посмотри мой тг канал, я там расписывал в посте
Спасибо рекомендациям ютуб что посоветовал ваше видео. И спасибо за ценный материал. Буду еще смотреть ваши видосы
Полезное видео, но касательно практической части хотелось бы все-таки более реалистичного сценария решения задач на том же leetcode-е: я имею ввиду моделирование реального технического интервью, где нужно написать код за ограниченное количество времени с проговариванием хода мыслей вслух как-будто бы зритель является своеобразным абстрактным интервьювером. Я ожидал нечто похожее.
Как вариант, можно было бы выбрать категорию Heap (Priority Queue), где на данный момент насчитывается 169 задач и выбрать какую-то случайную, когда заранее неизвестно описание, в моем понимании большую роль играет насколько быстро интервьюируемый способен понять описание задачи и какой результат требуется на выходе. Я конечно понимаю, что автор канала возможно все их уже решил, но даже если это так, то все равно было бы интересно понаблюдать за ходом мыслей: как вариант, можно поставить таймер минут на 40 для medium задач и придерживаться его.
P.S.: В любом случае очень полезный теоретический материал, было интересно.
Спасибо за труд, пересмотрю на репите)
Супер. Спасибо!
Отличное видео! Спасибо!
Отличное объяснение! Спасибо за труды. Правда не понял восторга от применения heap-а в задаче с k-ым максимальным. Сложность будет сложность вроде таже, что и сортировкой, nlog(n). Поправьте, если ошибаюсь
Хотя нет, инициализируем за k, потом добавляем (n-k) элементов, то есть O(k + (n-k)log(n)), прирост действительно неплохой при больших k
Привет! Хороший вопрос.
У нас есть n элементов и окно размера k. И оно так и останется максимального размера k в течение работы. Каждый новый элемент добавляется в окно и если инвариант нарушается в окне (window size == k + 1), мы убираем лишний (снова k). То есть глубина нашего дерева будет всегда log(k). Для каждого элемента мы свапнем его максимум log(k) раз. В целом тут k может быть равно n и тогда в крайнем случае действительно будет nlog(n). В среднем случае (считаем, что k чаще не очень большая) будет nlog(k). Например, если log(k) == 2 - мы рядом с "линейной сложностью" с константой C == 2.
Тут есть еще один ньюанс. Heap на массиве - чрезвычайно cache friendly data structure и может при не большом k (
Спасибо, на хэш таблицу еще тотального гайда не хватает)
Спасибо за понятное и доступное объяснение работы Heap алгоритма!
Подскажи плз - есть ли у тебя в каком нибудь видео рекомендация какой 📝список базовых алгоритмов необходимо изучить, чтобы начать видеть паттерны по твоему фрэймворку ?
❓Кстати, как ты считаешь - верно ли понимаю
что данное решение чуть быстрее будет работать (нашел на литкоде):
📌# 1 - это твое решение с учетом переработки с С++ на Python и ипортом heapq (готовой реализации)
# где ❗всегда для каждого элемента в цикле мы используем операцию heapq.heappush(heap, num)
# class Solution:
# def findKthLargest(self, nums: List[int], k: int) -> int:
# heap = []
# for num in nums:
# heapq.heappush(heap, num)
# if len(heap) > k:
# heapq.heappop(heap)
# return heap[0]
📌# 2 - решение от leetcode.com/problems/kth-largest-element-in-an-array/solutions/3906260/100-3-approaches-video-heap-quickselect-sorting
# где ⁉НЕ всегда для каждого элемента в цикле мы используем операцию heapq.heappush(heap, num), а тока когда num > heap[0]
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, num)
return heap[0]
Можно да. Я специально вставлял там наше решение с нуля, чтобы протестировать, что оно проходит на самых разных наборах данных. В реальности, мы так не делаем обычно :) А про паттерны посмотри мой тг канал, я там расписывал в посте