Алгоритмы с нуля
Хеширование: тренажёр для собеседований
Хеширование ты понимаешь. Собеседование проверяет, сможешь ли ты потянуться за hash map под таймером, вхолодную, и вслух объяснить стоимость.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Шесть задач из NeetCode-150 на приём arrays-hashing из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/6 решено
arrays hashing
Follow-up (вслух)
Проговори, почему это O(n) по времени и O(n) по памяти, и что изменится, если массив уже отсортирован.
Follow-up (вслух)
Когда фиксированный массив длины 26 строго лучше hash map здесь и как ввод в Unicode сломает это допущение?
Follow-up (вслух)
Сравни два варианта ключа: сортировка слова — O(k log k), сигнатура счётчиков — O(k). Почему сортировка всё же может быть предпочтительнее?
Follow-up (вслух)
Назови сложность подхода с heap против bucket-подхода и когда heap на самом деле умнее.
Follow-up (вслух)
Почему это O(1) по времени и памяти для фиксированной доски 9×9 и как изменится оценка для доски n×n?
Follow-up (вслух)
Защити оценку O(n): внутренний while выглядит вложенным, так почему общая работа всё же линейна?
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.