Comments 170
никогда не видел раньше O(1), что тут подразумевается, О(n)?
Это означает, что сложность алгоритма не зависит от размера входных данных. Это не означает, что алгоритм быстрый, это просто означает, что какого размера не были бы данными, время работы/размер дополнительной памяти алгоритма будет всегда одинаковым (грубо говоря).
Тут есть про это: https://ru.wikipedia.org/wiki/Временная_сложность_алгоритма
есть пример реальной задачи со сложностью О(1)?
получать что-то из какого-то массива не предлагать (с)
т.е. чтобы была реальная задача и её общий алгоритм был прям труЪ О(1), а не О(n).
я что-то ничего придумать не смог пока.
Обычно это что-то прямо связанное с математикой. Например поиск суммы членов геометрической прогрессии. Можно посчитать за O(n), можно взять готовую формулу O(1). Ну и, понятное дело, в самой задаче ничего про прогрессию не будет сказано. Там будет какая-нибудь история, где прогрессия будет правильным ответов.
Вам O(1) по памяти или по времени?
По памяти (как в статье) - полно: поиск максимума в массиве, поиск двух одинаковых элементов в двух массивах можно сделать за O(n^2) по времени и O(1) по памяти. Ещё такое можно, например, нам дают массив из n элементов (n от 1 до 10^9), но сами элементы от 1 до 100. Нам надо уметь очень быстро отвечать на запросы вида "сколько элементов в этом массиве меньше или равны x". Можно отсортировать массив и отвечать за log (n), а можно собрать массив count[i]: где i - это количество сколько раз элемент встретился в массиве, а потом предподсчитать префиксную сумму count[i] = count[i] + count[i - 1]. Тогда в каждом count[i] будет ответ на вопрос сколько элементов в массиве меньших чем i. В этом алгоритме его сложность по памяти совершенно не зависит от того какой длины входной массив - мы всегда выделяем массив из 100 элементов. Это тоже O(1) по памяти.
По времени тоже можно подобрать. Тут вопрос спекулятивный. Есть люди, считающие что даже сложение чисел в процессоре не O(1). В голову пришёл пример - сколько дней прошло от одной даты до другой - там O(1) по времени.
получать что-то из какого-то массива не предлагать (с)
Что значит, не предлагать? А давайте сравним связанный список, массив и их стоимость операций вставки, изменения, доступа, поиска. Получить случайный элемент массива - O(1), получить случайный элемент связанного списка - O(n), но вот вставить дополнительный элемент в самое начало списка - O(1) для связанного списка, и O(N) для массива. И так далее - O(1) при анализе контейнеров встречается повсеместно. Когда вы выбираете какие-то структуры данных для проекта про это нужно помнить.
Кто-то пропустил лекцию про О-большое?
int index = 5;
int item = list[index];
if (условие верно) then
выполнить некоторые операции с постоянным временем работы
else
выполнить некоторые операции с постоянным временем работы
for i = 1 to 100
for j = 1 to 200
выполнить некоторые операции с постоянным временем работытолку от этого похоже немного, т.к. кроме обращения по индексу массива ничего толком нет и это тоже такой себе пример.
кто-то хочет получить хз что из хз какого массива? без всякой обработки этого массива?
а общее время алгоритма будет какой сложностью?
особенно эпичная тут нижняя часть из вики, выполнить лютейший АДЪ вложенных циклов, но в каждом - "некоторые операции с постоянным временем работы".
нам не рассказывали про О(1) и я понимаю теперь почему, толку мало)
на олимпиадах как-то выигрывал всякие мышки/книжки/и т.д., просто в начале 00х призы были не особо большие и как-то обошёлся без этого сакрального знания.
куча макулатуры с дипломами валяется где-то у родителей, надо этот хлам посканить хоть, а то ни разу не пригодился ещё, но чем чЪорт не шутит))
из гордости (чем реально могу гордиться) - сделал оптимизацию одной формы EAV базы, которая занимала около 4мин на 5-10млн записей, я свёл её до 2-3 секунд.
5-10млн уников там означает лютейший треш в самой базе, это прям очень тяжело, особенно как оно работает по умолчанию при поиске по разным полям.
вроде чота понимаю, ну мне так кажется.
Представьте себе статью на Хабре, у которой есть автор, у которого есть аватар. Если положить это реляционную бд, то запрос этих 3 связанных сущностей по идентификатору статьи займёт О(n), где n - размер базы данных. Если добавить индексы, то это добавит O(log n) потребления памяти, но ускорит до O(log n). А если положить в графовую бд с прямыми ссылками между сущностями, то получим как раз O(1) без лишней памяти. То есть время запроса от размера базы не зависит.
Нет, O(n) - сложность (время) прямо зависит от числа элементов.
O(1) - сложность не зависит от числа элементов, является константой.
Пример - получение элемента массива по индексу элемента - сложность O(1).
Пример - родить одного или двух детей за один раз)
там местами можно попридираться ещё сильнее)
Более грамотные специалисты догадываются, что скорость поиска O(1), необходимую для превращения O(n²) в O(n), может обеспечить словарь (Map). Лучшие же кандидаты предусмотрительно отмечают недостаток такого подхода, заключающийся в использовании O(n) памяти. Здесь повышение скорости достигается за счёт увеличенного потребления памяти.
словарь (Map) создать тоже займёт время => супрЫз, общая сложность уже не О(1)
Никто и не говорил, что общая сложность будет O(1). Сказано только что поиск значения по ключу в словаре это O(1). Если вам нужно сделать 100 поисковых операций то это O(1 * n). Т.е. O(n)
Мне кажется, там что-то про константу было. Вроде как ее можно игнорировать, оставляя только n.
Существует простейшее решение, которое выполняется за O(n²) времени, но использует всего O(1) памяти
Такого решения не существует. По видимому имеется ввиду, что данные не загружаются в ОЗУ, а постоянно считываются с жёсткого диска и ответ постоянно же записывается на жёсткий диск. Однако с точки зрения оценки сложности алгоритмов даже использование магнитной ленты машины Тюринга расценивается именно как использование памяти.
И этому дядьке, который провёл 100500 собеседований не к лицу писать такие вещи по O(1) по памяти, когда он по сути использует своп вместо ОЗУ.
Мне кажется просто входные данные не учитываются при оценке сложности по памяти, а учитывается только сложность добавленная имплементацией решения/алгоритма, и она константа и не зависит от входных данных => O(1) памяти
Чтобы хранить выходные данные потребуется O(n) т.к. количество лояльных клиентов в первом приближении линейно зависит от общего числа клиентов n.
Либо на каждом найденном лояльном клиенте сохранять его на диск, что во первых безумие с точки зрения производительности, а во вторых всё равно потребляет O(n) с точки зрения теории сложности алгоритмов.
Список клиентов можно не только записывать, но и читать, тем самым предоставляя O(1) по памяти и докидывает несколько раз n во время, но там всё равно O(n²).
Не уверен, что с O(1) по памяти можно уложиться в O(n²): ведь у нас тогда нет дополнительной памяти для выходных данных, их придётся выплёвывать в условный stdout по очереди. Значит, придётся делать устранение дубликатов.
Даже интересно, какая на самом деле сложность получится. Решение с O(n³) видится с ходу (идём по первому списку, проверяем очередной элемент из него, если он нам подходит – заново проверяем все, что были до него, и если ни один из них не подходит – выдаём в stdout), но, может, можно улучшить?
Конечно, можно улучшить. В первом списке берем любой элемент. Для него проходимся по всему первому списку, чтобы убедиться, что это первое вхождение этого элемента (заодно смотрим, есть ли там 2 различные страницы). Потом проходимся по второму файлу, чтобы убедиться что он и там встречается (и опять же смотрим различные страницы). Достаточно хранить только 2 различные страницы и текущий userid. Сложность будет O(n^2+nm).
Да, действительно. И это, очевидно, предел.
Спасибо!
Ммм а почему вы игнорируете последнее решение из статьи с двумя указателями? В нем данные предварительно отсортированы по пользователю и странице, поэтому для устранения дубликатов в ответе достаточно при обходе каждого из двух списков пропускать идущие подряд одинаковые записи, а при перекрестном поиске не нужно искать по всему второму файлу, а достаточно просто двигать второй указатель, пока не найдется элемент с userID равным искомому или больше. Сложность получается O(n log n) на предварительную сортировку и всего лишь O(n) на обработку, т.к. каждый из двух списков обходится однократно; итоговая будет O(n log n + n) = O(n log n) при константной памяти.
Сортировка за O(n log n) вермени с O(1) дополнительной памяти, по-моему, невозможна. Сортировки внутри одного файла требуют O(log n) памяти, а если какой-нибудь radix sort сделать, то ему нужны дополнительные временные файлы. Что, в общем-то тоже является дополнительной памятью в некотором смысле.
Я тоже засомневался, поэтому полез проверить: можно O(n log n) с константной памятью, просто придется пожертвовать устойчивостью и, возможно, лучшим временем, но, кажется, здесь ни первое не пригодится, ни на втором все равно не выиграть.
Так оно O(n) по памяти (нужно место под отсортированный массив).
Вообще интересная тема, редко с таким сталкиваешься - вот нагуглилась работа, где авторы утверждают, что разработали алгоритм внешней сортировки с O(n log n) по времени, константной RAM-памятью и, похоже, вообще без дополнительного места на диске: надо будет потом попристальнее изучить.
Наткнулся сегодня на leetcode:
however the output does not count towards the space complexity.
И вот такое гуглится легко:
https://cs.stackexchange.com/questions/83574/does-space-complexity-analysis-usually-include-output-space
The space usage is the number of cells used on the working tapes,
so input and output space typically aren't counted.
(See, e.g., Section 2.5 of Papadimitriou.)
References
C.H. Papadimitriou, Computational Complexity. Addison–Wesley, 1992.
часто в оценке памяти не учитываются затраты на хранение как входных, так и выходных (результирующих) данных. то есть интересен именно оверхэд на то, что происходит в "чёрном ящике" нашего алгоритма.
Если специально не уточняется, то под памятью для алгоритмов всегда имеется ввиду именно ОЗУ, потому что раз данные есть, то значит дискового пространства для них хватило совершенно точно :-)
Для чтения требуется О(1), все правильно, и своп для этого не нужен. Просто читаем не каждый раз в новую область памяти, а в одну и ту же.
Завели буфер константного размера, прочитали часть файла в буфер, обработали, в этот же буфер прочитали следующую часть, пока файл не закончился. Памяти на чтение требуется ровно размер буфера, константный объем, не зависящий от размера файла, O(1).
Решал тестовое по подсчету уникальных айпи в 100гиговом тестовом файле, все отрабатывало за время чтения файла, JVM использовала меньше гига оперативы, и то только потому, что 512Мб надо было под флаги уникальности. Своп не использовался совершенно точно. И на диск в процессе я ничего не писал - не было нужды.
И этому дядьке писать про О(1) по памяти к лицу, т.к. он своп вместо ОЗУ не использует.
Upd. n - размер данных, т.е. здесь - число записей в журнале. Записей может быть 10 млрд, а клиентов 1млн, а страниц - 1000. Описанные автором структуры влезут в в условные 100 мб, а 10млрд записей по 100байт - терабайт.
С чего вы взяли, что есть какая-то запись на диск? Механизм может частью пайпа и по мере нахождения новых пользователей их сразу куда-то дальше переправлять, не дожидаясь конца обработки.
мы хотим сгенерировать список «лояльных клиентов»
Исключительно по условию задачи я вижу, что алгоритм должен в итоге выдать список.
Т.е. в результате работы алгоритма должен быть получен список клиентов, а не список IO операций ввода вывода, как предлагаете вы. Это так с точки зрения теории типов. В не очень строго типизированной Java на это особо внимание не обращают, но вот например в Haskell это критично - там компилятор забракует ваш код, т.к. результат работы функции не будет соответствовать её сигнатуре.
А с точки зрения теории сложности я наверное старовер, в том смысле что сложность любого алгоритма оцениваю с точки зрения его теоретической сложности на машине тюринга. И если сказано, что в итоге должен быть получен список лояльных клиентов, то значит, что этот список должен быть в памяти машины по завершению работы, а не в памяти какой то другой машины.
Какие IO операции? Какие другие машины? Опять что-то выдумываете. Это может быть обход генератора или чтение канала данных в том же процессе, просто другим модулем. Вы сами придумали это ограничение, что список должен быть передан полностью законченным, и теперь пытаетесь всех убедить, что автор сам себя не понял и вообще профнепригоден.
С точки зрения ABI задача вообще не описана, поэтому отвечать на рассуждения о компиляторах и теории типов не стану.
Мне кажется вполне реальной ситуация, когда я реализовал этот механизм, собирающий полный список, а в памяти не помещается даже готовый список-ответ, поэтому пришлось, например, потратиться на вертикальное масштабирование. Затем приходит заказчик этой ерунды и спрашивает, почему так долго и дорого, и нельзя ли по частям, мол, ему так было бы проще. А единственным оправданием будет "вы же сказали список, а я это понял так".
Хочу пару цитат из статьи привести:
В реальности инженеры постоянно сталкиваются с неоднозначностью, и корень большинства программных проблем можно найти в плохо определённых требованиях.
Наиболее грамотные кандидаты, прежде чем переходить к написанию кода, должны задавать уточняющие вопросы. Я рассчитываю увидеть в соискателях проявление рассудительности, так как в описанных условиях задачи присутствует двусмысленность.
Чтение канала данных в том же процессе, просто другим модулем это самая настоящая IO операция.
Ладно, не хочу больше продолжать этот теоретический спор, а то мне уже кто то в карму успел минусануть.
Хотя самому мужику из поста я бы много чего мог рассказать, что если уж он подразумевает, что в результате выхода должен быть не список клиентов, а список IO операций, то тогда уж в данном случае идеально походит структура Stream f m r изобретенная относительно недавно Кисилевым, Снойманом и Гонзалесом. Это потрясающая и очень интересная структура, но ну его нафиг с такой благодарной аудиторией, которая минусит от души.
Вы на самом деле подняли интересную тему, но как-то сходу принялись ему возражать.
сложность любого алгоритма оцениваю с точки зрения его теоретической сложности на машине тюринга
Здесь, насколько я помню, есть лента с входными данными для чтения и лента для записи результа. А все что между ними это и есть сам алгоритм - разные аспекты сложности которого мы хотим оценить.
В отношении оценки по памяти нас интересует не объем данных, который мы прочитали-обработали-записали, а сколько памяти нужно компьютеру, чтобы выполнить наш алгоритм. Поэтому то, что находится на лентах мы не считаем.
Автор пишет:
only uses O(1) of memory
Memory это неформальный сленг. В CS обычно говорят про Space Complexity и Auxiliary Space Complexity. Первая характеризует общий объем, который требуется алгоритму, включая и входные переменные. Вторая - только объем дополнительных переменных (которые алгоритм аллоцирует сам). Короче Space = Input + Auxiliary.
we want to generate a list of ‘loyal customers’
Здесь все упирается в то, что он имеет ввиду говоря 'a list' - какой-то абстрактный список или же некую конкретную структуру данных из хаскеля?
Судя по тому, что он дальше пишет про O(1), его интересует лишь дополнительный объем - без учёта входных и выходных данных. В самом деле, они заданы условиями задачи и будут всегда одинаковыми, поэтому при сравнении алгоритмов ими можно пренебречь.
В общем если зачем-то очень хочется, то дядьку можно упрекнуть в некоторой нестрогости изложения. Но с другой стороны, это публицистика, а не научная статья, чтобы устраивать ему за это вендетту.
O(1) дополнительной памяти, сами исходные данные он не оценивает и в этом есть смысл.
Какой своп? Мы раз за разом перечитываем исходные данные, они не включаются в оценку расхода памяти.
ЗЫ: но в O(n²) по времени, вроде, так просто не уложиться, надо же ещё дубликаты убирать...
"карта"? м.б. лучше оставить map?
Перевести map как карта в этом контексте - это насилие над здравым смыслом
Если уж так хочется перевести, то можно использовать давно устоявшийся в определённых кругах "словарь", имхо.
Почему?
Логика, по которой и карта и структура данных называется в английском одним и тем же словом map, имеет смысл. Map - это отображение 1 к 1 одного множества на другое. Каждая точка на карте отображается на точку реальной местности.
Слово set можно перевести на русский около 100 способами. Но это не значит, что надо в статьях по программированию переводить set как "закат" или "брусчатка".
Каждая точка на карте отображается на точку реальной местности.
Учитывая физические ограничения карты, одной точке соответствует не точка, а некая площадь, так что это не совсем честная биекция.
Фильтр "клиент посетил сайт в первый и второй день" выдаст ложно-положительное срабатывание на клиентах, заходящих на сайт незадолго до полуночи. То есть если в 23:59:59 будет запрошена одна страница а в 00:00:01 вторая, что такой клиент автоматически будет считаться таким же лояльным, как и клиент, заходивший на сайт два дня подряд в обеденный перерыв.
Да, но не надо усложнять... Как доп. вопрос хороший!
... Тогда надо будет добавить ещё условие на то чтобы между запросами было... Не меньше четырех-шести-восьми часов )) Смотря сколько кто спит. Хотя конкретно ваша проблема отсеивается буквально считанными минутами-десятками. Но по духу условия надо чтобы человек посетитель поспал между запросами ))
а помоему это реально клиент заходивший на сайт два дня подряд. Абсолютно честно
А я бы объединил файлы и сортировал как один массив. Тогда достаточно одного указателя плюс хранение предыдущего состояния (ну или два указателя, смещённых относительно друг друга на одну позицию) плюс битовый флаг смены даты и адреса страницы..
А я бы объединил файлы и сортировал как один массив.
А сортировать-то зачем? Не проще сделать почти плотный массив, вычисляя там номер записи по CustomerID? Тогда заполнение массива (со слиянием двух журналов) делается за один проход, а обработка - тем более...
Не совсем понятно про
вычисляя там номер записи по CustomerID
В общем случае это может быть хоть GUID, хоть ObjectID какой-нибудь
Ну да, для этого нужна будет отдельная функция, адаптированная к стилю назначения CustomerID. В худшем случае (если логика в значениях CustomerID не просматривается), и есть риск получить кучу коллизий в хэш-таблице, то придется что-то изобрести, чтобы их как-то минимизировать. Но все равно это О(1).
А обратная функция и вовсе бесплатна практически, т.к. исходное значение CustomerID мы запишем в структуру с его историей, которая намного больше в размере.
Если уже идти во все тяжкие оптимизации, то зачем вообще держать множества для страниц?
Можно обойтись простым <userId>: <string>. При этом не пустое значение будет означать, что у пользователем посещена только эта страница. А пустое значение - признак посещения более одной страницы. Т.е.
Первый день:
Если пользователя (ключа) нет в коллекции, то добавить туда вместе со значением страницы
Если пользователь есть, и значение страницы пустое, то пропустить.
Если пользователь есть, и значение страницы не совпадает с текущим, то заменить его на пустоту.
Второй день:
Если пользователь есть, и у него либо пустая строка (признак), либо строка не совпадает - то это лояльный пользователь.
Только не надо строку. Если тип ID уже не строка. Это удар по производительности и памяти. Часто ID позволяют выделить спец. значение, например если тип ID это int, а отрицательных в данных не бывает. Или если ID это GUID то можно использовать любой случайный для флага.
Существует риск совместимости с будущими изменениями. Например разрешили любые целые значения. Тогда лучше завести отдельный флаг или использовать алгебраический тип, если язык позволяет.
Только не надо строку. Если тип ID уже не строка. Это удар по производительности и памяти. Часто ID позволяют выделить спец. значение, например если тип ID это int, а отрицательных в данных не бывает. Или если ID это GUID то можно использовать любой случайный для флага.
Хорошо Вы живете ;-)
А я вот научный сотрудник, и сплошь и рядом получаю файлы с чужими рядами данных. Так у меня уже в подкорке зашито, что в чужом файле надо быть готовым к чему угодно. Не важно, что там в доках написано. Особенно если с данными на каком-то этапе поработали в Excell (тогда вообще жди беды на каждом углу). Хотя и журналы вряд ли существенно в лучшую сторону отличаются, так как туда обычно много всякого разного пишется, и нужные строчки не всегда можно очевидным образом отобрать.
Поэтому у меня уже рефлекс выработался: сначала все читать в string. И только потом, после проверки и разбора, конвертировать во что-то более адекватное типа чисел. С чем уже можно более-менее эффективно работать.
Хотя возможно, что это у меня просто профдеформация, так как я пишу на фортране, и без такого анализа я даже адекватную диагностику не смогу получить: в какой именно строке, в какой позиции и что именно вызвало подозрения. Фортран ведь всеядный, и если какой-то фрагмент строки можно в число превратить, то он разбираться не станет - просто прочитает, и все. А если нельзя, то еще хуже - выдаст ошибку, и тоже все. Поэтому проверять данные на соответствие каким-то требованиям мне приходится самому. Чтобы потом не тупить недоуменно над результатами из-за того, что в каком-то месте исходника точка поменялась на запятую, или наоборот...
Это отличная идея с точки зрения технической оптимизации, но она обладает фундаментальным недостатком, а именно: если завтра критерий лояльности изменится с "посетил 2 страницы" на "посетил 3 страницы", то вам придется переписывать примерно все.
То есть подобную оптимизацию можно проводить, только трижды согласовав проблему с бизнесом: а нам точно-точно всегда-всегда будет достаточно двух страниц как критерия лояльности? Из моего опыта, даже если менеджер отвечает "точно да" на этот вопрос, верить ему не стоит, т.к. он банально не понимает жизни.
только трижды согласовав проблему с бизнесом: а нам точно-точно всегда-всегда будет достаточно двух страниц как критерия лояльности
вам ответят "да", а после релиза попросят сделать 3 страницы, ибо "ну теперь вот видно, что 2 страницы мало")))
Это точно!) Я вообще больше рофлил, чем пытался дать ценный совет. Эти "любимые задачки" от глубоко окопавшихся в конторе сансеев всегда обрастают таким искусственным налетом, что сложно их воспринимать как реальные кейсы. Решать с закосом под продакшен или под спортивное программирование? Выбор похож на две чашки с ядом, к которому у собеседующего уже отличный иммунитет.
Насколько я понимаю, самым "устойчивым", т.е. потенциально готовым к изменению условий, решением будет самое простое: использовать единственный Map<userId, Info>, где в Info собирать стату по юзеру, и добавлять в массив результатов userId, только если на данной итерации стата достигла требуемого условия. Так мы заодно исключаем дублирование userId в массиве результатов и делаем всё за один цикл.
И мапа, и два указателя с предварительной сортировкой довольно устойчивы к изменению условий.
Надо три страницы - делается 3. Надо 2 в один день и 3-ю в другой - тоже делается.
И код будет не сильно длиннее текстового описания задачи
Ну так перепишем. Тоже мне новость, ситуация изменилась или умники какие-то нашли как программу лояльности обмануть. Через год это случится практически неизбежно; если сервис написан и забыт на долгое время, то скорее всего он или никому не нужен, или через полгодика рванёт из-за каких-то внутренних причин.
Но если записей много в журнале, будет переполнение памяти. А если у нас всего 640к оперативки? По заветам разработчиков DOS. Тогда берем и переписываем исходный файл на маленькие файлы, пока они не станут помещаться в памяти. Условно пользователи с именами начинающимися на А-Д в файл 0001.TXT, пользователи с именами Е-К в файл 0002.TXT и так далее (правильней по хешу, но так нагляднее). Если файлы большие еще режем на кусочки и далее обрабатываем по вашему алгоритму или сортировкой. То есть вместо одной большой базы в виде текстового на гигабайты данных у нас остается много маленьких файлов, вплоть до 1 файла на пользователя если памяти вообще мало и их быстро обрабатываем.
640кб оперативки? Не, это слишком по-богатому. Не забывайте, мы в космосе! В нашем распоряжении бесконечное количество магнитных бобин, но оперативки завезли только на 1к, для просмотра сайтов. Файлы с логами в формате "USER_ID:URL\n" (1 символ - 1 байт). Поэтому
Первый день:
Открываем поток на чтение файла первого дня
Не спеша читаем ид пользователя (пока не дойдем до знака ":")
Проверяем, если файла "1-USER_ID" не существует, то создаем поток на запись этого файла и побайтово записываем туда урл (пока не дойдем до знака "\n")
Если файл есть и он пустой, то пропускаем
Если файл есть и он не пустой, то открываем еще один поток на его чтение и побайтово читаем с двух потоков до первого отличия, и если такое находится - делаем файл пустым.
День второй:
По аналогии читаем файл 2-го дня, получив ид пользователя, проверяем файл "1-USER_ID", если файл есть и он пустой, либо его содержимое не совпадает - то это лояльный пользователь. Удаляем файл 1-USER_ID и мигаем светодиодом два раза.
мне кажется неуместно использовать слово "карта", тут или писать "словарь" или "хеш-таблица" или на худой конец писать "Map()", насколько я понимаю это специфичное что-то или для джавы или для питона?
Возможно я плохо выспался или плохо прочитал условие. Но чем плох вариант с `Map<CustomerId, PageId>` без всяких вложенных Set-ов и Map-ов? Просто сверяем PageId в Map и PageId в итерируемой записи. Если они не равны - перед нами посещение двух уникальных страниц. Чего ещё нужно?
Псевдокод на TS:
type TRecord = {
userId: number,
// timestamp: number, not needed
pageId: number;
}
const getLoyalUsers = (f1: TRecord[], f2: TRecord[]): number[] => {
const users1 = new Set<number>(f1.map(f => f.userId)); // O(n)
const users2 = new Set<number>(f2.map(f => f.userId)); // O(n);
const pagesSeen = new Map<number, number>(); // UserId -> PageId
const candidates = new Set<number>();
for (const list of [f1, f2]) { // O(n)
for (const r of list) {
if (pagesSeen.has(r.userId)) {
if (pagesSeen.get(r.userId) !== r.pageId)
candidates.add(r.userId); // seen 2 uniq pages
} else {
pagesSeen.set(r.userId, r.pageId); // 1st visit
}
}
}
return [...candidates].filter(userId =>
// check the user was active in both days
users1.has(userId) && users2.has(userId)); // O(n)
}Добавлю ссылку на свой же коммент на эту тему, но в другой ветке
через count min sketch тут никак не оптимизировать?
Удивительное по-прежнему рядом. Насколько я могу судить - это задачка уровня easy на leetcode. Если бы мне предложили ее, то я бы именно так ее и воспринял и сходу наколотил бы что-то подобно тому, что под спойлером.
Спойлер
# O(n) - time complexity
# O(n) - space complexity
day1 = [
{"t": 10, "page": 1, "user": 1},
{"t": 11, "page": 2, "user": 3},
{"t": 12, "page": 1, "user": 4},
{"t": 13, "page": 1, "user": 5},
{"t": 14, "page": 2, "user": 6},
{"t": 15, "page": 2, "user": 7},
]
day2 = [
{"t": 10, "page": 1, "user": 3},
{"t": 11, "page": 2, "user": 7},
{"t": 12, "page": 1, "user": 8},
{"t": 13, "page": 1, "user": 1},
{"t": 14, "page": 2, "user": 3},
{"t": 15, "page": 2, "user": 2},
]
users = {}
for d, day in enumerate([day1, day2]):
for record in day:
user = record["user"]
page = record["page"]
if user in users:
users[user]["days"].add(d)
users[user]["pages"].add(page)
else:
users[user] = {"days": set([d]), "pages": set([page])}
for user in users:
if len(users[user]["days"]) == 2 and (len(users[user]["pages"]) >= 2):
print(f'userId={user}', users[user])Не так давно видел предложение о многоуровневом собеседовании, на котором обещались задачки уровня hard, и это далеко не Amazon, Google и даже Microsoft.
Не, тут хешмап надо применить правильно, так что это medium как минимум. А так у вас почти такое же решение как и у автора. У вас тоже мап из userid в список страниц.
Тут оверхед - зачем накапливать страницы в users[user] когда после двух уже ясно, что результат для юзера достигнут?
Я прямо растерялся. Но попробую ответить. Я думаю, что при решении подобного рода задач не стоит гнаться за микрооптимизацией, которая то-ли случится, то-ли нет (у нас нет никаких дополнительных сведений о данных). К тому же, о такого рода оптимизации в формулировке задачи нет ни единого намека. При решении такого рода задач стремятся получить приемлемую сложность "О-большое", и при этом было бы очень желательно, чтобы реализация выглядела "лаконично" и понятно. Было бы здорово, если бы реализация допускала легкую модификацию при небольшом изменении входных данных. Например, у нас данные были бы не за 2 дня, а за 17. И "лояльным" пользователем следовало бы считать того, кто посещал не все дни, а хотя бы 8 из 17, и посмотрел за это время хотя бы 25 уникальных статей. Думаю, что предложенное мной решение в целом удовлетворяет требованиям, которые я перечислил выше. Ну и стоит сделать поправку на то, что я приступил к решению задачи, стараясь решить ее как можно быстрее и проще, имея при этом приемлемое значение "О-большое", так, как я бы делал это на собеседовании. Должен заметить, что я сначала я даже не стал читать комментариев автора, мне хватило условия задачи, оно показалось мне вполне понятным и достаточно определенным для того, чтобы можно было приступить к решению. А для любой микрооптимизации нужны веские основания и глубокое погружение в проблему, вряд ли стоит углубляться в это дело на собеседовании по собственной инициативе. Можно легко самого себя закопать, если начать придумывать себе проблемы на пустом месте. Но я не настаиваю, если вы способны предусмотреть всевозможные нюансы, убедительно объяснить необходимость их учета, и мастерски разрешить их прямо во время собеседования, то конечно, вы будете иметь преимущество.
Так фишка то в том, что оценивается не столько итоговый код, сколько путь к нему. Насколько кандидат умеет рассуждать, оценивать достоинства и недостатки и выбирать решение исходя из них.
Тут вся прелесь в том, что если кандидат слабый, то его можно дотянуть до ответа и это будет не такой большой стресс. А если кандидат сильный, то можно задачу и до real time mapreduce расширить.
Тоже первое что пришло в голову: слить и отсортировать оба файла при чтении в память раз "влезают".Дальше всё тупо.
N log N. Многовато :)
Зато решение элементарное и поддерживаемое. Если объемы такие, что сортировка за час отрабатывает, то может оно и хорошо: на фоне дискретности в 24 часа 1 час погоды не сделает.
Если кандидат просто посортировал, то это уровень младшего разработчика. Если объяснил почему так сделал и при каких условиях это оптимальный подход - это уже может и старший.
А еще можно неоптимальное но простое решение как оракула в тестах использовать.
мы хотим сгенерировать список «лояльных клиентов», отвечающих следующим критериям: (а) они посещали сайт в первый и второй день, (b) они посетили не менее двух уникальных страниц.
Условие задачи имеет вполне ясное и чёткое ТЗ. Так как ничего не сказано про дни, ничего не сказано про погоду, ничего не сказано про день рождения директора, ничего не сказано про любовницу, то и спрашивать про это здесь выглядит лишним. Часть кандидатов вполне четко и однозначно поняла ТЗ, а спрашивать в условиях стресса глупые уточняющие вопросы могли испугаться чтобы не показаться "тупыми".
1.Имел ли я ввиду посещение двух уникальных страниц в день или всего?
Ну и следующий вопрос не возникает, если про дни ни слова нет. Уникальная страница - она уникальная между всеми днями.
2.Есть ещё один важный уточняющий вопрос, который упускают 90% соискателей: «А как быть с повторами?»
Поэтому первые два уточнения я бы вычеркнул. Насчет использования БД и SQL:
Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
Затем, что такую задачу, как даёт автор никто не ставит. Точнее ставят, но это лишь первый этап (считай детский сад), когда PO только только начинает играть в аналитику.
А дальше буквально сразу пойдут задачи типа: А узнай из каких стран они к нам приходят, а узнай как они вели себя в течение года, а прикрути к ним историю покупок, интересов, разбивку по полу/возрасту/странам/городам/именам итд итп и вот оказывается, что лучше бы ты сразу это всё запихнул в БД, и уже там бы строил все эти отчеты, графики, метрики. И причем тут тебя больше волновала бы структура хранения данных в БД, объёмы данных, механики работы БД, репликация и/или параллельность расчётов (hadoop), потоковая или периодическая(ночная) перекачка данных, итд итп. Поэтому на вопрос:
зачем вносить излишнюю сложность ..для того, что можно решить с помощью всего 20 строк простого кода?
Я бы всё-же подискутировал...
Так как ничего не сказано про дни, ничего не сказано про погоду, ничего не сказано про день рождения директора, ничего не сказано про любовницу, то и спрашивать про это здесь выглядит лишним.
В этом, мне кажется, и стоит основная разница между мышлением олимпиадников и, назовем их, - коммерческих разработчиков.
Первые всецело доверяют постановщику задачи, понимают условие буквально и на этом сильно экономят своё время.
Вторые знают, что бизнес не умеет в буквальные формулировки, и поэтому сомневаются в каждом слове. Но в итоге это экономит деньги.
Оба подхода имеют право на существование, адекватный результат получается только в своем контексте.
проблема здесь в том, что возитесь с бизнесом вы, уточняете, а премию получит любой кроме программера, вы же типа просто сделали своб работу - закодировали, а бизнес мучился, придумывал, творил. Поэтому не сильно понятно зачем выходить за границы своей ответственности.
Зато в олимпиадах, со стороны организаторов, все наоборот. Вы все организуете, придумываете интересные задачи, ищете участников по разным уголкам света, устраиваете мероприятие, и ещё делаете массу разных вещей. А все призы достаются кому-то другому. =)
Если серьезно, я согласен, что вопрос комплексный и его можно рассматривать с разных сторон. Моя позиция здесь - свою работу нужно делать максимально качественно. А если не устраивают компенсации, то менять работодателя.
Сильно зависит от компании и подходов. У меня, например, прямо сейчас премия напрямую зависит от того, сколько пользователей станут пользоваться моим кодом. И у меня довольно большая мотивация чуть подумать, провести 1.5 часа на встречах и отбросить какой-то узкоспециализированный функционал на время после выплаты премий, чтобы сейчас сэкономить себе пару дней его реализации и отполировать какие-то моменты.
У автора стоит задача нанять человека, который будет не тупо писать код. Он хочет человека, который будет держать в уме задачи бизнеса и разумно тратить своё время (и деньги работодателя).
У автора стоит задача нанять человека, который будет не тупо писать код. Он хочет человека, который будет держать в уме задачи бизнеса и разумно тратить своё время (и деньги работодателя).
Ну значит это будет в его должностной инструкции и ему за это будет платиться зарплата. Это его работа и он будет её выполнять. Не вижу противоречий со сказанным ранее.
Но если вы наняли программиста, а хотите от него "и жнец и кузнец и а дуде игрец", то либо получите дилетанта плохо выполняющего свою работу, либо сильную текучесть кадров, так как вы позвали человека делать одно, а требуете другое.
В этом, мне кажется, и стоит основная разница между мышлением олимпиадников и, назовем их, - коммерческих разработчиков.
Глобально в работе это так. Я бы уточнял и спрашивал детали. Но это собеседование, которое больше направленно на алгоритмы, чем не проработку ТЗ. Там прямо в условиях задачи очень технически прописаны условия, что есть такие-то файлы, структура такая-то, надо решить такую-то задачу, и только её.
Если всё-же спрашивать наводящие вопросы и пытаться изначально решить проблему бизнеса (а не просто написать алгоритм), то стоит обсуждать вопрос дальше глубже - а что дальше попросит бизнес, какой будет следующий шаг, нужно ли будет хранить историю, нужно ли будет ещё брать какие-то атрибуты из этого файла, и может это и правда всё засунуть в БД. Вот это всё будет интересовать бизнес на следующем шаге, а вовсе не концентрироваться сейчас и жестко в алгоритме на вопросе "а как считать уникальность страниц".
Но это собеседование, которое больше направленно на алгоритмы, чем не проработку ТЗ. Там прямо в условиях задачи очень технически прописаны условия, что есть такие-то файлы, структура такая-то, надо решить такую-то задачу, и только её.
Автор про это написал, что его в первую очередь интересует как раз диалог, а не код:
The conversation is much more important to me than the actual lines of code my candidate writes on the whiteboard. What tradeoffs exist? How do you balance between them?
...
Great candidates must ask clarifying questions before jumping into coding. I’m hoping to see some intuition from my candidates as I’ve actually expressed the problem in an ambiguous way. Did I mean 2 unique pages per day or overall?
Я тут не спорю с тем, плох ваш подход или хорош. Бывают ситуации, когда именно так и надо поступать. Но в данном случае это ваше допущение, а их нужно всегда проверять.
Да брешет он. Т.е. все так говорят, что главное диалог а не код. Но по факту оффер предлагают только тогда, когда удается все решить. А когда по какой то причине не удается решить, то говорят так "вы хорошо излагаете мысли, и правильно рассуждаете, но вам наверное просто надо попрактиковаться в решении задач".
Map лучше переводить как "ассоциативный массив", а не "карта"
зачем вносить излишнюю сложность ..для того, что можно решить с помощью всего 20 строк простого кода?
Ответ, на мой взгляд, такой: решение, изложенное в статье, пишется за 15 минут и полностью удовлетворяет требованиям, которые есть здесь и сейчас. Когда понадобятся более сложные метрики, такое решение можно просто и относительно безболезненно выкинуть и начать думать в сторону БД.
Не стоит бояться одноразовых решений для конкретных задач. Потому что а) в определённых обстоятельствах всё равно придётся всё переделывать из-за изменившихся требований, и б) выкидывать решение, сделанное за 15 минут не так обидно, как если разработчики потратили месяцы на сложное решение, а бизнесу нужно срочно масштабироваться, а бизнесу нужно масштабироваться вниз.
А дальше буквально сразу пойдут задачи типа
поэтому с точки зрения практики такие данные уезжают в аналитическую БД и оттуда group by/having или аналоги. Это ещё в условии не появились часовые пояса, где надо разбивать сутки и считать "лояльность" и "уникальность" по часовому поясу конкретного юзера.
А задача - чисто на подумать.
Тоже первое что пришло в голову: слить и отсортировать оба файла при чтении в память раз "влезают".Дальше всё тупо.
Я пишу на фортране, поэтому я бы все-таки при чтении журнала :
1) слил два файла в один (т.е. сделал один общий список юзеров) и
2) конвертнул бы при чтении полученный журнал в свой внутренний формат, чтобы вместо строк получить числа и сэкономить память. Тогда каждое посещение страницы упаковывается в 8 байт (ID страницы + время в секундах).
Ну и еще мне нужна будет функция, которая преобразует CustomerId в более-менее плотный массив номеров пользователей. Чтобы без какой-либо сортировки не искать пользователя по файлу, а сразу на него попадать, просто вычисляя номер записи по CustomerId.
Итого у меня получится один массив структур, где элемент (структура) номер P содержит всю историю пользователя номер P (его CustomerId можно там же хранить, чтобы с обратной функцией не заморачиваться). Согласно ТЗ, нам надо хранить историю за два дня, причем критически важны первые две уникальные страницы... но в таком сжатом виде ничего (кроме ограничений памяти) не мешает хранить и более полные данные за более долгий срок, если только сайт не сверхпопулярный. Например, если моей программе доступно 10Гб ОП, то в описанный массив структур можно загнать несколько миллионов юзеров, и для каждого хранить
по сотне номеров страниц с меткой времени
Правда, для гиперактивных пользователей, которые больше сотни страниц посетили, тогда придется сделать отдельную таблицу, и скидывать туда избыточные страницы (сверх первой сотни). Для этого придется добавить в каждую структуру указатель на дополнительный список, который придется использовать при переполнении основной структуры. Со всеми вытекающими траблами (резкое замедление доступа и т.д.). В общем, такой подход будет работать, только если большинству юзеров хватит основного массива (это надо по фактической статистике сайта заранее уточнить - прокатит такой алгоритм, или нет).
Но если хватит - то возможности анализа/обработки расширяются многократно. Так что это уже вопрос к заказчику: планируется ли расширение задачи в будущем (для которого полная история требуется), или нет, и сколько памяти ему на это не жалко...
В таком варианте основная трудоемкость задачи выносится в предобработку, т.е. в процедуру чтения файла журнала во внутреннее представление. Зато потом у меня будет список юзеров с полной историей каждого. Из которой я могу извлечь любую статистику, которую захочу, за время О(N*m), где N*- число юзеров, а m - число посещенных страниц. Причем N*m получается для более продвинутых статистик, а в случае ТЗ-задачи m можно уменьшить до 2, что еще более улучшает картину.
Впрочем, пока мой массив умещается в память, статистика по юзерам в любом случае будет считаться "на лету". Если, конечно, количество гиперактивных юзеров (чью историю придется подгружать из дополнительной таблицы) не очень большое.
Итого, самой тяжелой операцией будет загрузка веб-журнала (там ведь данные могут быть в виде строк и вообще какие угодно). Поэтому если нужно обрабатывать историю не за пару дней, а побольше, то я бы еще сделал функцию, которая скидывает мою внутреннюю базу на диск и обратно. Фортран обычно пишет в файл данные прямо в машинном представлении, без какой-либо конвертации. Это почти что дамп памяти - т.е. намного быстрее, чем журнал декодировать. Ну и еще придется делать функцию, которая будет чистить внутреннюю базу от устаревших записей, но это совсем просто.
Итого для сайта с небольшим числом уникальных юзеров (миллионы) и умеренным количеством уникальных страниц, посещаемых за один визит большинством юзеров (сотня за несколько дней) получается алгоритм О(N), но который займет порядка 10Гб памяти.
Для сайта с небольшим числом уникальных юзеров (миллионы) и умеренным количеством уникальных страниц (в пределах 4294967295-1, т. е. сколько влезает в беззнаковое 4-байтное целое, нуль зарезервируем), вот как-то так не выйдет (на корявом псевдо-коде а-ля что-то си-образное):
const unsigned long MAX_USER_ID = 1000000; // миллион, представляете, целый миллион!
unsigned long visits[MAX_USER_ID][2]; // где-то 8Мб на миллион юзеров
// читаем первый файл
for([UserID, PageID] in file1)
{
*v = &visits[UserID]; // ну типа сцылко
if ( v[1] > 0) continue; // уже вторая заполнена - две уникальных есть
if ((v[0] > 0) && (v[0] != PageID)) v[1] = PageID; // первая заполнена и не равна текущей - заполнить вторую
else if (v[0] == 0) v[0] = PageID; // обе пустые - заполнить первую
}
// читаем второй файл
for(UserID, PageID in file2)
{
if ( v[1] > 0) print(UserID); // уже две уникальных за прошлый день
else if ((v[0] > 0) && (v[0] != PageID)) print(UserID); // была одна за прошлый день, а щас другая
// иначе за прошлый ничего не было - не надо
}Всего-то порядка 8Мб на миллион юзеров, 8Гб на миллиард, O(N), все дела.
Всего-то порядка 8Мб на миллион юзеров, 8Гб на миллиард, O(N), все дела.
Так о чем я и говорю ;-)
Только я бы все-таки прочитал журналы во внутренний формат предварительно, что позволяет легко масштабировать задачу на N дней вместо двух, и на другие статистики обобщить, когда спросят. Пусть и ценой кратного роста требований по памяти (т.к. я в свою табличку предлагаю целиком все данные загружать, а не только то, что нужно для конкретной задачки. Благо, для типичного сайта средней руки (миллион открытых страниц всеми юзерами в сумме в день) обычной десктопной памяти с лихвой хватит. Хотя и компакт-вариант алгоритма, разумеется, тоже возможен).
Ну и еще, мне очень хочется вынести работу с журналом в отдельную процедуру. Впрочем, это у меня наверно
тоже профдеформация
я просто не могу себе представить журнал, в котором нет ошибок и глюков ;-) Поэтому я бы их обработал в отдельной функции загрузки журнала, а не в основном цикле. Заодно убрал бы из журнала всякие посторонние записи (в ТЗ про них не сказано ничего, значит они там наверняка будут ;-)
Ну и копирование данных во внутреннюю табличку с их группировкой по юзерам позволит в будущем легко вычислять другие статистики, кроме ТЗ-шной. Тут же уже говорили, что утром следующего дня менеджер
обязательно это попросит ;-)
Кстати, это не только в бизнесе так. У нас в науке ТЗ точно также корректируется практически всегда "на лету", по мере знакомства с первыми результатами. Разница только в том, что вместо менеджера часто ты сам себе ТЗ корректируешь. Поэтому принцип "не закладывай в программу то, что может понадобиться потом" (а может и не понадобиться) у нас далеко не так актуален, как у нормальных людей ;-) Я заранее знаю, что в 2/3 случаев мне придется все переделывать, как только алгоритм заработает... как говорится, для этого не обязательно к бабке ходить ;-)
Ну хорошо, задача интересная. А какие исходы? Предположим, кандидат присидел час и не решил. Не берем?
Я вот так решил, но я бы точно с таким решением не прошел бы)
import pandas as pd
df1 = pd.read_csv('day1.csv')
df1['Day'] = 1
df2 = pd.read_csv('day2.csv')
df2['Day'] = 2
df = pd.concat((df1, df2), ignore_index=True)
df = df.groupby('CustomerId')[["Day", "PageId"]].nunique()
df = df.query("`Day`>1 and `PageId`>1")
print(*df.index)
Хорошо, подход более инженерный чем у всех остальных кандидатов!
Было бы интересно увидеть как вы решили бы эту же задачу на Polars и DuckDB в Python. И в сравнение и область применимости panda/polars/duckdb
Есть мнение, что подобное решение - основанное на "сторонних" библиотеках - на "стандартном" алгоритмическом собеседовании не приняли бы. Насколько я знаю, для решения алгоритмических задачек иногда разрешают использовать стандартную библиотеку, и только.
Не совсем по теме, но зачем нужен DuckDB при живом то Sqlite?
SQLite действительно живее всех живых и является предком DuckDB.
Можете рассматривать DuckDB как SQLite для аналитики, так как модели данных у них и подход к построению базы отличаются. Как минимум лучше чтобы делать запросы быстрее работающие с агрегацией данных и работать с форматами данных из Big Data мира: parquet, arrow, iceberg.
А можете ткнуть в сторону бенчмарков?
Есть три вида лжи: ложь, наглая ложь и бенчмарк.
Конечно: https://benchmark.clickhouse.com/ А можно начинать с документации что это и зачем.
А вы можете для своего решения сложность (по времени/памяти) указать?
Если сможете и обоснуете, то вполне нормально.
Чтение данных О(n), где n - суммарное количество записей в журналах.
Конкатенация пускай тоже О(n).
Groupby внутри сортирует данные, так что O(n + k*log(k)), где k - количество уникальных пользователей
Query - О(k).
Итого, как мне кажется, O(n + k*log(k))
Развивая идею, чтобы определить асимптотику лучше не гадать, а делать эксперименты и собирать метрики в отчёты с красивыми графиками - как это принято у data science вообще или нагрузочных тестировщиков в частности.
Понятия алгоритма и алгоритмической сложности это абстракции. Для анализа работы реальных комплексных приложений такой подход не сильно практичен. За каждым интерфейсом может скрываться что угодно: от гениальных оптимизаций до досадных ляпов - причем с флуктуациями от версии к версии.
В теории можно написать простой SQL-запрос и, конечно, крупные компании имеют огромные хранилища, в которых вы можете запросто подобное реализовать.
У меня первая ассоциация была Splunk.
Но в рамках собеседования нам это не нужно. Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
Можно просто уточнить, что интересует алгоритм, а не приложение. Это сразу отсекет массу вопросов про архитектуру, https://en.m.wikipedia.org/wiki/Non-functional_requirement и варианты написать программу с использованием высокоуровневых библиотек.
Интересно, что никто толком не придаёт значение того, что данные распределены в файлы по дням, то есть для многих сайтов день1 может иметь миллион записей, а день2 - тысячу, просто потому что день2 - это выходной..
Да и сама задача решается не особо инженерно, без мыслей о том, что вслед за двумя днями будут идти ещё десятки таких же дней, и к уже третьему дню было бы неплохо подготовиться, а не снова идти по файлу из день2 и перебирать все строки..
и к уже третьему дню было бы неплохо подготовиться, а не снова идти по файлу из день2 и перебирать все строки..
Так а чем Вам не нравится идея конвертации файлов журнала во внутренний формат с фасовкой данных по юзерам? Я конечно сюда из дикого заповедника заглянул, и в профессиональной специфике ни бум-бум. Но у меня получается, что пока данные лезут в память (а это нам вроде бы обещали), то самое тупое решение "в лоб" на древнем языке программирования на этапе расчета статистик будет иметь сложность O(N), где N-число даже не посещений, а юзеров. А самой тяжелой операцией будет разбор журнала во внутренние таблицы (и тут уже сложность O(M), где M-число записей в журнале). Поэтому разбор журнала лучше выполнять один раз для каждого нового файла с журналом, а потом сбрасывать получившуюся табличку (кумулятивную) на диск во внутреннем формате программы, что де-факто бесплатно
раз в сутки же ;-)
а если серьезно, то дамп памяти по-любому
кратно быстрее
Я тут неявно учел, что фортран мой массив структур в файл в машинном представлении скинет /прочтет. Про современные языки я просто не в курсе, но было бы удивительно, если там такую опцию не предусмотрели. Так что я надеюсь, что это на любом языке будет работать..
чем журнал разобрать. Не говоря уже, что размер таблички во внутреннем представлении на порядок меньше размера журнала...
Зато потом можно не только запрошенную статистику вычислять, а "чего изволите".
При этом решение получается расширяемое во все стороны: если завтра потребуется статистика за неделю, или алгоритм учета лояльности поменяется, то надо будет всего одну функцию изменить - ту, которая таблицу посещений текущего юзера анализирует.
Но, конечно, на сайты с большим числом посещений это решение масштабируется почти что никак. Как только суммарное число записей в "горячих" журналах (за последние несколько дней) приблизится к миллиарду, моя табличка в память перестанет влезать, а это
немедленный крах
Да, его можно слегка отсрочить, если при повторном посещении страницы обновлять время, а не создавать новую запись в табличке. Но при этом часть данных из журнала будет утрачена... поэтому моя профдеформация геофизика противится это делать ;-) Хотя по логике юзеры довольно часто на одни и те же страницы заходят, так что экономия может получиться в разы. Но в любом случае сайт уровня амазона не то, что на ноуте - на севере с тербайтом памяти таким методом не прокрутишь...
Неоднозначный подход - ожидают что разраб должен быть proactive, находить gaps в задании и задавать уточняющие вопросы, но исключают использование БД и SQL как redundant для scope, хотя этот подход также proactive (и масштабируемый за пределы доступной памяти).
Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
При хранении данных в базе, собственно запрос (без обвязки на подключение и рассоединение) не больше 3х строк.
Проблема таких собесов в том, что люди покажут только как они умеют изобретать велосипеды и подпирать костылями дурные решения. Моё собеседование бы закончилось тем, что я задавал бы вопросы в духе "а нафига вы данные в файлик писали?" или "это вы постоянно так решаете (aka изобретаете) проблемы?"
Программиста надо проверять в том поле, где будет его покрытие. Если это веб-разработчик или что-то про разработку (микро-)сервисной архитектуры, то лучше спросить про сеть или HTTP, про алгоритмы сжатия, задержки или хорошо по SQL прогнать (там задачек по дискретной математике хватит на полжизни).
Случай из жизни
Был у кореша в офисе, когда он не мог решить одну прикладную задачку с задержками и нужно было переделать архитектуру. Он заодно попросил поучаствовать в собесе нового фронтендера.
Сижу, значит, слушаю их (кореш, их тимлид из фронтендеров, hr'очка). А вопросы, значит, про алгоритмы, про матанализ, про протоколы, про SQL, про Linux... Я тихонько скидываю сообщение другу: "а чё, у вас часто фротендеры этим занимаются? Они же вроде у вас формочки почти всё время клепают. Спроси про вёрстку парня!" Буквально кореш получил сообщение, собеседуемый выдаёт: "Слушайте, а у вас фротендеры часто с этим работают? Чем вообще я буду здесь заниматься?" Мы вдвоём складываемся пополам от громкого хохота в голос, после чего кореш поворачивается к hr'очке и со слезами на глазах: "оформляй!"
Кстати, этот парень там быстро поднялся и оказался очень толковым. Хотя про SQL, линукс и алгоритмы довольно слабо отвечал.
Если человека в команду берут не на позицию разработки движка чего-то там с нуля, то зачастую стоит проверять на знание фреймворков и библиотек. Если хотите проверить сеньористость, то проверьте глубокие знания языка. При этом убедитесь, что сами знаете матчасть (а то такой цирк с конями был в жизни, что даже вспоминать страшно).
Лучший способ дать комплексное творческое тестовое, а потом на встрече его обсудить, если оно в целом стоит обсуждения. Но это задание должно быть:
приближенным к актуальным задачам
сделано в комфортном для кандидата режиме (но в рамках общего окна)
не делать его под присмотром (пусть дома сядет и спокойно сделает)
вылажено в портфолио на Github/Gitlab в открытом виде (помощь человеку с портфолио).
При этом уважительно надо общаться с обеих сторон. Дерзкие дегенераты с обеих сторон раздражают и вызывают глубокое отвращение в будущем к компании. После общения обе стороны должны получить профит в виде опыта и приятные воспоминания. Почему? Да потому что это networking, а земля круглая. Если в вакансии ни слова про алгоритмы, то и не проверяйте это. Проверьте именно то, что ищите.
Именно поэтому, сколько помню найм к себе, то люди потом уходили ещё более вдохновлённые, чем приходили. Даже после отказа, многие были мотивированы на рост и уверен нашли хорошее место, где применили свои навыки.
Моё собеседование бы закончилось тем, что я задавал бы вопросы в духе "а нафига вы данные в файлик писали?" или "это вы постоянно так решаете (aka изобретаете) проблемы?"
В данном контексте автор собесит в FAANG конторы где эта штука поставлена на поток. Он может и сам бы был рад задавать открытые вопросы но их собесы жестко стандартизированы и за шаг влево шаг вправо - расстрел. Поэтому такое поведение оно контрпродуктивно.
Если вам не интересен офер то непонятно зачем вообще приходить туда на собес зная наперед что там будут задачи с LeetCode. Ведь вы изначально в невыгодной позиции, собеседующему этот час оплатит компании а вам нет.
Если интересен то в лучшем случае вы урезаете свое время. Его и так немного, 45 минутный конвейер из 2 задачек.
Самой компании(из FAANG группы) же глубоко все равно на все эти инженерные "излишки", им нужно а) быстро б) фидбек сразу же в) стандартизировано. Если бы они не боялись судебных исков то просто давали бы стандартный тест на IQ, корреляция с реальной работой мне кажется была бы примерно такой же как и LeetCode задачи.
Я понимаю о чём вы, но это не значит, что это правильно. Именно благодаря потоку, они сливают деньги в трубу, а трудиться над оптимизацией не могут, просто потому что не умеют.
Если вам не интересен офер то непонятно зачем вообще приходить туда на собес
А так я и не хожу и даже не рассматриваю оттуда предложения. На это как бы намекает частичка "бы". Даже если "позязя" от рекрутеров слышу. Это было бы и правда контрпродуктивно.
Он может и сам бы был рад задавать открытые вопросы но их собесы жестко стандартизированы и за шаг влево шаг вправо - расстрел.
Статья говорит, что нет, не рад бы. Его вполне радует, что он придумал решение, под него задачу и может теперь узнать, насколько человек глубоко натренерован писать костыли. Стандарты не зло, как и законы. Зло рождается при применении этого со злым умыслом. В данном случае, сосредоточенность на своём чсв, а не поиске адекватных сотрудников (а задача именно такая).
С таким потоком, появляется всё больше историй, когда на работу устраиваются люди, которые вообще не умеют писать адекватный код и решения. А иногда вообще не умеют писать код, просто память хорошая. В итоге с малюсеньким микросервисом работают 10 разработчиков, вместо 3 (условно). То же касается раздутых процессов, скрамов в команде до с 3 разрабами и 4 менеджерами. Т.е. проблема не в том, что люди не принимают такой подход, а в том что очевидно, что он убогий и не особо эффективный, но менять ничего не будем, потому что "видите, мы успешные, а все лузеры". Только вот эти компании не со скрама начинали свой успех...
глубоко все равно на все эти инженерные "излишки"
Это вам в FAANG руководители разработки сказали, да? Или вы где-то слышали? Просто так, наверное, пачками разгоняли сотрудников недавно, которые зачастую по каким-то показателям не приносят прибыль, а только убытки. Хотя и там эффективные процессы помогли замесить и хороших менеджеров, и хороших разрабов.
Даже при том, что я не питаю хороших чувств к Маску и его подходу, я хорошо знаю как может сложиться бюрократическая машина, когда из 100 сотрудников, нет ни одного, кто хотя бы понимает как работает сеть, но пишут микросервисы.
Поэтому я и выразил свое мнение, насчёт процесса такого странного подхода к найму.
cat access.log access.log.1 | awk "{print $1}" | sort | uniq -c
Знаете, а я бы не хотела работать у вас… Для вас человек, страдающий преждевременной оптимизацией вместо поддерживаемости кода, предпочтительнее. Задачи написать быстро не стояло. Если писать весь код так, то… мне страшно представить кодовую базу вашу. Не правильнее было бы ожидать поддерживаемый код, а не быстрый?
Обычно разница между "быстрым" и "медленным" алгоритмом, это разница в константе (время на итерацию). Если у вас разница в BigO, то (не всегда, но часто) это разница между "правильно" и "неправильно", а не между "быстро" и "медленно". Никакой преждевременной оптимизацией тут и не пахнет. Человек по сути проверяет знания азов computer science (по сути знания Map).
Не правильнее было бы ожидать поддерживаемый код, а не быстрый?
Нужно писать поддерживаемый код всегда. Даже когда сказано, что он должен быть очень быстрым.
Почему это разница в BigO определяет правильность? Отправлю вас на кодфорс. Там все задачи красиво решаются с произвольным О, но если надо максимально быстро, то выйдет что-то страшное. Не дай бог такое писать в продакшене. И написать это поддерживаемо просто невозможно, так как никто не будет понимать твой fast inverse square root. Подводя итог: оптимизация может очень портить код, когда в этом нет никакой необходимости: задача об этом не просит.
Ну нет. Очень часто разница в BigO - Это разница между полным перебором и красивой структурой данных. И второе решение можно написать красиво и понятно, а вот полный перебор - почти всегда будет длинной странной рекусивной хтонью. Да, на олимпиадах весь код неподдерживаемый, потому что это write-only код для конкретной олимпиады. Но это не проблема алгоритмов, а проблема соревнований.
Вот когда уже не алгоритм выбирают, а начинают битовое сжатие, inverse square root и подобные трюки использовать в попытках ускорить решение в константу раз - вот там уже код страшный вылезает. И вот такое ни на олимпиадах, ни в продакшене часто и не надо, ибо это попытка выжать еще чуть-чуть скорости.
Пример из поста. Я могу очень логично и элегантно написать решение за квадрат(на вскмдку). Он излишен конкретно для этой задачи, но его потом можно будет переиспользовать в отличие от процедуры, заточенной под супер конкретную задачу. Чтобы оптимизировать решение больше, придётся жертвовать обобщенностью решения т. е. как-то тонко эксплуатировать условия. И чем больше оптимизация, тем больше конкретизация под задачу. Под конкретную сейчас. ТЗ имеет свойство меняться, и придётся всё переписывать с нуля на ровном месте.
Я могу очень логично и элегантно написать решение за квадрат
Вам так кажется, пока вы не начали писать. Проверить, что userid оба дня встречается - еще получится примерно также просто написать, как по умному, а вот уже для 2 различных страниц у вас появится точно такой же map. И как-то с ним работать в двух вложенных циклах будет даже запутаннее, чем решение в посте.
Оптимальное решение с map-ом из set-ов страниц отлично дополняется под почти любые изменения. Хотите 3 разные страницы - легко. Хотите разные страницы в каждый день - делаете 2 мапа. Переписывания будут не сильно сложнее чем в решении за квадрат, в котором тоже все, кроме двух внешних циклов придется выкинуть и переписать с нуля при каком-то более хитром изменении ТЗ.
но если надо максимально быстро
Разница между максимально быстро и быстро, обычно, заключается не в BigO, а в константе между BigO. Всяким трюкам, позволяющим снизить накладные расходы.
оптимизация может очень портить код
Тут речь идёт не об оптимизации, а о выборе алгоритма. И я не припоминаю никаких случаев на своей практике, где нормальный код нельзя было поддерживаемо написать и чтобы код был "очень испорчен".
Хуже всего, в вебе, это чаще всего вопрос мозгов одной строки:
return collection.reduce((acc, item) => {
// ...some logic...
- return { ...acc, [item.id]: blabla }
+ acc[item.id] = blabla;
+ return acc;
})Люди фигачат O(n^2) в абсолютно бессмысленных местах руководствуясь полу-религиозными нормами или просто ввиду не знания основ. Подробнее об этом писал тут.
Автор реально думает, что в состоянии изменить чью-то жизнь. Вершитель судеб. ))
Наименование переменных с числами в названии - оно само по себе наталкивает на мысль, что в автоматизированной системе нужно работать с абстракциями и не хардкодить количество дней еще и не зашивать в именование переменных всё это дело. Но подбор персонала это очень сложная вещь! Тут можно и на ухищрения пойти, но такого кода в проде быть не должно в любом случае
Ох. Задача хорошая, а вот интерпретация её интервьюером... как бы это сказать...
Я когда такую задачу вижу, у меня сразу первый вопрос: мы этих пользователей хотим найти один раз для какого-нибудь ежегодного отчёта - и всё? Или каждый день и по нескольку раз?
Если первое, то O(n²), конечно, неоптимально, но приемлемо. К тому же просто, надёжно и легко расширяется.
Если второе, то вы, наверное, хотите спросить как нам гонять аналитику на большом количестве данных? Потому что не могу я поверить, что завтра руководство не потребует списка пользователей, которые заходят на сайт как минимум дважды в неделю за час до полуночи.
А то, что данные влезают в память - так это вообще провокация. Если этих данных больше сотни мегабайт, то сегодня влезают, завтра перестанут. Я на такое уже давно не ведусь.
Нет. Уж лучше про зайчиков и лисичек, которые в лесу меняются подарками спрашивайте: так хотя бы понятно, что спрашивающему решение нафиг не сдалось.
программисты открывают для себя реализации Nested Loop, Hash и Merge join - на файлах смотреть без регистрации и смс
Map это все-таки O(log N), а не O(1). Поэтому решение, описанное в статье - это не O(N), а O(N log M), где M - число уникальных клиентов.
Ну и решение со словарями отдельно для 1го и 2го дня явно не тянет на лучшее. Выше уже приводился более оптимальный и универсальный (расширяемый на случай, когда дней станет не 2, а 3 и страниц не 2, а 5) вариант с единственным словарем, содержащим для пользователя посещенные дни и посещенные страницы и последовательным обновлением этого словаря из 1го и 2го файлов. Если хочется на первом этапе микрооптимизации, можно сначала не хранить список дней и страниц, а только флаг посещения первого дня, единственный PageID и флаг лояльности. Тогда при необходимости расширить условие будет единственное и понятное место, кототоре надо отрефакторить.
Map это все-таки O(log N), а не O(1)
Смотря что там внутри. Если дерево, то O(log N), если хэш-мэп, то амортизированное O(1)
если хэш-мэп, то амортизированное O(1)
really?
Что вас тут смущает? Хешмапы в среднем работают за O(1). Вон, даже в справке написано, что c++ unordered_map работает за константу:
Search, insertion, and removal of elements have average constant-time complexity.
Map это все-таки O(log N), а не O(1)
hashmap?
O(1)bst?
O(logN)
Согласен
Хороший пример того, что нужно кидать в Codility и отправлять перед собеседованием. И очень хорошо формулировать требования, насколько быстрый алгоритм вы хотите получить. Потому что неприятно проходить подобные собеседования. Можно, но неприятно. Сильно зависит от удачи. Не со всеми людьми приятно вживую контактировать.
Старость - это когда бегло просмотрел условия задачи, прикинул, что тут, наверное, понадобится база данных и потом смотришь вполглаза, как молодежь с задором упражняется.
Понимать что там внутри вашей БД полезно. Особенно когда БД становится на самом деле большой. БД работает по тем же алгоритмам. Хорошая БД должна смочь выдать оптимальную версию алгоритма по адекватному запросу.
Интересно становится когда вы понимаете что этот запрос должен работать нормально, а БД не может. Без знания алгоритмов и решения таких задачек в уме вы не сможете увидеть такие моменты.
Что это за язык?
Почему map, а не unordered_map?
Если речь идет о скорости, а память неограниченна, как в задании, то выгодно вместо словаря использовать массив размером в гигабайт, например. Где индекс массива - это порядковый номер записи за указанный день.
Такая реализация быстрее словаря, так как выборка по индексу моментальная. Также, можно сделать динамически изменяемый массив, как в списке, только быстрее на 5%. В итоге получится словарь-список.
Тесты показали, что при таком подходе можно делать выборку 4 миллиона записей в секунду за произвольный день. При этом, одновременно писать в эту бд 500 000 значений в секунду.
Ну и обработка массива дальше быстрее любых словарей. Только за 40 минут это не придумать, у меня ушел месяц на тесты и проверки скорости и перебор вариантов.
Если индекс массива это номер записи, то как во всех этих записях найти юзера, который заходил в разные дни на разные страницы, кроме как дважды перебирая все элементы массива?
Да, для каждого дня нужно перебирать отдельно, то есть в сумме два раза, а потом объединять множества. Однако, это будет быстрее за счет быстрого ядра - использование чистых массивов, плюс nosql база, где все значения одного свойства хранятся в своем отдельном файле. При загрузке файла целиком - сразу сделать сортировку для ускорения прохода по массиву.
Мне сложно описать всю идею, описание очень большое, хоть идея и основана на примитивах . А словарь – это конечно классно, но кушает в итоге намного больше памяти, плюс считать хэши для всего...
Проще описать результат моего подхода за счет грамотной структуры файловой бд, а также чистых массивов.
По результатам тестов: я могу в реальном времени листать через интернет график в 4млн значений на экране, по любому параметру и за любой период. И это не в виде картинки, а строя по данным из бд и со сложной обработкой прореживания. Аналогично - с листанием таблиц через веб, только там прореживания уже нет.
Просто я хочу сказать, что алгоритм - отнюдь не самое затратное место, надо рассматривать в комплексе, включая бд. И даже использование словарей.
Мораль басни: перед тем как решать тестовое задание, если ты не читаешь мысли, уточни что хитрый собеседующий молчаливо ждёт от тебя не вставив в требования. Может он фанат ломбок и не станет читать код без него :) если он занимается хайлоад то вероятно что задача на производительность, ресурсы и т.д.
Дисклеймер: все собеседования по программированию ужасны…
Задача простая, каковыми являются 99% задач в конторах, занимающихся разработкой и поддержкой браузерных интерфейсов пользователя к торговой БД.
Решение тоже должно быть простым, чтобы: а) не раздражать менеджера, б) не увеличивать число сущностей сверх необходимого,
в) оптимизировать (уменьшить) затраты своей личной рабочей (умственной) силы на подённой службе у частного владельца средства производства.
Оба файла так и так придётся прочесть полностью. И желательно каждый только по разу.
Для этого используем HasнMap для объекта хранения, где ключом (Key)является CustomerId, а значением (Value) - PageId первой из встреченных страниц, посещённых пользователем. Можно и Set обойтись, по идее, если есть понимание, что он использует меньше памяти или работает быстрее, но я лично сомневаюсь в заметной разнице между этими классами. От Set отвращает то, что для поиска в нём необходимо использовать инстанс класса, а для HashMap годится и значение CustоmerId. Которое может быть просто строкой. Конечно, это можно обойти, чтобы не создавать каждый раз инстанс класса объекта хранения, что сделает код менее ясным.
Timestamp вообще не нужен, по условию задачи. Ведь у нас только 2 дня (файла) и ищем мы вхождения в 2 файла, т.е. фактически Timestamp уже разделен по этим самым файлам так, как надо.Читаем 1-й файл (первого дня) и заполняем HashMap именами уникальных пользователей с Value=PageId, как первой посещённой страницей.
Если при чтении 1-го файла имя пользователя уже присутствует в HasнMap, а PageId из файла отличается от оного в HashMap, это означает, что пользователь посетил уже 2 уникальные страницы и мы фиксируем этот факт тем, что вместо PageId записываем null, используя это значение как флаг состояния (посещено 2+ страницы). В будущем, если обнаруживаем, что Value==null, то уже знаем, что по числу страниц этот пользователь удовлетворяет искомому набору и нам все последующие посещённые им PageId уже не интересны (в условии про интерес ничего нет).
Читаем 2-й файл для второго дня и проверяем наличие CustomerId из текущей строки в HashMap.
Если текущий CustomerId из строки файла в HashMap не обнаружен, переходим на следующую строку, т.к. этот CustomerId точно не посещал сайт в 1-й день и не проходит по этому критерию.
Если текущий CustomerId в HashMap есть и его PageId==null, сразу переносим (с удалением из HashMap, чтобы лишний раз его не проверять) проверяемый CustomerId в список результатов, т.к. уже ясно, что он посетил не менее 2-х страниц (ещё в 1-м файле) и обнаружен только что и во 2-м файле.
Если PageId в HashMap отличается от текущего PageId, также переносим этого пользователя из HashMap (т.к. он посетил одну страницу в 1-м файле и иную, с текущим PageId, во 2-м).Итого, после линейного прочтения двух файлов, мы уже получаем искомый список CustomerId, посещавших сайт оба дня и побывавших на его не менее чем 2-х уникальных страницах.
Другого смысла в этом результате нет, условием более ничего не предусматривалось.
Нет ни списка посещённых страниц, ни времени их посещения, т.е. нет даже урезанной мякотки, являющейся сырьём для сокрушения мозга пользователей и составления интригующих отчётов для инвесторов.
Решение на Perl:
#!/usr/bin/perl
use strict;
use warnings FATAL => 'all';
my @logFiles = qw/file1.log file2.log/;
my $hash = {};
for my $log (@logFiles) {
open(my $logF, '<', $log) or die "$!\n";
while (my $record = <$logF>) {
my ($Timestamp, $PageId, $CustomerId) = split /\t/, $record;
my $dayNumber = extractDay($Timestamp);
$hash->{$CustomerId}->{dayNumber}->{$dayNumber} = 1;
$hash->{$CustomerId}->{PageId}->{$PageId} = 1;
print "$CustomerId is loyal" if (scalar (keys $hash->{$CustomerId}->{dayNumber}) > 1
&& scalar (keys $hash->{$CustomerId}->{PageId}) > 1);
}
}А вы тут не выводите многократного одного и того же посетителя? Скажем если он посетил 3 уникальных страницы.
В Perl нет HashSet-ов? (`->{$blabla}=1` выглядит избыточным)
Получу. Но это детали реализации, в ТЗ про это не было.
Что это?
Мало ли чего в ТЗ нет. Не аргумент. Особенно на собеседовании. Кандидат должен либо уточнить, либо догадаться. Кому нужны дубликаты - никому.
Это структура данных для хранения множеств. Устроена примерно так же, как и HashMap (это то что вы применили), но чуть более узко специализированная.
HashMap это KeyValue хранилище, где Key уникальны.
HashSet это Value хранилище, где Value уникальны.
#!/usr/bin/perl
use strict;
use warnings FATAL => 'all';
my @logFiles = qw/file1.log file2.log/;
my $hash = {};
for my $log (@logFiles) {
open(my $logF, '<', $log) or die "$!\n";
while (my $record = <$logF>) {
my ($Timestamp, $PageId, $CustomerId) = split /\t/, $record;
my $dayNumber = extractDay($Timestamp);
$hash->{$CustomerId}->{dayNumber}->{$dayNumber} = 1;
$hash->{$CustomerId}->{PageId}->{$PageId} = 1;
my $isLoyal = (scalar (keys $hash->{$CustomerId}->{dayNumber}) > 1
&& scalar (keys $hash->{$CustomerId}->{PageId}) > 1);
print "$CustomerId is loyal" if $isLoyal && !$hash->{$CustomerId}->{isLoyal};
$hash->{$CustomerId}->{isLoyal} = 1;
}
close $logF;
}
Проблема с этой задачей в том, что она простая, но решение, которое он хочет, скорее всего будет хуже в реальной жизни, чем банальная загрузка в бд. Вместо хранения множества страниц за первый день можно было бы использовать фильтр блума.
Моя любимая задача для собеседований по программированию