В сети есть уйма постов и видео, где разбираются ответы на вопросы LeetCode. Но обычно рассмотрение в них происходит с позиции соискателя, а не работодателя. В этой же статье я приведу разбор собственной задачи по программированию, которую использовал при приёме людей на работу в Amazon, Google и Microsoft.
За 25 лет в сфере Big Tech я провёл более тысячи собеседований: чуть больше восьмисот в Amazon в качестве Bar Raiser, пару сотен в Microsoft и около сотни в Google.
Моя награда AWS Top Bar Raiser Q1.2020
В сфере Big Tech проводится три вида собеседований на должность инженера ПО: [1] по программированию, [2] по проектированию систем, [3] по навыкам управления и работы с людьми, пониманию культуры и так далее. Циклы собеседований обычно представляют комбинацию этих видов. Например, для кандидатов на должность SDE-I (младший инженер по проектированию систем) может присутствовать 3 собеседования по программированию, 1 по проектированию систем и 1 по навыкам управления. При этом на должность старшего инженера может проводиться 1 собеседование по программированию, 2 по проектированию систем и 3 по управленческим навыкам. Лично я предпочитаю не ограниченные временем собеседования по навыкам управления, так как они позволяют лучше понять кандидатов. Но всё же проверять навыки программирования тоже нужно, и этот этап является необходимым злом.
Дисклеймер: все собеседования по программированию ужасны, включая мои. Вам даётся всего 45 минут, чтобы сформировать рекомендацию о найме либо отказе, которая может изменить чью-то жизнь. И при этом люди никогда не раскрываются по-настоящему, так как находятся под давлением временны́х рамок, испытывают волнение и нервное истощение. При этом задаваемые вопросы должны вписаться в установленный промежуток времени и дать интервьюеру определённые сигналы. Я предпочитаю задавать более простые вопросы, чтобы построить качественный диалог, в котором смогу проанализировать ход мышления соискателя.
Для меня гораздо важнее сама беседа, чем код, который человек пишет на доске. Какие при этом существуют компромиссы? Как найти между ними баланс? Выступая в роли интервьюера, именно я должен обеспечить для соискателя качественный процесс, понять, когда нужно дать подсказки или задать наводящие вопросы, и как корректировать свои ожидания с учётом конкретного контекста.
В собеседованиях по программированию я часто ставил перед соискателями описанную далее задачу, отчасти основанную на реальных процессах компании. И сегодня я вас с ней познакомлю, продемонстрировав, что именно я стремился понять с её помощью о соискателе.
Условие задачи
Предположим, у нас есть сайт, и мы отслеживаем просматриваемые посетителями страницы на предмет бизнес-метрик.
Каждый раз, когда кто-то заходит на сайт, мы делаем запись в журнал, отмечая
Timestamp, PageId и CustomerId. К концу дня у нас формируется большой файл со множеством подобных записей, и для каждого нового дня заводится новый такой файл.Располагая двумя файлами журнала (для дня 1 и дня 2), мы хотим сгенерировать список «лояльных клиентов», отвечающих следующим критериям: (а) они посещали сайт в первый и второй день, (b) они посетили не менее двух уникальных страниц.
Это не сильно сложный вопрос, но он требует некоторых размышлений, а также понимания сложности кода и структур данных. Можно легко определить клиентов, посещавших сайт в оба дня, а также тех, кто посетил не менее двух уникальных страниц. А вот чтобы найти пересечение этих двух показателей, потребуется немного постараться.
Я задавал соискателям эту задачу где-то раз 500, что позволило мне достаточно хорошо её откалибровать. В результате я выяснил, что рекомендация о найме/отказе на её основе совпадает с итоговым решением о найме примерно в 95% случаев. Я также могу масштабировать эту задачу для кандидатов более высокого уровня, что делает её очень гибкой. При этом в ходе решения я также могу в случае затруднений дать человеку ряд намёков или подсказок.
Уточняющие вопросы
Наиболее грамотные кандидаты, прежде чем переходить к написанию кода, должны задавать уточняющие вопросы. Я рассчитываю увидеть в соискателях проявление рассудительности, так как в описанных условиях задачи присутствует двусмысленность.
Имел ли я ввиду посещение двух уникальных страниц в день или всего?
Это значительно влияет на решение. Я имею в виду «всего 2 уникальных страницы», поскольку так задача становится намного интереснее. Около половины соискателей сразу же переходят к решению, не уточняя этого нюанса, и половина из них ошибочно предполагают, что я подразумевал «2 уникальных страницы в день». Если передо мной менее опытный кандидат, то я изначально даю ему подсказки, прежде чем он переходит к коду. Если же кандидат опытный, я некоторое время ожидаю и смотрю, возникнут ли у него вопросы в ходе продумывания алгоритма.
В реальности инженеры постоянно сталкиваются с неоднозначностью, и корень большинства программных проблем можно найти в плохо определённых требованиях. Поэтому я хочу получить сигнал о том, что человек заметил присутствующую двусмысленность и хочет её прояснить.
Есть ещё один важный уточняющий вопрос, который упускают 90% соискателей: «А как быть с повторами?» Имеется в виду посещение одной и той же страницы в один день или в разные дни. В моей задаче под повторами подразумевается именно это.
Третий значимый уточняющий вопрос относится к предполагаемому масштабу. Умещаются ли собранные данные в памяти? Можно ли загрузить в неё содержимое одного из журналов? А обоих?
В основу этой задачи легла реальная система под названием Clickstream, над которой я работал в Amazon. Она отвечала за отслеживание поведения пользователей на amazon.com. Мы обрабатывали петабайты событий от миллионов одновременных пользователей на гигантском кластере Hadoop, включающем десяток тысяч хостов, и за обслуживание этой системы у нас отвечала целая команда инженеров. Однако в рамках 45-минутного собеседования мы берём гораздо меньший масштаб и представляем, что собранные данные в памяти умещаются.
И последний существенный уточняющий вопрос был связан с тем, насколько важно соотношение производительность – память – обслуживаемость. Существует простейшее решение, которое выполняется за O(n²) времени, но использует всего O(1) памяти. Есть более эффективное решение, выполняющееся за O(n) времени, но использующее O(n) памяти. А есть промежуточный вариант, при котором выполняется предварительная обработка за O(n log n), требующая O(k) памяти, что позволяет выполнять основной алгоритм за O(n), задействуя O(1) памяти.
У каждого решения есть свои плюсы и минусы. Некоторые из эвристик, которые вы можете использовать для повышения быстродействия или оптимизации потребления памяти, могут усложнить восприятие и последующее расширение кода. В случае более опытных кандидатов я надеялся, что у нас по этому поводу возникнет интересная беседа.
А нельзя просто использовать базу данных?
В теории можно написать простой SQL-запрос и, конечно, крупные компании имеют огромные хранилища, в которых вы можете запросто подобное реализовать. Но в рамках собеседования нам это не нужно. Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
▍ Простейшее решение
Отправная точка:
Около 80% кандидатов сначала пробуют простейшее решение. Оно самое лёгкое и естественное. Это решение представляет некую форму алгоритма «для каждого элемента файла 1 перебрать всё содержимое файла 2 в поиске элементов с тем же
id посетителя, параллельно отслеживая просмотренные им страницы».Проблема такого решения в том, что оно требует O(n²) времени.
Я не возражаю, когда человек начинает с простейшего варианта, но хочу в итоге увидеть в нём осознание того, что выполнение за O(n²), пожалуй, не станет приемлемым ни для какой задачи. Причём хочется, чтобы это осознание пришло как можно раньше и без подсказок. Ни один первоклассный инженер не должен прибегать к алгоритму, выполняющемуся за O(n²), если только не работает в условиях недостаточной памяти или иных неустранимых ограничений.
Когда соискатель излагает это решение, требующее O(n²) времени, я вежливо улыбаюсь и жду. В этот момент я реально надеюсь, что следующими его словами будут «…но этот алгоритм имеет сложность O(n²). Удастся ли мне повысить его эффективность?» Тогда я задаю наводящий вопрос: «А каково время выполнения этого решения?» Чаще всего после такой подсказки соискатель осознаёт, в чём суть и переходит к реализации более эффективного варианта.
▍ Превращение O(n²) в O(n)
В этот момент вам нужно подумать о том, какую структуру данных следует использовать, и как вы будете сохранять данные.
Слабые кандидаты прибегают к связанным спискам или массивам. Вам неизвестен размер данных наперёд, поэтому массивы использовать нельзя. А в связанных списках поиск происходит за О(n), значит, вы снова придёте к тому же алгоритму O(n²), как бы ни старались. Можно использовать дерево, но так как в нём поиск происходит за O(log n), в лучшем случае вы получите O(n log n).
Более грамотные специалисты догадываются, что скорость поиска O(1), необходимую для превращения O(n²) в O(n), может обеспечить словарь (Map). Лучшие же кандидаты предусмотрительно отмечают недостаток такого подхода, заключающийся в использовании O(n) памяти. Здесь повышение скорости достигается за счёт увеличенного потребления памяти.
Если вы используете словарь, то что будет ключом, а что – значением? На этот вопрос я получал всевозможные ответы. Некоторые кандидаты используют в качестве ключа
PageId, а в качестве значения – CustomerId, но это не поможет. После этого человек пробует поменять их местами. Но это тоже не решит проблему, поскольку упускается тот факт, что для каждого посетителя у вас может присутствовать множество страниц, а не одна. Другие кандидаты догадываются, что в качестве значения словаря нужно использовать коллекцию страниц, но они прибегают к списку, что меня расстраивает, так как в этом случае не учитывается возможное присутствие повторов. Когда человек учитывает обработку повторов, это позволяет оценить, насколько он понимает отличия между списками и множествами. Итак, нам подойдёт
Map <CustomerId, Set<PageId>>. Но станете ли вы загружать содержимое обоих файлов в один словарь? Или же используете две, по одной для каждого? А, может, вы обойдётесь просто загрузкой содержимого файла 1 в словарь и обработаете файл 2, не сохраняя?Самые грамотные кандидаты понимают, что могут пойти третьим путём. Это потребует намного меньше памяти и создаст более простой алгоритм. Хорошие кандидаты тоже до этого додумываются, но не без подсказок.
Выполнить условие «клиенты, посетившие сайт в оба дня» довольно просто: вы считываете запись посетителя из дня 2, и если он находится в словаре из дня 1, значит, это наш человек:
А вот условие «клиенты, посетившие не менее двух уникальных страниц», правильно выполнить чуть сложнее, поэтому в случае затруднений я даю подсказку: «У вас есть множество страниц из дня 1 и одна страница из дня 2…как определить, что это не менее двух уникальных страниц?»
Слабые кандидаты используют перебор элементов множества (
Set) на предмет присутствия среди них страницы из дня 2. Такой подход снова превращает алгоритм O(n) в O(n²). И меня удивило количество людей, выбравших этот вариант. Более грамотные соискатели выполняют функцию .contains() для множества, обрабатывающую набор хэшей за O(1). Но и в этой логике есть подвох.Рассуждение для получения правильного решения будет таким: если вы находитесь внутри цикла
If, и клиент посетил не менее двух страниц в день 1, а также посетил любую страницу в день 2, то он является лояльным независимо от того, какая это была страница. В противном случае он посетил в день 1 только одну страницу, что ведёт к вопросу: «Отличается ли эта страница от страницы из дня 2?» Если да, то посетитель лоялен. В ином случае это повтор, а значит, остаются сомнения, и нужно продолжать цикл.
Здесь важно внимание к деталям, таким как использование
> вместо >= или упущение ! во втором условии. Я видел такое довольно часто. Лучшие кандидаты быстро замечали такие нюансы, когда перепроверяли алгоритм после его завершения. Хорошие кандидаты замечали их после некоторых намёков. Это позволяло мне сделать объективные выводы о навыках отладки.▍ Оптимизация решения
Лучшие кандидаты зачастую дополнительно проводят некоторую оптимизацию, демонстрируя внимание к мелочам и мастерство. Плюсом при этом выступает обсуждение компромиссов между внесением оптимизации и будущей обслуживаемостью.
Например, если мы работаем в условиях ограниченной памяти, то не нужно сохранять в словаре каждую страницу из дня 1 – будет достаточно двух. Поскольку задача гласит «не менее двух страниц», значит, множество с размером 2 или даже массив такого же размера задействует меньше памяти, чем неограниченное множество.
Либо, если вы уже определили, что посетитель лоялен, то не нужно тратить такты процессора на повторение логики при очередной встрече этого посетителя в файле второго дня.
Про оптимизацию: вы можете поспорить, что в случае изменения требований в будущем эти оптимизации усложнят корректировку алгоритма. Это объективный аргумент. Я рад, когда человек может вести вразумительную дискуссию на тему плюсов и минусов различных решений, предлагая для них сбалансированные альтернативы. В то же время возможность при необходимости оптимизировать алгоритм является чертой грамотного инженера, и вам потребуется порой идти на это в своей работе.
Иное решение
Подавляющее большинство кандидатов в итоге используют подход со словарём, но изредка (не более 5%) встречаются такие, которые прибегают к иному решению.
Что, если предварительно обработать файлы и упорядочить их по
CustomerId, а затем по PageId?Предварительная обработка – это мощный приём в арсенале программиста, особенно если вы собираетесь выполнять операцию многократно. Такую обработку можно произвести при первом выполнении или же заранее, чтобы в перспективе добиться сокращения общего времени выполнения. Упорядочивание файлов может выполняться в константной памяти (constant memory), занимая O(n log n) времени.
Когда файлы упорядочены, задача упрощается, и решить её можно с помощью метода двух указателей, требующего для выполнения O(n) времени и O(1) памяти.
В этом случае вы перемещаете указатели для файла 1 и файла 2 до тех пор, пока они оба не укажут на один
CustomerId. Это будет означать, что посетитель заходил на сайт в оба дня. И поскольку вторым ключом сортировки выступает PageId, нужно использовать ещё один метод двух указателей, чтобы определить наличие не менее двух уникальных страниц. В итоге получается метод двух указателей, вложенный в другой метод двух указателей. Забавная задачка! Её реализацию я оставлю в качестве упражнения для заинтересованных читателей.Итоги
Надеюсь, для вас оказался полезен этот инсайдерский взгляд на выполнение задачи по программированию с разбором слабых, хороших и наиболее грамотных решений.
Удачи вам на будущих собеседованиях!
Узнавайте о новых акциях и промокодах первыми из нашего Telegram-канала ????
Комментарии (142)
BadDancer
24.11.2023 13:14+13Нет, O(n) - сложность (время) прямо зависит от числа элементов.
O(1) - сложность не зависит от числа элементов, является константой.
Пример - получение элемента массива по индексу элемента - сложность O(1).
PATRI0T
24.11.2023 13:14Пример - родить одного или двух детей за один раз)
boojum
24.11.2023 13:14Двух - дольше
MiyuHogosha
24.11.2023 13:14-1Процесс заполнеия О(1), обработка О(1), затраты ресурсов О(n), вывод результатов О(n)
aegelsky
24.11.2023 13:14заполнения уже не О(1), если надо пройти все элементы - линейная сложность от количества.
или заполняем чем попало?)
Cerberuser
24.11.2023 13:14Синхронно выполняемая часть (то бишь то, что имеет значение для конечного пользователя) - таки O(1). O(n) там в фоновом процессе спрятано. Да и константа достаточно маленькая, чтобы на реалистичных значениях n не играть роли.
aegelsky
24.11.2023 13:14-4там местами можно попридираться ещё сильнее)
Более грамотные специалисты догадываются, что скорость поиска O(1), необходимую для превращения O(n²) в O(n), может обеспечить словарь (Map). Лучшие же кандидаты предусмотрительно отмечают недостаток такого подхода, заключающийся в использовании O(n) памяти. Здесь повышение скорости достигается за счёт увеличенного потребления памяти.
словарь (Map) создать тоже займёт время => супрЫз, общая сложность уже не О(1)
faiwer
24.11.2023 13:14+4Никто и не говорил, что общая сложность будет
O(1). Сказано только что поиск значения по ключу в словаре этоO(1). Если вам нужно сделать 100 поисковых операций то это O(1 * n). Т.е.O(n)
ArkadiyShuvaev
24.11.2023 13:14Мне кажется, там что-то про константу было. Вроде как ее можно игнорировать, оставляя только n.
faiwer
24.11.2023 13:14-1Убрать
1изO(1)вы не сможете. Одну операцию сделать всё же придётся :)Но да, константы игнорируются, когда они ни на что не влияют.
O(2n)это тоже самое, что иO(3n)иO(n+3.14)иO(n). Но совсем не то же самое, чтоO(n^2)илиO(2^n).
nin-jin
24.11.2023 13:14Не константы игнорируются, а все степени полинома, кроме максимальной, так как не влияют на асимптотику.
GospodinKolhoznik
24.11.2023 13:14+5Существует простейшее решение, которое выполняется за O(n²) времени, но использует всего O(1) памяти
Такого решения не существует. По видимому имеется ввиду, что данные не загружаются в ОЗУ, а постоянно считываются с жёсткого диска и ответ постоянно же записывается на жёсткий диск. Однако с точки зрения оценки сложности алгоритмов даже использование магнитной ленты машины Тюринга расценивается именно как использование памяти.
И этому дядьке, который провёл 100500 собеседований не к лицу писать такие вещи по O(1) по памяти, когда он по сути использует своп вместо ОЗУ.
n43jl
24.11.2023 13:14+17Мне кажется просто входные данные не учитываются при оценке сложности по памяти, а учитывается только сложность добавленная имплементацией решения/алгоритма, и она константа и не зависит от входных данных => O(1) памяти
GospodinKolhoznik
24.11.2023 13:14+3Чтобы хранить выходные данные потребуется O(n) т.к. количество лояльных клиентов в первом приближении линейно зависит от общего числа клиентов n.
Либо на каждом найденном лояльном клиенте сохранять его на диск, что во первых безумие с точки зрения производительности, а во вторых всё равно потребляет O(n) с точки зрения теории сложности алгоритмов.
chupasaurus
24.11.2023 13:14+1Список клиентов можно не только записывать, но и читать, тем самым предоставляя O(1) по памяти и докидывает несколько раз n во время, но там всё равно O(n²).
bullgare
24.11.2023 13:14+2часто в оценке памяти не учитываются затраты на хранение как входных, так и выходных (результирующих) данных. то есть интересен именно оверхэд на то, что происходит в "чёрном ящике" нашего алгоритма.
BadDancer
24.11.2023 13:14+16Если специально не уточняется, то под памятью для алгоритмов всегда имеется ввиду именно ОЗУ, потому что раз данные есть, то значит дискового пространства для них хватило совершенно точно :-)
Для чтения требуется О(1), все правильно, и своп для этого не нужен. Просто читаем не каждый раз в новую область памяти, а в одну и ту же.
Завели буфер константного размера, прочитали часть файла в буфер, обработали, в этот же буфер прочитали следующую часть, пока файл не закончился. Памяти на чтение требуется ровно размер буфера, константный объем, не зависящий от размера файла, O(1).
Решал тестовое по подсчету уникальных айпи в 100гиговом тестовом файле, все отрабатывало за время чтения файла, JVM использовала меньше гига оперативы, и то только потому, что 512Мб надо было под флаги уникальности. Своп не использовался совершенно точно. И на диск в процессе я ничего не писал - не было нужды.
И этому дядьке писать про О(1) по памяти к лицу, т.к. он своп вместо ОЗУ не использует.
Upd. n - размер данных, т.е. здесь - число записей в журнале. Записей может быть 10 млрд, а клиентов 1млн, а страниц - 1000. Описанные автором структуры влезут в в условные 100 мб, а 10млрд записей по 100байт - терабайт.
xxxphilinxxx
24.11.2023 13:14+4С чего вы взяли, что есть какая-то запись на диск? Механизм может частью пайпа и по мере нахождения новых пользователей их сразу куда-то дальше переправлять, не дожидаясь конца обработки.
GospodinKolhoznik
24.11.2023 13:14-1мы хотим сгенерировать список «лояльных клиентов»
Исключительно по условию задачи я вижу, что алгоритм должен в итоге выдать список.
Т.е. в результате работы алгоритма должен быть получен список клиентов, а не список IO операций ввода вывода, как предлагаете вы. Это так с точки зрения теории типов. В не очень строго типизированной Java на это особо внимание не обращают, но вот например в Haskell это критично - там компилятор забракует ваш код, т.к. результат работы функции не будет соответствовать её сигнатуре.
А с точки зрения теории сложности я наверное старовер, в том смысле что сложность любого алгоритма оцениваю с точки зрения его теоретической сложности на машине тюринга. И если сказано, что в итоге должен быть получен список лояльных клиентов, то значит, что этот список должен быть в памяти машины по завершению работы, а не в памяти какой то другой машины.
xxxphilinxxx
24.11.2023 13:14+4Какие IO операции? Какие другие машины? Опять что-то выдумываете. Это может быть обход генератора или чтение канала данных в том же процессе, просто другим модулем. Вы сами придумали это ограничение, что список должен быть передан полностью законченным, и теперь пытаетесь всех убедить, что автор сам себя не понял и вообще профнепригоден.
С точки зрения ABI задача вообще не описана, поэтому отвечать на рассуждения о компиляторах и теории типов не стану.
Мне кажется вполне реальной ситуация, когда я реализовал этот механизм, собирающий полный список, а в памяти не помещается даже готовый список-ответ, поэтому пришлось, например, потратиться на вертикальное масштабирование. Затем приходит заказчик этой ерунды и спрашивает, почему так долго и дорого, и нельзя ли по частям, мол, ему так было бы проще. А единственным оправданием будет "вы же сказали список, а я это понял так".Хочу пару цитат из статьи привести:
В реальности инженеры постоянно сталкиваются с неоднозначностью, и корень большинства программных проблем можно найти в плохо определённых требованиях.
Наиболее грамотные кандидаты, прежде чем переходить к написанию кода, должны задавать уточняющие вопросы. Я рассчитываю увидеть в соискателях проявление рассудительности, так как в описанных условиях задачи присутствует двусмысленность.
GospodinKolhoznik
24.11.2023 13:14+6Чтение канала данных в том же процессе, просто другим модулем это самая настоящая IO операция.
Ладно, не хочу больше продолжать этот теоретический спор, а то мне уже кто то в карму успел минусануть.
Хотя самому мужику из поста я бы много чего мог рассказать, что если уж он подразумевает, что в результате выхода должен быть не список клиентов, а список IO операций, то тогда уж в данном случае идеально походит структура Stream f m r изобретенная относительно недавно Кисилевым, Снойманом и Гонзалесом. Это потрясающая и очень интересная структура, но ну его нафиг с такой благодарной аудиторией, которая минусит от души.
funca
24.11.2023 13:14+4Вы на самом деле подняли интересную тему, но как-то сходу принялись ему возражать.
сложность любого алгоритма оцениваю с точки зрения его теоретической сложности на машине тюринга
Здесь, насколько я помню, есть лента с входными данными для чтения и лента для записи результа. А все что между ними это и есть сам алгоритм - разные аспекты сложности которого мы хотим оценить.
В отношении оценки по памяти нас интересует не объем данных, который мы прочитали-обработали-записали, а сколько памяти нужно компьютеру, чтобы выполнить наш алгоритм. Поэтому то, что находится на лентах мы не считаем.
Автор пишет:
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), его интересует лишь дополнительный объем - без учёта входных и выходных данных. В самом деле, они заданы условиями задачи и будут всегда одинаковыми, поэтому при сравнении алгоритмов ими можно пренебречь.
В общем если зачем-то очень хочется, то дядьку можно упрекнуть в некоторой нестрогости изложения. Но с другой стороны, это публицистика, а не научная статья, чтобы устраивать ему за это вендетту.
ARad
24.11.2023 13:14+4O(1) дополнительной памяти, сами исходные данные он не оценивает и в этом есть смысл.
nik135
24.11.2023 13:14+40"карта"? м.б. лучше оставить map?
tenzink
24.11.2023 13:14+15Перевести map как карта в этом контексте - это насилие над здравым смыслом
Kickoman
24.11.2023 13:14+4Если уж так хочется перевести, то можно использовать давно устоявшийся в определённых кругах "словарь", имхо.
SergioShpadi
24.11.2023 13:14Почему?
Логика, по которой и карта и структура данных называется в английском одним и тем же словом map, имеет смысл. Map - это отображение 1 к 1 одного множества на другое. Каждая точка на карте отображается на точку реальной местности.
bromzh
24.11.2023 13:14+2Слово set можно перевести на русский около 100 способами. Но это не значит, что надо в статьях по программированию переводить set как "закат" или "брусчатка".
Каждая точка на карте отображается на точку реальной местности.
Учитывая физические ограничения карты, одной точке соответствует не точка, а некая площадь, так что это не совсем честная биекция.
pae174
24.11.2023 13:14+28Фильтр "клиент посетил сайт в первый и второй день" выдаст ложно-положительное срабатывание на клиентах, заходящих на сайт незадолго до полуночи. То есть если в 23:59:59 будет запрошена одна страница а в 00:00:01 вторая, что такой клиент автоматически будет считаться таким же лояльным, как и клиент, заходивший на сайт два дня подряд в обеденный перерыв.
alexkuzko
24.11.2023 13:14... Тогда надо будет добавить ещё условие на то чтобы между запросами было... Не меньше четырех-шести-восьми часов )) Смотря сколько кто спит. Хотя конкретно ваша проблема отсеивается буквально считанными минутами-десятками. Но по духу условия надо чтобы человек посетитель поспал между запросами ))
ktotomskru
24.11.2023 13:14+1ага, и ещё тайм-зону добавить, у клиента это может быть ещё сегодня, а на сервере уже наступило завтра
Ivan22
24.11.2023 13:14а помоему это реально клиент заходивший на сайт два дня подряд. Абсолютно честно
Akina
24.11.2023 13:14+10А я бы объединил файлы и сортировал как один массив. Тогда достаточно одного указателя плюс хранение предыдущего состояния (ну или два указателя, смещённых относительно друг друга на одну позицию) плюс битовый флаг смены даты и адреса страницы..
adeshere
24.11.2023 13:14А я бы объединил файлы и сортировал как один массив.
А сортировать-то зачем? Не проще сделать почти плотный массив, вычисляя там номер записи по CustomerID? Тогда заполнение массива (со слиянием двух журналов) делается за один проход, а обработка - тем более...
amphasis
24.11.2023 13:14Не совсем понятно про
вычисляя там номер записи по CustomerID
В общем случае это может быть хоть GUID, хоть ObjectID какой-нибудь
adeshere
24.11.2023 13:14Ну да, для этого нужна будет отдельная функция, адаптированная к стилю назначения CustomerID. В худшем случае (если логика в значениях CustomerID не просматривается), и есть риск получить кучу коллизий в хэш-таблице, то придется что-то изобрести, чтобы их как-то минимизировать. Но все равно это О(1).
А обратная функция и вовсе бесплатна практически, т.к. исходное значение CustomerID мы запишем в структуру с его историей, которая намного больше в размере.
vodevel
24.11.2023 13:14+22Если уже идти во все тяжкие оптимизации, то зачем вообще держать множества для страниц?
Можно обойтись простым <userId>: <string>. При этом не пустое значение будет означать, что у пользователем посещена только эта страница. А пустое значение - признак посещения более одной страницы. Т.е.
Первый день:
Если пользователя (ключа) нет в коллекции, то добавить туда вместе со значением страницы
Если пользователь есть, и значение страницы пустое, то пропустить.
Если пользователь есть, и значение страницы не совпадает с текущим, то заменить его на пустоту.
Второй день:
Если пользователь есть, и у него либо пустая строка (признак), либо строка не совпадает - то это лояльный пользователь.
ARad
24.11.2023 13:14Только не надо строку. Если тип ID уже не строка. Это удар по производительности и памяти. Часто ID позволяют выделить спец. значение, например если тип ID это int, а отрицательных в данных не бывает. Или если ID это GUID то можно использовать любой случайный для флага.
Существует риск совместимости с будущими изменениями. Например разрешили любые целые значения. Тогда лучше завести отдельный флаг или использовать алгебраический тип, если язык позволяет.adeshere
24.11.2023 13:14+9Только не надо строку. Если тип ID уже не строка. Это удар по производительности и памяти. Часто ID позволяют выделить спец. значение, например если тип ID это int, а отрицательных в данных не бывает. Или если ID это GUID то можно использовать любой случайный для флага.
Хорошо Вы живете ;-)
А я вот научный сотрудник, и сплошь и рядом получаю файлы с чужими рядами данных. Так у меня уже в подкорке зашито, что в чужом файле надо быть готовым к чему угодно. Не важно, что там в доках написано. Особенно если с данными на каком-то этапе поработали в Excell (тогда вообще жди беды на каждом углу). Хотя и журналы вряд ли существенно в лучшую сторону отличаются, так как туда обычно много всякого разного пишется, и нужные строчки не всегда можно очевидным образом отобрать.
Поэтому у меня уже рефлекс выработался: сначала все читать в string. И только потом, после проверки и разбора, конвертировать во что-то более адекватное типа чисел. С чем уже можно более-менее эффективно работать.
Хотя возможно, что это у меня просто профдеформация, так как я пишу на фортране, и без такого анализа я даже адекватную диагностику не смогу получить: в какой именно строке, в какой позиции и что именно вызвало подозрения. Фортран ведь всеядный, и если какой-то фрагмент строки можно в число превратить, то он разбираться не станет - просто прочитает, и все. А если нельзя, то еще хуже - выдаст ошибку, и тоже все. Поэтому проверять данные на соответствие каким-то требованиям мне приходится самому. Чтобы потом не тупить недоуменно над результатами из-за того, что в каком-то месте исходника точка поменялась на запятую, или наоборот...
PVoLan
24.11.2023 13:14+10Это отличная идея с точки зрения технической оптимизации, но она обладает фундаментальным недостатком, а именно: если завтра критерий лояльности изменится с "посетил 2 страницы" на "посетил 3 страницы", то вам придется переписывать примерно все.
То есть подобную оптимизацию можно проводить, только трижды согласовав проблему с бизнесом: а нам точно-точно всегда-всегда будет достаточно двух страниц как критерия лояльности? Из моего опыта, даже если менеджер отвечает "точно да" на этот вопрос, верить ему не стоит, т.к. он банально не понимает жизни.
Schalaeff
24.11.2023 13:14+8только трижды согласовав проблему с бизнесом: а нам точно-точно всегда-всегда будет достаточно двух страниц как критерия лояльности
вам ответят "да", а после релиза попросят сделать 3 страницы, ибо "ну теперь вот видно, что 2 страницы мало")))
vodevel
24.11.2023 13:14+3Это точно!) Я вообще больше рофлил, чем пытался дать ценный совет. Эти "любимые задачки" от глубоко окопавшихся в конторе сансеев всегда обрастают таким искусственным налетом, что сложно их воспринимать как реальные кейсы. Решать с закосом под продакшен или под спортивное программирование? Выбор похож на две чашки с ядом, к которому у собеседующего уже отличный иммунитет.
Alexandroppolus
24.11.2023 13:14+7Насколько я понимаю, самым "устойчивым", т.е. потенциально готовым к изменению условий, решением будет самое простое: использовать единственный Map<userId, Info>, где в Info собирать стату по юзеру, и добавлять в массив результатов userId, только если на данной итерации стата достигла требуемого условия. Так мы заодно исключаем дублирование userId в массиве результатов и делаем всё за один цикл.
vmarunin
24.11.2023 13:14И мапа, и два указателя с предварительной сортировкой довольно устойчивы к изменению условий.
Надо три страницы - делается 3. Надо 2 в один день и 3-ю в другой - тоже делается.
И код будет не сильно длиннее текстового описания задачи
sim31r
24.11.2023 13:14+2Но если записей много в журнале, будет переполнение памяти. А если у нас всего 640к оперативки? По заветам разработчиков DOS. Тогда берем и переписываем исходный файл на маленькие файлы, пока они не станут помещаться в памяти. Условно пользователи с именами начинающимися на А-Д в файл 0001.TXT, пользователи с именами Е-К в файл 0002.TXT и так далее (правильней по хешу, но так нагляднее). Если файлы большие еще режем на кусочки и далее обрабатываем по вашему алгоритму или сортировкой. То есть вместо одной большой базы в виде текстового на гигабайты данных у нас остается много маленьких файлов, вплоть до 1 файла на пользователя если памяти вообще мало и их быстро обрабатываем.
vodevel
24.11.2023 13:14+1640кб оперативки? Не, это слишком по-богатому. Не забывайте, мы в космосе! В нашем распоряжении бесконечное количество магнитных бобин, но оперативки завезли только на 1к, для просмотра сайтов. Файлы с логами в формате "USER_ID:URL\n" (1 символ - 1 байт). Поэтому
Первый день:
Открываем поток на чтение файла первого дня
Не спеша читаем ид пользователя (пока не дойдем до знака ":")
Проверяем, если файла "1-USER_ID" не существует, то создаем поток на запись этого файла и побайтово записываем туда урл (пока не дойдем до знака "\n")
Если файл есть и он пустой, то пропускаем
Если файл есть и он не пустой, то открываем еще один поток на его чтение и побайтово читаем с двух потоков до первого отличия, и если такое находится - делаем файл пустым.
День второй:
По аналогии читаем файл 2-го дня, получив ид пользователя, проверяем файл "1-USER_ID", если файл есть и он пустой, либо его содержимое не совпадает - то это лояльный пользователь. Удаляем файл 1-USER_ID и мигаем светодиодом два раза.
faiwer
24.11.2023 13:14+11Возможно я плохо выспался или плохо прочитал условие. Но чем плох вариант с `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) }
iamawriter
24.11.2023 13:14+7Удивительное по-прежнему рядом. Насколько я могу судить - это задачка уровня 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.
wataru
24.11.2023 13:14Не, тут хешмап надо применить правильно, так что это medium как минимум. А так у вас почти такое же решение как и у автора. У вас тоже мап из userid в список страниц.
ef_end_y
24.11.2023 13:14+1Тут оверхед - зачем накапливать страницы в users[user] когда после двух уже ясно, что результат для юзера достигнут?
iamawriter
24.11.2023 13:14+2Я прямо растерялся. Но попробую ответить. Я думаю, что при решении подобного рода задач не стоит гнаться за микрооптимизацией, которая то-ли случится, то-ли нет (у нас нет никаких дополнительных сведений о данных). К тому же, о такого рода оптимизации в формулировке задачи нет ни единого намека. При решении такого рода задач стремятся получить приемлемую сложность "О-большое", и при этом было бы очень желательно, чтобы реализация выглядела "лаконично" и понятно. Было бы здорово, если бы реализация допускала легкую модификацию при небольшом изменении входных данных. Например, у нас данные были бы не за 2 дня, а за 17. И "лояльным" пользователем следовало бы считать того, кто посещал не все дни, а хотя бы 8 из 17, и посмотрел за это время хотя бы 25 уникальных статей. Думаю, что предложенное мной решение в целом удовлетворяет требованиям, которые я перечислил выше. Ну и стоит сделать поправку на то, что я приступил к решению задачи, стараясь решить ее как можно быстрее и проще, имея при этом приемлемое значение "О-большое", так, как я бы делал это на собеседовании. Должен заметить, что я сначала я даже не стал читать комментариев автора, мне хватило условия задачи, оно показалось мне вполне понятным и достаточно определенным для того, чтобы можно было приступить к решению. А для любой микрооптимизации нужны веские основания и глубокое погружение в проблему, вряд ли стоит углубляться в это дело на собеседовании по собственной инициативе. Можно легко самого себя закопать, если начать придумывать себе проблемы на пустом месте. Но я не настаиваю, если вы способны предусмотреть всевозможные нюансы, убедительно объяснить необходимость их учета, и мастерски разрешить их прямо во время собеседования, то конечно, вы будете иметь преимущество.
VladimirFarshatov
24.11.2023 13:14+4Тоже первое что пришло в голову: слить и отсортировать оба файла при чтении в память раз "влезают".Дальше всё тупо.
TimsTims
24.11.2023 13:14+8мы хотим сгенерировать список «лояльных клиентов», отвечающих следующим критериям: (а) они посещали сайт в первый и второй день, (b) они посетили не менее двух уникальных страниц.
Условие задачи имеет вполне ясное и чёткое ТЗ. Так как ничего не сказано про дни, ничего не сказано про погоду, ничего не сказано про день рождения директора, ничего не сказано про любовницу, то и спрашивать про это здесь выглядит лишним. Часть кандидатов вполне четко и однозначно поняла ТЗ, а спрашивать в условиях стресса
глупыеуточняющие вопросы могли испугаться чтобы не показаться "тупыми".1.Имел ли я ввиду посещение двух уникальных страниц в день или всего?
Ну и следующий вопрос не возникает, если про дни ни слова нет. Уникальная страница - она уникальная между всеми днями.
2.Есть ещё один важный уточняющий вопрос, который упускают 90% соискателей: «А как быть с повторами?»
Поэтому первые два уточнения я бы вычеркнул. Насчет использования БД и SQL:
Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
Затем, что такую задачу, как даёт автор никто не ставит. Точнее ставят, но это лишь первый этап (считай детский сад), когда PO только только начинает играть в аналитику.
А дальше буквально сразу пойдут задачи типа: А узнай из каких стран они к нам приходят, а узнай как они вели себя в течение года, а прикрути к ним историю покупок, интересов, разбивку по полу/возрасту/странам/городам/именам итд итп и вот оказывается, что лучше бы ты сразу это всё запихнул в БД, и уже там бы строил все эти отчеты, графики, метрики. И причем тут тебя больше волновала бы структура хранения данных в БД, объёмы данных, механики работы БД, репликация и/или параллельность расчётов (hadoop), потоковая или периодическая(ночная) перекачка данных, итд итп. Поэтому на вопрос:
зачем вносить излишнюю сложность ..для того, что можно решить с помощью всего 20 строк простого кода?
Я бы всё-же подискутировал...
funca
24.11.2023 13:14+13Так как ничего не сказано про дни, ничего не сказано про погоду, ничего не сказано про день рождения директора, ничего не сказано про любовницу, то и спрашивать про это здесь выглядит лишним.
В этом, мне кажется, и стоит основная разница между мышлением олимпиадников и, назовем их, - коммерческих разработчиков.
Первые всецело доверяют постановщику задачи, понимают условие буквально и на этом сильно экономят своё время.
Вторые знают, что бизнес не умеет в буквальные формулировки, и поэтому сомневаются в каждом слове. Но в итоге это экономит деньги.
Оба подхода имеют право на существование, адекватный результат получается только в своем контексте.
Zara6502
24.11.2023 13:14+1проблема здесь в том, что возитесь с бизнесом вы, уточняете, а премию получит любой кроме программера, вы же типа просто сделали своб работу - закодировали, а бизнес мучился, придумывал, творил. Поэтому не сильно понятно зачем выходить за границы своей ответственности.
funca
24.11.2023 13:14Зато в олимпиадах, со стороны организаторов, все наоборот. Вы все организуете, придумываете интересные задачи, ищете участников по разным уголкам света, устраиваете мероприятие, и ещё делаете массу разных вещей. А все призы достаются кому-то другому. =)
Если серьезно, я согласен, что вопрос комплексный и его можно рассматривать с разных сторон. Моя позиция здесь - свою работу нужно делать максимально качественно. А если не устраивают компенсации, то менять работодателя.
Sulerad
24.11.2023 13:14Сильно зависит от компании и подходов. У меня, например, прямо сейчас премия напрямую зависит от того, сколько пользователей станут пользоваться моим кодом. И у меня довольно большая мотивация чуть подумать, провести 1.5 часа на встречах и отбросить какой-то узкоспециализированный функционал на время после выплаты премий, чтобы сейчас сэкономить себе пару дней его реализации и отполировать какие-то моменты.
У автора стоит задача нанять человека, который будет не тупо писать код. Он хочет человека, который будет держать в уме задачи бизнеса и разумно тратить своё время (и деньги работодателя).
Zara6502
24.11.2023 13:14У автора стоит задача нанять человека, который будет не тупо писать код. Он хочет человека, который будет держать в уме задачи бизнеса и разумно тратить своё время (и деньги работодателя).
Ну значит это будет в его должностной инструкции и ему за это будет платиться зарплата. Это его работа и он будет её выполнять. Не вижу противоречий со сказанным ранее.
Но если вы наняли программиста, а хотите от него "и жнец и кузнец и а дуде игрец", то либо получите дилетанта плохо выполняющего свою работу, либо сильную текучесть кадров, так как вы позвали человека делать одно, а требуете другое.
TimsTims
24.11.2023 13:14+1В этом, мне кажется, и стоит основная разница между мышлением олимпиадников и, назовем их, - коммерческих разработчиков.
Глобально в работе это так. Я бы уточнял и спрашивал детали. Но это собеседование, которое больше направленно на алгоритмы, чем не проработку ТЗ. Там прямо в условиях задачи очень технически прописаны условия, что есть такие-то файлы, структура такая-то, надо решить такую-то задачу, и только её.
Если всё-же спрашивать наводящие вопросы и пытаться изначально решить проблему бизнеса (а не просто написать алгоритм), то стоит обсуждать вопрос дальше глубже - а что дальше попросит бизнес, какой будет следующий шаг, нужно ли будет хранить историю, нужно ли будет ещё брать какие-то атрибуты из этого файла, и может это и правда всё засунуть в БД. Вот это всё будет интересовать бизнес на следующем шаге, а вовсе не концентрироваться сейчас и жестко в алгоритме на вопросе "а как считать уникальность страниц".
funca
24.11.2023 13:14+1Но это собеседование, которое больше направленно на алгоритмы, чем не проработку ТЗ. Там прямо в условиях задачи очень технически прописаны условия, что есть такие-то файлы, структура такая-то, надо решить такую-то задачу, и только её.
Автор про это написал, что его в первую очередь интересует как раз диалог, а не код:
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?
Я тут не спорю с тем, плох ваш подход или хорош. Бывают ситуации, когда именно так и надо поступать. Но в данном случае это ваше допущение, а их нужно всегда проверять.
GospodinKolhoznik
24.11.2023 13:14+4Да брешет он. Т.е. все так говорят, что главное диалог а не код. Но по факту оффер предлагают только тогда, когда удается все решить. А когда по какой то причине не удается решить, то говорят так "вы хорошо излагаете мысли, и правильно рассуждаете, но вам наверное просто надо попрактиковаться в решении задач".
TimsTims
24.11.2023 13:14Да тут в принципе все правы. Никогда не знаешь, что в голове у интервьюера, и что он хочет услышать.
antonkrechetov
24.11.2023 13:14-1зачем вносить излишнюю сложность ..для того, что можно решить с помощью всего 20 строк простого кода?
Ответ, на мой взгляд, такой: решение, изложенное в статье, пишется за 15 минут и полностью удовлетворяет требованиям, которые есть здесь и сейчас. Когда понадобятся более сложные метрики, такое решение можно просто и относительно безболезненно выкинуть и начать думать в сторону БД.
Не стоит бояться одноразовых решений для конкретных задач. Потому что а) в определённых обстоятельствах всё равно придётся всё переделывать из-за изменившихся требований, и б) выкидывать решение, сделанное за 15 минут не так обидно, как если разработчики потратили месяцы на сложное решение, а бизнесу нужно срочно масштабироваться, а бизнесу нужно масштабироваться вниз.
DBalashov
24.11.2023 13:14+1А дальше буквально сразу пойдут задачи типапоэтому с точки зрения практики такие данные уезжают в аналитическую БД и оттуда group by/having или аналоги. Это ещё в условии не появились часовые пояса, где надо разбивать сутки и считать "лояльность" и "уникальность" по часовому поясу конкретного юзера.
А задача - чисто на подумать.
adeshere
24.11.2023 13:14+2Тоже первое что пришло в голову: слить и отсортировать оба файла при чтении в память раз "влезают".Дальше всё тупо.
Я пишу на фортране, поэтому я бы все-таки при чтении журнала :
1) слил два файла в один (т.е. сделал один общий список юзеров) и
2) конвертнул бы при чтении полученный журнал в свой внутренний формат, чтобы вместо строк получить числа и сэкономить память. Тогда каждое посещение страницы упаковывается в 8 байт (ID страницы + время в секундах).
Ну и еще мне нужна будет функция, которая преобразует CustomerId в более-менее плотный массив номеров пользователей. Чтобы без какой-либо сортировки не искать пользователя по файлу, а сразу на него попадать, просто вычисляя номер записи по CustomerId.
Итого у меня получится один массив структур, где элемент (структура) номер P содержит всю историю пользователя номер P (его CustomerId можно там же хранить, чтобы с обратной функцией не заморачиваться). Согласно ТЗ, нам надо хранить историю за два дня, причем критически важны первые две уникальные страницы... но в таком сжатом виде ничего (кроме ограничений памяти) не мешает хранить и более полные данные за более долгий срок, если только сайт не сверхпопулярный. Например, если моей программе доступно 10Гб ОП, то в описанный массив структур можно загнать несколько миллионов юзеров, и для каждого хранить
по сотне номеров страниц с меткой времени
Правда, для гиперактивных пользователей, которые больше сотни страниц посетили, тогда придется сделать отдельную таблицу, и скидывать туда избыточные страницы (сверх первой сотни). Для этого придется добавить в каждую структуру указатель на дополнительный список, который придется использовать при переполнении основной структуры. Со всеми вытекающими траблами (резкое замедление доступа и т.д.). В общем, такой подход будет работать, только если большинству юзеров хватит основного массива (это надо по фактической статистике сайта заранее уточнить - прокатит такой алгоритм, или нет).
Но если хватит - то возможности анализа/обработки расширяются многократно. Так что это уже вопрос к заказчику: планируется ли расширение задачи в будущем (для которого полная история требуется), или нет, и сколько памяти ему на это не жалко...
В таком варианте основная трудоемкость задачи выносится в предобработку, т.е. в процедуру чтения файла журнала во внутреннее представление. Зато потом у меня будет список юзеров с полной историей каждого. Из которой я могу извлечь любую статистику, которую захочу, за время О(N*m), где N*- число юзеров, а m - число посещенных страниц. Причем N*m получается для более продвинутых статистик, а в случае ТЗ-задачи m можно уменьшить до 2, что еще более улучшает картину.
Впрочем, пока мой массив умещается в память, статистика по юзерам в любом случае будет считаться "на лету". Если, конечно, количество гиперактивных юзеров (чью историю придется подгружать из дополнительной таблицы) не очень большое.
Итого, самой тяжелой операцией будет загрузка веб-журнала (там ведь данные могут быть в виде строк и вообще какие угодно). Поэтому если нужно обрабатывать историю не за пару дней, а побольше, то я бы еще сделал функцию, которая скидывает мою внутреннюю базу на диск и обратно. Фортран обычно пишет в файл данные прямо в машинном представлении, без какой-либо конвертации. Это почти что дамп памяти - т.е. намного быстрее, чем журнал декодировать. Ну и еще придется делать функцию, которая будет чистить внутреннюю базу от устаревших записей, но это совсем просто.
Итого для сайта с небольшим числом уникальных юзеров (миллионы) и умеренным количеством уникальных страниц, посещаемых за один визит большинством юзеров (сотня за несколько дней) получается алгоритм О(N), но который займет порядка 10Гб памяти.
SquareRootOfZero
24.11.2023 13:14+2Для сайта с небольшим числом уникальных юзеров (миллионы) и умеренным количеством уникальных страниц (в пределах 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), все дела.
adeshere
24.11.2023 13:14+2Всего-то порядка 8Мб на миллион юзеров, 8Гб на миллиард, O(N), все дела.
Так о чем я и говорю ;-)
Только я бы все-таки прочитал журналы во внутренний формат предварительно, что позволяет легко масштабировать задачу на N дней вместо двух, и на другие статистики обобщить, когда спросят. Пусть и ценой кратного роста требований по памяти (т.к. я в свою табличку предлагаю целиком все данные загружать, а не только то, что нужно для конкретной задачки. Благо, для типичного сайта средней руки (миллион открытых страниц всеми юзерами в сумме в день) обычной десктопной памяти с лихвой хватит. Хотя и компакт-вариант алгоритма, разумеется, тоже возможен).
Ну и еще, мне очень хочется вынести работу с журналом в отдельную процедуру. Впрочем, это у меня наверно
тоже профдеформация
я просто не могу себе представить журнал, в котором нет ошибок и глюков ;-) Поэтому я бы их обработал в отдельной функции загрузки журнала, а не в основном цикле. Заодно убрал бы из журнала всякие посторонние записи (в ТЗ про них не сказано ничего, значит они там наверняка будут ;-)
Ну и копирование данных во внутреннюю табличку с их группировкой по юзерам позволит в будущем легко вычислять другие статистики, кроме ТЗ-шной. Тут же уже говорили, что утром следующего дня менеджер
обязательно это попросит ;-)
Кстати, это не только в бизнесе так. У нас в науке ТЗ точно также корректируется практически всегда "на лету", по мере знакомства с первыми результатами. Разница только в том, что вместо менеджера часто ты сам себе ТЗ корректируешь. Поэтому принцип "не закладывай в программу то, что может понадобиться потом" (а может и не понадобиться) у нас далеко не так актуален, как у нормальных людей ;-) Я заранее знаю, что в 2/3 случаев мне придется все переделывать, как только алгоритм заработает... как говорится, для этого не обязательно к бабке ходить ;-)
igrishaev
24.11.2023 13:14Ну хорошо, задача интересная. А какие исходы? Предположим, кандидат присидел час и не решил. Не берем?
himch
24.11.2023 13:14+4Я вот так решил, но я бы точно с таким решением не прошел бы)
import pandas as pddf1 = pd.read_csv('day1.csv')df1['Day'] = 1df2 = pd.read_csv('day2.csv')df2['Day'] = 2df = 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)
igor_suhorukov
24.11.2023 13:14+1Хорошо, подход более инженерный чем у всех остальных кандидатов!
Было бы интересно увидеть как вы решили бы эту же задачу на Polars и DuckDB в Python. И в сравнение и область применимости panda/polars/duckdb
iamawriter
24.11.2023 13:14+1Есть мнение, что подобное решение - основанное на "сторонних" библиотеках - на "стандартном" алгоритмическом собеседовании не приняли бы. Насколько я знаю, для решения алгоритмических задачек иногда разрешают использовать стандартную библиотеку, и только.
igor_suhorukov
24.11.2023 13:14+1Не знаю, я проходил лидом в берлинский стартап - job offer так получал.
Нужно понимать алгоритмическую сложность, понимать как работает то что используешь и обходить стороной тех кто пишет свои велосипеды для аналитики...
kenoma
24.11.2023 13:14Не совсем по теме, но зачем нужен DuckDB при живом то Sqlite?
igor_suhorukov
24.11.2023 13:14SQLite действительно живее всех живых и является предком DuckDB.
Можете рассматривать DuckDB как SQLite для аналитики, так как модели данных у них и подход к построению базы отличаются. Как минимум лучше чтобы делать запросы быстрее работающие с агрегацией данных и работать с форматами данных из Big Data мира: parquet, arrow, iceberg.
kenoma
24.11.2023 13:14А можете ткнуть в сторону бенчмарков?
igor_suhorukov
24.11.2023 13:14+1Есть три вида лжи: ложь, наглая ложь и бенчмарк.
Конечно: https://benchmark.clickhouse.com/ А можно начинать с документации что это и зачем.
bay73
24.11.2023 13:14+2А вы можете для своего решения сложность (по времени/памяти) указать?
Если сможете и обоснуете, то вполне нормально.himch
24.11.2023 13:14+1Чтение данных О(n), где n - суммарное количество записей в журналах.
Конкатенация пускай тоже О(n).
Groupby внутри сортирует данные, так что O(n + k*log(k)), где k - количество уникальных пользователей
Query - О(k).
Итого, как мне кажется, O(n + k*log(k))funca
24.11.2023 13:14-4Развивая идею, чтобы определить асимптотику лучше не гадать, а делать эксперименты и собирать метрики в отчёты с красивыми графиками - как это принято у data science вообще или нагрузочных тестировщиков в частности.
Понятия алгоритма и алгоритмической сложности это абстракции. Для анализа работы реальных комплексных приложений такой подход не сильно практичен. За каждым интерфейсом может скрываться что угодно: от гениальных оптимизаций до досадных ляпов - причем с флуктуациями от версии к версии.
funca
24.11.2023 13:14В теории можно написать простой SQL-запрос и, конечно, крупные компании имеют огромные хранилища, в которых вы можете запросто подобное реализовать.
У меня первая ассоциация была Splunk.
Но в рамках собеседования нам это не нужно. Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
Можно просто уточнить, что интересует алгоритм, а не приложение. Это сразу отсекет массу вопросов про архитектуру, https://en.m.wikipedia.org/wiki/Non-functional_requirement и варианты написать программу с использованием высокоуровневых библиотек.
Germanets
24.11.2023 13:14+1Интересно, что никто толком не придаёт значение того, что данные распределены в файлы по дням, то есть для многих сайтов день1 может иметь миллион записей, а день2 - тысячу, просто потому что день2 - это выходной..
Да и сама задача решается не особо инженерно, без мыслей о том, что вслед за двумя днями будут идти ещё десятки таких же дней, и к уже третьему дню было бы неплохо подготовиться, а не снова идти по файлу из день2 и перебирать все строки..adeshere
24.11.2023 13:14+1и к уже третьему дню было бы неплохо подготовиться, а не снова идти по файлу из день2 и перебирать все строки..
Так а чем Вам не нравится идея конвертации файлов журнала во внутренний формат с фасовкой данных по юзерам? Я конечно сюда из дикого заповедника заглянул, и в профессиональной специфике ни бум-бум. Но у меня получается, что пока данные лезут в память (а это нам вроде бы обещали), то самое тупое решение "в лоб" на древнем языке программирования на этапе расчета статистик будет иметь сложность O(N), где N-число даже не посещений, а юзеров. А самой тяжелой операцией будет разбор журнала во внутренние таблицы (и тут уже сложность O(M), где M-число записей в журнале). Поэтому разбор журнала лучше выполнять один раз для каждого нового файла с журналом, а потом сбрасывать получившуюся табличку (кумулятивную) на диск во внутреннем формате программы, что де-факто бесплатно
раз в сутки же ;-)
а если серьезно, то дамп памяти по-любому
кратно быстрее
Я тут неявно учел, что фортран мой массив структур в файл в машинном представлении скинет /прочтет. Про современные языки я просто не в курсе, но было бы удивительно, если там такую опцию не предусмотрели. Так что я надеюсь, что это на любом языке будет работать..
чем журнал разобрать. Не говоря уже, что размер таблички во внутреннем представлении на порядок меньше размера журнала...
Зато потом можно не только запрошенную статистику вычислять, а "чего изволите".
При этом решение получается расширяемое во все стороны: если завтра потребуется статистика за неделю, или алгоритм учета лояльности поменяется, то надо будет всего одну функцию изменить - ту, которая таблицу посещений текущего юзера анализирует.
Но, конечно, на сайты с большим числом посещений это решение масштабируется почти что никак. Как только суммарное число записей в "горячих" журналах (за последние несколько дней) приблизится к миллиарду, моя табличка в память перестанет влезать, а это
немедленный крах
Да, его можно слегка отсрочить, если при повторном посещении страницы обновлять время, а не создавать новую запись в табличке. Но при этом часть данных из журнала будет утрачена... поэтому моя профдеформация геофизика противится это делать ;-) Хотя по логике юзеры довольно часто на одни и те же страницы заходят, так что экономия может получиться в разы. Но в любом случае сайт уровня амазона не то, что на ноуте - на севере с тербайтом памяти таким методом не прокрутишь...
vagon333
24.11.2023 13:14+5Неоднозначный подход - ожидают что разраб должен быть proactive, находить gaps в задании и задавать уточняющие вопросы, но исключают использование БД и SQL как redundant для scope, хотя этот подход также proactive (и масштабируемый за пределы доступной памяти).
Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
При хранении данных в базе, собственно запрос (без обвязки на подключение и рассоединение) не больше 3х строк.
action52champion
24.11.2023 13:14Да нет же, подход вполне однозначный: разработчик должен задавать уточняющие вопросы, но только такие, которые его величество собеседующий сочтет стоящими исходя из своего опыта и уровня интеллекта.
onegreyonewhite
24.11.2023 13:14+4Проблема таких собесов в том, что люди покажут только как они умеют изобретать велосипеды и подпирать костылями дурные решения. Моё собеседование бы закончилось тем, что я задавал бы вопросы в духе "а нафига вы данные в файлик писали?" или "это вы постоянно так решаете (aka изобретаете) проблемы?"
Программиста надо проверять в том поле, где будет его покрытие. Если это веб-разработчик или что-то про разработку (микро-)сервисной архитектуры, то лучше спросить про сеть или HTTP, про алгоритмы сжатия, задержки или хорошо по SQL прогнать (там задачек по дискретной математике хватит на полжизни).
Случай из жизни
Был у кореша в офисе, когда он не мог решить одну прикладную задачку с задержками и нужно было переделать архитектуру. Он заодно попросил поучаствовать в собесе нового фронтендера.
Сижу, значит, слушаю их (кореш, их тимлид из фронтендеров, hr'очка). А вопросы, значит, про алгоритмы, про матанализ, про протоколы, про SQL, про Linux... Я тихонько скидываю сообщение другу: "а чё, у вас часто фротендеры этим занимаются? Они же вроде у вас формочки почти всё время клепают. Спроси про вёрстку парня!" Буквально кореш получил сообщение, собеседуемый выдаёт: "Слушайте, а у вас фротендеры часто с этим работают? Чем вообще я буду здесь заниматься?" Мы вдвоём складываемся пополам от громкого хохота в голос, после чего кореш поворачивается к hr'очке и со слезами на глазах: "оформляй!"
Кстати, этот парень там быстро поднялся и оказался очень толковым. Хотя про SQL, линукс и алгоритмы довольно слабо отвечал.
Если человека в команду берут не на позицию разработки движка чего-то там с нуля, то зачастую стоит проверять на знание фреймворков и библиотек. Если хотите проверить сеньористость, то проверьте глубокие знания языка. При этом убедитесь, что сами знаете матчасть (а то такой цирк с конями был в жизни, что даже вспоминать страшно).
Лучший способ дать комплексное творческое тестовое, а потом на встрече его обсудить, если оно в целом стоит обсуждения. Но это задание должно быть:
приближенным к актуальным задачам
сделано в комфортном для кандидата режиме (но в рамках общего окна)
не делать его под присмотром (пусть дома сядет и спокойно сделает)
вылажено в портфолио на Github/Gitlab в открытом виде (помощь человеку с портфолио).
При этом уважительно надо общаться с обеих сторон. Дерзкие дегенераты с обеих сторон раздражают и вызывают глубокое отвращение в будущем к компании. После общения обе стороны должны получить профит в виде опыта и приятные воспоминания. Почему? Да потому что это networking, а земля круглая. Если в вакансии ни слова про алгоритмы, то и не проверяйте это. Проверьте именно то, что ищите.
Именно поэтому, сколько помню найм к себе, то люди потом уходили ещё более вдохновлённые, чем приходили. Даже после отказа, многие были мотивированы на рост и уверен нашли хорошее место, где применили свои навыки.
Tsimur_S
24.11.2023 13:14+2Моё собеседование бы закончилось тем, что я задавал бы вопросы в духе "а нафига вы данные в файлик писали?" или "это вы постоянно так решаете (aka изобретаете) проблемы?"
В данном контексте автор собесит в FAANG конторы где эта штука поставлена на поток. Он может и сам бы был рад задавать открытые вопросы но их собесы жестко стандартизированы и за шаг влево шаг вправо - расстрел. Поэтому такое поведение оно контрпродуктивно.
Если вам не интересен офер то непонятно зачем вообще приходить туда на собес зная наперед что там будут задачи с LeetCode. Ведь вы изначально в невыгодной позиции, собеседующему этот час оплатит компании а вам нет.
Если интересен то в лучшем случае вы урезаете свое время. Его и так немного, 45 минутный конвейер из 2 задачек.
Самой компании(из FAANG группы) же глубоко все равно на все эти инженерные "излишки", им нужно а) быстро б) фидбек сразу же в) стандартизировано. Если бы они не боялись судебных исков то просто давали бы стандартный тест на IQ, корреляция с реальной работой мне кажется была бы примерно такой же как и LeetCode задачи.
GoogleTan
24.11.2023 13:14-2Знаете, а я бы не хотела работать у вас… Для вас человек, страдающий преждевременной оптимизацией вместо поддерживаемости кода, предпочтительнее. Задачи написать быстро не стояло. Если писать весь код так, то… мне страшно представить кодовую базу вашу. Не правильнее было бы ожидать поддерживаемый код, а не быстрый?
faiwer
24.11.2023 13:14+4Обычно разница между "быстрым" и "медленным" алгоритмом, это разница в константе (время на итерацию). Если у вас разница в BigO, то (не всегда, но часто) это разница между "правильно" и "неправильно", а не между "быстро" и "медленно". Никакой преждевременной оптимизацией тут и не пахнет. Человек по сути проверяет знания азов computer science (по сути знания Map).
Не правильнее было бы ожидать поддерживаемый код, а не быстрый?
Нужно писать поддерживаемый код всегда. Даже когда сказано, что он должен быть очень быстрым.
GoogleTan
24.11.2023 13:14Почему это разница в BigO определяет правильность? Отправлю вас на кодфорс. Там все задачи красиво решаются с произвольным О, но если надо максимально быстро, то выйдет что-то страшное. Не дай бог такое писать в продакшене. И написать это поддерживаемо просто невозможно, так как никто не будет понимать твой fast inverse square root. Подводя итог: оптимизация может очень портить код, когда в этом нет никакой необходимости: задача об этом не просит.
wataru
24.11.2023 13:14+5Ну нет. Очень часто разница в BigO - Это разница между полным перебором и красивой структурой данных. И второе решение можно написать красиво и понятно, а вот полный перебор - почти всегда будет длинной странной рекусивной хтонью. Да, на олимпиадах весь код неподдерживаемый, потому что это write-only код для конкретной олимпиады. Но это не проблема алгоритмов, а проблема соревнований.
Вот когда уже не алгоритм выбирают, а начинают битовое сжатие, inverse square root и подобные трюки использовать в попытках ускорить решение в константу раз - вот там уже код страшный вылезает. И вот такое ни на олимпиадах, ни в продакшене часто и не надо, ибо это попытка выжать еще чуть-чуть скорости.
GoogleTan
24.11.2023 13:14-1Пример из поста. Я могу очень логично и элегантно написать решение за квадрат(на вскмдку). Он излишен конкретно для этой задачи, но его потом можно будет переиспользовать в отличие от процедуры, заточенной под супер конкретную задачу. Чтобы оптимизировать решение больше, придётся жертвовать обобщенностью решения т. е. как-то тонко эксплуатировать условия. И чем больше оптимизация, тем больше конкретизация под задачу. Под конкретную сейчас. ТЗ имеет свойство меняться, и придётся всё переписывать с нуля на ровном месте.
wataru
24.11.2023 13:14+1Я могу очень логично и элегантно написать решение за квадрат
Вам так кажется, пока вы не начали писать. Проверить, что userid оба дня встречается - еще получится примерно также просто написать, как по умному, а вот уже для 2 различных страниц у вас появится точно такой же map. И как-то с ним работать в двух вложенных циклах будет даже запутаннее, чем решение в посте.
Оптимальное решение с map-ом из set-ов страниц отлично дополняется под почти любые изменения. Хотите 3 разные страницы - легко. Хотите разные страницы в каждый день - делаете 2 мапа. Переписывания будут не сильно сложнее чем в решении за квадрат, в котором тоже все, кроме двух внешних циклов придется выкинуть и переписать с нуля при каком-то более хитром изменении ТЗ.
faiwer
24.11.2023 13:14+1но если надо максимально быстро
Разница между максимально быстро и быстро, обычно, заключается не в BigO, а в константе между BigO. Всяким трюкам, позволяющим снизить накладные расходы.
оптимизация может очень портить код
Тут речь идёт не об оптимизации, а о выборе алгоритма. И я не припоминаю никаких случаев на своей практике, где нормальный код нельзя было поддерживаемо написать и чтобы код был "очень испорчен".
Хуже всего, в вебе, это чаще всего вопрос
мозговодной строки:return collection.reduce((acc, item) => { // ...some logic... - return { ...acc, [item.id]: blabla } + acc[item.id] = blabla; + return acc; })Люди фигачат
O(n^2)в абсолютно бессмысленных местах руководствуясь полу-религиозными нормами или просто ввиду не знания основ. Подробнее об этом писал тут.
DikyAV
24.11.2023 13:14+1Автор реально думает, что в состоянии изменить чью-то жизнь. Вершитель судеб. ))
Kiel
24.11.2023 13:14Наименование переменных с числами в названии - оно само по себе наталкивает на мысль, что в автоматизированной системе нужно работать с абстракциями и не хардкодить количество дней еще и не зашивать в именование переменных всё это дело. Но подбор персонала это очень сложная вещь! Тут можно и на ухищрения пойти, но такого кода в проде быть не должно в любом случае
faiwer
24.11.2023 13:14YAGNI с вами поспорит по этому поводу. Не нужно городить абстракции без необходимости.
xflower
24.11.2023 13:14+2Ох. Задача хорошая, а вот интерпретация её интервьюером... как бы это сказать...
Я когда такую задачу вижу, у меня сразу первый вопрос: мы этих пользователей хотим найти один раз для какого-нибудь ежегодного отчёта - и всё? Или каждый день и по нескольку раз?
Если первое, то O(n²), конечно, неоптимально, но приемлемо. К тому же просто, надёжно и легко расширяется.
Если второе, то вы, наверное, хотите спросить как нам гонять аналитику на большом количестве данных? Потому что не могу я поверить, что завтра руководство не потребует списка пользователей, которые заходят на сайт как минимум дважды в неделю за час до полуночи.
А то, что данные влезают в память - так это вообще провокация. Если этих данных больше сотни мегабайт, то сегодня влезают, завтра перестанут. Я на такое уже давно не ведусь.
Нет. Уж лучше про зайчиков и лисичек, которые в лесу меняются подарками спрашивайте: так хотя бы понятно, что спрашивающему решение нафиг не сдалось.
Ivan22
24.11.2023 13:14+3программисты открывают для себя реализации Nested Loop, Hash и Merge join - на файлах смотреть без регистрации и смс
iovodov
24.11.2023 13:14Map это все-таки O(log N), а не O(1). Поэтому решение, описанное в статье - это не O(N), а O(N log M), где M - число уникальных клиентов.
Ну и решение со словарями отдельно для 1го и 2го дня явно не тянет на лучшее. Выше уже приводился более оптимальный и универсальный (расширяемый на случай, когда дней станет не 2, а 3 и страниц не 2, а 5) вариант с единственным словарем, содержащим для пользователя посещенные дни и посещенные страницы и последовательным обновлением этого словаря из 1го и 2го файлов. Если хочется на первом этапе микрооптимизации, можно сначала не хранить список дней и страниц, а только флаг посещения первого дня, единственный PageID и флаг лояльности. Тогда при необходимости расширить условие будет единственное и понятное место, кототоре надо отрефакторить.Alexandroppolus
24.11.2023 13:14+1Map это все-таки O(log N), а не O(1)
Смотря что там внутри. Если дерево, то O(log N), если хэш-мэп, то амортизированное O(1)
Algrinn
24.11.2023 13:14Хороший пример того, что нужно кидать в Codility и отправлять перед собеседованием. И очень хорошо формулировать требования, насколько быстрый алгоритм вы хотите получить. Потому что неприятно проходить подобные собеседования. Можно, но неприятно. Сильно зависит от удачи. Не со всеми людьми приятно вживую контактировать.
gatoazul
24.11.2023 13:14Старость - это когда бегло просмотрел условия задачи, прикинул, что тут, наверное, понадобится база данных и потом смотришь вполглаза, как молодежь с задором упражняется.
BugM
24.11.2023 13:14Понимать что там внутри вашей БД полезно. Особенно когда БД становится на самом деле большой. БД работает по тем же алгоритмам. Хорошая БД должна смочь выдать оптимальную версию алгоритма по адекватному запросу.
Интересно становится когда вы понимаете что этот запрос должен работать нормально, а БД не может. Без знания алгоритмов и решения таких задачек в уме вы не сможете увидеть такие моменты.
RokhinSergey
24.11.2023 13:14Почему map, а не unordered_map?
buriy
24.11.2023 13:14Автор и имел в виду hashmap, просто имейте в виду, что в разных языках названия немного отличаются.
coal
24.11.2023 13:14Если речь идет о скорости, а память неограниченна, как в задании, то выгодно вместо словаря использовать массив размером в гигабайт, например. Где индекс массива - это порядковый номер записи за указанный день.
Такая реализация быстрее словаря, так как выборка по индексу моментальная. Также, можно сделать динамически изменяемый массив, как в списке, только быстрее на 5%. В итоге получится словарь-список.
Тесты показали, что при таком подходе можно делать выборку 4 миллиона записей в секунду за произвольный день. При этом, одновременно писать в эту бд 500 000 значений в секунду.
Ну и обработка массива дальше быстрее любых словарей. Только за 40 минут это не придумать, у меня ушел месяц на тесты и проверки скорости и перебор вариантов.
GospodinKolhoznik
24.11.2023 13:14Если индекс массива это номер записи, то как во всех этих записях найти юзера, который заходил в разные дни на разные страницы, кроме как дважды перебирая все элементы массива?
coal
24.11.2023 13:14Да, для каждого дня нужно перебирать отдельно, то есть в сумме два раза, а потом объединять множества. Однако, это будет быстрее за счет быстрого ядра - использование чистых массивов, плюс nosql база, где все значения одного свойства хранятся в своем отдельном файле. При загрузке файла целиком - сразу сделать сортировку для ускорения прохода по массиву.
Мне сложно описать всю идею, описание очень большое, хоть идея и основана на примитивах . А словарь – это конечно классно, но кушает в итоге намного больше памяти, плюс считать хэши для всего...
Проще описать результат моего подхода за счет грамотной структуры файловой бд, а также чистых массивов.
По результатам тестов: я могу в реальном времени листать через интернет график в 4млн значений на экране, по любому параметру и за любой период. И это не в виде картинки, а строя по данным из бд и со сложной обработкой прореживания. Аналогично - с листанием таблиц через веб, только там прореживания уже нет.
coal
24.11.2023 13:14Просто я хочу сказать, что алгоритм - отнюдь не самое затратное место, надо рассматривать в комплексе, включая бд. И даже использование словарей.
OKonstantin
24.11.2023 13:14+1Мораль басни: перед тем как решать тестовое задание, если ты не читаешь мысли, уточни что хитрый собеседующий молчаливо ждёт от тебя не вставив в требования. Может он фанат ломбок и не станет читать код без него :) если он занимается хайлоад то вероятно что задача на производительность, ресурсы и т.д.
aegelsky
никогда не видел раньше O(1), что тут подразумевается, О(n)?
T-D-K
Это означает, что сложность алгоритма не зависит от размера входных данных. Это не означает, что алгоритм быстрый, это просто означает, что какого размера не были бы данными, время работы/размер дополнительной памяти алгоритма будет всегда одинаковым (грубо говоря).
Тут есть про это: https://ru.wikipedia.org/wiki/Временная_сложность_алгоритма
aegelsky
есть пример реальной задачи со сложностью О(1)?
получать что-то из какого-то массива не предлагать (с)
т.е. чтобы была реальная задача и её общий алгоритм был прям труЪ О(1), а не О(n).
я что-то ничего придумать не смог пока.
faiwer
Обычно это что-то прямо связанное с математикой. Например поиск суммы членов геометрической прогрессии. Можно посчитать за O(n), можно взять готовую формулу O(1). Ну и, понятное дело, в самой задаче ничего про прогрессию не будет сказано. Там будет какая-нибудь история, где прогрессия будет правильным ответов.
T-D-K
Вам 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) по времени.
Ogra
Что значит, не предлагать? А давайте сравним связанный список, массив и их стоимость операций вставки, изменения, доступа, поиска. Получить случайный элемент массива - O(1), получить случайный элемент связанного списка - O(n), но вот вставить дополнительный элемент в самое начало списка - O(1) для связанного списка, и O(N) для массива. И так далее - O(1) при анализе контейнеров встречается повсеместно. Когда вы выбираете какие-то структуры данных для проекта про это нужно помнить.
MiyuHogosha
Кто-то пропустил лекцию про О-большое?
aegelsky
толку от этого похоже немного, т.к. кроме обращения по индексу массива ничего толком нет и это тоже такой себе пример.
кто-то хочет получить хз что из хз какого массива? без всякой обработки этого массива?
а общее время алгоритма будет какой сложностью?
особенно эпичная тут нижняя часть из вики, выполнить лютейший АДЪ вложенных циклов, но в каждом - "некоторые операции с постоянным временем работы".
нам не рассказывали про О(1) и я понимаю теперь почему, толку мало)
на олимпиадах как-то выигрывал всякие мышки/книжки/и т.д., просто в начале 00х призы были не особо большие и как-то обошёлся без этого сакрального знания.
куча макулатуры с дипломами валяется где-то у родителей, надо этот хлам посканить хоть, а то ни разу не пригодился ещё, но чем чЪорт не шутит))
из гордости (чем реально могу гордиться) - сделал оптимизацию одной формы EAV базы, которая занимала около 4мин на 5-10млн записей, я свёл её до 2-3 секунд.
5-10млн уников там означает лютейший треш в самой базе, это прям очень тяжело, особенно как оно работает по умолчанию при поиске по разным полям.
вроде чота понимаю, ну мне так кажется.
nin-jin
Представьте себе статью на Хабре, у которой есть автор, у которого есть аватар. Если положить это реляционную бд, то запрос этих 3 связанных сущностей по идентификатору статьи займёт О(n), где n - размер базы данных. Если добавить индексы, то это добавит O(log n) потребления памяти, но ускорит до O(log n). А если положить в графовую бд с прямыми ссылками между сущностями, то получим как раз O(1) без лишней памяти. То есть время запроса от размера базы не зависит.
xxxDef
Если вернутся к исходной задаче статьи, то надо еще учесть стоимость операции "положить".