Холиварофорум

Анон

Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Здесь я буду ныть писать о том, как отращиваю лапищи, чтобы найти работу лучше и интереснее нынешней.
Когда-то (года три назад) я и мечтать не смел о той работе, которая у меня есть сейчас, и тогда я тоже отращивал лапищи, что придаёт мне мотивацию и некоторую уверенность в себе. Но расти порой больно и сложно, особенно когда в сутках так мало времени. 
Думаю, что этот безбложик мне хоть немного, но поможет.
Лапищи я буду отращивать путём решения задач на алгоритмы и структуры данных (всяческие операции с бинарными деревьями например тащемта), а также запиливания небольших проектов (всё на питоне). В идеале (программа максимум) хочу перекатиться из автоматизитора в бэкенд-инженеры. Программа минимум - научиться за полчаса решать задачки hard уровня (положим, с LeetCode) оптимальным способом (с линейной или логарифмической производительностью).

Буду называться анон-левел-апер

Отредактировано (2021-06-16 07:55:45)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Анонче, благодатной почвы твоим деревьям!

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Анонче, благодатной почвы твоим деревьям!

Спасибо, анончик!

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Итак, я начал с понедельника.

Выбрал задачку среднего уровня, на динамическое программирование.
Long story short: дана матрица с целыми числами, надо было вернуть матрицу-ответ, каждый элемент которой - сумма элементов блока  (подматрицы) в исходной матрице,  блок рассчитывается как квадрат со сторонам определённой длины, центр - координаты элемента в матрице-ответе. Причём границы блока могут выходить за границы исходной матрицы, тогда считать только сумму тех элементов, которые  попадают в границы исходной матрицы.

Полтора часа после работы я сидел и пытался понять задание, что же мне надо сделать. Не выдержал под конец, полез в обсуждение - там обсудили и разобрали задание и пришли к мнению, что сформулирована задача не очень понятно (ну да, лепи отговорки).  Жутко расстроился вчера, думал о том, что потерял время. И что время вообще - драгоценная вещь. Было очень плохо думать о том, сколько я уже потерял. Начал казнить себя, что начал решать задачи так поздно. В идеале надо бы всегда держать мозги в тонусе.

Сегодня почитал пару статей, где люди описывали свой опыт подготовки, в обеих статьях у авторов было по 4 недели, чтобы подготовиться к собеседованию в Гугл (и они прошли). Я поставил себе срок где-то 6 месяцев (куда собеседоваться - пока не знаю, буду пробовать разные компании, но до уровня собеседования в Гугл мне очень далеко пока). Оба автора работали полный день, и занимались до или после работы, как и я собираюсь. Рекомендовали: 2-3 часа кодинга - отдых - 2-3 часа дизайн. Ну и плюс держать режим, высыпаться, делать упражнения, правильно есть (есть я люблю!). Я пока занимаюсь только кодингом. За два часа (45 минут работать, 15 отдыхать) чувак в среднем решал одну лёгкую задачу, одну среднюю.

Я решил среднюю сегодня (после того, как впал в отчаяние и сокрушался, почему я такой тупой) за 3 часа, ну не считая вчерешних попыток разобраться, хех. Есть куда стремиться.

Вообще я даже не ожидал, что мой алгоритм с первого раза пройдёт все тесты, и это было приятно: я не безнадёжен. Код, конечно, мог быть проще и красивей (синонимы в контексте кода), но производительность ок (иначе некоторые тесты свалились бы), и главное - работает. Улучшать имплементацию буду позже.

А ещё я понял, что в моей голове есть иногда препятствия. Какой-то голос убеждает меня, что я тупой, это вот сыновья маминых подруг другие решают за полчаса, но это какой-то особый тип людей. Другой голос говорит, что не верит, будтоо у меня что-то получится, и потому стараться бесполезно, это другие какие-то люди могут хорошо пройти собеседование, ну вы поняли. Хочу выброситб эти дурацкие мысли.

Тем временем написало несколько рекрутёров, и я им ответил - в любом случае, полезно получить побольше опыта реальных собеседований (я же всё равно не верю пока, что пройду лол, так что почему бы и не попробовать, не тратя силы на волнение об уже заранее известном результате).

анон-левел-апер

Отредактировано (2021-06-16 08:31:33)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сегодня решил задачку среднего уровня на динамическое программирование за 33 минуты, но там было и задание сформулировано понятнее, и вместо матрицы был одномерный массив. Но всё равно доволен!
После этого понял, что устал (уже 9 вечера) и отправился спать пораньше: отдых тоже очень важен.

P.S. А перед сном даже смог написать несколько строчек в свой оридж-долгострой, до которого не доходили руки неделю!

анон-левел-апер

Отредактировано (2021-06-17 10:29:05)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Решил ещё одну среднюю задачку, снова на динамическое программирование, это была модификация вчерашней, с дополнительным условием. Потратил 49 минут.
Так-то неплохо, чувствую, как мозги начинают разминаться)) Следующая задачка - та же с очередной модификацией, и вот там надо использовать деревья и поиск в глубину. Освежу-ка в памяти это и завтра приступлю.
Задумался о том, как мозг учится, сколько раз надо повторить новый приём/навык, чтобы потом видеть, где надо его применить и таки применить, и чтобы не было такого, что ты вроде бы и освоил, а потом забыл.

