Реальное Собеседование Data Science в VK | АЛГОРИТМЫ
Вставка
- Опубліковано 15 чер 2024
- Сегодня я прохожу собеседование в VK, алгоритмическая секция. Смотри это видео, чтобы узнать, какие вопросы мне задавали.
🐳 Следи за новостями: t.me/gernar228/ - новости, анонсы, бесплатный контент
🍑 Приватный телеграм: t.me/gernar228_bot/ - весь движ тут: сообщество, собесы, мои личные консультации и другой эксклюзивный контент!
⬆️ Boosty больше недоступен, всё переехало в телеграм ⬆️
Полная версия: • (full) Собес ВК
00:00 Начало
00:48 Первая задача
01:30 Вторая задача
04:05 Решение второй задачи
09:40 Советы
11:34 Конец - Наука та технологія
🐳 Следи за новостями: t.me/gernar228/ - новости, анонсы, бесплатный контент
🍑 Приватный телеграм: t.me/gernar228_bot/ - весь движ тут: сообщество, собесы, мои личные консультации и другой эксклюзивный контент!
⬆ Boosty больше недоступен, всё переехало в телеграм ⬆
• Полная версия: ua-cam.com/video/h_7oC_KY13o/v-deo.htmlsi=Z1NYf-Nhci0Y6YPW
Похожую задачку как-то дали в ДЗ в школе нетология, весь вечер блин убил)) Да и лямбда функции, множества, циклы, функции, всё вот это было.
Спасибо за контент!_
Классный алгоритм. Не представляю, как ты во время интервью это придумал. Гений
Твоë решение второй задачи имеет асимптотику по времени o(n*n). Чтобы было o(n), нужно при нахождении присутствующего в множестве пройденных символов убрать все символы от начала выбранной подстроки до вхождения в неë этого символа включительно и продолжить цикл считая началом подстроки символ следующий за последним удалëнным. То есть будет два указателя: один впереди, другой сзади подтягивается и в хешсете символы между ними включительно. Словарь здесь не нужен.
красавчик
Есть классное решение второй задачки с помощью функции префикса для вычисления подстрок (вида z функций)
преф. функция тут оверкилл, конечно) К тому же реализация за линию пишется не тривиально
У меня вопрос по второму заданию.
Могу ли я создать (generate) все возможные подстроки из заданной строки, даже с повторяющимися значениями, без изменения порядка. Потом, найти все возможные подстроки максимальной длины с неповторяющимися значениями.
будет ли такой подход правильным? заранее спасибо
думаю, такое решение не примут, потому что оно по сложности и по памяти невероятно затратное. А тебе нужен самый оптимальный алгоритм. Попробуй прикинуть какая сложность у твоего по времени и памяти у твоего алгоритма.
где узнать про техники решения алгозадач
Прикольная задача. Легкая, если в целом понимать как такие задачи решать. Я почему-то сразу подумал о методе 2 указателей и проходе по строке с добавлением в хэш-мапу. Соответственно, если встречаем повторяющийся элемент (в хэш-мапе у нас уже у этого элемента значение 1) - просто идем вторым указателем до этого элемента (параллельно исключая из хэш-мапы другие неповторяющиеся элементы, которые встретятся) и начинает отсчет после него.
Единственное, я не совсем понял, зачем все это нужно на пайтоне. В том плане, что очевидно, что разные оптимизации обычно проводятся на других ЯП (не в обиду питонистам, но их язык очевидно нужен, чтобы как можно быстрее сделать что-то готовое, а не для того, чтобы он летал как ракета).
Алг задачи на всех языках одинаковые, и на всех языках они одинаково бесполезны на практике. Это проверка на задротство
@@gernar228 Ну так-то если заниматься системным программированием, и делать что-то крайне требовательное к скорости - вполне может и пригодиться, как по мне.
если понимать как, то все становится просто и легко
Кажется тут тупо очередью (указателями₽ можно вторую решить. Когда встретили повторяющийся символ, тупо идём слева и выкидываем все символы пока не выкинули повторяемый (который споава). Все. Длину не сложно смотреть. Количество выкидываний - линия. Количество добавлений - линия. Вот и все
а зачем нам что-то выкидывать? нужно подряд идущие
Вторая задача не O(N), вы там создаете set вовсе не константной длины для каждого факта повтора.
когда мы создаем сет, то символы, от с которых мы его создаем, уникальны. Значит их количество не больше чем число символов в алфавите.
Тут скорее загвоздка не в конечном алфавите, а в составлении множества. Для set(string[start: i]) нам нужно пройти (i - start) элементов. А это может быть хоть 1,2, так и N/4, N/2 и т.д. элементов. Поэтому создание множества действительно может стоить линию.
Однако промежутки (start: i) не пересекаются, поэтому больше чем O(N) в сумме не получится.
@@user-ri5qr9sb6j Размер set не будет больше размера используемого алфавита, так что не будет там N/2 и т.д., если N >> размера алфавита.
p.s. Был не прав, посыпаю голову пеплом :)
@@gernar228в UTF32 число различных символов тоже ограничено. Вообще в решениях часто ограничиваются типом int32 для индексов. Можно ли считать это константой при определении асимптотики?! Слишком уж большая константа.
чет прям задача со строками похожа больно на 24 задание из егэ по информатике гробового типа
Егэ гробового типа - это когда если не сдал, то посылают америнские беспилотники сачком ловить?
да, всё видео об этом думал 😂😂
Да ладно, это выполнимая, тем более, что тебя готовят к этому)
А позвали на следующей этап?)
да
@@gernar228 По-моему у них несколько этапов, сам слился на ML дизайне(
@@gernar228 Удачи на следующем
А это VK, который раньше был Mail ru или VK, которая соц сеть?
Там много отделов, я так и не понял куда я собесился
Вопрос: почему сложность О(n), если функция мах в цикле также имеет сложность О(n)? Т.е. сложность Вашего решения О(n**2)?)
max между двумя числами это O(1). Ты путаешь с функцией поиска максимального элемента в массиве
Согласен с Вами)
Смутило название переменной max_arr поначалу
Сейчас увидел, что дальше сравнивается длина двух подстрок)
@@gernar228 и все же внутри цикла string[start:i] тоже имеет O(n). Для строки: [длинная_уникальная_строка]*2 в итоге будет порядка n^2/2 обращений ко всем символам
@@gernar228 В общем спасает конечность алфавита) Сложность предложенного решения - O(k*(n - k)), где k - длина алфивита
Разве О(k*(n-k)) при константном k не является линейным временем?
стоит ли идти в дата сайнс?
Только пересоздание сета за линию работает, а не за константу
Можно было проверять, что нового элемента нет в словаре индексов или его индекс меньше, чем start
Пользуясь правом первого коммента, еще раз задам вопрос про Яндекс:
Про полученный грейд ниже ожиданий можно поподробнее? Тебе до финалов сказали грейд? Так вроде не делают
Поддерживаю вопрос) и спасибо за видео, интересно. Сам планирую в ВК собеситься.
Залетай в чатик, там подробней могу рассказать. Но в целом да, мне позвонили после третьего собеса и сказали что грейд получился ниже чем вакансия на которую я подавался. Алгоритмы и были финальным собесом, по сути.
@@gernar228 Скинь мне 1000, оформлю подписку сразу на 10 месяцев и залечу в чат. Честно-честно
это добровольно, просто там я отвечаю быстрее и чаще чем в комментах
А какой у тебя ник в ods?
Такой же
это позиция мидла была ?
А собеседующего случайно не Андреем зовут?))
хз
2.17, sliding window самый очевидный вариант ее решения. Так за O(n) спокойно можно