Реальное Собеседование Data Science в VK | АЛГОРИТМЫ
ฝัง
- เผยแพร่เมื่อ 2 มิ.ย. 2024
- Сегодня я прохожу собеседование в VK, алгоритмическая секция. Смотри это видео, чтобы узнать, какие вопросы мне задавали.
🐳 Следи за новостями: t.me/gernar228/ - новости, анонсы, бесплатный контент
🍑 Приватный телеграм: t.me/gernar228_bot/ - весь движ тут: сообщество, собесы, мои личные консультации и другой эксклюзивный контент!
⬆️ Boosty больше недоступен, всё переехало в телеграм ⬆️
Полная версия: • (full) Собес ВК
00:00 Начало
00:48 Первая задача
01:30 Вторая задача
04:05 Решение второй задачи
09:40 Советы
11:34 Конец - วิทยาศาสตร์และเทคโนโลยี
Спасибо за контент!_
Похожую задачку как-то дали в ДЗ в школе нетология, весь вечер блин убил)) Да и лямбда функции, множества, циклы, функции, всё вот это было.
Классный алгоритм. Не представляю, как ты во время интервью это придумал. Гений
У меня вопрос по второму заданию.
Могу ли я создать (generate) все возможные подстроки из заданной строки, даже с повторяющимися значениями, без изменения порядка. Потом, найти все возможные подстроки максимальной длины с неповторяющимися значениями.
будет ли такой подход правильным? заранее спасибо
думаю, такое решение не примут, потому что оно по сложности и по памяти невероятно затратное. А тебе нужен самый оптимальный алгоритм. Попробуй прикинуть какая сложность у твоего по времени и памяти у твоего алгоритма.
Твоë решение второй задачи имеет асимптотику по времени o(n*n). Чтобы было o(n), нужно при нахождении присутствующего в множестве пройденных символов убрать все символы от начала выбранной подстроки до вхождения в неë этого символа включительно и продолжить цикл считая началом подстроки символ следующий за последним удалëнным. То есть будет два указателя: один впереди, другой сзади подтягивается и в хешсете символы между ними включительно. Словарь здесь не нужен.
красавчик
где узнать про техники решения алгозадач
Есть классное решение второй задачки с помощью функции префикса для вычисления подстрок (вида z функций)
преф. функция тут оверкилл, конечно) К тому же реализация за линию пишется не тривиально
А это 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 не является линейным временем?
Вторая задача не 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 для индексов. Можно ли считать это константой при определении асимптотики?! Слишком уж большая константа.
А позвали на следующей этап?)
да
@@gernar228 По-моему у них несколько этапов, сам слился на ML дизайне(
@@gernar228 Удачи на следующем
А какой у тебя ник в ods?
Такой же
🐳 Следи за новостями: t.me/gernar228/ - новости, анонсы, бесплатный контент
🍑 Приватный телеграм: t.me/gernar228_bot/ - весь движ тут: сообщество, собесы, мои личные консультации и другой эксклюзивный контент!
⬆ Boosty больше недоступен, всё переехало в телеграм ⬆
• Полная версия: th-cam.com/video/h_7oC_KY13o/w-d-xo.htmlsi=Z1NYf-Nhci0Y6YPW
чет прям задача со строками похожа больно на 24 задание из егэ по информатике гробового типа
Егэ гробового типа - это когда если не сдал, то посылают америнские беспилотники сачком ловить?
да, всё видео об этом думал 😂😂
Да ладно, это выполнимая, тем более, что тебя готовят к этому)
это позиция мидла была ?
Прикольная задача. Легкая, если в целом понимать как такие задачи решать. Я почему-то сразу подумал о методе 2 указателей и проходе по строке с добавлением в хэш-мапу. Соответственно, если встречаем повторяющийся элемент (в хэш-мапе у нас уже у этого элемента значение 1) - просто идем вторым указателем до этого элемента (параллельно исключая из хэш-мапы другие неповторяющиеся элементы, которые встретятся) и начинает отсчет после него.
Единственное, я не совсем понял, зачем все это нужно на пайтоне. В том плане, что очевидно, что разные оптимизации обычно проводятся на других ЯП (не в обиду питонистам, но их язык очевидно нужен, чтобы как можно быстрее сделать что-то готовое, а не для того, чтобы он летал как ракета).
Алг задачи на всех языках одинаковые, и на всех языках они одинаково бесполезны на практике. Это проверка на задротство
@@gernar228 Ну так-то если заниматься системным программированием, и делать что-то крайне требовательное к скорости - вполне может и пригодиться, как по мне.
если понимать как, то все становится просто и легко
Только пересоздание сета за линию работает, а не за константу
Можно было проверять, что нового элемента нет в словаре индексов или его индекс меньше, чем start
Пользуясь правом первого коммента, еще раз задам вопрос про Яндекс:
Про полученный грейд ниже ожиданий можно поподробнее? Тебе до финалов сказали грейд? Так вроде не делают
Поддерживаю вопрос) и спасибо за видео, интересно. Сам планирую в ВК собеситься.
Залетай в чатик, там подробней могу рассказать. Но в целом да, мне позвонили после третьего собеса и сказали что грейд получился ниже чем вакансия на которую я подавался. Алгоритмы и были финальным собесом, по сути.
@@gernar228 Скинь мне 1000, оформлю подписку сразу на 10 месяцев и залечу в чат. Честно-честно
это добровольно, просто там я отвечаю быстрее и чаще чем в комментах
А собеседующего случайно не Андреем зовут?))
хз
2.17, sliding window самый очевидный вариант ее решения. Так за O(n) спокойно можно