Из дыбра: вчера думал, что устроил себе незапланированный чит-день в плане еды (не смог сопротивляться неплохому поке), а сегодня посчитал по калориям - нет, уложился в коридор, и даже остался лёгкий дефицит. Ещё и весы порадовали утром надо это отметить праздничным ужином
А ещё сегодня хотел посмотреть в окно, что это там народ по дороге толпой на великах едет, и ударился лбом о стекло внезапно, как-то его и не заметил

анон-левел-апер

Отредактировано (2021-06-18 08:06:25)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сегодня разбирал задачу, на которую нацелился вчера. Понял, что сейчас сразу я её не решу, поэтому прочитал объяснение к ней, разобрал разные подходы (рекурсия, рекурсия с мемоизацией, динамическое программирование). Думаю задачу пока отложить, а через некоторое время вернуться и решить по следам того, как я понял объяснения подходов к решению. Потратил где-то 90 минут.

Один из перерывов оказался долгим: съездили за боба-чаем, у меня был матча(надеюсь, я правильно это пишу) с сырной пенкой и мармеладом из личи - весьма недурно (хоть и вышел за пределы сегодняшних калорий, но весы с утра снова порадовали, лучше, чем вчера даже)! Придало мне новых сил после рабочего дня) На работе кстати пробовал новый (ну как новый, немного знаком) для себя язык, джава скрипт - ну ок вроде.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сегодня решил 2 средних задачки, на динамическое программирование и массивы, потратил где-то часа 3. Тупил что-то: то ли задачки посложнее, то ли устал за неделю.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Подпишусь. Заглавный пост как про меня: что три года назад и мечтать нельзя было о нынешней работе. Только я ничего не решаю (а зря), в тематических чатах тусю только ( в рид-онли, канешн).
Есть мнение, что если вкурить раздел Learn, оно еще бойчее пойдет.
Удачи и дисциплины тебе, анон! И больших лапищ.

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Подпишусь. Заглавный пост как про меня: что три года назад и мечтать нельзя было о нынешней работе. Только я ничего не решаю (а зря), в тематических чатах тусю только ( в рид-онли, канешн).
Есть мнение, что если вкурить раздел Learn, оно еще бойчее пойдет.
Удачи и дисциплины тебе, анон! И больших лапищ.

Спасибо, анон!
Главное - что прогресс таки есть, и получается находить работу лучше! Да и освоить что-то новое никогда не будет лишним - даже если не пригодится напрямую, то потренируешь мозг.
В тематических чатах я тоже тусую, там предлагают мок-собеседования, вот думаю набраться уверенности и попробовать)

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

В субботу было думал после задачек с утра заняться своими хобби, но как закончил заниматься, то понял, что навалилась жуткая усталость. В итоге до одного хобби руки дошли только к вечеру, сделал немного и неправильно, придётся начинать заново. До второго руки так и не дошли.

В воскресенье решил вообще не напрягаться и только отдыхать (иначе я знаю, что быстро сломаюсь и буду не в силах продуктивно работать и готовиться к собеседованиям). На завтрак поехали в кафешку (прошлый раз были там больше года назад), и что-то это доставило мне такую радость - соскучилась по кафешке, место выпало у окошка, еда понравилась, да и просто настроение было хорошим. А потом как-то приуныл дома, что половина воскресенья уже прошла, а я что-то так и не отдохнул толком, и хобби не позанимался, и на работу немного влом завтра 
Но вкусные роллы немного поправили настроение, а потом прокатились за боба-чаем, и я устроил себе чит-день (а весы утром порадовали снова, ещё на немного). Хех, почти в каждом посте упоминаю еду)

P.S. Начал ещё смотреть ужастик (Ужас Амитивилля, 2005), но он настолько меня разочаровал унылыми и тупыми (надо ли упоминать, что совсем не страшными) крипи-штампами, что фейспалмнул и выключил, начал смотреть другой, из 70-х, но потом уехали за чаем, не досмотрел. Выглядит вроде поприличнее.

анон-левел-апер

Отредактировано (2021-06-21 09:46:43)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Вторая неделя пошла.
Захотел немного сменить тему и решил среднюю задачку на хэш-таблицы. Потратил около часа. Не очень рад этому, буду улучшать время.

Есть хорошая мысль, которой я следую: "Перед тем, как думать, как, понять, зачем". Мой алгоритм мог быть проще и короче (как и мои посты лол), если бы я сразу за деревьями разглядел лес, то вместо углубления в имплементацию я бы подумал, а для чего я сейчас заполняю словарь вот этими значениями? Что я хочу получить? И это помогло бы заимплментировать алгоритм проще. Буду думать, что это произошло оттого, что я давно не практиковался (ну да, продолжай оправдываться). Ладно, ещё одно оправдание - пробковой доски с этой прикрепленной цитатой у меня не было перед глазами в этот раз (хорошая попытка).

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

