Code Challenges

Один из вопросов, которые я часто задаю на собеседованиях, - это разработка библиотеки обработки логов: Вам нужно написать библиотеку для обработки логов в следующем формате: метка_времени<TAB>сообщение Библиотека будет передана другой команде для дальнейшей поддержки и улучшений, поэтому поддерживаемость и расширяемость являются самыми важными требованиями. Библиотека должна поддерживать следующие операции “из коробки”: фильтрация подсчет гистограммы Первоначальная версия также включала некоторые языковые и фоновые особенности, которые я никогда не включаю в свою оценку, потому что считаю, что они ставят кандидата в положение, когда ему нужно угадать мои ожидания. ...

Один из вопросов, который я действительно люблю задавать во время кодовых собеседований, звучит так: Дан непрерывный поток слов, словарь на диске и стоимость чтения с диска, создайте потоковый процессор, который возвращает true, когда слово существует в словаре, при этом минимизируя затраты на чтение с диска. Пример: Словарь: {Собака, Кошка, Птица, Лев, ...} Входные данные: [Собака, Кошка, Агхд, ...] Выходные данные: [True, True, False, ...] Выходные данные true, true, false, потому что “собака” и “кошка” существуют в словаре слов, а “Агхд” не считается словом. ...

На моих собеседованиях по программированию я часто использую упрощенную версию этой задачи с Leetcode. Даны две строки s и p, вернуть true, если s содержит анаграмму p. Мне нравится эта задача, потому что решение можно постепенно улучшать, и есть много чего обсудить. От алгоритмической сложности до оптимизации на уровне кэша процессора. Здесь я хочу рассказать, как решил эту задачу в первый раз. Самое затратное решение Первое решение, которое приходит в голову: давайте создадим список всех возможных анаграмм, а затем просто проверим, есть ли одна из них в строке s. Звучит просто, не так ли? Но есть несколько проблем с этим подходом. Во-первых, реализация эффективного алгоритма для генерации всех возможных перестановок уже является достаточно сложной задачей. А во-вторых, временная сложность итогового решения будет примерно O(s*p!). Факториал растет очень быстро: 3! == 6, 5! == 120, 10! == 3,628,800, и вы не захотите с этим иметь дело. ...