Comments 69
Недавно встретилась по работе интересная задача, прямо на те самые презираемые на интервью алгоритмы. Очередное доказательство, что, по крайней мере, в Гугле алгоритмы нужны. А значит и интервью у них вообще-то не оторваны от реальности.
Ну т.е. встретилась задача, и разобраться, сделать research - не судьба? Обязательно алгоритмы нужны на собесе? А если какой-то алгоритма в памяти такого нанятого кандидата не оказалось, то всё, "у него лапки"?
Я часто вижу такую точку зрения, что эти задачки на литкоде и собеседованиях - это такая лотерея, что человек их заучивает, и потом либо ему повезло, и он похожую задачу решал, либо не повезло.
Мне кажется, эти задачи скорее простые примеры из базового курса по Computer Science - то есть, если вы этот курс прошли, и прорешали эти задачи, то вероятность встретить задачу уровня easy/medium, к которой вообще непонятно, как подступиться, мала. Даже если в вузе такого курса не было, их на ютубе много, от MIT или МФТИ, например.
Другое дело, что многим быстрее рискнуть и бессистемно запомнить принцип решения пары сотен задач, чем проходить годовой курс и разбираться в теории, но я не знаю, насколько это проблема собеседований.
По поводу сделать research - далеко не всегда его можно делать, если вы не знаете основы computer science (А если знаете - то решение задачек на собеседовании не будет проблемой). В гугле часто возникают задачи, для которых надо придумать новый, прежде несуществующий, алгоритм, а не просто применить новый, они публикуют научные статьи каждый год.
сделать research - не судьба?
У "другого программиста" из статьи не возникло беспокойства по поводу O(N^2) и как следствие повода этот самый ресерч делать. Он запилил простой вариант за 10-15 минут и закрыл таск
Почему вы решили что не возникло? Может очень даже возникло. И проведя комплексный анализ что N не настолько велико, а сопровождаемость кода сильно упадёт, было принято верное решение "не умничать".
Повторю: N до 10000. Это для вас "не велико"?
В зависимости от задачи, да, это могут быть совсем копейки.
В другом комменте написал: Сэкономлеты тысячи часов процессорного времени в день.
Как известно, алгоритмы за
это алгоритмы, которые падают только на проде (падают в смысле "выходят за все мыслимые пределы по времени").
Аналогичный пример: если не знать про FullScan vs IndexScan, то заметить наличие проблемного FullScan во время разработки — крайне маловероятно. И я видел примеры, когда делали таблицу с историческими данными без индексов...
Без обширного знания алгортмов и навыков их применения вы этот research не сделаете.
Во-первых, вы скорее всего и не заметите, что тут вообще какие-то алгоритмы нужны. Но, допустим, вы профайлером нашли место где самый долгий цикл и даже подумали почему-то, а вдруг тут алгоритмами что-то можно сделать.
Вторая загвоздка: вы не найдете решение задачи, не зная ни про какие RMQ. В интернете вот такая постановка задачи не встречается. Там числа и отрезки, а у вас какие-то пользователи и события.
Ну, допустим, вам дико повезло. И вы нашли заветное описание алгоритма в интернете. Без понимания и знаний вы его заставить работать в вашей (напоминаю - измененной задаче) скорее всего не сможете.
Но, даже если вам необычайно повезет и вы все найдете в интернете, вы потратите на это дело во много раз больше времени, чем подготовленный человек, из-за преодоления упомянутых выше преград.
А если какой-то алгоритма в памяти такого нанятого кандидата не оказалось
Если кандидат проходит собеседования и решает случайные задачи, то это значит, что или он выучил их очень много (что маловероятно и очень сложно), или он в них разбирается и способен выводить решения сам. Так что и новую неизвестную задачу сможет свести к известным алгоритмам или хотя бы понять, из какой области алгоритмы нужны и искать их по правильным ключевым словам в реальной работе.
А что касается интервью - там не дают каких-то особо заумных алгоритмов. Плюс для прохождения интервью не обязательно решать задачу именно тем методом, что имел ввиду автор задачи. Даже решать ее целиком и правильно не обязательно. Достаточно грамотно рассуждать, свести задачу к чему-то осмысленному и перечислить хоть какие-то вменяемые альтернативы, да выдать немного хорошего кода для самых инетересных частей предложенного решения. Не нужно знать все наизусть, надо знать базу и уметь ее применять.
Так что и новую неизвестную задачу сможет свести к известным алгоритмам или хотя бы понять, из какой области алгоритмы нужны и искать их по правильным ключевым словам в реальной работе.
Да, конечно!
Плюс для прохождения интервью не обязательно решать задачу именно тем методом, что имел ввиду автор задачи. Даже решать ее целиком и правильно не обязательно. Достаточно грамотно рассуждать, свести задачу к чему-то осмысленному и перечислить хоть какие-то вменяемые альтернативы, да выдать немного хорошего кода для самых инетересных частей предложенного решения.
Это вы теоретизируете. Ваш код тупо скопипастят и прогонят через тесты. Хоть один не прошёл - досвидос.
Нет, не теоретизирую. Я эти интервью в гугле провожу. Я знаю, как они, по крайней мере, дложны работать. Нет, код никуда в падавляющем большинстве случаев не копируют и не прогоняют. Он в 60% случаев вообще не скомпилировался бы по моим ощущениям, но кандидаты интервью проходят.
Я, конечно, не могу полностью исключать существование отдельных странных кадров, которые вопреки инструктажу интервью проводят имено так, как вы говорите, а для отчета выдумывают что-то вменяемое, и поэтому им никто еще не надавал по рукам. Но это должно быть ничтожное меньшинство ситуаций.
Нет, не теоретизирую. Я эти интервью в гугле провожу. Я знаю, как они, по крайней мере, дложны работать. Нет, код никуда в падавляющем большинстве случаев не копируют и не прогоняют. Он в 60% случаев вообще не скомпилировался бы по моим ощущениям, но кандидаты интервью проходят
Вы в Гугле работаете? Получали согласование с руководством на такие комментарии?
Надеюсь вы понимаете, что из этого комментария легко написать статью "СОТРУДНИК ГУГЛ ПРИЗНАЛСЯ, ЧТО НАНИМАЕТ НА РАБОТУ ЛЮДЕЙ, НЕ УМЕЮЩИХ ПРОГРАММИРОВАТЬ" - и опровергать это придется на сильно высоком уровне.
Чота там подраспустил вас нынче ваш комплаенс, в наши времена за такие комменты по шапкам прилетало сразу.
Без обширного знания алгортмов и навыков их применения вы этот research не сделаете.
Я про research более общего генезиса: как вообще подобного рода задачи решаются. Изучить весь опыт и best practices. Может тут вообще алгоритмы не нужны и задача решает другими подходами. Либо эффективно применяются довольно специфичные алгоритмы, учитывающие природу domain knowledge.
Это вообще более глобальная проблема. У нас же чуть что, каждый тут же бежит изобретать свой 5 колёсный велосипед из говна и палок того что лучше всего умеет.
Эта задача в такой формулировке вообще нигде не встречается. Вы буквально ничего по ней нигде не найдете, если только уже не обладаете достаточным набором знаний, чтобы переформулировать/свести ее к чему-то более стандартному.
В такой - конечно не встречается. Было бы странно если бы встречалась.Да, надо обладать некоторым объёмом знаний предметной области чтобы смочь переформулировать или найти что-то более-менее близкое. Да и вообще понимать что на самом деле делаешь. В любом случае, это в первую очередь domain knowledge, research, а алгоритмы тут уже постольку-поскольку.
надо обладать некоторым объёмом знаний предметной области
И какие же знания "предметной области" тут помогут? Единственное знание, что тут нужно, это что можно быстро искать максимум на отрезке в массиве и это не "предметная область", это алгоритмы. Или, по-вашему, обработка логов и вычисление статистики - это такая особая предметная область?
Это же классический Accidently quadratic! Давно уже есть идея написать по статью на обозрение всем, кто считает, что алгоритмы не нужны.
Мне кажется, что сбор статистики -- это то, что возникает всегда и везде. У меня возникла как-то задача, которую в целом можно описать как "нужно быстро считать какую-то статистику за недавний промежуток времени переменной длины в онлайн". Подсчет суммы/среднего/минимума мы сделали довольно легко с
на запрос, был даже довольно экзотичный случай подсчета среднеквадратиченого отклонения, который тоже считается и тут у меня тоже есть ссылочка на квадрат. Но вот у нас дело дошло до квантиля и тут мы поняли, что задаче резко стала сложнее -- внезапно в какой-то момент научились тоже делать за логарфим с помощью wavelet tree.
был даже довольно экзотичный случай подсчета среднеквадратиченого отклонения, который тоже считается и тут у меня тоже есть ссылочка на квадрат.
Спасибо за ссылочку, надо бы там пофиксить. Это отклонение же элементарно считается.
Про квантили интересно: не могли бы вы поточнее описать задачу? Длина окон прямо от зароса к запросу меняется? Было бы интересно почитать, как вы там делали с wavelet tree. Если окна совсем произвольные, то пока вижу как сделать за O(log^3(n)) каким-нибудь деревом отрезков декартовых деревьев и бинпоиском по ответу.
Окна не совсем произвольные. В целом понятно, что если например окно фиксированного размера по времени или скажем по количеству событий, то можно обойтись любым бинарным деревом поиска с поддержкой размера поддеревьев для поиска.
Решение за log^3 -- там есть несколько вариантов, но в целом это что-то в духе декартого дерево по времени, в каждой вершине что-то что умеет считать порядковую статистику. Есть вариации, но все они log^3 запрос + nlogn памяти. По поводу wavelet tree на 100% не уверен, но кажется в этой статье описан алгоритм, который мы использовали. Уточню, что там не logn, а log U в предположении, что все величины -- это целые числа из диапазона [1..U]
Так какие у вас там окна? Размер от запроса к запросу меняется? Окно всегда кончается в текущем элементе? Формализуйте, если вам не сложно, задачу, пожалуйста.
Размер окна от запроса к запросу меняется, да. Окно всегда кончается в текущем элементе, да. Возможно поможет контекст: дело происходило на транспортном уровне передачи данных, где мы хотим посчитать актуальную статистику за последний RTT - round trip time, время от отправки пакета до получения фидбека по нему - это величина ведят себя достаточно предсказуема большую часть времени, но в критические моменты начинает изменяться и на это нужно реагировать.
Спасибо за статью. Очень интересная структура данных получается.
Кстати,
"нужно быстро считать какую-то статистику за недавний промежуток времени переменной длины в онлайн". Подсчет суммы/среднего/минимума мы сделали довольно легко с
Если у вас запросы именно "за недавний промежуток", т.е. идут в порядке увеличения правых концов, то вам как раз подходит алгоритм из статьи для реализации минимума за O(1).
А для такого случая есть еще проще алгоритм со стеком, он есть на e-maxx, едиинственное -- для случая когда длина не фиксирована, то мы делали бинарный поиск. Еще я до конца не понял, можно ли алгоритм из статьи делать онлайн
Алгоритм со стеком с e-maxx не работает, если начала окон произвольно меняются. Про бинарный поиск по стеку я как раз и написал в конце статьи про альтернативный вывод.
Алгоритм в статье как раз реализует два метода: AddSample, GetMaxFromNLast. Он оффлайн в смысле, что ему надо запросы обрабатывать в строгом порядке увеличения концов. Но это как раз ваш случай.
Но ведь человек, написавший изначальный код, тоже прошёл через алгоритмическое собеседование.
Кстати, интересно насколько быстрее работает ваш вариант. Предположим, на 10000 элементах.
надо еще по ресурсам компании смотреть, по срокам. этот код еще поддерживать нужно. возможно менять и добавлять. и тут, возможно, придется искать того специалиста, которому пригодились его знания, либо переписывать на квадрат, чтобы можно было недорого, поддерживать этот код.
Зачем его менять и добавлять? Решатель для RMQ лежит в директории с универсальными общими библиотеками, менять его вряд ли когда-то придется. Если кому-то надо будет его доработать под их нужды (например, под минимум), то у них какая-то похожая алгоритмическая задача и без знаний они ее все-равно не решат. Сам код обработчика событий лишь вызывает 2 функции у решателя в библиотеке, поддерживать его сможет даже формошлеп. Ну и, в конце-концов, интервью с алгоритмами проходили все, так что считается, что любой программист должен уметь хотя бы разобраться в таком коде.
Решатель для RMQ лежит в директории с универсальными общими библиотеками, менять его вряд ли когда-то придется.
Не, ну почему не придётся, как раз таки допилить ради ускорение всех компонент, которые его использует -- здравое дело. С другой стороны, чаще всего у опытных разработчиков не должно быть проблем сделать улучшение без изменения интерфейса.
С другой стороны, чаще всего у опытных разработчиков не должно быть проблем сделать улучшение без изменения интерфейса.
Любой опытный разработчик понимает что любое внесение изменений чревато проблемами. И чем заумней код, тем выше шансы что-то там незаметно для юнит-тестов поломать.
Вы гиперболизируете, как-будто из вашего сообщения стоит сделать вывод, что писать новый код не выгодно, потому что это чревато проблемами.
Да, я прекрасно понимаю есть например ситуации когда есть код, не меняющийся десятилетиями и прекрасно работающий, использующийся всеми. Делать изменения в таком коде ради выигрыша 0,1% нецелесоообразно из-за надёжности. Но если подобные проекты забрасываются, то рано или поздно оказываются на свалке истории.
Вообще говоря, в "хороших" компаниях, людей не мыслящих категориями алгоритмов и структур данных, вообще не пустят к такого рода задачам. Просто из-за профнепригодности.
В конкретном примере, я думаю, разработчик был даже знаком с алгоритмами и структурами данных и все равно написал квадратичное решение. Что может только подчеркивать насколько эти знания и умения не просто освоить и применить.То есть для тех, кто считает, что, мол, ну когда время прижмет, тогда и разберусь, хочу сказать что -- нет. Скорее всего, не разберетесь.
Это не те знания которые вы, там, прочитав умные книжки по чистой архитектруре, получили и сразу стали применять как по лекалу. Люди годами изучают и не могут изучить нормально.
А то, что на интревью, бывает, что лотерея, типа, учил, учил и не попалось -- ну да, бывает. Не без изъянов эти интервью. Это как раз точка улучшения - сделать так, чтобы не конкретные алгоитмы спрашивали, а скорее проверяли алгоритмическое мышление.
Ну и вообще, если вы начнете копать глубже, то тот софт, на котором вы уже и не "должны" понимать алгоритмы и структуры данных, он , скоре всего, и написан при помощи этих алгоритмов и структур данных. Вот начните даже с операционных систем и идите выше. До ваших веб серверов, где вы там что-то "архитектурите".
Итак, задача: есть лог видео конференции, состоящий из событий - в такое-то время такой-то пользователь подключился или отключился. И надо посчитать всякую разную статистику. Среди прочего скучного надо для каждого пользователя найти, сколько максимально пользователей было вместе с ним в какой-то момент времени.
вероятно я тот самый кто ничего не понял из статьи, но вопросы у меня вызывает вот что. В задаче у вас есть работающее уже решение, то есть логи пишутся. А вам нужно не переписать систему логирования, а разобрать лог. А это сразу - парсер, который съест всё время, а только потом уже ваш алгоритм. И тут вопрос к производительности и памяти. А будет ли квадратичное решение медленнее вашей городушки парсер+алгоритм? В статье я про это ничего не вижу, а значит и разговоры про что там нужно пока преждевременны. В своих скромных статьях всё же я провожу сравнение по скорости и доказываю что алгоритмы полезны, но и там встаёт затронутый вопрос - а кто потом всё это будет поддерживать???
Логи собираются с пользователей, их потом надо аггрегировать и обработать. Это и есть то место, где решается задача. Тут разговор не об одной программе, где можно сразу что-то подсчитать и потом записать в лог, или о базе данных, где можно соптимизировать sql запрос вместо обработки потом - тут распределенная система из пользователей, подключенных к серверам в разных частях света.
Да, перекачка всего это объема данных и аггрегация по конференциям занимют дольше времени, чем даже квадратичный алгоритм, но это не значит, что из-за одного медленного этапа можно забить на оптимизацию всех других.
Я написал, что решение быстрее даже для 2 пользователей, а значит оно во всем лучше. Думал этого достаточно.
Реальные боевые данные я показать не могу, но в бенчмарке это решение соптимзировало обработку с 3300мс до 18мс для небольшого набота тестовых данных. И то, что раньше работало на ~600 серверах от 20 до 150 минут (в зависимости от размеров коференций), стало отрабатывать за меньше минуты на тех же серверах. Да, это всего 5-20% от всего пайплайна. Но это несколько часов процессорного времени, на 600 серверах, несколько раз в день. Т.е. этот код сохранил 1000-7500 часов процессорного времени каждый день.
У гугла, конечно, очень много серверов, но это не значит, что можно их бездумно жрать.
я не сомневаюсь в ваших компетенциях, я скорее о полноте самой статьи (в данном случае о недостатке компетенции читателя).
но это не значит, что можно их бездумно жрать
о нет, я как раз за алгоритмы и оптимизации везде и всюду, особенно что касается экономии ресурсов.
Вот например:
Всего-то чатик на ПК, а вес как у приличной игры, как-то не уверен я что кто-то что-то тут оптимизирует. Кстати это обновление я не могу поставить уже неделю, обрывается скачивание, видимо товарищ майор дёргает рубильник )
У смартфонов та же проблема, как только средний смарт стал 4-8 гигов оперативки и 256 диска - понеслась, даже простейший софт весит гигабайты.
Один мой друг™ однажды встретил похожую задачу в системе крупной медицинской сети. Масштаб не гугловый, конечно, но объёмы данных и частота операций с ними тоже нехилая. Местные кулибины наворотили в java-коде сложных алгоритмов, которыми очень гордились, и даже расстроились, когда все они были заменены на довольно простые, но на много более эффективные sql-запросы с использованием диапазонных типов.
просто тут есть два конца спектра: алгодрочеры и отрицатели и обе категории странные.
Каждый должен заниматься своим делом. Парочка (условно) алгоритмистов в команде конечно не помешает. Парочка других специалистов. Каждый посмотрит на задачу под своим углом. Тогда есть шанс получить действительно грамотное решение.
Да, иногда бывает лучше оптимизировать сразу работу с базой данных, чем пост-процессинг. Это если у вас навороченная база данных, где это уже сделать можно. В моем случае - это распределенное хранилище и map-reduce чтобы его обрабатывать. Там нет "более эффективных" sql запросов.
Да, именно так. Если логи закинуть в БД то без всяких математических алгоритмов можно эту задачу решить элементарными SQL запросами c оконными функциями. При наличии индексов по датам все будет летать.
Но в СУБД же не магическая магия работает.
Эм... ответьте мне на несколько вопросов, пожалуйста:
1) Какая СУБД может использоваться вот тут? Учтите, ей надо поглотить несколько террабайт данных.
2) Составьте-ка, пожалуйста, эффективный запрос, который по таблице с событиями подключения/отключения посчитает указанную в статье статистику. Хотя бы найдите мне индекс, который позволит быстро искать `select max(active_count) where id >= A and id <= B` у базы данных из первого вопроса.
3) Что, по вашему, происходит внутри базы данных, отвечающей на этот запрос? Действительно ли загрузка террабайт данных в БД, чтобы обработать их там, будет эффективнее просто обработки их хорошим алгоритмом сразу в кластере Map-reduce прямо на месте их аггрегации?
Практически любая.
В нашем мире данные всего и вся лежат в БД. Поэтому логично адаптироваться именно под такой способ хранения. Тем более что внутри современных БД лежат реально мощные механизмы для обработки данных. Решить же задачу можно разными путями. От простого "в лоб" через умный SQL запрос и до предварительного расчёта, а то и вообще учёта количества активных пользователей для каждого подключения. Затраты практически нулевые и результат уже готов.
Как уже написал. Обычно агрегация подобных данных и так уже лежит в БД.
От простого "в лоб" через умный SQL запрос и до предварительного расчёта, а то и вообще учёта количества активных пользователей для каждого подключения. Затраты практически нулевые и результат уже готов.
Простой в лоб - это будет тот же самый квадратичный алгорим, только крутящийся в движке БД. Что за предварительный расчет вы предалагаете? Что за умный SQL запрос? Давайте, вот есть конкретная задача, покажите, как ее классно решать с БД.
В лучшем случае внутри БД будет примерно такой же по производительности алгоритм, в худжем - гораздо медленнее. Я думаю там где-то точно должно быть решение за логарифм с использованием деревьев отрезков или чего-то подобного в индексе, но это все-равно медленнее.
В нашем мире данные всего и вся лежат в БД.
Если они действительно лежат в БД и не подразуменевается их срочная оперативная обработка и выдача результата, то может проще эту обработку просто зашедулить с низким приоритетом. Сколько эти "тысячи часов процессорного времени" в денежных единицах? Стоит ли овчинка выделки этими алгоритмами?
Я не математик, но как программист, неплохо владеющий SQL стал бы решать эту задачу средствами SQL. И если эта задача действительно насущно необходима, то внес бы изменения в архитектуру этой системы с целью эффективной отработки SQL запросов по этой задаче на этапе логина и выхода из него. В общем все просто , если не ставить целью разработку сложных алгоритмов , когда можно эту задачу решить проще и быстрее. Это тоже разработка алгоритма, но в отличие от ЯП алгоритм в SQL это другой тип мышления, это работа со множествами, их пересечениями и отношениями. Просто глядя на диаграмму, мне почемуто вспомнился способ умножения чисел с помощью вертикальных линий, и здесь то же самое, если провести вертикальную черту то количество пересечений с отрезком или просто суммирование на интервале это и есть количество одновременных логинов. От этого можно и отталкиваться.
Конкретно в случае автора проблема в этом
Учтите, ей надо поглотить несколько террабайт данных.
А проблема статьи в том, что программистов, работающих с такими объёмами данных, один на десять тысяч или даже меньше, однако автор свою уникальную ситуацию пытается подать закономерностью и обобщить на всех.
Обратите внимание, я написал про "в гугле". В гугле и вообще в ФААНГе много кто работает с такими объемами данных.
Ну а в конечном итоге, в денежных единицах сколько такая оптимизация экономит?
Фиг подсчитаешь, сколько это в денежных еденицах. 10000 часов работы одного ядра процессора, это сколько в долларах? Вот столько в день и сэкономлено. А как туда посчитать предотваращение сбоя в работе из-за фактически ДОС атаки, когда вдруг в какой-то день будет много больших конференций и пайплан за день не отработает и в системе не будет данных?
Фиг подсчитаешь,
А надо бы. А то как бы не получилось что нанимаем программистов за $100 в час чтобы они сэкономили $1 в час.
Для того и research, и вообще think outside-of-the-box.
А в ВУЗах учат ещё и подсчитывать экономику всех этих прекрасных инноваций, а не бежать сломя голову внедрять "вау круто же".
А то как бы не получилось что нанимаем программистов за $100 в час чтобы они сэкономили $1 в час.
Вы как-то не так считаете. Программист потратил час-два-три, и потом этот $1 в час экономится каждый час, каждый день. Через 4-12 дней оно выйдет в ноль и потом начнет приносить прибыль.
И вообще, какие инновации, какое внедрение? Это фикс уже работающего в проде кода, чтобы он работал лучше. Вы перед каждым изменением в коде просчитываете все экономические последствия? А вы просчитываете, насколько экономически целесообразен этот просчет, ведь программист за $100 в час вместо полезной работы сидит считает, надо ли фиксить код, или итак сойдет. А имеет ли тогда смысл просчитывать целесообразность просчета целесообразности подсчета? Вашу логику за пол шажочка можно свести к абсурду.
Просчитывать надо большие проекты при планировании работы за большие промежутки вермени. А фиксить баги и проблемы в коде - это прямая рабочая обязанность программиста, за это ему и платят.
Вы как-то не так считаете.
Я пока вообще никак не считаю. Я лишь подсвечиваю что считать хотя бы приблизительно - надо.
надо ли фиксить код, или итак сойдет.
Удивительное дело, но именно по этой причине даже баги порой не чинят. Потому что например уже есть готовый workaround, а фиксинг может вылиться в непредсказуемое время-деньги, плюс последствия что-то ещё заодно сломать.
Вашу логику за пол шажочка можно свести к абсурду.
А не сводите.
Эта метрика - одна из сотен. Ради нее одной перелопачивать всю архитектуру - плохая идея.
внес бы изменения в архитектуру этой системы с целью эффективной отработки SQL запросов по этой задаче на этапе логина и выхода из него.
Можно по-подробнее? Развейте эту мысль.
Я не математик, но как программист, неплохо владеющий SQL стал бы решать эту задачу средствами SQL.
То о чём и говорили: решают задачу не "правильно", а как умеют. Кто в алгоритмы умеет, кто в SQL...
Как разраб и архитектор информационных систем с математическим образованием и строчкой в дипломе математик-инженер скажу так. Вышка и алгоритмы нужны чтобы изначально правильно откалибровать мозг. Но ни разу в работе не нужны были алгоритмы в математическом понимании.
То что привела автор это обычная работа разработчика, не кодера. Т.е. мы и так постоянно применяем алгоритмы в работе. Даже правильный порядок действий это тоже ведь алгоритм. И сделать то, что приведено в статье математическое образование не требуется, как и какое-то особенное алгоритмическое. На таком уровне соображать должен любой, кто называет себя разработчиком. Мы ведь постоянно сталкиваемся с подобными оптимизациями. Это фактически просто здравый смысл.
это обычная работа разработчика
Это фактически и есть основная мысль моей статьи, спасибо.
Но ни разу в работе не нужны были алгоритмы в математическом понимании.
Это просто уже народный термин. Любая не совсем тривиальная и наивная работа с данными - это уже "алгоритм". А программирование - это написать обработчик клика по кнопке и прочее перекладывание джейсонов. И когда их такие спрашивают на интервью в фаанг - это, редиски такие, валят оторванными от реальности задачами.
И сделать то, что приведено в статье математическое образование не требуется
Ну вообще, не рассуждая математически или не зная про классическую задачу RMQ, это решение вывести или найти практически невозможно. Так что надо именно теоретическую базу хотя бы один раз в жизни почитать.
А вроде она и без RMQ решается, просто порассуждать логически:
Квадрат - это не дело, но вроде не трудно заметить, что текущее кол-во подключенных пользователей общее для этих пользователей
Рассмотрим сначала упрощённый до руды вариант - пользователи только подключаются и не отключаются до самого конца – тут все тривиально (максимум будет общим для всех и равен кол-ву событий)
Теперь усложняем – сначала пользователи только подключаются, а потом только отключаются – что тут меняется? Да собственно ничего, кроме того, что надо поймать момент, когда начинаются отключения и зафиксировать «прибыль»
Ну и финальное усложнение – после одного или нескольких отключений могут снова пойти подключения… - но вроде это где-то уже было – с первого подключения после отключений по сути начинается вариант 2, т.е. надо просто фиксировать локальные максимумы для текущего множества пользователей
В итоге:
На выходе имеем словарик типа
«локальный максимум : множество пользователей, для которых когда-либо был зафиксирован этот локальный максимум»
Сортируем словарик по ключам (т.е. по локальным максимумам) по убыванию и в цикле по ключам для каждого пользователя из множества под ключом проставляем максимум, равный этому ключу, предварительно выкинув из множества тех пользователей, которых мы уже видели, т.е. которым мы уже проставили максимум на предыдущих итерациях.
Алгоритмы нужны программистам, или cамая быстрая и простая реализация RMQ