Как вам мастерство кликбейтных заголовков? https://leetcode.com/problems/shortest-distance-to-a-character/discuss/1054195/Python-O(N)-O(1)-Pointers-100-hire-in-Google-solution!

Вот вот)) сколько нулей не помню, но примерно такой баг

https://0.30000000000000004.com/

Как вам мастерство кликбейтных заголовков? https://leetcode.com/problems/shortest-distance-to-a-character/discuss/1054195/Python-O(N)-O(1)-Pointers-100-hire-in-Google-solution!

прикольно, что в один проход 👍 я в два решил, но зато код легче читать)

прикольно, что в один проход 👍 я в два решил, но зато код легче читать)

Там у меня выше есть в 2. Там +- одно и тоже по читаьельности

Там у меня выше есть в 2. Там +- одно и тоже по читаьельности

Слева направо, и справа налево

Так читабельнее

Кому-то кликбейт не понравился 😃

Кому-то кликбейт не понравился 😃

Да капец. Хейтеры диз поставили.

Ага, ага, 15 просмотров и 3 лайка тупо за видос, верим верим

Там у меня выше есть в 2. Там +- одно и тоже по читаьельности

кстати, когда в 2 прохода, индексы можно ведь не хранить, понятно что по памяти и так и так O(n), но тем не менее)

Я вот тоже начал писать в один проход, но запутался и забил. Прошёл туда и обратно

Я вот тоже начал писать в один проход, но запутался и забил. Прошёл туда и обратно

Я сам если честно пока в discuss не увидел “two pointers” не догадался до такого.

Никогда не думал, что vim удобный

Капец, перешел с Chrome на Safari, а с VScode на Vim – +2гб оперативки

Никогда не думал, что vim удобный

Что у тебя со сглаживанием шрифтов?

Что у тебя со сглаживанием шрифтов?

Я его выключил

Я его выключил

А, ок

А, ок

У меня еще 720p

У меня еще 720p

Экран. Мак эир, ули

https://twitter.com/krllsdv/status/1358305460152131587?s=19

Теперь гадай, на чъей стороне Яндекс 🤣

Капец, перешел с Chrome на Safari, а с VScode на Vim – +2гб оперативки

Я наоборот перешёл с вим на vscode. Включил там вим мод и в итоге тоже самое что и было у меня в виме только не нужно вручную ничего настраивать. Немного медленнее конечно, но фича с ремоут контейнерами конечно килер фича. Да и pylance тоже хорош

Я наоборот перешёл с вим на vscode. Включил там вим мод и в итоге тоже самое что и было у меня в виме только не нужно вручную ничего настраивать. Немного медленнее конечно, но фича с ремоут контейнерами конечно килер фича. Да и pylance тоже хорош

Ужас, а сколько оперативки на ноуте? Что за ремоут контейнеры? С докером что-то?

8гб Ага вскод запускает внутри контейнера процес и конектиться к нему https://code.visualstudio.com/docs/remote/containers

я вот насчитал 49%

Страшно признаваться, но я плохо посчитал, правильно было бы сказать 34-40% обязательных выплат, а ндс в налоги по зарплате я считаю неверно плюсовать

Happy Monday! 👋 Задача этой недели — найти пик в массиве. Хорошая задача с тривиальным решением и развитием в бинарный поиск. https://vitkarpov.me/posts/peak-index-in-a-mountain-array/

есть ещё такой алгоритм для поиска локальных экстремумов https://en.wikipedia.org/wiki/Golden-section_search https://medium.com/datadriveninvestor/golden-section-search-method-peak-index-in-a-mountain-array-leetcode-852-a00f53ed4076 Он немного по-другому работает, но всё равно O(log N)

Happy Monday! 👋 Задача этой недели — найти пик в массиве. Хорошая задача с тривиальным решением и развитием в бинарный поиск. https://vitkarpov.me/posts/peak-index-in-a-mountain-array/

Крайне рекомендую для бин поиска использовать инварианты

