Алгоритмы с нуля
Списки, стеки, очереди: свободное припоминание
Припоминание сильнее перечитывания. На каждый промпт проговори или запиши полный ответ по памяти, прежде чем открыть модельный — именно усилие припоминания закрепляет юнит.
Восстанови хребет юнита — почему linked list меняет индексацию на вставку в голову, как разворот и tortoise-and-hare манипулируют pointer, почему stack и queue — это дисциплины, а не структуры, и почему monotonic stack линеен — не подглядывая в уроки.
- 01Почему доступ по индексу — O(n) у linked list, но O(1) у массива, и что linked list получает взамен?
- 02Пройди in-place разворот singly linked list. Какое одно движение pointer нельзя пропускать и каковы стоимости по времени и памяти?
- 03Объясни технику fast-and-slow (tortoise-and-hare). Почему pointer обязаны встретиться внутри цикла и почему ровно два шага у быстрого?
- 04И stack, и queue можно реализовать на массиве или linked list. Так что же на самом деле их различает и как выбирать между ними под задачу?
- 05Что такое deque и почему dequeue у FIFO queue через наивный shift массива тихо рушит производительность?
- 06Опиши monotonic stack и паттерн next-greater-element. Почему он O(n) несмотря на цикл внутри цикла?
Если ты смог восстановить каждый ответ по памяти, ты держишь хребет юнита: linked list меняет O(1)-индексацию на O(1)-вставку в голову, потому что разбросанность требует обхода; разворот и tortoise-and-hare — это дисциплинированные танцы pointer, где ты сохраняешь связи до перезаписи; stack и queue — дисциплины LIFO/FIFO, которые выбираешь по нужному порядку и никогда не делаешь dequeue через shift; а monotonic stack превращает O(n^2)-скан в O(n) по инварианту push-once/pop-once.