Separate Black and White Balls
Два типа "шаров". Всех 2ого типа нужно переместить в правую часть делая перестановки с ближайшим.
Кажется, что такую задачу мне давали в Т-банке.
Ниткод рассказал бодро и понятно. Но ничего не понятно.
Пока понятно, что можно и не свапать.
Ещё пару солюшенов. И ок понятно.
——————
Дошли до 1ой единицы. Потенциальный инкремент счётчика перестановок.
000000 1 0 1
|
potentional_swap
Если бы было так:
000000 1
Надо выходить. Или же неикрементнуть результат.
Если бы было так:
000000 1 1
Надо неикрементнуть результат.
У нас так:
000000 1 0
|
Поскольку это ноль, надо отобразить это в результате.
res += cnt
Ок, значит будет:
000000 0 1 (но физически менять не обязательно!)
т.е. res = 1;
Далее. На самом деле у нас в изначальном примере в конце другая единица:
000000 0 1 1
|
Опять единица? Инкрементнули счётчик(сейчас равен 2). Но пока не добавляем ничего в результат.
Ок. Закончили. res = 1; count = 2, выходим. Но...
...если бы был еще 0:
000000 0 1 1 0
Что теперь надо?
Мы же хотим текущие единицы сдвинуть ещё:
000000 0 1 1 0 -> 000000 0 0 1 1
000000 0 1 1 0
|
Встретили ноль. Добавляем в результат текущее значение счётчика res +=2, т.е. к одному в результате прибавили 2, получилось 3.
Чуть магией попахивает. Но работает.
Благодаря этому постоянному инкременту количеству swap'ов как бы сохраняем состояние. Счётчик как память. Плюс, когда встречаемcя с 1цей пока что инкременим на всякий случай, но в результат не добавляем.
Случается этот самый случай - встретили 0. И что тогда? Все предыдущие единицы надо снова сдвигать! Т.е. тогда когда-то почему-то подвинули(встретили 0). И вот опять. Ну что ж. Такова жизнь. se la vi.
Кажется, что пока объяснял немного больше понял.
Тот момент, когда уже сколько-то решаешь, но вот очередная задача оказывается эдакой.
#Т-Банк
Два типа "шаров". Всех 2ого типа нужно переместить в правую часть делая перестановки с ближайшим.
Кажется, что такую задачу мне давали в Т-банке.
Ниткод рассказал бодро и понятно. Но ничего не понятно.
Пока понятно, что можно и не свапать.
Ещё пару солюшенов. И ок понятно.
——————
Дошли до 1ой единицы. Потенциальный инкремент счётчика перестановок.
000000 1 0 1
|
potentional_swap
Если бы было так:
000000 1
Надо выходить. Или же неикрементнуть результат.
Если бы было так:
000000 1 1
Надо неикрементнуть результат.
У нас так:
000000 1 0
|
Поскольку это ноль, надо отобразить это в результате.
res += cnt
Ок, значит будет:
000000 0 1 (но физически менять не обязательно!)
т.е. res = 1;
Далее. На самом деле у нас в изначальном примере в конце другая единица:
000000 0 1 1
|
Опять единица? Инкрементнули счётчик(сейчас равен 2). Но пока не добавляем ничего в результат.
Ок. Закончили. res = 1; count = 2, выходим. Но...
...если бы был еще 0:
000000 0 1 1 0
Что теперь надо?
Мы же хотим текущие единицы сдвинуть ещё:
000000 0 1 1 0 -> 000000 0 0 1 1
000000 0 1 1 0
|
Встретили ноль. Добавляем в результат текущее значение счётчика res +=2, т.е. к одному в результате прибавили 2, получилось 3.
Чуть магией попахивает. Но работает.
Благодаря этому постоянному инкременту количеству swap'ов как бы сохраняем состояние. Счётчик как память. Плюс, когда встречаемcя с 1цей пока что инкременим на всякий случай, но в результат не добавляем.
Случается этот самый случай - встретили 0. И что тогда? Все предыдущие единицы надо снова сдвигать! Т.е. тогда когда-то почему-то подвинули(встретили 0). И вот опять. Ну что ж. Такова жизнь. se la vi.
Кажется, что пока объяснял немного больше понял.
Тот момент, когда уже сколько-то решаешь, но вот очередная задача оказывается эдакой.
#Т-Банк
🔥2
Number of Islands
Задача из списка Яндекса. Ладно. Уговорили в 00:43.
Да, я её решал. По-моему, даже сам по крайней мере алгоритм понял, сделал. Помню я что-то сейчас? А ты как думаешь?
1.4 года прошло.
Попробую накидать алгоритм. В списке нита 150 стоит в разделе Графы. В списке яндекса dfs/bfs. Ну что ж. Поможет. Ли?
Аппрувнутый код заккоментировал прищуриваясь так, чтобы не рассмотреть решение. Помучаюсь, наверное, немного. А потом спать.
https://leetcode.com/problems/number-of-islands/
#Yandex
Задача из списка Яндекса. Ладно. Уговорили в 00:43.
Да, я её решал. По-моему, даже сам по крайней мере алгоритм понял, сделал. Помню я что-то сейчас? А ты как думаешь?
1.4 года прошло.
Попробую накидать алгоритм. В списке нита 150 стоит в разделе Графы. В списке яндекса dfs/bfs. Ну что ж. Поможет. Ли?
Аппрувнутый код заккоментировал прищуриваясь так, чтобы не рассмотреть решение. Помучаюсь, наверное, немного. А потом спать.
https://leetcode.com/problems/number-of-islands/
#Yandex
LeetCode
Number of Islands - LeetCode
Can you solve this real interview question? Number of Islands - Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent…
An island is surrounded by water and is formed by connecting adjacent…
👍1
Парсинг китайской грамоты. Не побежденный.
Dailик. Побеждать себя. Побеждать алгоритм.
Читаю задание. Китайская грамота. Ничего не понятно.
I. Есть набор чисел на входы
Есть bitwise OR - т.е. побитовое или. 1 | 2 = 3;
II. Есть subset
Подмножество. Подмножества? Нет. О. Чего? nums a. Какие у него есть подмножества? Набор чисел?
По какому признаку? Все уникальные? Сделать из них группы? Вернуть их? Или какой-то результат?
return: кол-во разных не нулевых подмножеств. У которых... Которые делаем по признаку...
"У тебя максимальное число(больше всех) битовых операций ИЛИ!"
Что? Ты что-нибудь понял?
У этой задачи примерно 80% рейтинг приёмов. Плачу. Т.е. достаточно лёгкая...
Подмножество - это что получили из nums удаляя(а может и нет!) элементы.
А разные подмножества - когда каждый отличается от другого... чем-то?... (C) Кэп
⏳ ...спустя время...Hint 1, 2. Нет. Они не помогают, когда не понял условие задачи. Есть мастера bitwise OR?
Просто же! 84% acceptance.
🕐 ...прошло пару часов...
Какая комбинация из чисел при их операции OR друг с другом даст максимально возможное число.
А?! КакогО?!
🕘 ...настал вечер. Работа. Садик. Тех. Конференция. Созвон. И вот Ya back again.
21:05. Погнали.
То есть, мне нужно попробовать каждый с каждым, да ещё и в разных комбинациях. Хотя, порядок не важен:
Эм... да здесь кол-во перестановок. Задача на них.
🧠 Хотя, нет. Стоит ли решать под вечер с не варящим котелком? Гоу ниткод? Блин, был близок...
Ещё попытка.
Перебираю все возможные комбинации. Без разницы какие числа где стоят относительно друг друга. Нужны лишь уникальные комбинации по самим неповторяющимся числам.
У каждого числа есть индекс. Так, чтобы одно число с этим же индексом в этом наборе не присутствовало.
III. Получить все комбинации...
Допустим получил. Пройдусь по ним, находя такую, которая даёт макс результат при применение ко всем числам в этой комбинации побитового ИЛИ.
Пускай текущий пока максимальный. Его добавляю во временный результат из списка таких комбинаций.
Если нашёл более максимальный, сбрасываю временный результат, добавляю текущую комбинацию(сет).
// это больше для меня, или тебе также полезен такой формат поста-рассуждения?
Ок. Сводим к простой(наверное) подзадачи по получению комбинаций.
Рекурсия? Dynamic programming? С каждого текущего места может пойти в следующее. Или через следующее.
IV. Наблюдение
Явно само подмножество, которое состоит из всех элементов и будет макс. Кстати да. Вот отправная точка.
Могут ли меньше элементов дать такой же результат? Да! В силу специфики bitwise OR. Какие-то единички просто друг друга перетерают. Ну, не мешают.
Но такое число - молодец. Рождает новую комбинацию.
Ну как бы ничего плохого не стало от единицы. От 5ки уже там бит стоял. Зато добавилась новая комбинация в ответ:
{5}
{5, 1}
V. Код
Ну это всё лирика. Show me your code. Again. And I tell you who you are.
Сделал решение. Пока не всё проходит.
2 2 2. 7 комбинаций. У меня меньше.
Все напишем:
VI. Конец
😢 Всё, здесь я закончился. Один цикл с рекурсией внутри по всем. А зачем она?... Просто бы итерировался.
Надо начинать каждый раз со следующего числа. Первая комбинация - оно само. Остальные - комбо из оставшихся чисел, где его же может и не быть))
Вот они. Все 7 комбинаций. Ок.
Ок. 2/3 test case.
Ок. Отладка. Ещё время... Не нахожу что не так...
Ок. Слишком долго. Смотрю solution.
Вывод
Был близок. Как это можно решить за 0.5 часа?
У меня заняло утром 17 минут и сейчас 1.5 часа.
Говорят, что если 0.5 часа не получается, надо смотреть. Ну тут азарт. Я думаю, нормально. Можно и поспать.
Dailик. Побеждать себя. Побеждать алгоритм.
Читаю задание. Китайская грамота. Ничего не понятно.
I. Есть набор чисел на входы
Есть bitwise OR - т.е. побитовое или. 1 | 2 = 3;
0001
0010
----
0011
II. Есть subset
Подмножество. Подмножества? Нет. О. Чего? nums a. Какие у него есть подмножества? Набор чисел?
По какому признаку? Все уникальные? Сделать из них группы? Вернуть их? Или какой-то результат?
return: кол-во разных не нулевых подмножеств. У которых... Которые делаем по признаку...
"У тебя максимальное число(больше всех) битовых операций ИЛИ!"
Что? Ты что-нибудь понял?
У этой задачи примерно 80% рейтинг приёмов. Плачу. Т.е. достаточно лёгкая...
Подмножество - это что получили из nums удаляя(а может и нет!) элементы.
А разные подмножества - когда каждый отличается от другого... чем-то?... (C) Кэп
⏳ ...спустя время...Hint 1, 2. Нет. Они не помогают, когда не понял условие задачи. Есть мастера bitwise OR?
Просто же! 84% acceptance.
🕐 ...прошло пару часов...
Какая комбинация из чисел при их операции OR друг с другом даст максимально возможное число.
А?! КакогО?!
🕘 ...настал вечер. Работа. Садик. Тех. Конференция. Созвон. И вот Ya back again.
21:05. Погнали.
То есть, мне нужно попробовать каждый с каждым, да ещё и в разных комбинациях. Хотя, порядок не важен:
3 2 1 5
3 2
3 2 1
3 2 1 5
....
2 3 <---уже была
2 1
2 5
2 1 5
2 3 5
....
1 3
1 2 <---уже была
1 5
....
Эм... да здесь кол-во перестановок. Задача на них.
Ещё попытка.
Перебираю все возможные комбинации. Без разницы какие числа где стоят относительно друг друга. Нужны лишь уникальные комбинации по самим неповторяющимся числам.
У каждого числа есть индекс. Так, чтобы одно число с этим же индексом в этом наборе не присутствовало.
0 1 2 3 4
5 2 9 9 3
5 5 <--нельзя, т.к. у обоих индекс 0
9 9 <--ок, это разные 9ки
III. Получить все комбинации...
Допустим получил. Пройдусь по ним, находя такую, которая даёт макс результат при применение ко всем числам в этой комбинации побитового ИЛИ.
Пускай текущий пока максимальный. Его добавляю во временный результат из списка таких комбинаций.
Если нашёл более максимальный, сбрасываю временный результат, добавляю текущую комбинацию(сет).
// это больше для меня, или тебе также полезен такой формат поста-рассуждения?
Ок. Сводим к простой(наверное) подзадачи по получению комбинаций.
Рекурсия? Dynamic programming? С каждого текущего места может пойти в следующее. Или через следующее.
IV. Наблюдение
Явно само подмножество, которое состоит из всех элементов и будет макс. Кстати да. Вот отправная точка.
Могут ли меньше элементов дать такой же результат? Да! В силу специфики bitwise OR. Какие-то единички просто друг друга перетерают. Ну, не мешают.
Но такое число - молодец. Рождает новую комбинацию.
К примеру дали [5, 1]:
5ка - 0101
1ца - 0001
Их комбинация:
5 | 1 - 0101 = 5
Ну как бы ничего плохого не стало от единицы. От 5ки уже там бит стоял. Зато добавилась новая комбинация в ответ:
{5}
{5, 1}
V. Код
Ну это всё лирика. Show me your code. Again. And I tell you who you are.
Сделал решение. Пока не всё проходит.
2 2 2. 7 комбинаций. У меня меньше.
Все напишем:
2
2 2
2 2 2
2 2
VI. Конец
😢 Всё, здесь я закончился. Один цикл с рекурсией внутри по всем. А зачем она?... Просто бы итерировался.
Надо начинать каждый раз со следующего числа. Первая комбинация - оно само. Остальные - комбо из оставшихся чисел, где его же может и не быть))
2
2 2
2
Вот они. Все 7 комбинаций. Ок.
Ок. 2/3 test case.
Ок. Отладка. Ещё время... Не нахожу что не так...
Ок. Слишком долго. Смотрю solution.
Вывод
Был близок. Как это можно решить за 0.5 часа?
У меня заняло утром 17 минут и сейчас 1.5 часа.
Говорят, что если 0.5 часа не получается, надо смотреть. Ну тут азарт. Я думаю, нормально. Можно и поспать.
Please open Telegram to view this post
VIEW IN TELEGRAM
🐳1
🗂 Избыточность тебе нужна! Ищи её!
Find Kth Bit in Nth Binary String
🤾♂️ Утренняя разминка в субботу. И сразу вывод - наблюдай за избыточностью!
⏱️ Примерно пол часа на решение. И оно принято! ✅
А потом посмотреть как бывает ещё... Я сделал brute force.
В editorial несколько решений. Посмотрел нита. Ну да. Оптимизация. Как всегда.
Нужно быть/стараться быть наблюдательным. Посмотреть на данные. На возможную избыточность.
🙄 Реально ли на интервью до этого дойти? Возможно, с подсказками да.
Или же заучил и прошёл. Но это может быть не лучше. Это поймут. Хотя, если не списывать, а выдавать из головы размышляя, то, кажется что, пойдёт.
Просто отлично прошёл. Просто вчера её решал и ещё помнишь 😁
❓ А тебе попадалась эта задача? Если да, то когда и где?
Find Kth Bit in Nth Binary String
🤾♂️ Утренняя разминка в субботу. И сразу вывод - наблюдай за избыточностью!
⏱️ Примерно пол часа на решение. И оно принято! ✅
А потом посмотреть как бывает ещё... Я сделал brute force.
В editorial несколько решений. Посмотрел нита. Ну да. Оптимизация. Как всегда.
Нужно быть/стараться быть наблюдательным. Посмотреть на данные. На возможную избыточность.
🙄 Реально ли на интервью до этого дойти? Возможно, с подсказками да.
Или же заучил и прошёл. Но это может быть не лучше. Это поймут. Хотя, если не списывать, а выдавать из головы размышляя, то, кажется что, пойдёт.
Просто отлично прошёл. Просто вчера её решал и ещё помнишь 😁
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥1
😳 Неожиданное деление на 2
1️⃣ 0️⃣ Обычно смещение используется в задачах на битовые манипуляции.
Первый раз встретил в контексте бинарного поиска)
Но всё-ли хорошо с такой операций?
Первый раз встретил в контексте бинарного поиска)
Но всё-ли хорошо с такой операций?
Please open Telegram to view this post
VIEW IN TELEGRAM
💫 Подготовка закончена. Пора пробовать
📆 Месячный забег неожиданно подошёл к концу. Почему неожиданно? Я думал, что собеседование будет только в середине недели. hr в понедельник напомнила, что собеседование вечером 🫨
🎓 Хотел успеть за эти пару дней пройтись по решенным задачам. Ну что ж. Прошёл за пару часов по списку рекомендованных к решению. И не зря.
На встречи попались задачи:
1) На два указателя
2) На скользящее окно
Поскольку в голове были подгружены какие-то паттерны, получилось продвинуться.
❓ Прошёл на следующий этап? Об этом узнаем в течение пары дней)
▶️ Если интересно, в будущем расскажу подробней о самом прохождение.
📆 Месячный забег неожиданно подошёл к концу. Почему неожиданно? Я думал, что собеседование будет только в середине недели. hr в понедельник напомнила, что собеседование вечером 🫨
🎓 Хотел успеть за эти пару дней пройтись по решенным задачам. Ну что ж. Прошёл за пару часов по списку рекомендованных к решению. И не зря.
На встречи попались задачи:
1) На два указателя
2) На скользящее окно
Поскольку в голове были подгружены какие-то паттерны, получилось продвинуться.
▶️ Если интересно, в будущем расскажу подробней о самом прохождение.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍5🔥2
⚙️ Тактика подготовки на leetcode
Понравился пост товарища, который также собеседуется в Yandex. И уже прошёл несколько секций.
Понравился пост товарища, который также собеседуется в Yandex. И уже прошёл несколько секций.
👍1
Forwarded from tech0ver
⛏ Тактика подготовки на leetcode
Изначально у меня был подход с решением всех задач по порядку — этот подход можно назвать «отсутствием подхода», потому что с каждой задачей меняется тема и сложность.
Сейчас у меня следующий подход:
1. Выбираем тему задач, от простой к сложной, например, Array — в leetcode это поле поиска Tag
2. Выбираем сложность, от простой к сложной, например, Easy — это поле поиска Difficulty
3. Задачу можно брать:
- по порядку в списке
- отсортировать по полю Acceptance — чем меньше, тем сложнее
- посмотреть в подборках
Не секрет что у каждой задачи есть паттерн решения, поэтому нам важно решить задачу на каждый паттерн, чтобы научиться его считывать.
4. Если задача для нас новая — пытаемся решить через brute-force, это поможет натолкнуть на более оптимальный способ решения.
Если не получается решить, можно подсмотреть в Related Topics у задачи, там можно узнать паттерн, например, Two Pointers.
Если и это не помогло, можно поискать решение данной задачи как
Обязательно определяем time/space complexity.
5. После решения n-ого кол-ва задач, когда мы уже считываем паттерн — мы повышаем сложность и меняем тему, повторяя шаги.
#algo
Изначально у меня был подход с решением всех задач по порядку — этот подход можно назвать «отсутствием подхода», потому что с каждой задачей меняется тема и сложность.
Сейчас у меня следующий подход:
1. Выбираем тему задач, от простой к сложной, например, Array — в leetcode это поле поиска Tag
2. Выбираем сложность, от простой к сложной, например, Easy — это поле поиска Difficulty
3. Задачу можно брать:
- по порядку в списке
- отсортировать по полю Acceptance — чем меньше, тем сложнее
- посмотреть в подборках
Не секрет что у каждой задачи есть паттерн решения, поэтому нам важно решить задачу на каждый паттерн, чтобы научиться его считывать.
4. Если задача для нас новая — пытаемся решить через brute-force, это поможет натолкнуть на более оптимальный способ решения.
Если не получается решить, можно подсмотреть в Related Topics у задачи, там можно узнать паттерн, например, Two Pointers.
Если и это не помогло, можно поискать решение данной задачи как
solution название задачи, а можно взять похожую задачу в Similar Questions, чтобы на ней разобрать решение и вернуться.Обязательно определяем time/space complexity.
5. После решения n-ого кол-ва задач, когда мы уже считываем паттерн — мы повышаем сложность и меняем тему, повторяя шаги.
#algo
👍7
Посмотрим, посмотрим.
А чем ты занимаешься в этот прекрасный вечер перед выходными?
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1
🪟➡️ Скользящее окно для тебя
На собеседование в Яндекс попалась задача на скользящее окно. В моменте сказал про этот паттерн. И это было хорошо, что понял его.
Предлагаю твоему вниманию моё сегодняшнее решение задачи "Найти длину максимально длинной подстроки без повторных символов".
Держим хэш. Если элемент попадался, удаляем слева.
Подробнее описал в решениях на самой платформе:
https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/6003337/sliding-windows-with-picture-you-want-to-see/
Удачи в подготовке и интервью!
На собеседование в Яндекс попалась задача на скользящее окно. В моменте сказал про этот паттерн. И это было хорошо, что понял его.
Предлагаю твоему вниманию моё сегодняшнее решение задачи "Найти длину максимально длинной подстроки без повторных символов".
Держим хэш. Если элемент попадался, удаляем слева.
Подробнее описал в решениях на самой платформе:
https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/6003337/sliding-windows-with-picture-you-want-to-see/
Удачи в подготовке и интервью!
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1
Forwarded from 𝖉𝖊𝖋𝖙
Короч я сделал годовой стрик на литкоде.
Советую я кому то повторить - нет
Получил ли я пользу - нет
Продолжу - нет
Решал ли все дни сам - нет
Сложно ли это - да
Бессмысленно - да
Хотелось ли все бросить - да.
Это был ТЛ;ДР.
Короч как по мне решать литкод осознанно по темам намного веселее и приятнее. Типа взял тему и пошел херачить. Спустя время даже харды пишутся. Можешь решить несколько задач в день, а можешь и ни одной. Всякое бывает.
Спустя какое то время я просто решал или списывал что бы просто закрыть день и не сгорел стрик.
Стал ли я лучше решать? Объективно нет. Пользы больше было после следования методологии которую раньше делал для курса.
Советую я кому то повторить - нет
Получил ли я пользу - нет
Продолжу - нет
Решал ли все дни сам - нет
Сложно ли это - да
Бессмысленно - да
Хотелось ли все бросить - да.
Это был ТЛ;ДР.
Короч как по мне решать литкод осознанно по темам намного веселее и приятнее. Типа взял тему и пошел херачить. Спустя время даже харды пишутся. Можешь решить несколько задач в день, а можешь и ни одной. Всякое бывает.
Спустя какое то время я просто решал или списывал что бы просто закрыть день и не сгорел стрик.
Стал ли я лучше решать? Объективно нет. Пользы больше было после следования методологии которую раньше делал для курса.
👍4🔥2