Самая длинная последовательность и кэш LRU
Решите задачу longest-consecutive-sequence за O(n) с помощью множества, а затем спроектируйте кэш LRU, используя OrderedDict
«Самая длинная последовательность и кэш LRU» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Задача о самой длинной последовательности последовательных чисел
LeetCode 128 «Самая длинная последовательность последовательных чисел»: получив неотсортированный массив, найдите длину самой длинной последовательности последовательных целых чисел. Например, [100,4,200,1,3,2] содержит последовательность [1,2,3,4] длиной 4. Сложность состоит в том, чтобы решить задачу за O(n), а не за O(n log n), которое даёт сортировка с последующим просмотром.
Главная идея: используйте множество для проверок наличия за O(1) и начинайте подсчёт последовательности только с её наименьшего элемента — это определяется проверкой отсутствия предшествующего числа в множестве.
def longestConsecutive(nums):
num_set = set(nums)
best = 0
for n in num_set:
if n - 1 not in num_set: # n is the start of a sequence
curr_n = n
length = 1
while curr_n + 1 in num_set:
curr_n += 1
length += 1
best = max(best, length)
return best
print(longestConsecutive([100,4,200,1,3,2])) # 4
print(longestConsecutive([0,3,7,2,5,8,4,6,0,1])) # 9Почему доказательство O(n) верно
Каждое число посещается во внутреннем цикле while не более одного раза за все итерации внешнего цикла for. Хотя цикл while находится внутри цикла for, общее количество итераций while по всем внешним итерациям не превышает n, поскольку каждое число может быть «curr_n + 1» не более чем для одной последовательности. Этот амортизированный анализ даёт общую сложность O(n), как и анализ монотонного стека.
# Demonstrate O(n) total inner iterations
nums = list(range(1000)) # worst case: one long sequence
num_set = set(nums)
inner_iters = 0
for n in num_set:
if n - 1 not in num_set:
curr = n
while curr + 1 in num_set:
curr += 1
inner_iters += 1
print('n =', len(nums), ' total inner iterations =', inner_iters)
# inner_iters = n-1 <= n => O(n)Альтернатива: подход на основе сортировки
Для сравнения, подход с сортировкой и просмотром выполняется за O(n log n): отсортируйте массив, удалите последовательные дубликаты, а затем подсчитайте последовательные серии. Хотя этот подход медленнее, он использует O(1) дополнительной памяти, если сортировка выполняется на месте. Подход с множеством использует O(n) дополнительной памяти. На собеседовании упомяните оба варианта и уточните, допустимо ли решение за O(n log n) с учётом ограничений по памяти.
def longestConsecutive_sort(nums):
if not nums:
return 0
nums.sort()
best = length = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
continue # skip duplicates
if nums[i] == nums[i-1] + 1:
length += 1
best = max(best, length)
else:
length = 1
return best
print(longestConsecutive_sort([100,4,200,1,3,2])) # 4Что такое кэш LRU
Кэш LRU (наименее недавно использованный) — это структура данных фиксированной вместимости, которая вытесняет элемент, не использовавшийся дольше всего, когда заполнена и требуется вставить новый элемент. Операции: get(key) возвращает значение, если ключ существует (и помечает его как недавно использованный), или -1, если ключ отсутствует; put(key, value) вставляет пару (при заполненной структуре вытесняя элемент LRU).
Кэши LRU используются в операционных системах (для замещения страниц), кэшах браузеров и кэшах запросов к базам данных. В задаче LeetCode 146 требуется реализовать такой кэш с операциями get и put за O(1).
Кэш LRU с использованием OrderedDict
Встроенная структура collections.OrderedDict сохраняет порядок вставки и поддерживает операцию move_to_end(key) за O(1), чтобы пометить элемент как использованный совсем недавно. При выполнении put переместите ключ в конец; при переполнении удалите первый элемент (LRU). Это обеспечивает операции get и put за O(1) благодаря встроенной структуре, в основе которой внутри находятся двусвязный список и хеш-таблица.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict LRU (first item)
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1 (and 1 becomes most recently used)
cache.put(3, 3) # evict key 2 (LRU)
print(cache.get(2)) # -1
cache.put(4, 4) # evict key 1 (LRU)
print(cache.get(1)) # -1
print(cache.get(3)) # 3
print(cache.get(4)) # 4Кэш LRU с нуля: двусвязный список + HashMap
Реализация с нуля использует двусвязный список (для удаления узла за O(1)) и хеш-таблицу (для поиска узла по ключу за O(1)). Список поддерживает порядок от LRU (head.next) до MRU (tail.prev). Фиктивные сторожевые узлы head и tail устраняют особые случаи при вставке и удалении на границах списка.
class DNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCacheDLL:
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> DNode
self.head = DNode() # dummy LRU end
self.tail = DNode() # dummy MRU end
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_tail(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key, val):
if key in self.map:
self._remove(self.map[key])
node = DNode(key, val)
self._add_to_tail(node)
self.map[key] = node
if len(self.map) > self.cap:
lru = self.head.next
self._remove(lru)
del self.map[lru.key]
cache = LRUCacheDLL(2)
cache.put(1,1); cache.put(2,2)
print(cache.get(1)) # 1
cache.put(3,3)
print(cache.get(2)) # -1 (evicted)Почему для LRU используется двусвязный список
Односвязный список не может удалить произвольный узел за O(1), если неизвестен предшествующий узел. Двусвязный список хранит указатели prev и next, благодаря чему удаление по ссылке на узел выполняется за O(1). Хеш-таблица обеспечивает доступ к узлу по ключу за O(1). Вместе эти структуры дают следующий результат: get(key) за O(1) находит узел и за O(1) перемещает его в хвост; put(key) за O(1) добавляет узел и за O(1) удаляет узел LRU из головы списка.
# Why not a singly linked list?
# To remove a node you need its predecessor
# With SLL: must traverse from head to find predecessor => O(n)
# With DLL: node.prev IS the predecessor => O(1) removal
print('SLL removal: O(n) — must find predecessor by traversal')
print('DLL removal: O(1) — node.prev is immediately available')
print('Hash map lookup: O(1) — get DNode reference by key')
print('Combined LRU get/put: O(1) average')Кэш LFU (используемый реже всего)
Более сложный вариант — кэш LFU (LeetCode 460), в котором вытесняется элемент с наименьшим количеством обращений. При равенстве частот приоритет определяется давностью использования: вытесняется наименее недавно использованный элемент среди наименее часто используемых. Реализация требует трёх структур данных: отображения «ключ — значение», отображения «ключ — частота» и отображения «частота — OrderedDict» для сохранения порядка вставки внутри каждой группы частот. Операции LFU get и put выполняются за амортизированное O(1).
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.min_f = 0
self.kv = {} # key -> val
self.kf = {} # key -> freq
self.fk = defaultdict(OrderedDict) # freq -> {key: None}
def _touch(self, key):
f = self.kf[key]
self.kf[key] = f + 1
del self.fk[f][key]
if not self.fk[f] and f == self.min_f:
self.min_f += 1
self.fk[f+1][key] = None
def get(self, key):
if key not in self.kv:
return -1
self._touch(key)
return self.kv[key]
def put(self, key, val):
if self.cap == 0: return
if key in self.kv:
self.kv[key] = val
self._touch(key)
else:
if len(self.kv) == self.cap:
lfu_key, _ = self.fk[self.min_f].popitem(last=False)
del self.kv[lfu_key]; del self.kf[lfu_key]
self.kv[key] = val; self.kf[key] = 1
self.fk[1][key] = None; self.min_f = 1Шаблоны проектирования: хеш-таблица + связный список
Кэш LRU иллюстрирует мощный шаблон проектирования: объединяйте хеш-таблицу для поиска по ключу за O(1) со связным списком для упорядоченных операций за O(1). Этот шаблон встречается в нескольких задачах на проектирование, которые задают на собеседованиях: кэш LRU, кэш LFU, списки с пропусками и некоторые варианты очередей. Всякий раз, когда задаче нужны одновременно поиск за O(1) и операции с порядком за O(1), рассматривайте эту комбинацию.
На собеседовании явное описание этого шаблона демонстрирует системное мышление и знакомство с классическими сочетаниями структур данных.
Последовательность последовательных чисел в матрице
Расширение идеи последовательных чисел на двумерный случай: получив матрицу целых чисел, найдите длину самой длинной последовательности последовательных чисел, которую можно проследить, переходя на каждом шаге в соседнюю ячейку. Здесь сочетаются BFS/DFS и подход с множеством для поиска последовательных чисел. Сохраните позицию каждого значения, а затем для каждого начального значения проверяйте, существует ли значение value+1 среди соседей.
# Simpler: find longest consecutive values in a 2D matrix (no adjacency)
def longestConsecutiveMatrix(matrix):
all_vals = set()
for row in matrix:
for v in row:
all_vals.add(v)
best = 0
for v in all_vals:
if v - 1 not in all_vals: # start of sequence
length = 0
while v in all_vals:
v += 1
length += 1
best = max(best, length)
return best
m = [[1, 5, 3], [4, 6, 2], [8, 7, 9]]
print(longestConsecutiveMatrix(m)) # 9 (1..9 all present)Итоги для собеседования: возможности множества и HashMap
Эти две задачи объединяет одна идея: преобразование задач со сложностью O(n log n) или O(n)² в задачи со сложностью O(n) с помощью подходящей хеш-структуры. Задача о самой длинной последовательности последовательных чисел использует множество, чтобы проверять наличие предшествующего числа за O(1). Кэш LRU использует хеш-таблицу для мгновенного поиска узла и двусвязный список для обновления порядка за O(1). В обоих случаях медленный обход заменяется проверкой наличия или поиском за O(1).
Когда интервьюер спрашивает: «Можно ли сделать это лучше, чем за O(n log n)?», почти всегда отвечайте: «Используйте хеш-таблицу или хеш-множество, чтобы избежать сортировки».
Быстрая проверка
Проверьте, насколько хорошо вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали: самая длинная последовательность последовательных чисел решается за O(n) благодаря множеству для проверки наличия за O(1) и началу подсчёта только с начал последовательностей, кэш LRU обеспечивает операции get и put за O(1) с помощью OrderedDict (или хеш-таблицы и двусвязного списка при реализации с нуля), а шаблон «хеш-таблица + связный список» служит повторно используемым строительным блоком для структур данных с чувствительным к порядку доступом за O(1). Далее мы вернёмся к рекурсии и разберём базовый случай, доверие и построение решения.
Часто задаваемые вопросы
Урок «Самая длинная последовательность и кэш LRU» бесплатный?
Да — полный текст урока «Самая длинная последовательность и кэш LRU» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Самая длинная последовательность и кэш LRU»?
Решите задачу longest-consecutive-sequence за O(n) с помощью множества, а затем спроектируйте кэш LRU, используя OrderedDict Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Самая длинная последовательность и кэш LRU»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Внутреннее устройство хеш-функций и обработка коллизий
- Два слагаемых и множество вариантов
- Подсчёт частот и группировка
- Самая длинная последовательность и кэш LRU