Говорил сегодня с рекрутёром, обещает раунд более технического разговора с тим-лидом(?) на тему того, что я делал и какие инструменты использовал в работе, если я понравлюсь - то потом уже интервью на кодинг, если пройду его - виртуальный онсайт. Сказал, что хотел бы иметь время для подготовки, рекрутёр ответил, что неделю могут дать.

Хотел написать о чём-то помимо подготовки, но забыл :(

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Ещё понял внезапно: исчезло то щемящее чувство, когда думаешь о том, что ты зря потратил время, и оно уже никогда не вернётся. А ещё ушла тревожность по сравнению с прошлой неделей, когда я места себе не находил. Не уверен, насколько повлияли мои занятия, но очень рад))

анон-левел-апер

Отредактировано (2021-06-22 09:03:15)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Вчера почти не было времени заниматься, потратил 35 минут на понимание задания (среднее, массивы и жадные алгоритмы) + наброски идей как решать. Шло туго.
Задача: дана строка из 0 и 1, каждый элемент - это ящик, в котором лежит шар (1) или не лежит шар(0). Надо вывести массив, в котором каждый элемент с индексом i представляет собой число шагов, которые нужны для того, чтобы перенести все шары в ящик i. За один раз можно перенести только один шар и в одном ящике может быть больше одного шара за раз.

Бывают задачи, на которые смотришь и у тебя нет идей как решать. Совсем нет. Ты понимаешь, что надо сделать, но от тебя ускользает основная идея, ты видишь лишь её части, но не хватает будто бы связующего звена.

▼Решение⬍

    Для каждого ящика посчитать, сколько от него слева и справа есть шаров, и сколько надо движений, чтобы переложить все шары справа и слева в этот ящик (справа + слева).

    Завести массив-ответ размером с исходный массив и заполнить нулями. Сделать первый проход по массиву слева направо и для всех ящиков (исключая крайний левый), на каждом шаге проверять, есть ли шар. Если шар есть, к специально созданной переменной (первая, изначально равно 0) добавляем единицу.  Тут же в цикле считать, сколько надо движений, чтобы переложить все эти шары слева от текущего ящика в этот самый ящик: используется вторая переменная, к значению которой каждый шаг добавляется текущее число шаров слева (значение первой переменной) - ведь мы переносим каждый ход все эти шары. В массиве-ответе в элемент с индексом, равным переменной цикла, записать значение второй переменной - число действий.

    Сделать второй проход - справа налево и посчитать всё то же самое для каждого ящика, только справа. В этот раз в массив-ответ к каждому элементу прибавить количество движений, необходимое для переноски всех шаров справа (потому что число движений для переноски всех шаров слева уже есть).

Например, исходный массив [0, 0, 1, 0, 1, 1]
Число шаров слева (как будет изменяться значение переменной, где мы храним число шаров) для каждого элемента: 0 0 0 1 1 2
Число шаров справа (как будет изменяться значение переменной, где мы храним число шаров) для каждого элемента: 3 3 2 2 1 0
Сколько движений, чтобы переложить все шары справа: 0 0 0 1 2 4
Сколько движений, чтобы переложить все шары слева: 11 8 5 3 1 0
Сколько движений всего, чтобы перенести шары с обеих сторон: 11 8 5 4 3 4

Излагаю решение своими словами, надеюсь, что мозгу это поможет закрепить концепцию, хех.

Зато вторую задачу, тоже среднюю, на массив и хэш-таблицы, с ходу решил минут за 15   

В итоге сегодня потратил 1 час 45 минут.

Сегодня говорили с другим рекрутёром: набирается новая команда, нужен специфический опыт, которого у меня пока нет, но есть похожий. Вот как найдут этого командообразующего человека с опытом, вот тогда мне позвонят снова.

анон-левел-апер

Отредактировано (2021-06-25 08:25:16)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Средняя задача на жадные алгоритмы, массивы и матрицы за 50 минут. До решения додумался с первого раза, без открывания подсказок, это радует.

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

Не знаю, стоит ли упрощать себе жизнь используя вместо куска собственноручно написанного кода всяческие функции типа zip(*array) и разные структуры данных из коллекций типа defaultdict, на всякий случай не использую - не на всех собеседованиях это одобряют, так что не буду лениться и терять сноровку, хех.

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

Ещё сегодня немного расхламлялись.

анон-левел-апер

Отредактировано (2021-06-25 08:26:10)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Вчера
Был день отпуска, с утра решал

1. Сколько в массиве есть непрерывных подмассивов, чья сумма равно заданному числу

▼Решение⬍

1. Brute force, два вложенных цикла для перебора всех возможных подмассивов и расчёт суммы для каждого подмассива отвалился по времени
2. Кумулятивная сумма массива, два вложенных цикла и вычитание по индексам вместо подсчёта суммы каждый раз - отвалилось по времени
3. Два вложенных цикла, два указателя на начало и конец подмассива - отвалилось по времени
4. Хэш-таблица, которая содержит значение кумулятивной суммы для каждого элемента как ключ, а значение ключа - сколь часто встречается эта кумулятивная сумма (начинаем ключи с 0, его значение - 1, потому что считать мы начинаем тоже с нуля).

