> Какая структура данных подходит для хранения количества букв в строках при проверке анаграмм (Kotlin, Android)

Короткий ответ

Для проверки анаграмм оптимальна hash-таблица (в Kotlin - HashMap<Char, Int> или IntArray фиксированного размера для ASCII). Она даёт O(n) по времени и O(1) по памяти для фиксированного алфавита. Альтернатива - сортировка строк, но это O(n log n). Для мобильных приложений с ограниченными ресурсами hash-таблица предпочтительнее, так как не требует дополнительной аллокации при использовании IntArray.

Подробное объяснение

Основная задача - сравнить частотное распределение символов в двух строках. Подходят три подхода:

1. HashMap<Char, Int> - универсален для Unicode, но имеет overhead на boxing и hash-вычисления.
2. IntArray(26) - для английского алфавита, максимально быстрый и компактный, но требует маппинга символов в индексы.
3. Сортировка строк - проще в реализации, но неэффективна для длинных строк.

Для Android-приложений критична производительность на слабых устройствах. IntArray выигрывает за счёт отсутствия аллокаций и кэш-локальности. Для Unicode (например, кириллицы) потребуется HashMap, но можно использовать IntArray с размером 65536 для BMP-символов.

Trade-off: HashMap гибче, IntArray быстрее. Выбор зависит от предполагаемого алфавита и требований к памяти.

На практике

В Android-проектах обычно работают с пользовательским вводом, где строки короткие. Поэтому разница между O(n) и O(n log n) незначительна, но важна консистентность подхода. Если приложение поддерживает мультиязычность - используйте HashMap, иначе IntArray.

Также учитывайте, что String в Kotlin - это UTF-16, поэтому для корректной работы с эмодзи или редкими символами нужна нормализация (например, codePoints()).

Пример кода

// Для ASCII/латиницы
fun isAnagramWithIntArray(s1: String, s2: String): Boolean {
    if (s1.length != s2.length) return false
    val counts = IntArray(26)
    for (i in s1.indices) {
        counts[s1[i] - 'a']++
        counts[s2[i] - 'a']--
    }
    return counts.all { it == 0 }
}

// Для Unicode
fun isAnagramWithHashMap(s1: String, s2: String): Boolean {
    if (s1.length != s2.length) return false
    val counts = HashMap<Char, Int>()
    s1.forEach { counts[it] = (counts[it] ?: 0) + 1 }
    s2.forEach { counts[it] = (counts[it] ?: 0) - 1 }
    return counts.values.all { it == 0 }
}

Как отвечать на собеседовании

Начните с уточнения контекста: какой алфавит, какой размер строк, требования к памяти. Затем предложите два варианта и объясните trade-off. Покажите, что понимаете ограничения Kotlin/Android: boxing, аллокации, производительность на слабых устройствах. Упомяните edge cases: разная длина, пробелы, регистр, Unicode-нормализация.

Хороший ответ - это не просто выбор структуры, а демонстрация системного мышления: оценка сложности, памяти, читаемости и поддержки.

Что проверяет интервьюер

• Понимание базовых структур данных и их сложности.
• Умение принимать решения с учётом контекста (мобильная платформа).
• Знание особенностей Kotlin: HashMap с nullable-значениями, IntArray vs Array<Int>.
• Внимание к деталям: обработка регистра, пробелов, Unicode.
• Способность объяснить trade-off и обосновать выбор.

Типичные ошибки

• Предложение сортировки без анализа сложности.
• Использование HashMap для ASCII без объяснения, почему это хуже IntArray.
• Игнорирование проверки длины строк - ранний выход экономит ресурсы.
• Забывают про регистр и пробелы: "Анаграмма" и "аНаграмма" - это разные строки, если не нормализовать.
• Использование groupingBy и eachCount без понимания, что это создаёт лишние коллекции.
• Не учитывают, что String.length в Kotlin считает UTF-16 code units, а не символы - для эмодзи это ломает логику.