Все-таки надо различать «я изучал и примерно ориентируюсь в теме, но не смогу воспроизвести на доске» и «я никогда не изучал и не собираюсь, потому что в работе не нужно». Подобные вопросы задают чтобы аккуратно отделить первых от вторых, а не потому что считают что программист обязан помнить все алгоритмы сортировки.
Ну и на тему «мне это не нужно в работе» не хватает ссылки на статью Джоэля о текущих абстракциях.
Я уверен, что большая часть собеседующих, дающих подобные задачки и понимающих зачем они их дают, более чем удовлетворятся если вы «восстановите» алгоритм после пары подсказок. Вот только здесь, как мне кажется, за «я это все равно забуду» держатся те кто и не учился.
Последний раз я писал свой индекс два месяца назад. Но, соглашусь, это специфика задач.
А дальше вы зачем-то спорите сами с собой. Вот дальше я именно говорю о том, что если вас учили именно создавать и анализировать, а не использовать, то в процессе вы именно простой бинарный поиск и писали. И именно поэтому он есть в задачах, а красно-черных деревьев там нет. И потому что это основа без которой люди даже не задумываются о том, что лежит под рекомендованными абстракциями, почему и как их правильно использовать.
Перечитайте задачи. Речь о совершенно базовых вещах — бинарный поиск, обход бинарного дерева, рекурсивная сортировка. Это есть в ЛЮБОЙ книжке по базовым алгоритмам. Вы этим пользуетесь каждый день, когда используете, например, ассоциативные массивы или индексы в базах данных. Это вещи которые с листком бумажки и ручкой объясняются за несколько минут и потом не забываются, потому что они слишком простые чтобы их забыть и вы их начинаете видеть их везде. Даже если какие-то детали забываются — с тем же листком бумажки они восстанавливается за минуты, если вы хотя бы один раз в жизни написали руками этот несчастный бинарный поиск.
А то о чем вы написали имеет место, но не имеет ни малейшего отношения к обсуждаемым примерам задач.
UPD. И да, если человек придет на собеседование и не сможет рассказать про бинарный поиск — у меня возникнут очень большие сомнения в его способности программировать. Именно программировать, а не собирать что-то по туториалу из кусочков кода. Потому что очень сложно научиться программировать и пройти мимо настолько базовых вещей.
Вот только разговор о совсем-совсем базовых вещах (бинарное дерево, блин!).
Вы можете себе представить инженера-электронщика забывшего закон Ома? Как такое может случиться?
Только если он его и не знал и проектировал схемы эвристически и копипастом, не понимая законов лежащих в основе этих схем.
Там нету задач, для которых требуется помнить какие-либо сложные алгоритмы. Если человек помнит базовые принципы бинарного поиска, бинарного дерева и знает что такое рекурсия — то бинарное дерево и квиксорт он напишет. И механизм разрешения коллизий придумает, если просто знает что такое хэш-функция. А если не помнит… Это не «не помнит», это «не знает». Он просто не потратил за всю свою карьеру два-три вечера чтобы разобраться с простейшей базой (которую надо знать, даже если в работе он использует готовые библиотеки. Потому что абстракции текут). Тогда пусть говнокодит в другом месте, ни программировать ни учиться он просто не умеет, и пригоден только для решения типовых сценарных задач.
И сами вопросы (много очень простых алгоритмических задач и ничего толкового по самому языку, его рантайму, архитектуре, etc) и реакция на них в комментариях (блин, ребят, это очень простые задачи, для решения которых достаточно прочесть ОДНУ не очень длинную книжку, и, да, эти вещи нужно знать для программирования) очень хорошо показывают текущее состояние фронтенда.
Каждая заявка влияет на стейт нашего продавца, а значит порядок обработки все-таки важен.
Более того, в реальных задачах на operations research есть процесс обработки заявки имеющий конкретную длину и стоимость, а сама заявка — тайм-аут, и стратегия разгребания очереди может очень сильно повлиять на финансовое состояние продавца.
Просто оставлю это здесь — https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8
В итоге — по определению непрерывного пуассоновского потока. Событие ненулевой вероятности, но по определению мы этой вероятностью пренебрегаем и считаем, что сумма пуассоновских потоков — это тоже пуассоновский поток.
Ок. Действительно, существует абстрактное понятие элементарного события (https://en.wikipedia.org/wiki/Elementary_event), вероятность которого в непрерывном пространстве всегда равна нулю, из чего в определениях делается вывод, что в непрерывном пространстве имеют вероятность только НЕэлементарные события (а события в пуассоновском потоке, очевидно, вероятность имеют).
И, действительно, определение пуассоновского процесса в русской википедии содержит «Свойство ординарности: вероятностью наступления за элементарный промежуток времени более одного события можно пренебречь по сравнению с вероятностью наступления за этот промежуток не более одного события», с чем я спорить не буду.
Определение свойства из другого источника: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени Δt есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале.
Про нулевую вероятность не нашел ничего.
Вот только нигде я не нашел определения того, что пуассоновский поток оперирует именно элементарными событиями. Наоборот, везде рассматривают ТОЛЬКО события попадания в некоторый интервал (тут, например, довольно подробно — https://en.wikipedia.org/wiki/Poisson_point_process).
Именно так. Я не зря упомянул про протекающие абстракции.
Да.
Ну и на тему «мне это не нужно в работе» не хватает ссылки на статью Джоэля о текущих абстракциях.
UPD Ссылка на Козулю — это прекрасно, конечно
Вполне достаточно того, что вы не в курсе, что квотирование, анализ, генерация и выполнение AST в рантайме изобретены далеко не в дотнете.
Последний раз я писал свой индекс два месяца назад. Но, соглашусь, это специфика задач.
А дальше вы зачем-то спорите сами с собой. Вот дальше я именно говорю о том, что если вас учили именно создавать и анализировать, а не использовать, то в процессе вы именно простой бинарный поиск и писали. И именно поэтому он есть в задачах, а красно-черных деревьев там нет. И потому что это основа без которой люди даже не задумываются о том, что лежит под рекомендованными абстракциями, почему и как их правильно использовать.
А то о чем вы написали имеет место, но не имеет ни малейшего отношения к обсуждаемым примерам задач.
UPD. И да, если человек придет на собеседование и не сможет рассказать про бинарный поиск — у меня возникнут очень большие сомнения в его способности программировать. Именно программировать, а не собирать что-то по туториалу из кусочков кода. Потому что очень сложно научиться программировать и пройти мимо настолько базовых вещей.
Вы можете себе представить инженера-электронщика забывшего закон Ома? Как такое может случиться?
Только если он его и не знал и проектировал схемы эвристически и копипастом, не понимая законов лежащих в основе этих схем.
Более того, в реальных задачах на operations research есть процесс обработки заявки имеющий конкретную длину и стоимость, а сама заявка — тайм-аут, и стратегия разгребания очереди может очень сильно повлиять на финансовое состояние продавца.
Но да, давайте прекратим.
И, действительно, определение пуассоновского процесса в русской википедии содержит «Свойство ординарности: вероятностью наступления за элементарный промежуток времени более одного события можно пренебречь по сравнению с вероятностью наступления за этот промежуток не более одного события», с чем я спорить не буду.
Определение свойства из другого источника: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени Δt есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале.
Про нулевую вероятность не нашел ничего.
Вот только нигде я не нашел определения того, что пуассоновский поток оперирует именно элементарными событиями. Наоборот, везде рассматривают ТОЛЬКО события попадания в некоторый интервал (тут, например, довольно подробно — https://en.wikipedia.org/wiki/Poisson_point_process).