Соль в том, что в цикле for на каждом шаге к счётчику подмассивов мы прибавляем значение ключа, равное следующему: из кумулятивной суммы для текущего элемента массива вычитаем заданное число - то есть если разность между числом и кумулятивной суммой нашлась в хэш-таблице, то это значит, что нашёлся один подмассив, чья сумма равно заданному числу (прибавляем 1 к счётчику подмассивов). Если нет, то прибавляем 0.
Обновляем кумулятивную сумму, добавляем в хэш-таблицу.
В итоге возвращаем счётчик подмассивов.
Прошло по времени.

2. Вернуть индексы двух чисел из массива, чья сумма равно заданному числу - лёгкая. Известно, что в массиве только два таких числа. Повторения одного числа не допускаются.

▼Решение⬍

Полный перебор за квадратичное время сразу выглядел плохой идеей, поэтому использовал хэш-таблицу.
Для каждого числа вычислял разность между ним и заданным числом - это ключ, значение - индекс текущего числа. Проверить для текущего числа в массиве, нет ли его среди ключей (вот эта вот недостающая разность заданного числа и уже встреченного в массиве ранее). Если число, которое есть эта недостающая разность есть в словаре, то вернуть его индекс и значение ключа, ключ - недостающая разность.

На первую потратил 2 с половиной часа  В оправдание скажу, что первые несколько решений не прошли из-за лимита времени. Жутко разболелась голова, две таблетки не помогли. Когда всё-таки решил, то понял, что теперь мне очень больно и медленно думать. Но чувство вины, что столько провозился и столько потратил времени на одну задачу, грызли. Тогда пошёл на компромисс - я решаю лёгкую задачу и отдыхаю. Решил вторую задачу за 4 минуты.
Отсюда выводы: 1) если совсем устал и плохо - отдохни и не мучайся чувством вины 2)на лёгкие задачи можно не смотреть вообще (как я и подозревал, хех), ничего полезного для себя не почерпну.
Зато радует, что так быстро смог решить лёгкую, потому что год - полтора назад я мог потратить минут 15-30 на такого уровня задачу. Прогресс!

После решения задач пошёл гулять на кладбище - оно довольно старое (конечно, не настолько старое, как я люблю, но уютное и попадаются интересные и красивые надгробия).
Потом вечером пошёл гулять с фотоаппаратом (пытаюсь вернуться к одному из хобби  ), пропустил почти весь свет, понял, что устал, натёр ноги, но фоточки вроде ничего.

Ел черешню, гамал в качестве отдыха.

Сегодня
С утра решил одну среднюю задачу, 1 час 27 семь минут. Оправдашка: самое очевидное, brute force решение не прошло по времени.
Дан массив чисел, индекс элемента - координата по оси x на двумерной шкале, значение элемента - координата на оси y. Надо представить, что эти координаты формируют собой контейнер, который можно заполнить водой. Надо найти максимальную площадь, которую можно заполнить водой (наклонять контейнер, если одна стенка выше другой, нельзя, т.е. заполняем водой до нижней границы). Массивы, два указателя, жадные алгоритмы.

▼Решение⬍

1 попытка: в двух циклах for, один вложен в другой, перебрать все возможные контейнеры. Хранить текущий максимум в переменной и обновлять по мере надобности. O(n^2), не прошло по времени.
2 попытка: один цикл while, два указателя, также храним текущий максимум. Рассчитываем максимум на каждом шаге: или это предыдущий максимум или новый (разность координат  умножить на минимальную высоту двух стен контейнера). Если левая стена меньше правой, то после проверки/обновления максимума увеличиваем левый указатель на единицу, иначе правый уменьшаем. Идея - рассчитать сначала контейнер на максимальной ширине, потом искать контейнер поуже, но повыше.

Сегодня, скорее всего, поедем к друзьям в гости.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Итак, средняя задача на массивы, хэш-таблицы, кумулятивную сумму и математику - 1 час 30 минут

▼Дан массив и число, вернуть True, если подмассив длиной как минимум в 2 элемента, чья сумма - множитель заданного числа, иначе False⬍

Итерироваться по массиву. На каждом шаге к кумулятивной сумме остатков от деления суммы элементов на заданное число прибавлять остаток от деления этой суммы сложенной со значением текущего элемента.
Коряво выразился, но уже пора спать, и я упорот, так что напишу кодом: cum_sum = (cum_sum + nums[iter]) % k)
В хэш-таблице хранить эти кумулятивно сложенные остатки от деления как ключи, а индексы соответствующих элементов массива как строки (первый ключ 0 (остаток от деления равен нулю) со значением -1): если на очередном шаге мы увидим, что такой уже есть, то проверим разность индексов (нам нужен подмассив длиной как минимум 2).
Тут и вступает в дело ключ 0 со значением -1: если сумма элементов является множителем (остаток от деления = 0), и длина подмассива больше 1, то возвращаем True.

Средняя задача на массивы, матрицы, сортировку - 1 час 30 минут

▼Дана матрица, отсортировать все её диагонали и вернуть отсортированную матрицу⬍

