Особенности Kotlin в алгоритмических задачах
Вопрос
Какие особенности Kotlin и JVM ты учитываешь, когда решаешь алгоритмические задачи?
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Быстрый ввод-вывод: BufferedReader, StringTokenizer, StringBuilder
Переполнение Int молчаливое, суммы в Long
Примитивные массивы вместо Array<Int> и списков
Стек вызовов ограничен, глубокая рекурсия падает
ArrayDeque, PriorityQueue, TreeMap из коробки
Импорт java.util.* подменяет ArrayDeque
Что могут спросить следом
- Почему
List<Int>медленнееIntArray? - Как написать max-кучу?
Разбор
На JVM главные грабли не в алгоритме, а в мелочах. Ввод читаю через BufferedReader и StringTokenizer, вывод собираю в StringBuilder, иначе на сотнях тысяч чисел можно не уложиться в лимит. Int переполняется молча, поэтому все суммы, произведения и расстояния сразу делаю Long, а литералы пишу с L. Для больших объёмов беру IntArray и LongArray: List<Int> хранит упакованные объекты, это и память, и кеш-промахи. Стек потока ограничен, рекурсивный DFS на цепочке из 10^5 вершин упадёт, поэтому обходы пишу итеративно. Из стандартной библиотеки использую ArrayDeque как стек и очередь, PriorityQueue как кучу, TreeMap для поиска ближайшего ключа, groupingBy().eachCount() для частот. И помню мелкую ловушку: import java.util.* подменяет Kotlin ArrayDeque на Java-версию, у которой last() становится линейным.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.