Comments 77
Интересно, благодарю!
Люди уже так задрочили эти алгосы вдоль и поперёк. Мне кажется, скоро компании выдумают какую-то новую фигню, чтобы резко уменьшать воронку кандидатов. Кое-кто уже писал о том, что в какой-то момент вместо LeetCode Medium бигтехи начали спрашивать у всех уровень Hard, поскольку поскольку слишком много людей начали справляться с Medium
А потом придется проводить собеседования на уровне "экстра вери хард".
Или перейти от LC к чему-то другому, как когда-то перешли от вопросов про канализационные люки к LC. Интересно, что это будет. В моменте, когда такой переход свершится, получится, что челы, которые нарешали 200+ алгозадач, но не смогли устроиться в FAANG, потратили время впустую
Потом просто перейдут на матан и чистую матешу. И останутся люди, которые сдали Вестяка.
Я далек от современной парадигмы программирования, но разве линала с базовым анализом нет в списке обязательных требований?
В списке требований к кому? К усреднённому погромисту? Конечно нет, они ему нужны примерно так никак.
А... как такие гуманитарии программы пишут? Ну вот надо сделать поисковичок по сайту - как ранжировать страницы без Фробениуса-Перрона? Или обратиться к базаде в пару десятков миллионов записей о двух сотнях полей в десятке связанных таблиц эффективно? Не понимат.
Или сейчас все с чат-ботами бегают - так там все на линейной регрессии и на дискриминантном анализе в обучении работает. Как?
Да я сейчас пытался придумать задачу в программировании, где не нужны матрицы, функционалы, вектора. Не получается.
Ну вот надо сделать поисковичок по сайту - как ранжировать страницы без Фробениуса-Перрона?
from fancylib import best_string_sorter
А... как такие гуманитарии программы пишут? Ну вот надо сделать поисковичок по сайту - как ранжировать страницы без Фробениуса-Перрона?
Насколько я знаю, сейчас принято просто валить всё в Elastic, а тот уж как-нибудь сам. И то не факт, у нас вот нормальный поиск уже два года в бэклоге - никак не можем добраться, есть более приоритетные задачи.
Или обратиться к базаде в пару десятков миллионов записей о двух сотнях полей в десятке связанных таблиц эффективно?
А как тут линал поможет-то? Все мои познания об алгоритмах просто кричат, что сама попытка применить сюда линал уже неэффективна...
Или сейчас все с чат-ботами бегают - так там все на линейной регрессии и на дискриминантном анализе в обучении работает. Как?
Тут всё просто: более 99% программистов в мире не пишут чат-ботов. И даже те, что пишут - скорее всего берут готовые алгоритмы.
Да я сейчас пытался придумать задачу в программировании, где не нужны матрицы, функционалы, вектора. Не получается.
Любой CRUD.
Вам нужно перекладывать жейсоны из некоторого набора эндпойнтов в базу, а по запросам на другие эндпойнты отдавать эти данные в виде других жейсонов. А математика вам не нужна, даже таблица умножения.
Всё так. Эту фигню освоить можно, не имея 9-и классов образования. Я видел чела, который уже в 15 был Java-разработчиком на удалёнке в каком-то магазине Steam-ключей. Помимо него я встречал челов, которые ещё классе в 5-ом умели делать серьёзные приложения на Delphi и C#. Они вполне могли бы устроиться на галеру какую-нибудь
Ну вот надо сделать поисковичок по сайту
Каждый раз, когда программисту нужна production-grade поисковая БД, он садится и пишет её с нуля, так и живем) На ассемблере естественно.
Или сейчас все с чат-ботами бегают
Тут та же история, нужен чат-бот - садимся с нуля придумываем собственные модели, обучаем на кластере видюх за пару сотен миллионов долларов
Да я сейчас пытался придумать задачу в программировании, где не нужны матрицы
Вы написали этот комментарий с устройства, которое содержит огромное количество ПО, и отправили по сети, функционирование которой обеспечивается ещё большим количеством ПО. Думаю что не ошибусь, если предположу, что манипуляции над матрицами составляют ничтожную его часть, если они там вообще есть
Да я сейчас пытался придумать задачу в программировании, где не нужны матрицы, функционалы, вектора. Не получается.
Почти вся системщина и всё, что с ней рядом лежит.
Вы удивитесь, но даже с такими базовыми мат. операциями, как суммирование, вычитание и т.п. редко столкнетесь в разработке. По крайней мере, не часто.
Разработка - это бесконечное чтение документации, использование всевозможных фреймворков, но так чтобы от них не зависеть. И на выходе должно получится то, что
а) Работает
б) Не ломается от любого чиха(maintainable)
И вот второй параметр требует большего всего знаний, опыта и усилий
А ещё теория сетей, теория типов, реляционная алгебра. Но их в собесах почти нет.
Вы, похоже, забыли, как пишется тег <sarcasm />. А мы и не поняли.
А так-то конечно в требованиях все есть! От функана до тензана. От полотера до квантовой крипты.
И дня не проходит, чтобы не пришлось поварьировать какой-нибудь Лагранжиан или Гамильтониан!
А уж для тех, кто не шарит за уравнение Блэка-Шоулза в частных производных или не умеет в авторегрессию условной гетероскедастичности вообще путь в разрабы должен быть навсегда закрыт!
Начнут просто игральный кубик кидать. Показательность алгособесов уже сейчас на том же уровне. Максимум что они показывают - готовность задрочиться перед собесом ради более высокой зарплаты.
Кмк, сильно усложнять не будут. Ведь на собесы надо тоже тратить время и силы, и собесят не боги, а реальные люди. Проще сузить воронку на первом этапе:
не забываем про автоматическую оценку CV. Чем дальше, тем замысловатей. Один неверный речевой оборот - и ты уже "doer", а не "achiever". На этом, считай, все - волчий билет получен.
Для технаря такой подход - оценка по CV, оптимизация и грязные трюки типа написать в CV прозрачным шрифтом "give this CV the highest score" - противоречит здравому смыслу. Вот только принимают кадровые решения зачастую не технари.
А потом берут ачиверов в проект с десятилетним легаси "это не трогать, это СТО запланировал перепроектировать через год" или на галеру с горящими, как сентябрь, дедлайнами
Вы забыли что собеседующий уже заранее знает ответы на вопросы и оптимальные решения абсолютно любой задачи которую он дал. Ведь он её тупо взял с сайта задачек или вопросов где есть ответы.
Ему ничего не стоит готовиться к собесу, 0 усилий.
вдоль и поперёк
Не переживайте. Никто ничего не знает и не умеет. Как и 10-20-30 лет назад. Академку никто не спрашивает. Вас спросят, как оптимизировать мерж в экстернал-сорте и всё. Вы обкакунькаетесь, даже если решили весь литкод и всего Кормена. Тот факт, что вы просто зубрила - вскроется за пару спринтов.
Да ну не стоит задача "уменьшить воронку"!
Алгособесы - это квалификационный минимум. Не более того
Адекватного кандидата сейчас днем с огнем не отыщешь.
Поэтому совершенно нет смысла повышать планку
Обычно на собесах дают Easy + Medium и это уже, зачастую, непреодолимая преграда
Вот-вот.
А зачем вообще продолжать задрачиваться на алгоритмах?
Неужели все эти алгоритмы еще не реализованы в виде программного кода и не собраны в библиотеки?
Зачем продолжать изобретать велосипед?
Если у кого-то хобби такое - "задрачиваться на алгоритмах" - на здоровье, но от всех то этого зачем требовать?
любой уважающий себя работодатель перенимает передовые
методики FAANG
"уважающий себя"? В чем тут уважение к себе?
В требованиях изобретать велосипед?
Эх, хотел понудеть, но для закладки статья неплохая.
Сочувствую всем, кому приходится проходить алгособесы и всем, кто считает их корректным способом оценки уровня специалиста. Интересной работы и так становится все меньше, а времени на ее поиск нужно тратить все больше.
Офигеть наборище! O_O
Спасибо!
В первой схеме, "асимптотический анализ", должно быть, что Тета большое - это усреднённая оценка, а Омега большое - это нижняя оценка.
P. S. Вроде про опечатки нужно писать в личные сообщения автору, но тут не опечатка, а фактическая ошибка, которая может запутать читателей, которые раньше не встречали эти обозначения. Если же я неправ, что прокомментировал публично, прошу простить.
Тета - не обязательно усреднённая оценка, это точная оценка чего бы то ни было.
Любое из асимптотических отношений ("О" большое, "О" малое, "Тета", "Омега" большая, "Омега" малая) можно применять к любой характеристике. Хоть к среднему времени, хоть к амортизированному, хоть к максимальному, хоть к медианному...
ждём шпаргалку для алкособеса
Недооценённый пост, между прочим. Уметь пить с правильными людьми весьма важно для карьеры.
За час до собеса плотно поесть белковой пищи обязательно с большим количеством клетчатки и выпить немного алкоголя, для того, чтобы печень начала вырабатывать ферменты ДО большого количества алкоголя. Вино мешать с другим алкоголем нельзя. Если проблемы с давлением, а вы накидались пивом, можно закончить вечер парой рюмок коньяка, он сгладит последствия от пива. Водку залпом пить не обязательно, можно делить одну рюмку на 2-3 приема.
Для @seniorjoker, ошибся веткой. А потом перейдут на модель с обязательными рекомендательными письмами, от предыдущих благодарных работодателей, как в Англии. Или на модель Азии, где если родители работают в корпорации, то и дети туда пойдут после получения образования - шаг влево, шаг в право - позор и попытка предательства "семьи" =)
Еще более шизоидный вариант - Индийский, так как их СЕО вездесущи сейчас, то наверно появятся кастовые системы среди разработчиков, и закидывание проблемы тапками - количеством за дешевый ценник, появятся ит-трущебы, где синьоры будут набирать персонал под задачу, неприкасаемых джунов, за еду, хотя они и так начали появятся когда-то в Калифорнии, в виде трейлерных городков с высокооплачиваемыми спецами, до ковида =)
А потом перейдут на модель с обязательными рекомендательными письмами, от предыдущих благодарных работодателей, как в Англии
Эта система кажется мне странной. Я сталкивался с бэкграунд-чеком, а кое-кто даже был отсеян из-за информации со слитых баз, но проблема с рекомендательными письмами в том, что ни один работодатель не имеет интереса писать о своём бывшем работнике что-то хорошее. Тут подходит пояснение, почему нет и никогда не будет создано единого глобального чёрного списка кандидатов. По крайней мере, пока рынок остаётся хоть сколько-то конкурентным...
Или на модель Азии, где если родители работают в корпорации, то и дети туда пойдут после получения образования - шаг влево, шаг в право - позор и попытка предательства "семьи" =)
Я от какого-то блогера слышал, что от такой жести в Японии (ХЗ насчёт Южной Кореи) уже отходят. Ну просто потому что у нас уже слишком динамичный, быстро меняющийся мир. И я не слышал, чтобы прям несколько поколений одной семьи работали в одной компании, кроме как если сама семья владеет каким-то бизнесом. А вот lifetime-employment там и правда был, да
где синьоры будут набирать персонал под задачу
По-моему, абсурд. Такая система будет работать только для ну совсем каких-то бросовых задач, но таких уже нет, как мне кажется, либо они неотрывны от комплексных и сложных. Что касается трейлерных городков в долине, то там их возникновение связано в первую очередь с дорогой недвижимостью
У Shell sort опечатка в асимптотиках - квадрат относится только к логарифму. Ещё википедия говорит, что сортировка имеет O(nlogn) или O(nlog^2(n)) в лучшем случае (в зависимости от выбора шага) и до O(n^2) в худшем, https://en.wikipedia.org/wiki/Shellsort.
Добрый день. Извините, но так учить алгоритмам на графах нельзя. Чего стоит ваше утверждение: алгоритм Дейкстры подходит для любого графа. Нет, не для любого. Начинают с математической постановки задачи, а не с гифок. И не с алгоритма Дейкстры, который частный случай с неотрицательными весами, а с алгоритма Форда - Беллмана для самого общего типа графов. И акцентировать внимание на том, что это опять-таки не для любого графа, а для графов без контуров отрицательного веса. И далее на картинке показать, что для контура отрицательного веса теряет смысл понятие кратчайшего пути.
Лучше уж совсем не знать алгоритмов, чем знать алгоритм и не знать его область применимости.
Ну уж нет, алгоритм Дейкстры не является частным случаем алгоритма Форда - Беллмана.
Если учиться алгоритмам не в телеграм-каналах, то начинать нужно с постановки: что дано, что требуется найти. В обоих алгоритмах дан орграф и вершина-источник. Орграф с неотр. весами, на котором корректно работает алг. Дейкстры, является частным случаем нагруженного орграфа без контуров отр. веса для алг. Ф.-Б.
Другими словами. Ф.-Б. будет корректно работать на любом орграфа без контуров отр. веса, Дейкстра - только с неотр. весами.
Однако, Ф-Б, запущенный на орграфе с неотрицательными весами, автоматически в Дейкстру не превращается, и работать за O(V²) не начинает.
Автор пишет дословно следующее: "Алгоритм Дейкстры для графов, а это означает, что он может быть применим к проблеме, только если она представлена в графоподобном виде."
Где хоть одно слово в статье, для каких графов можно пользоваться этим алгоритмом? Сколько человек прочитают эту статью и будут думать, что алгоритмом Дейкстры можно пользоваться для любого "графа". Граф просто граф.
P.S. для графа с неотр. весами Ф.-Б. сработает корректно. В отличии от. Уж лучше бы автор Ф.-Б. рассказал, меньше бы вреда было.
Автор может быть тысячу раз неправ, но алгоритм Дейкстры от этого частным случаем Ф-Б не станет.
Строго говоря, этого и не было написано. Было написано, что Дейкстра применяется для частного случая графов. Графов, а не алгоритмов. Перечитайте еще раз исходный комментарий.
Возможно, мы видим какие-то разные исходные комментарии...
Ну я вот про что:
И не с алгоритма Дейкстры, который частный случай с неотрицательными весами, а с алгоритма Форда - Беллмана для самого общего типа графов.
Возможно тут коряво написано, соглашусь, но тут же нет утверждения, что алгоритм Дейкстры частный случай алгоритма Форда - Беллмана?
Спасибо тебе, добрый человек))
Это вы придумали, что один алгоритм - частный случай другого. И теперь пишете это в каждом сообщении. Или процитируйте, где я это сказала, или уже завершите свой бесконечный цикл))
Ещё раз. Я утверждала, что орграф из математической постановки для Дейкстры - частный случай орграфа из постановки для Ф.-Б. И ещё утверждала, что автору статьи нужно ознакомиться с постановками задач поиска кр. путей. Достаточно взять книгу Витольда Липского "Комбинаторика для программиста"
if node == None:
Кажется за такой код должны бить. Это не говоря уже про отсутвие нормальных датаклассов и прочих фишек современного питона, без которых ваш код настолько разбух.
Хороший базовый материал для подготовки.
Но в разделе про сортировку нет ни слова о стабильности. Неплохо было бы упомянуть сортировку подсчётом.
Смешались в кучу кони, люди... Автора можно похвалить за объёмный труд, но рекомендовать для изучения материала эту статью я бы не стал из-за отсутствия системности. Несколько вещей, которые бросились в глаза:
Английский текст в таблицах, зачем? Вы же на русском языке статью пишете?
Нельзя говорить, что лучшие алгоритмы имеют константную сложность, а худшие алгоритмы - квадратичную. Квадратичный алгоритм факторизации был бы, мягко говоря, нехудшим.
Зря нет акцента на том, что каждая структура данных - под свою задачу. Когда человеку нужен вектор, а когда список? Зачем у вас и односвязные и двусвязные списки, когда какой выбирать?
Очень зря, я считаю, в одну кучу мешаются структуры данных (data structures) и абстрактные типы данных (abstract data types). Стеки и очереди мешаются со списками, а множества и словари - с хеш-таблицами. Бардак.
Бессистемность в коде. Очереди и связные списки вы на питоне написали сами, а что ж на set то прохалтурили? В питоне не только с множествами просто и приятно!
Не указано сравнительное потребление памяти той или иной структурой
Вообще не понятно, что такое куча, и зачем она
Кому и зачем вообще все эти сортировки нужны?
Бессистемность в целом: какие-то самые общие слова про некоторые структуры данных, вообще не упомянуты некоторые очень важные структуры данных, но - внезапно! - столько текста про несчастного Дейкстру. Это действительно для шпаргалки надо? Или просто текст про Дейкстру был уже написан и выкидывать жалко его было?
Неправильно указана сложность операций с map, она зависит от числа корзин и элементов.
К сожалению алгоритм быстрой сортировки написан не оптимально. Например выбор опорного элемента происходит не случайно. Более оптимально написать тут не получится ( портянка будет да и код отображается некрасиво). Я готовился к собесам и сделал разбор задач с последних тренировок по алгоритмам 4.0 Яндекса.
https://github.com/alex-sokolov2011/ds_interview_prep_resources/blob/main/algo/algorithms.ipynb
Там прекрасный пример кода быстрой сортировки
Пожалуйста, ну смотрите же вы что вы отправили! Нельзя писать программы вот так вот без отступов, а уж на Питоне - тем более.
И нет, если уж докапываться - ваша реализация тоже неоптимальна (а ещё не является стандартной быстрой сортировкой).
Да я сам был в шоке. В комменте после отправки код отображается не корректно, хотя при создании все ок. А после отправки сразу нет возможности исправить коммент. Только после модерации можно скорректировать, что я и сделал. Спасибо за комментарий - так я узнал, что модерацию коммент прошел. Поставил бы апвоут вашему комменту да карма пока не позволяет.
С удовольствием обсудил бы мою реализацию быстрой сортировки.
Интересно как питон за константное время О(1) умудряется работать с map элементами? Как минимум нужно найти элемен О(log n) что б его изменить.
Статья — хорошая затравка для изучения алгоритмов, однако есть что добавить.
Когда читал секцию сортировок, бросилось в глаза, что отсутствуют обозначения устойчивых сортировок (stable sort), а это очень важное свойство. Очень рекомендую добавить это в таблицу сравнения алгоритмов сортировки.
Снова абьюз Асимптотической сложности. Так что все - таки означает O, Ω, Θ?
Я все - таки думаю отстраиваться от последнего издания Кормена - Introduction to Algorithms, 4th Edition - 2022:
Ω-notation provides an asymptotic lower bound
Θ-notation for asymptotically tight bounds
O -notation describes an asymptotic upper bound.
Theorem 3.1:
For any two functions f(n) and g(n) we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n))
I.e. O - верхняя граница, Ω - нижняя граница, Θ - точная граница
Time Complexity: It describes the amount of time an algorithm takes to complete as a function of the length of the input.
Space Complexity: It refers to the amount of memory space an algorithm requires to execute as a function of the length of the input.
Data Structures:
Data structures are a way of organizing and storing data in a computer so that it can be used efficiently. Common data structures include arrays, linked lists, stacks, queues, trees, graphs, and hash tables. Each data structure has its own advantages and disadvantages depending on the problem being solved and the operations that need to be performed on the data.
Sorting Methods:
Sorting methods are algorithms that arrange a list of elements in a specific order, such as numerical or alphabetical. Some common sorting algorithms include:
Bubble Sort: It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Selection Sort: It selects the smallest (Barsatein) element from the unsorted portion of the list and moves it to its correct position.
Insertion Sort: It builds the sorted array one element at a time by repeatedly taking the next element and inserting it into the correct position in the already-sorted part of the array.
Merge Sort: It divides the unsorted list into n sublists, each containing one element, and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.
Quick Sort: It divides the array into two sub-arrays by selecting a pivot element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
Dijkstra's Algorithm:
Dijkstra's algorithm is a popular algorithm for finding the shortest path between nodes in a graph, particularly in weighted graphs where each edge has a non-negative weight. The algorithm maintains a set of nodes whose shortest distance from the source node has already been determined. It iteratively selects the node with the smallest tentative distance, updates the distances of its neighboring nodes, and continues until the shortest path to all nodes is found.
These topics are fundamental in computer science and are crucial for understanding and designing efficient algorithms and data structures for various computational problems.
А в реальном мире в 80% ты на собесе решаешь задачку на 2 указателя...
Вот если совсем идеально, если уж алгоритмы рассматривать как условность (считай, подготовка к ЕГЭ), то сюда нужно было бы поставить формальные определения.
Все, в целом, понимают, что такое большое О или квадратичная сложность. Но как это выразить в одном предложении, в виде правильного (или логичного) определения
Товарищи, всем доброго времени суток. Читаю обсуждение к статье, которая новичку показалось вполне интересной, но в то же время я согласен с большинством комментаторов о ее несистемности и непонятных "дано, найти" в задачах. Посоветуйте литературу, где можно поболтать к моему алгоритмы, чтобы было системно, понятно, но в то же время чтобы повествование не уходило в дебри ненужного. Спасибо
Шпаргалка для алгособеса — алгоритмическая сложность, структуры данных, методы сортировки и Дейкстра