Определить все диагонали (слева направо), отсортировать их и вернуть. Всё просто.
1. Как получить элементы всех диагоналей? Тут я подвис надоооолго. Начал придумывать алгоритмы, понимал, что они громоздки и не работают, начинал заново. В итоге узнал трюк: Все ячейки в диагонали (i,j) имеют одинаковую разность, так что мы можем получить диагональ, используя разность i-j.

Например: исходная матрица [[3,3,1,1],[2,2,1,2],[1,1,1,2]].
Получаем диагонали (одинаковые цифры в матрице внизу - айди диагоналей):

        0 -1 -2 -3
        1 0 -1 -2
        2 1 0 -1

m - число строк, n - число столбцов
for x in range(m):
    for y in range(n):
        # get the elements of each diagonal and put them to mat_dict
        mat_dict[x - y].append(mat[x][y])

2. В хэш таблицу mat_dict записать айди диагонали как ключ и её элементы в массив-значение
3. Отсортировать массивы в обратном порядке
4. Для каждой отсортированной диагонали поместить её элементы обратно в матрицу и вернуть

Почти всю эту неделю болела голова, иногда так, что не помогали таблетки(( Чувствую усталость, понял, что триггерит от любых вопросов коллег в чате. Ещё и подготовка к релизу начинается - это значит, что будет несколько вех, над каждой из вех надо работать, и в конце недели вечером (лучше времени для такого и не найти!) выяснилось, что кое-что не работает 

Я недоволен тем, сколько времени уходит на решение задачи средней сложности и что далеко не сразу могу прийти к оптимальному решению - некоторые приёмы для меня новые, надеюсь, что со временем и опытом будет легче. А ещё я косноязычен

Меня расстраивает, что пока часто бывает так, что я смотрю на задачу и кроме самого элементарного brute force решения  мне в голову ничего не приходит (как с получением диагоналей матрицы) без нескольких подсказок или вообще полного разбора задачи в обсуждениях.

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

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

анон-левел-апер

Отредактировано (2021-07-02 09:27:45)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Матрицы, массивы, динамическое программирование, средний уровень: 1 час 37 минут  -_-

▼Матрица m на n, состоящая из 0 и 1, посчитать, сколько в ней квадратных подматриц, содержащих только единицы⬍

Создать вторую матрицу размером с исходную (или можно использовать исходную и делать in-place) - будет таблица для динамического программирования. Значение самой верхней строки и самого левого столбца такие же, как в исходной матрице.
Начиная с первой строки и первого столбца (если индексация с 0), в двух вложенных циклах для каждого элемента матрицы, если он равен единице,  (рассматривая его как правый нижний угол подматрицы) определять и записывать в таблицу ДП, какого размера  он формирует заполненный 1 квадрат с элементами вокруг себя (будучи правым нижним углом квадрата) - вверху, внизу и по диагонали слева сверху, если текущий элемент равен 1, иначе сразу записываем в таблицу для ДП ноль.
Как определять величину квадрата: 1 (значение текущего элемента матрицы) + минимальное значение из элементов вокруг (сверху, слева, по диагонали слева сверху)
        for x in range(1, m):
            for y in range(1, n):
                dp_table[x][y] = 1 + min(
                    dp_table[x - 1][y], dp_table[x][y - 1],
                    dp_table[x - 1][y - 1]
                )
Минимальное - потому что если где-то поблизости оказался ноль, то подматрицы из единиц не выйдет.

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

Для матрицы
0 1 1 1
1 1 1 1
0 1 1 1

ДП таблица будет выглядеть так:

0 1 1 1
1 1 2 2
0 1 2 3

После чего вернуть сумму всех значений из ДП таблицы - сколько всего квадратных подматриц, заполненных единицами (квадрат может иметь сторону, равную 1 - единичный элемент тоже представляет собой квадрат).

Для этого примера ответ будет 15:
10 квадратов со стороной длинной 1, 4 квадрата со стороной 2, 1 квадрат со стороной 3.

Вспомнил, как в питоне правильно создавать вложенные списки (список, чьи элементы - тоже списки), чтобы они не были одним и тем же списком в памяти (когда изменяешь в цикле первый или n-ный из таких списков, то при этом изменяются все списки): надо [[] for i in range(n)] вместо [[]] * n 

Мне надо подтянуть матрицы: отсутствие практики сказывается плохо.

анон-левел-апер

Отредактировано (2021-07-02 23:59:11)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Матрицы, массивы, динамическое программирование, средний уровень: 1 час 12 минут в общем. Где-то минут 15 ушло на решение, не учитывающее граничные кейсы (потому что вчера решал такую же задачку, сегодня решил закрепить понимание принципа),  потом добавил минут за 15-30 проверки для граничных кейсов (вырожденные матрицы, матрица из одного элемента), потом оптимизировал имплементацию.

▼Дана матрица, заполненная нулями и единицами. Найти площадь самого большого квадрата в матрице, заполненного только единицами⬍

Как и в прошлый раз, создаём ДП-таблицу, каждый элемент представляет собой размер квадрата от левого верхнего угла до правого нижнего угла подматрицы, и координаты элемента в ДП-таблице представляют собой координаты этого правого нижнего угла.
Завёл переменную, где хранить длину стороны максимального на данном шаге квадрата-подматрицы.
Два вложенных цикла, на каждом шаге рассчитываю рассчитываю величину новой подматрицы из единиц (если таковая есть), проверяю, не надо ли обновить максимум.
В конце возвращаю переменную, где хранится максимум, умноженную саму на себя.

Оптимизации:
1) Рассчитать граничные кейсы отдельно для матрицы из одного элемента, для вырожденных матриц, для матрицы размером 2 на 2, где единицы только в самом левом столбце и самой верхней строке.
2) Не рассчитывать отдельно граничные кейсы, использовать ДП таблицу (двумерный массив), на 1 строку и 1 столбец больше исходной матрицы, чтобы обращаться к левому столбцу и верхней строке в цикле как к [x - 1][y - 1]
3) Использовать одномерный массив для ДП таблицы (размером число столбцов + 1), потому что нам надо обращаться только к предыдущей строке в том же столбце (dp[y]), предыдущему столбцу в той же строке (dp[y - 1])  и элементу по диагонали в предыдущей строке и предыдущем столбце (dp[y] - значение правого нижнего угла с предыдущей итерации, диагональ налево вверх) - этот диагональный элемент храним в отдельной переменной и обновляем на каждой итерации.

