BACK TO BLOG
Мой неожиданный фейл с LinkedList
В LeetCode есть ряд задач типа «Design a data structure» (622. Design Circular Queue, 706. Design HashMap и т. д.).
Пока готовилась к собесам, решала подобные задачи и получалось укладываться в свои 45 минут. Пока не попробовала решить 707. Design LinkedList.
Основной код я набросала примерно за минут 20, уверенно жму «Submit» и… фейл. Тесты не прошли. Поправила и теперь падает на других кейсах. Проходит час. Потом полтора. Нервничаю, начинаю путаться. Понимаю, что если бы это был настоящий собес, то давно бы завалила. Паника. В итоге только спустя 2,5 часа я смогла наконец-то засабмитить рабочее решение.
Как так?! Всего-то нужно было написать несколько методов для linkedlist. Теорию я вроде прочитала, поняла. Это ведь не деревья или графы. Должно быть тривиальным.
Позже, когда я начала читать разборы и смотреть комментарии, оказалось, я не одна. И есть статистика, которая это подтверждает.
У LeetCode есть метрика под названием Acceptance rate. Это процент правильных ответов от общего числа попыток.
705. Design HashSet: 67.3%
622. Design Circular Queue: 53.0%
706. Design HashMap: 66.1%
225. Implement Stack using Queues: 68.3%
641. Design Circular Deque: 64.4%
355. Design Twitter: 43.4% (задача на системный дизайн)
А теперь как думаете, сколько у 707. Design Linked List?
29.4%!
Почему?
Причина 1. Нужно вручную управлять указателями next (иногда и prev), и очень легко ошибиться.
Причина 2. Edge cases есть в каждом методе, иногда по несколько.
Причина 3. Разная логика проверки индексов в разных методах.
Причина 4. Нужны нестандартные виды обхода linked list: indexed, penultimate и sentinel-based (для оптимизации).
Причина 5. Если что-то забыть, то linked list не бросает exception, а ведёт себя неожиданно, усложняя отладку.
Всё это похоже на поход по минному полю: забыли обновить один pointer и всё сломалось, не продумали edge case и взрыв.
Что помогло?
1. Разделила задачу на маленькие логические части.
2. Взяла бумагу и карандаш: рисовала и проверяла каждый шаг алгоритма.
3. Продумала основные edge cases: пустой список, один элемент и полный список.
4. Только потом приступила к коду.
5. Не торопилась, фокусировалась на закреплении.
В задачах на linked list дольше рисуешь, чем кодируешь.
Совет
Для начала хорошо овладейте вот этими техниками для singly и doubly linked list:
1. Indexed и penultimate traversal
2. Insert at head/tail
3. Insert between
4. Delete head/tail и delete between
Начать можно с этих задач:
Особенно важна логика проверки edge cases в этих техниках.
После всех этих шагов, дней через 3–4, я снова попробовала решить 707 и на этот раз справилась за 28 минут. Хоть я и удовлетворена, но претензии всё ещё остались. Кто вообще дал право Linked List, ещё и линейной структуре, меня так мучать?
Не дайте Linked List вас травмировать. Освойте паттерны и техники и берегите своё ментальное здоровье.