Крайне рекомендую для бин поиска использовать инварианты

Расскажешь подробнее?

Happy Monday! 👋 Задача этой недели — найти пик в массиве. Хорошая задача с тривиальным решением и развитием в бинарный поиск. https://vitkarpov.me/posts/peak-index-in-a-mountain-array/

Найти такое условие, которое выполняется внутри всего цикла. Тогда все индексы и присваивания и большелиборавно пишутся сами собой

Дональд Кнут пишет, что хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск без багов был опубликован только в 1962. ))) https://habr.com/ru/post/91605/

Дональд Кнут пишет, что хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск без багов был опубликован только в 1962. ))) https://habr.com/ru/post/91605/

А реализация на жаве исправила ещё один баг (с переполнением инта) в двухтысячных

Найти такое условие, которое выполняется внутри всего цикла. Тогда все индексы и присваивания и большелиборавно пишутся сами собой

то есть грубо говоря внутри цикла можно поставить ассерт, который если упадёт — значит что-то пошло не так, раз инвариант нарушен. интересно в данном случае, что это будет за инвариант.

то есть грубо говоря внутри цикла можно поставить ассерт, который если упадёт — значит что-то пошло не так, раз инвариант нарушен. интересно в данном случае, что это будет за инвариант.

Даже не просто внутри цикла, а перед и после каждой строки в цикле

Даже не просто внутри цикла, а перед и после каждой строки в цикле

да, вообще тема про инварианты интересная

В programming pearls чувак это продемонстрировал наглядно

Жемчужины программирования

В programming pearls чувак это продемонстрировал наглядно

👍

На каком языке это написано?

На каком языке это написано?

На псевдокоде си-подобном

Дональд Кнут пишет, что хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск без багов был опубликован только в 1962. ))) https://habr.com/ru/post/91605/

Лооол. Ну двоичный поиск реально не просто написать

Happy Monday! 👋 Задача этой недели — найти пик в массиве. Хорошая задача с тривиальным решением и развитием в бинарный поиск. https://vitkarpov.me/posts/peak-index-in-a-mountain-array/

А что думаете о таком формате бинарного поиска, где не нужно делать +1 или -1? https://pastebin.com/zCMSeG3C

А что думаете о таком формате бинарного поиска, где не нужно делать +1 или -1? https://pastebin.com/zCMSeG3C

нормальная история, главное это четко понимать смысл L,R. я бы в данном случае начинал L=-1, а не 0. Типа по смыслу L,R тогда границы за которыми _точно решения нет_ (включительно). И тогда получается логичным условие для while R - L > 1, т.е. когда указатели встали рядом, значит _между_ ними дальше решения нет (и дальше нет смысла искать)

мне такой подход даже больше нравится

А что думаете о таком формате бинарного поиска, где не нужно делать +1 или -1? https://pastebin.com/zCMSeG3C

Ооо, там целая философия

нормальная история, главное это четко понимать смысл L,R. я бы в данном случае начинал L=-1, а не 0. Типа по смыслу L,R тогда границы за которыми _точно решения нет_ (включительно). И тогда получается логичным условие для while R - L > 1, т.е. когда указатели встали рядом, значит _между_ ними дальше решения нет (и дальше нет смысла искать)

+ l = mid + 1 и r = mid Или l = mid и r = mid - 1 Зависит от того, нам надо left boundary или right

+ l = mid + 1 и r = mid Или l = mid и r = mid - 1 Зависит от того, нам надо left boundary или right

это тоже хороший поинт, да. нужен ли нам lower_bound или upper_bound. не так важно, если все числа уникальные.

это тоже хороший поинт, да. нужен ли нам lower_bound или upper_bound. не так важно, если все числа уникальные.

не правильно сказал. не уникальные, а строго возрастающие убывающие, как в условии сказано. то есть нет такого что рядом стоят одни и те же числа.