Что интересно, вариант 3 с одномерной ДП таблицей потребляет 15.7 МВ памяти, а вариант 2 с двумерной (большей) ДП таблицей потребляет 15.6. Разница в Runtime 196 (3) против 220(2) миллисекунд.
Вариант 1 с отдельной обработкой граничных решений и двумерной ДП таблицей потребляет 15.7 МВ памяти, Runtime 208 миллисекунд.

Ещё разбирал задачу на бинарные деревья и динамическое программирование, чтобы она какое-то время поварилась в голове, а я бы решил её попозже, заняло 11 минут 30 секунд.

Вчера позанимался немного хобби, сделал прогресс, правда, не без фейла: две маленькие детали соединил не так, пришлось разъединять обратно. Хорошо, что вовремя заметил и не соединил более крепким способом. Вывод: не надо заниматься хобби поздним вечером, когда уже устал.

Купил карандаш для глаз, накрасился и рад.

анон-левел-апер

Отредактировано (2021-07-04 00:09:48)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Итак,
Первая неделя: 10 ч, 22 минуты - 5 задач решено, 1 разобрал на будущее. Среднее время решения где-то 1 час 42 минуты. Средний уровень
Вторая неделя: 8 ч, 12 минут - 7 задач решено, средний уровень, кроме одной лёгкой. Среднее время 1 час 21 минута (не учитывая лёгкую за 5 минут)
Третья неделя:  5 ч, 49 минут - 4 задачи, средний уровень. Среднее время 1 час 27 минут

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

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

После работы пошёл бегать, побегал минут 20 где-то, всё было нормально, как вдруг ощутил, что у меня словно закончилась энергия, и ноги трясутся и подгибаются, и я вот-вот упаду. До этого я бегал с января по май, потом был перерыв два месяца, теперь я возобновляю бег, и вот в первый же день - пожалуйста, хоть вроде и не особо напрягался, и не голодал. Затёк домой, плюхнулся на диван, оклемался, пошёл решать задачки.

Массивы, хэш-таблицы, средний уровень: 12 минут (вообще 9, но я решал в редакторе, а потом переписывал в редактор литкода).

▼Дан массив размера n, заполненный положительными целыми числами в диапазоне от 1 до n, каждое число встречается 1 или два раза, вывести массив, состоящий из чисел, встречающихся два раза⬍

Использовать хэш-таблицу, чтобы хранить частоту элементов в массиве, потом вывести те ключи этой таблицы, чьи значения равны 2.

Ещё вариант - использовать исходный массив как хэш-таблицу и замапить число на индекс в массиве (у ключа 0 будет значение 1 - то есть элемент со значением 1 замаплен на индекс 0 и так далее).  Если число встречается первый раз - присваиваем отрицательное значение элементу по этому индексу.
Начинаем с начала и проверяем, если индекс, на который замаплено значение текущего элемента, меньше нуля. Если меньше, добавляем число в результирующий массив. Иначе - делаем значение по этому индексу отрицательным (вот тут оно нам встретилось первый раз, поэтому мы используем проверку, как выше: если по индексу для этого элемента уже содержится отрицательное число, то есть текущее число уже встречалось, то оно - наш кандидат, который встречается два раза).

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

▼Дана строка, разбить её таким образом, чтобы каждый символ встречался не более чем в одной подстроке и вернуть массив с размерами подстрок⬍

Например: строка "ababcbacadefegdehijhklij", её можно разбить на 3 подстроки так, чтобы каждый символ встречался только в одной подстроке:  "ababcbaca", "defegde", "hijhklij". Длины этих подстрок (и ответ) - [9,7,8].

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

