там чувак прямо образцово-показательное интервью показал

Кстати, задачка из популярного видоса "как мы собеседуем в гугле" — https://www.youtube.com/watch?v=XKu_SEDAykw

Оу

Ой

Как-то не ловко вышло сегодня

Сел я значит как обычно тупить

Тратить 2-3 часа на Литкод

Сделал первое попавщееся в голову решение (ну минут 20-30 думал)

И Accepted

Без психов, непонятного поведения и ошибок...

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

Ладно, жду когда закончит кто-нибудь (@vitkarpov @KlenZeleny ?) и попрошу сделать код ревью или предложит более элегантное решение

А то я в шоке до сих пор

Ладно, жду когда закончит кто-нибудь (@vitkarpov @KlenZeleny ?) и попрошу сделать код ревью или предложит более элегантное решение

👍 я ещё не смотрел что там, напишу тогда, любопытно

Ладно, жду когда закончит кто-нибудь (@vitkarpov @KlenZeleny ?) и попрошу сделать код ревью или предложит более элегантное решение

Сделал. Решал через стек, причём даны векторы и удобно с ними работать сразу как со стеками, снимая элементы с конца, а потом просто развернуть ответ. В итоге, время O(N + M) и память O(1) если не считать вектор под ответ (иначе тоже `O(N+M)`)

@Glazomer47 code review, pls, https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11

Кстати, в последнее время работаю строго по помодоро и заметил реальный прогресс! Прямо вот эти магические 25 минут таймера заставляются сконцентрироваться 😄

Конкретно вот эту задачу решил за 20 минут: от момента как увидел условие до момента как сдал. Для меня это очень быстро, обычно я намного дольше сижу! И вот как показывает практика с таймером — как раз потому что много отвлекаюсь.

Конкретно вот эту задачу решил за 20 минут: от момента как увидел условие до момента как сдал. Для меня это очень быстро, обычно я намного дольше сижу! И вот как показывает практика с таймером — как раз потому что много отвлекаюсь.

Это первый раз так быстро или уже закономерность?

Это первый раз так быстро или уже закономерность?

Зависит от задачи, конечно. Прямо за 20 минут целиком это первый, да.

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

@Glazomer47 code review, pls, https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11

https://pastebin.com/btGnjyG1

@Glazomer47 code review, pls, https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11

Красивее чем у меня код

Читабельнее в разы

Ну, в 2-3 раза

Я повторяю код

Когда этого можно не делать

Понял в чем моя проблема

Красивее чем у меня код

Вообще сейчас посмотрел и понял, что наверное зря упёрся в стеки — можно реально двумя указателями от конца пройтись и не портить исходные данные 😄

Перемудрил слегка.

Вообще сейчас посмотрел и понял, что наверное зря упёрся в стеки — можно реально двумя указателями от конца пройтись и не портить исходные данные 😄

Ага

Меня бесяц итераторы в плюсах

Они спрогие капец...

С конца нормально не прокрутишь

Вообще сейчас посмотрел и понял, что наверное зря упёрся в стеки — можно реально двумя указателями от конца пройтись и не портить исходные данные 😄

https://pastebin.com/NF1aFew3

С конца нормально не прокрутишь

ну, rbegin/rend, по идее, должны так же работать

но с итераторами в целом надо быть осторожным, как бы не инвалидировалось чего

ну, rbegin/rend, по идее, должны так же работать

Такой магии не знаю еще 🤣

но с итераторами в целом надо быть осторожным, как бы не инвалидировалось чего

Всм?

@Glazomer47 code review, pls, https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11

Это секретная репа?!

Или так можно только с gist делать

Или так можно только с gist делать

ага, только с gist

ну, если нет приватного репо на GitHub

Всм?

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

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

А, я не понял что значит инвалидация

для этого в документации к контейнерам надо смотреть гарантируется ли неинвалидация итератора или нет

Кстати с итераторами и листами может не может быть инвалидации

Но может быть ошибка

Если уничтожить элемент

ага. классический пример это когда ты итерируешься по контейнеру и делаешь erase в том же самом цикле

и будет потом работать через раз

Но до сих пор сижу думаю над O(N)

Булев массив длины target+1

Булев массив длины target+1

А, я уже решил

Через Словарь

Через Словарь

Или так

https://leetcode.com/problems/interval-list-intersections/discuss/647641/C-simple-O(n)-solution

https://leetcode.com/problems/interval-list-intersections/discuss/647641/C-simple-O(n)-solution

Тоже самое что и у Виктора

Только if какой-то страшный

Тоже самое что и у Виктора

Не смотрел решение

@Glazomer47 code review, pls, https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11

.

https://pastebin.com/NF1aFew3

Это я переделал его

Тоже самое что и у Виктора

Не совсем, скорее как у тебя, с указателями. Я там ещё снимал элементы со стека.

Только if какой-то страшный

В if проверка на то, что начало одного интервала находится внутри другого интервала

В if проверка на то, что начало одного интервала находится внутри другого интервала

Ну я понял

А у вас как?

https://pastebin.com/NF1aFew3

Просто читается хуже чем

А у вас как?

Да абсолютно так же

Я сделал через индексы

В if проверка на то, что начало одного интервала находится внутри другого интервала

хм, а зачем она такая сложная? у меня аналогичная проверка вот такая: https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11#file-interval-intersection-cpp-L13

А почему reverse в конце?

А почему reverse в конце?

а я с конца иду

А почему reverse в конце?

Это Виктор на скору руку сделал

хм, а зачем она такая сложная? у меня аналогичная проверка вот такая: https://gist.github.com/vitkarpov/ebd1541bf5deb9d9f8fab9416621ff11#file-interval-intersection-cpp-L13

Да я наспех сделал, прошло с первого раза. Не оптимизировал даже

Он решил как можно быстрее

Но не сразу до этого дошел

Да я наспех сделал, прошло с первого раза. Не оптимизировал даже

У нас у всех так)

Сначала думал про кучу ифоф

Это Виктор на скору руку сделал

да не, всё верно. я ж с конца иду, поэтому надо reverse 🙂

Сначала думал про кучу ифоф

+

Как обычно, щас wrong answerвылезет, буду в голове дебажить

А тут неожиданно сразу accepted