а есть задачки где это как раз важно, и вот там я начинаю путаться «без словаря» 😃 каждый раз приходится смотреть как пишется lower_bound на всякий случай.

> L=-1, а не 0 @vitkarpov а разве полу-интервалы не чаще применяются?

> L=-1, а не 0 @vitkarpov а разве полу-интервалы не чаще применяются?

🤷‍♂️ . а как понять чаще или нет?

может как-то можно сравнить что проще для понимания или какие есть задачи где это имеет значение.

Ну я пока только 1 задачу из 20 на бинарный не смог этим полуинтервалом решить.

Ну я пока только 1 задачу из 20 на бинарный не смог этим полуинтервалом решить.

ого! какую?

Сам список задач на бинарный поиск (и еще несколько не в списке) https://leetcode.com/list/5dtpe73v/ Не получилась задача: https://leetcode.com/problems/find-k-closest-elements https://pastebin.com/fBwm4HSA

И то подозреваю что скорее всего просто что то упустил

Сам список задач на бинарный поиск (и еще несколько не в списке) https://leetcode.com/list/5dtpe73v/ Не получилась задача: https://leetcode.com/problems/find-k-closest-elements https://pastebin.com/fBwm4HSA

вообще крутой список, конечно. ты прорешиваешь по разным темам, да?

Источники: - самые популярные задачи - https://leetcode.com/explore/learn/card/binary-search/ - https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems - https://leetcode.com/discuss/general-discussion/691825/binary-search-for-beginners-problems-patterns-sample-solutions - https://leetcode.com/list/5aubwh9g/ +фильтр, если негативных оценок больше позитивных Большинство задач из списка входит в 2-3 источника сразу, так как они более-менее схожи.

Ну сейчас подход решать одну тему недели 2 хотя бы. Правда пока получалось только с рекурсией, ДП, сейчас бинарный поиск, на этой неделе переход на тему графы @ganqqwerty тоже причастен к этому подходу

А тренировка рандомных тем - контесты и задачи которые в разных источниках всплывают (чаты какие то или знакомые)

А что думаете о таком формате бинарного поиска, где не нужно делать +1 или -1? https://pastebin.com/zCMSeG3C

Что касается меня, то всегда пишу бинпоиск с +1 и -1 одновременно

Что касается меня, то всегда пишу бинпоиск с +1 и -1 одновременно

Тогда у тебя будет еще одна проверка, и по итогу не покажешь случайное место, куда подходит вставка, а не конкретно слева или справа

Тогда у тебя будет еще одна проверка, и по итогу не покажешь случайное место, куда подходит вставка, а не конкретно слева или справа

Ну для поиска числа это не важно. Конкретно в этой задаче пришлось убрать +1, чтобы определить ответ по левой границе

-1 точнее

@PavelSavelyev приветствую настоящего живого СТО в чате 😉

@PavelSavelyev приветствую настоящего живого СТО в чате 😉

Привет-привет :)

Привет-привет :)

добро пожаловать 😊 решил в перерывах между директорством порешать литкод? 😃

любопытно, что привело технического директора относительно немаленькой компании в этот чат.

найм? 😃

для контекста. мы тут периодически обсуждаем задачки, собеседования, и флудим.

Наконец-то яндексойдов заберут на х2 в мэил как и обещали в мемах

Наконец-то яндексойдов заберут на х2 в мэил как и обещали в мемах

😂

Наконец-то яндексойдов заберут на х2 в мэил как и обещали в мемах

куда записываться? 🙂

куда записываться? 🙂

Видимо к Павлу, в Юлу 😉

куда записываться? 🙂

В СберБанк, к @yeti_or

Вася @yeti_or, возьмешь не глядя?) Только мне бы в Казани остаться 😛

Вася @yeti_or, возьмешь не глядя?) Только мне бы в Казани остаться 😛

Удаленку не дадут )

Я сегодня разблокировал ачивку тайпскрипта: 0 any на 100к кода :D

куда записываться? 🙂

Сам бы не отказался найти :)