Создаём словарь, где ключи - буквы, а значения - индекс последнего вкрапления этой буквы в строку лол.
Заводим два указателя - левый и правый, оба пока равны нулю. Заводим пустой массив для ответа.
Идём по i, c in enumerate(s)  (i - индекс, с - значение в строке по этому индексу). На каждом шаге определяем границы подстроки: правый указатель равен максимум из своего текущего значения и индекса последнего вкрапления текущей буквы. Проверяем, равен ли правый указатель переменной цикла i - это означает, дошли ли мы до границ подстроки. Если равен, то в массив ответов добавляем (разность между правым и левым индексами + 1 - потому что индексация с нуля). Обновляем значение левого индекса - он равен переменная цикла + 1 - начинаем определять новую подстроку.

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

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

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

Утром говорили с другим рекрутёром из той же компании, которой не понравилось моё резюме, в этот раз была другая команда. Сошлись на том, что я напишу рекрутёру, как буду готов решить кодовую задачку (как я понял, на строки), которую они дадут. Я сказал, что мне надо бы пока время подготовиться, неделя-другая. Так что уделю внимание строкам.

Сначала болела голова, потом просто был разбитым и практически ни на что не пригодным. Запустил несколько джоб в Дженкинсе, помог коллеге-разработчику подебажить (аааа, как меня бесят разработчики, которые копипастят код, не разбираясь, как он работает, а потом у них закономерно не работает, тесты падают, они идут ко мне, и я им объясняю, почему, и помогаю пофиксить). Потом с другим разработчиком разбирались, почему не работает мой код - я не добавил нужный декоратор.

Лежал на диване на грани сна и яви.

Если было бы можно взять и отключить себя на сегодня, чтобы проснуться завтра утром, скипнуть этот день, я бы так сделал. Дурацкое состояние, когда ничего не хочется и ничего не интересно, и сам себе поднадоел, прокручиваешь в голове свои фейлы и не можешь остановиться. Чтобы отвлечься, сел решать задачки, а ведь ранее думал было пропустить сегодня.

Строки, стек, средний уровень - 5 минут

▼Дана строка, состоящая из круглых скобок, вернуть количество скобок, которое нужно, чтобы сделать строку сбалансированной, то есть каждой открывающей скобке соответствует закрывающая⬍

Завёл стек (массив, просто вытаскивал из него последний элемент), шёл по строке и складывал туда открывающие скобки. Если встречалась закрывающая скобка - выбрасывал с конца одну открывающую, таким образом уравновешивая разнонаправленные скобки. Потом вернул длину этого массива - сколько скобок осталось без пары. Можно добавить обработку кейса, когда массив-стек пуст, т. е. выбрасывать нечего, а открывающая скобка встретилась. Прошло с первого раза. Посмотрела предлагаемое решение к задаче - используют две переменные  и в них считают баланс, но мне показалось, что со стеком как-то понятнее.

Строки, 33 минуты ушло на то, чтобы понять, что мне надо разобрать определённый алгоритм.

▼Дана строка, дан паттерн. Удалить из строки все вхождения паттерна и вернуть результат. После удаления паттерна в строке может появится ещё паттерн из оставшихся символов⬍

Например: строка "daabcbaabcbc", паттерн= "abc".
Удалим первое вхождение паттерна, получим "dabaabcbc". Удалим второе вхождение - получим "dababc", удалим третье - получим "dab", и вот это "dab" и надо вернуть.

Потратил 33 минуты, потом полез в объяснения, понял, что нужно использовать алгоритм Кнута-Морриса-Пратта, отложил на будущее, потому что уже пора идти спать (оправдашка! я слежу за тобой, я проверю, что ты освоишь и применишь этот алгоритм!).

Ради интереса ввязался в июльский челлендж: каждый день решать по одной задаче, которые появляются в 12 ночи и которые надо решить в эти сутки
Массивы, уровень не указан, 5 минут

▼Дана матрица n на n, строки и столбцы отсортированы по возрастанию (в неубывающем порядке, уточнено там). Вернуть k-й самый маленький элемент в матрице⬍

Я посмотрел на описание, на пример, развернул матрицу в одномерный массив, отсортировал, вернул из отсортированного массива элемент с индексом [k - 1], прошло с первого раза 
Зато применил развёртывание матрицы matrix в массив одной строку (питонистам можно): [item for sub_matrix in matrix for item in sub_matrix]

Вот теперь повеселел, и настроение стало лучше. 

Быть может, перед сном напишу ещё пару строчек своего ориджа.

анон-левел-апер

Отредактировано (2021-07-08 08:54:01)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сегодня был почти таким же бесполезным на работе, хотя несколько тикетов можно будет закрыть по итогам сегодняшних обсуждений. Было много митингов (ненавижу митинги).
Один из коллег уходит работать в другое место, и была виртуальная прощальная вечеринка: менеджер заказала нам коктейли с доставкой каждому (ингридиенты и инструкции). Я выбрал безалкогольную версию, будучи уверен, что алкоголь (основной компонент, который ещё и создаёт объём, собственно) просто заменят чем-то другим, типа газировки. И что же? Оказалось, что безалкогольный по мнению той фирмы, что этим занимается, - это без алкоголя, а не с чем-то другим вместо него.
В итоге я заменил виски колой и было ничего так.

Выпнул себя побегать, решил в это раз не слишком напрягаться и больше слушать свой организм, побегал неплохо так, потом ещё погулял.

