Не вижу, где я нагрубил. Вы просто скопировали текст из чата, поленились его проверить, проанализировать и сделать из него свои выводы. Никак иначе, чем "засорять интернет" я это назвать не могу.
Обращаю ваше внимание, я не давал никакой оценки утверждений нагенеренным в вашем комментарии. Я лишь резко негативно выразился про ваше действие.
Ну вот это вот и стоило сделать автору комментария, а не цитировать чатжпт! Даже если в этом конкретном случае оно оказалось 100% правильно. Это сломанные часы, которые 2 раза в день показывают правильное время.
Цитировать chatgpt стоит только в обсуждениях его самого, вроде примеров где он справляется или наоборот. Оно же галюционирует. Поэтому надо его вывод всегда проверять по сторонним источникам, в этом случае достаточно процитировать их. Вы же только разводите энтропию и засоряете интернет.
Завист от того, в чем именно "как круглый". Чтобы его было легко катить, углы при вершинах должны быть достаточно большие. Но тут нет четкой границы - чем больше вершин, тем больше угол, тем легче катить. Из бытового опыта кажется, что 20 угольник уже будет достаточно круглым. 5 угольник - точно нет. 10 угольник - наверное да.
Чтобы люк внутрь не проваливался, как круглый, надо, чтобы разница между диаметром люка (2 наиудаленнейшие точки) и наименьшим сечением была минимальна, меньше толщины люка. Ну, это примерно, потому что если рассматривать люк сверху у него сечение будет прямоугольник и надо чтобы он в N-угольник не пролазил. Еще надо учесть, что дырка из под люка на самом деле на сколько-то процентов меньше люка, он же на каких-то краях лежит.
Тут надо нарисовать N-угольник и подумать. Кажется, минимальное сечение - это высота из вершины в противоположную сторону (или высота между противоположными сторонами для четного N). Диаметром будет или расстояние между противоположными точками для четного N, или ближайшая хорда (разделяющая (N-1)/2 и (N+1)/2 вершин). Можно вывести формулы там будут какие-нибудь косинусы каких-нибудь Pi/2N и какая-то штука должна быть меньше ширины люка. Тут еще где-то будет фактор уменьшения дырки под люк.
На самом деле задача максимально простая и доступна 8-ми классинику.
Это если грубо усреднять и прикидывать. Тут в статье тоже допущения:
Это также предполагает, что множественные вхождения не перекрываются
И еще вместо точного вычисления берется приближение
масштабируется как экспоненциально распределенная случайная величина
Вообще, есть точная формула для вычисления матожидания количества нажатий(у меня есть статья с ее выводом):
Тут Pi^i - это i раз проитерированная префикс функция.
Если искомый текст длины L физически никак не может пересечься сам с собой (начало и конец - совсем разные предложения), то это вырождается просто в K^L.
Руководствуясь теми же уравнениями можно вывести и точную формулу для вероятности набрать текст за N нажатий, но там все так красиво не сворачивается.
Ну вот они на круге. Какое-то между ними расстояние есть (в смысле количество шагов по списку). Обозначим его L. Пока понятно? За одну итерацию цикла вы двигаете быстрый 2 раза, а медленный 1 раз. Как меняется расстояние между ними? Вспомните, что быстрый догоняет медленный - он сзади него. Медленный сделал шаг вперед - ушел вперед от медленного. Расстояние увеличилось на 1. Быстрый сделал 2 шага вперед - он догоняет медленный, расстояние на эти 2 шага уменьшилось. В итоге расстояние изменилось на -2+1= -1. Т.е. уменьшилось на 1. Так понятнее?
Не возможен. Если расписывать доказательство оценки по нормальному, то все видно. Когда медленный вступет на цикл, где-то там уже будет быстрый. И растояние между ними по кругу от быстрого будет L. За одну итерацию это растсояние увеличивается на 1 (медленный сделал шаг вперед) и уменьшается на 2 (быстрый его двумя шагами доганяет). Т.е. расстояние станет L+1-2 = L-1. Оно уменьшается на 1. И за ровно L итераций указатели встретятся - расстояние станет 0.
А еще антимонопольщики настучали гуглу по рукам, мол давать вот эти деньги на продвижение своего поиска в браузерах - нельзя. Теперь этих денег у мозиллы не будет вообще.
Вот метод, как найти все кратчайшие пути (вы в другой статье спрашивали): cначала Дейкстрой найдите расстояния до всех вершин. Потом рекурсивным перебором из конца, идите в каждую вершину, если расстояние там + длина ребра = расстоянию тут. Когда дошли до начала выводите текущий путь задом на перед. Можно, кстати, упростить этот момент, если запускать Дейкстру не из начала в конец, а наоборот, из конца в начало. Тогда восстановленый путь не надо будет разворачивать. Ну, если у вас граф не ориентированный, конечно. В ориентированном надо сначала все ребра развернуть.
Учтите только, что различных путей кратчайшей длины может быть экспоненциально много, а в случае ребер нулевой длины - вообще бесконечное количество. Кстати, для ребер отрицательной длины дейкстра вообще не работает, про это стоило упомянуть в статье.
Это разные классы алгоритмов. Дейкстра ищет до всех вершин, а A* до одной конкретной. A* в этом случае обычно лучше. Правда, не везде и не всегда. Если эвристика не очень точная и долго вычисляемая, то Дейкстра будет даже быстрее A*.
Плохое объяснение. Особенно с учетом, что статьями про дейкстру завален интернет в целом и хабр в частности.
Вы воспроизводите самую большую ошибку комментариев - когда в них просто продублировано, что делает код:
# присваиваем 10 в переменную a
a = 10
По вашей статье невозможно понять алгоритм, только вызубрить. Ни слова про то, что он является по сути динамическим программированием, почему он работает, что его можно делать без очереди и так будет даже быстрее на плотных графах. Вообще, правильно сначала объяснить алгоритм без очереди, а потом уже ее сверху навешивать как оптимизацию.
Плотность воды 997 кг/м^3. У мочи, согласно гуглу, чуть больше - 1002. Для простоты округлим до 1000 кг/м^3.
Радиус Шварцшильда:
10^36 литров - это 10^33 м^3 - сфера радиусом 6.203\*10^10 метров.
Масса там 10^33 кг, радиус Ш. получается 1.486*10^6
Т.е. просто шар из мочи в космосе примерно в 40000 раз больше, чем радиус Шварцшильда, т.ч. черной дыры там нет.
Согласно физике оно, конечно, начнет сжиматься. Вопрос в том, получится ли там какая-то ядерная реакция, которая сможет эту массу удержать от коллапса в черную дыру. Вроде как в звездах сжигается водород. H2O скорее всего при таких давлениях перестанет быть молекулой, так что водорода будет достаточно, чтобы это получилась звезда в 1000 солнечных масс.
Отдельный вопрос, а вращается ли этот шар? При вращении он как раз может распасться на куски о организовать планеты (ледяные только) и какую-то звезду в центре поменьше. Правда, вращение должно быть очень быстрое, чтобы вещество по краям смогло разлететься подальше, ибо масса в 1000 солнц в радиусе меньше орбиты земли не кажется чем-то реалистичным.
Время считается в элементарных операциях. Так-то можно объявить сортировку массива "операцией" и иметь сортировку за O(1).
Сложение является O(1) операцией только пока числа ограничены в размере. В противном случае надо это учитывать. В большинстве алгоритмов, даже если входные числа сколь угодно большие, сложность не поменяется, потому что N в O(f(N)) - обычно это размер входных данных. И на практике этот момент часто игнорируют. Но иногда это важно. Как в этой задаче.
есть вероятность, что тебе просто неповезёт с задачей (или повезёт
Поэтому в крупных компаниях вроде гугла дают несколько раундов разных задачек. И завалить 1 из них - не проблема вообще. При этом знание базы и умение мыслить алгоритмически повышают вероятность решить задачу гораздо больше, чем вызубривание решений. Для этого же, кстати, задачи часто меняют, особенно, если они утекают. Поэтому, кстати, задач нужно очень много.
например мы отсеим очень крутого и опытного спеца, только из-за того, что он с такого рода задачами не пересекался
Печально, но не проблема. За забором еще 10 крутых и опытных спецов, которые с такого рода задачами сталкивались или хотя бы готовились к интервью. Если спец такой крутой, то прочитать одну книжку, присланную ХРом и подумать потом над задачами он сможет запросто.
оценивать кандидата методом ва-банк (с помощью одной чисто теоретической/синтетической задачей) является неэффективным подходом.
См мой первый ответ выше
А вот 2-3 задачи попроще, взятых с реальных проектов, будет гораздо репрезентативней, с точки зрения оценки навыков кандидата.
Проблема тут в том, что вытащить и абстрагировать задачу с реального проекта для интервью весьма сложно. Вы же не можете 30 минут только давать кандидату контекст и объяснять, что сделать надо. Если же что-то можно выделить, то там либо получаются тривиальные вещи вроде fizzbuzz, что не подходит, ибо кандидатов надо отсеивать, или получится что-то посложнее, что ни по какому критерию никак не отличается от литкод medium-hard задачек. Плюс, тут специфика фаангов - там везде своя внутренняя кухня, свои фреймворки и решения (чаще всего потому, что они появились раньше популярных фреймворков), поэтому любая задача с настоящего проекта будет точно такой же абстрактной число дробилкой.
Не вижу, где я нагрубил. Вы просто скопировали текст из чата, поленились его проверить, проанализировать и сделать из него свои выводы. Никак иначе, чем "засорять интернет" я это назвать не могу.
Обращаю ваше внимание, я не давал никакой оценки утверждений нагенеренным в вашем комментарии. Я лишь резко негативно выразился про ваше действие.
Ну вот это вот и стоило сделать автору комментария, а не цитировать чатжпт! Даже если в этом конкретном случае оно оказалось 100% правильно. Это сломанные часы, которые 2 раза в день показывают правильное время.
Да конечно. На порядки медленее сишного кода.
Цитировать chatgpt стоит только в обсуждениях его самого, вроде примеров где он справляется или наоборот. Оно же галюционирует. Поэтому надо его вывод всегда проверять по сторонним источникам, в этом случае достаточно процитировать их. Вы же только разводите энтропию и засоряете интернет.
Завист от того, в чем именно "как круглый". Чтобы его было легко катить, углы при вершинах должны быть достаточно большие. Но тут нет четкой границы - чем больше вершин, тем больше угол, тем легче катить. Из бытового опыта кажется, что 20 угольник уже будет достаточно круглым. 5 угольник - точно нет. 10 угольник - наверное да.
Чтобы люк внутрь не проваливался, как круглый, надо, чтобы разница между диаметром люка (2 наиудаленнейшие точки) и наименьшим сечением была минимальна, меньше толщины люка. Ну, это примерно, потому что если рассматривать люк сверху у него сечение будет прямоугольник и надо чтобы он в N-угольник не пролазил. Еще надо учесть, что дырка из под люка на самом деле на сколько-то процентов меньше люка, он же на каких-то краях лежит.
Тут надо нарисовать N-угольник и подумать. Кажется, минимальное сечение - это высота из вершины в противоположную сторону (или высота между противоположными сторонами для четного N). Диаметром будет или расстояние между противоположными точками для четного N, или ближайшая хорда (разделяющая (N-1)/2 и (N+1)/2 вершин). Можно вывести формулы там будут какие-нибудь косинусы каких-нибудь Pi/2N и какая-то штука должна быть меньше ширины люка. Тут еще где-то будет фактор уменьшения дырки под люк.
Какая дешевая манипуляция. При чем тут вообще квадратные миллионы абсолютно пустой территории, на которой никто не живет?
Это если грубо усреднять и прикидывать. Тут в статье тоже допущения:
И еще вместо точного вычисления берется приближение
Вообще, есть точная формула для вычисления матожидания количества нажатий(у меня есть статья с ее выводом):
Тут Pi^i - это i раз проитерированная префикс функция.
Если искомый текст длины L физически никак не может пересечься сам с собой (начало и конец - совсем разные предложения), то это вырождается просто в K^L.
Руководствуясь теми же уравнениями можно вывести и точную формулу для вероятности набрать текст за N нажатий, но там все так красиво не сворачивается.
Ну вот они на круге. Какое-то между ними расстояние есть (в смысле количество шагов по списку). Обозначим его L. Пока понятно? За одну итерацию цикла вы двигаете быстрый 2 раза, а медленный 1 раз. Как меняется расстояние между ними? Вспомните, что быстрый догоняет медленный - он сзади него. Медленный сделал шаг вперед - ушел вперед от медленного. Расстояние увеличилось на 1. Быстрый сделал 2 шага вперед - он догоняет медленный, расстояние на эти 2 шага уменьшилось. В итоге расстояние изменилось на -2+1= -1. Т.е. уменьшилось на 1. Так понятнее?
На каком предложении не понятно?
Не возможен. Если расписывать доказательство оценки по нормальному, то все видно. Когда медленный вступет на цикл, где-то там уже будет быстрый. И растояние между ними по кругу от быстрого будет L. За одну итерацию это растсояние увеличивается на 1 (медленный сделал шаг вперед) и уменьшается на 2 (быстрый его двумя шагами доганяет). Т.е. расстояние станет L+1-2 = L-1. Оно уменьшается на 1. И за ровно L итераций указатели встретятся - расстояние станет 0.
А еще антимонопольщики настучали гуглу по рукам, мол давать вот эти деньги на продвижение своего поиска в браузерах - нельзя. Теперь этих денег у мозиллы не будет вообще.
Вот метод, как найти все кратчайшие пути (вы в другой статье спрашивали): cначала Дейкстрой найдите расстояния до всех вершин. Потом рекурсивным перебором из конца, идите в каждую вершину, если расстояние там + длина ребра = расстоянию тут. Когда дошли до начала выводите текущий путь задом на перед. Можно, кстати, упростить этот момент, если запускать Дейкстру не из начала в конец, а наоборот, из конца в начало. Тогда восстановленый путь не надо будет разворачивать. Ну, если у вас граф не ориентированный, конечно. В ориентированном надо сначала все ребра развернуть.
Учтите только, что различных путей кратчайшей длины может быть экспоненциально много, а в случае ребер нулевой длины - вообще бесконечное количество. Кстати, для ребер отрицательной длины дейкстра вообще не работает, про это стоило упомянуть в статье.
Это разные классы алгоритмов. Дейкстра ищет до всех вершин, а A* до одной конкретной. A* в этом случае обычно лучше. Правда, не везде и не всегда. Если эвристика не очень точная и долго вычисляемая, то Дейкстра будет даже быстрее A*.
Плохое объяснение. Особенно с учетом, что статьями про дейкстру завален интернет в целом и хабр в частности.
Вы воспроизводите самую большую ошибку комментариев - когда в них просто продублировано, что делает код:
По вашей статье невозможно понять алгоритм, только вызубрить. Ни слова про то, что он является по сути динамическим программированием, почему он работает, что его можно делать без очереди и так будет даже быстрее на плотных графах. Вообще, правильно сначала объяснить алгоритм без очереди, а потом уже ее сверху навешивать как оптимизацию.
рабочие места такие:
Плотность воды 997 кг/м^3. У мочи, согласно гуглу, чуть больше - 1002. Для простоты округлим до 1000 кг/м^3.
Радиус Шварцшильда:
10^36 литров - это 10^33 м^3 - сфера радиусом 6.203\*10^10 метров.
Масса там 10^33 кг, радиус Ш. получается 1.486*10^6
Т.е. просто шар из мочи в космосе примерно в 40000 раз больше, чем радиус Шварцшильда, т.ч. черной дыры там нет.
Согласно физике оно, конечно, начнет сжиматься. Вопрос в том, получится ли там какая-то ядерная реакция, которая сможет эту массу удержать от коллапса в черную дыру. Вроде как в звездах сжигается водород. H2O скорее всего при таких давлениях перестанет быть молекулой, так что водорода будет достаточно, чтобы это получилась звезда в 1000 солнечных масс.
Отдельный вопрос, а вращается ли этот шар? При вращении он как раз может распасться на куски о организовать планеты (ледяные только) и какую-то звезду в центре поменьше. Правда, вращение должно быть очень быстрое, чтобы вещество по краям смогло разлететься подальше, ибо масса в 1000 солнц в радиусе меньше орбиты земли не кажется чем-то реалистичным.
В других темах считали. Через 4-5 лет на этом экспоненциальном счетчике штраф как раз достигнет гугла - 10^100
Впаяли? Или это была сумма иска, требуемая правоторговцами? Они там сколько угодно могут запросить, суд по идее особо наглые просьбы проигнорирует.
Время считается в элементарных операциях. Так-то можно объявить сортировку массива "операцией" и иметь сортировку за O(1).
Сложение является O(1) операцией только пока числа ограничены в размере. В противном случае надо это учитывать. В большинстве алгоритмов, даже если входные числа сколь угодно большие, сложность не поменяется, потому что N в O(f(N)) - обычно это размер входных данных. И на практике этот момент часто игнорируют. Но иногда это важно. Как в этой задаче.
Поэтому в крупных компаниях вроде гугла дают несколько раундов разных задачек. И завалить 1 из них - не проблема вообще. При этом знание базы и умение мыслить алгоритмически повышают вероятность решить задачу гораздо больше, чем вызубривание решений. Для этого же, кстати, задачи часто меняют, особенно, если они утекают. Поэтому, кстати, задач нужно очень много.
Печально, но не проблема. За забором еще 10 крутых и опытных спецов, которые с такого рода задачами сталкивались или хотя бы готовились к интервью. Если спец такой крутой, то прочитать одну книжку, присланную ХРом и подумать потом над задачами он сможет запросто.
См мой первый ответ выше
Проблема тут в том, что вытащить и абстрагировать задачу с реального проекта для интервью весьма сложно. Вы же не можете 30 минут только давать кандидату контекст и объяснять, что сделать надо. Если же что-то можно выделить, то там либо получаются тривиальные вещи вроде fizzbuzz, что не подходит, ибо кандидатов надо отсеивать, или получится что-то посложнее, что ни по какому критерию никак не отличается от литкод medium-hard задачек. Плюс, тут специфика фаангов - там везде своя внутренняя кухня, свои фреймворки и решения (чаще всего потому, что они появились раньше популярных фреймворков), поэтому любая задача с настоящего проекта будет точно такой же абстрактной число дробилкой.