Сел решать задачи.
Динамическое программирование, бинарные деревья, поиск в глубину, средний уровень - 21 минута

▼Дано бинарное дерево, представляющее собой дома с количеством наживы в них, нельзя грабить два соседних дома (в данном случае родителя и детей одновременно). Вернуть максимальную сумму наживы после ограбления всех домов⬍

Рекурсия: если нода дерева пуста, возвращаем массив с двумя элементами, оба нули. Для левого и правого детей рекурсивно вызываем ту же функцию.
Возвращаем массив, состоящий из двух элементов: значение текущей ноды плюс второе значение массива, который вернулся слева + второе значение массива, который вернулся справа - первый элемент, максимум из значений массива, который вернулся слева + максимум из значений массива, который вернулся справа.
В первом элементе мы храним значение для того случая, когда грабим текущий дом и не грабим два соседних, т. е. потомков - берём значение этого дома и возвращаем значения для потомков левого и правого потомков, самих левого и правого потомков не грабим.
Во втором элементе храним значение для случай, когда не грабим текущий дом, тогда берём максимальные значения от ограбления его потомков и складываем их.

В вызывающей функции возвращаем максимум из двух элементов массива, который нам вернула рекурсивная функция.

Это была задача, которую я раньше сразу не осилил, а разобрал и оставил на будущее.

Строки, хэш-таблицы, сортировка, средний уровень - 19 минут

▼Дана строка из букв и цифр, вывести эту строку, отсортированную по частоте символов в ней⬍

Посчитать, сколько раз встречается каждый символ с использованием хэш-таблицы. Отсортировать хэш-таблицу по значению, сформировать новую строку, выведя каждый ключ столько раз, сколько он встречается, и так по убыванию частоты символов.

Динамическое программирование, массивы, попытка решить - 34 минуты

▼Дано два массива, вернуть длину самого большого общего подмассива⬍

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

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

анон-левел-апер

Отредактировано (2021-07-09 07:52:49)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

На работе шуршал бодрее нимношк.

Хотел пойти погулять после, но потом решил, что влом и гамал час. Потом сел решать задачи.

Строки, жадные алгоритмы, средний уровень - 1 час 12 минут

▼Дана строка, прсдатвляющая собой целое число. Найти минимальное количество deci-binary чисел, которые бы суммировались до этого числа. deci-binary числа - десятичные числа, состоящие из нулей и единиц, при этом первая цифра числа только 1. Для n = "32" ответ будет 3 (10 + 11 + 11 = 32), для n = "82734" ответ будет 8⬍

Long story short: минимальное число deci-binary чисел равно максимальной цифре данного числа.

Объяснение: допустим, нам нужно x deci-binary чисел, чтобы получить в сумме данное число. Чтобы получить сумму x deci-binary чисел в i-том месте равной цифре d в исходном числе, у нас должно быть ровно d deci-binary чисел среди их количества x, имеющих 1 в позиции i.
Таким образом, минимальное количество deci-binary чисел, нужных, чтобы получить в сумме исходное число равно значению максимальной цифры в числе.

Подсказки были такие: посчитать количество единиц для каждой отдельной цифры числа, потом объединять полученные значения (подсказка скорее запутала).

Полез разбирать и понимать решение.

Понять на примере 82734:

Расписываем все единицы для каждой цифры числа, сверху вниз: имеет значение позиция цифры в числе (индекс в строке в данном случае). 
8 2 7 3 4
1 1 1 1 1
1 1 1 1 1
1 0 1 1 1
1 0 1 0 1
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 0 0 0

Восемь единиц для первой цифры числа, равной 8 (вот поэтому ответ и равен максимальной цифре числа), две единицы (и нули!) для второй цифры числа, равной 2, и так далее.
Получилось 8 чисел длиной 5 цифр (длина исходного числа).

Складываем полученные числа (8 чисел длиной 5) и получаем исходное число. 11111 + 11111 + 10111 + 10101 + 10100 + 10100 + 10100 + 10000 = 82734

Массивы, динамическое программирование (ежедневный челлендж) - 55 минут

▼Найти длину самой длинной возрастающей подпоследовательности в массиве целых чисел⬍

Завести одномерный массив, инициализировать единицами, создать счётчик длин, равный пока 1. Вложенные циклы: во внешнем (i) идём от 1 до конца массива, во внутреннем(j) от 0 до значения переменной внешнего цикла.
Смотрим на каждом шаге, есть ли возрастающая подпоследовательность (если элемент массива с индексом i больше элемента с индексом j и при этом значение таблицы в i меньше, чем 1 + значение в j), в значение таблицы пишем длину найденной подпоследовательности (значение таблицы в i = 1 + значение таблицы в j).
Счётчику длин присваиваем максимум из (его значения и длины найденной подпоследовательности).

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

анон-левел-апер

Отредактировано (2021-07-10 09:49:08)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Подпишусь, мой лвл недотягивает (в какой-то момент не вдупляю ни задачи, ни решения)), но интересно и мотивирующе. Когда анон растет над собой - Терпения и настойчивости тебе))
(желающий в лвл-ап анон, который не может осознать режим в работа +2(3/4) часа учебы после)