Алгоритмы в Ai-Masters
AI Masters — это двухгодичный курс, который можно сравнить с ШАД. Обучение на курсах AI Masters действительно качественное, и это прекрасная возможность получить дополнительные полезные знания за два года.
Подробный пост о этапах поступление написано здесь.
В Ai-Masters алгоритмы встретите в основном на экзамене, и там будет всего одна задача. Эта задача значительно отличается от тех, с которыми можно столкнуться на собеседованиях или в ШАД (за исключением олимпиады ШАД, которую запустили в 2024 году). Также алгоритмы будут на собесе, но по опыту прошлых лет там простетские вопросы в духе: какие знаете сортировки, посчитайте сложность алгоритма.
Если у вас есть опыт участия в олимпиадах по программированию, то эти задачи покажутся вам несложными. Они примерно соответствуют второй задаче ВсОШ.
Мне кажется, что если у вас есть пробелы по математике, то лучше сосредоточиться именно на ней. Многие люди спокойно поступают не решая задачу по алгоритмам, но знать алгоритмы важно для того чтобы успешно закрыть курс по алгоритмам, так что ботать алгоритмы стоит, но не для того чтобы решить эту единственную задачу, а для того чтобы была база и заодно прокачать скилы для успешного прохождения собесов.
С примером и разбором одной из задач можно ознакомиться здесь.
И так как все таки подготовиться.
Как уже сказал вам необходима прочная база. Подготовка к алгоритмическому собеседованию или в ШАД отлично подходит. Подробнее про подготовку можно почитать здесь и здесь
Теперь готовимся к AI-Masters (кстати эта подготовка вам поможет к собесу и в какую-то хорошую HFT компанию).
Так как задачи по алгоритмам попадаются разные, то нужно перестраховаться и прокачать алгоритмы по следующим темам.
* Многомерное ДП и дп по подмножествам
* Дп по поддеревьям
* Теория игр
* Эйлерев путь
* Планарные графы, независимое множества (графы)
* Структуры данных (ДО, Фенвик, Sparce Table)
* Хеши
Также рекомендую решать региональные олимпиады школьников - первых двух задач будет достаточно.
Все темы выше проходят в стандартном курсе по алгоритмам, например в МФТИ, лекции которые можно найти в ютубе.
Задачи на эти темы спокойно можно найти в informatics.
AI Masters — это двухгодичный курс, который можно сравнить с ШАД. Обучение на курсах AI Masters действительно качественное, и это прекрасная возможность получить дополнительные полезные знания за два года.
Подробный пост о этапах поступление написано здесь.
В Ai-Masters алгоритмы встретите в основном на экзамене, и там будет всего одна задача. Эта задача значительно отличается от тех, с которыми можно столкнуться на собеседованиях или в ШАД (за исключением олимпиады ШАД, которую запустили в 2024 году). Также алгоритмы будут на собесе, но по опыту прошлых лет там простетские вопросы в духе: какие знаете сортировки, посчитайте сложность алгоритма.
Если у вас есть опыт участия в олимпиадах по программированию, то эти задачи покажутся вам несложными. Они примерно соответствуют второй задаче ВсОШ.
Мне кажется, что если у вас есть пробелы по математике, то лучше сосредоточиться именно на ней. Многие люди спокойно поступают не решая задачу по алгоритмам, но знать алгоритмы важно для того чтобы успешно закрыть курс по алгоритмам, так что ботать алгоритмы стоит, но не для того чтобы решить эту единственную задачу, а для того чтобы была база и заодно прокачать скилы для успешного прохождения собесов.
С примером и разбором одной из задач можно ознакомиться здесь.
И так как все таки подготовиться.
Как уже сказал вам необходима прочная база. Подготовка к алгоритмическому собеседованию или в ШАД отлично подходит. Подробнее про подготовку можно почитать здесь и здесь
Теперь готовимся к AI-Masters (кстати эта подготовка вам поможет к собесу и в какую-то хорошую HFT компанию).
Так как задачи по алгоритмам попадаются разные, то нужно перестраховаться и прокачать алгоритмы по следующим темам.
* Многомерное ДП и дп по подмножествам
* Дп по поддеревьям
* Теория игр
* Эйлерев путь
* Планарные графы, независимое множества (графы)
* Структуры данных (ДО, Фенвик, Sparce Table)
* Хеши
Также рекомендую решать региональные олимпиады школьников - первых двух задач будет достаточно.
Все темы выше проходят в стандартном курсе по алгоритмам, например в МФТИ, лекции которые можно найти в ютубе.
Задачи на эти темы спокойно можно найти в informatics.
🔥4❤2👍1
Задача Яндекса.
Обязательно реши эту задачу если идешь в Яндекс.
Не могу не поделится задачей, которую крутят уже пятый раз подряд.
Задача называется Permutation in String.
В задаче говорится, что дается две строки s1 и s2 и нужно вернуть true если в s2 существует подстрока, которая является перестановкой строки s1.
Единственное собеседующий скажет что в строках могут быть абсолютно любые символы (то есть не только латинские буквы)
Решение:
Первое решение, которое попросят улучшить:
Давайте в словаре d1 посчитаем то сколько раз встречается каждая буква в s1.
Теперь наша задача, найти такой i, что Count(s2[i, i + len(s1) - 1]) = d1.
Для этого мы могли бы хранить второй словарь d2 где будем хранить вхождения букв на подотрезке длины len(s1) и обновлять значения ключей (делаем +1 и -1 к буквам s[i] и s2[i - len(s1)] соответственно)
Сложность такого алгоритма O(n * min(len(s1), m) где m - количество различных букв в строках.
Вы могли подумать откуда тут произведение ?
Произведение возникает из за того что мы на каждом шагу сравниваем две хеш-тиблицы.
Второе решение:
Обойдемся только одной хеш таблицей, чтобы не сравнивать на каждом шаге две хеш таблицы как мы это делали выше.
Посчитаем словарь d1 также как и выше для строки s1.
Теперь проходится по строке s2 окошкой длины len(s1) и мы когда делаем -1 и +1 для букв s2[i] и s2[i - len(s1)] соответственно, таким образом храня в словаре разницу!
Когда значения какого-то ключа обнулилось мы должны удалить этот ключ.
Когда словарь становится пустым (то есть len(d1) == 0) мы нашли нужный подотрезок.
Сложность алгоритма O(n)
Код в комментариях.
Обязательно реши эту задачу если идешь в Яндекс.
Не могу не поделится задачей, которую крутят уже пятый раз подряд.
Задача называется Permutation in String.
В задаче говорится, что дается две строки s1 и s2 и нужно вернуть true если в s2 существует подстрока, которая является перестановкой строки s1.
Единственное собеседующий скажет что в строках могут быть абсолютно любые символы (то есть не только латинские буквы)
Решение:
Давайте в словаре d1 посчитаем то сколько раз встречается каждая буква в s1.
Теперь наша задача, найти такой i, что Count(s2[i, i + len(s1) - 1]) = d1.
Для этого мы могли бы хранить второй словарь d2 где будем хранить вхождения букв на подотрезке длины len(s1) и обновлять значения ключей (делаем +1 и -1 к буквам s[i] и s2[i - len(s1)] соответственно)
Сложность такого алгоритма O(n * min(len(s1), m) где m - количество различных букв в строках.
Вы могли подумать откуда тут произведение ?
Произведение возникает из за того что мы на каждом шагу сравниваем две хеш-тиблицы.
Второе решение:
Обойдемся только одной хеш таблицей, чтобы не сравнивать на каждом шаге две хеш таблицы как мы это делали выше.
Посчитаем словарь d1 также как и выше для строки s1.
Теперь проходится по строке s2 окошкой длины len(s1) и мы когда делаем -1 и +1 для букв s2[i] и s2[i - len(s1)] соответственно, таким образом храня в словаре разницу!
Когда значения какого-то ключа обнулилось мы должны удалить этот ключ.
Когда словарь становится пустым (то есть len(d1) == 0) мы нашли нужный подотрезок.
Сложность алгоритма O(n)
Код в комментариях.
🔥19👍4❤2👏1
Задача Яндекса.
Дается N пар чисел a_i, b_i.
Вы строите N отрезков, где концы i-того отрезка находятся в (a_i, 0) и (1, b_i).
Найти количество отрезков этого множества, которые не пересекаются с другими отрезками.
Например
a = [1, 2, 3, 4, 5]
b = [4, 5, 1, 5, 6]
Ответ 1
Только последний отрезок не пересекается.
Решение:
Давайте отсортируем отрезке по координате a_i.
Теперь подумаем, когда отрезок (a_i, 0), (1, b_i) пересекается с другим отрезком j.
У нас два варианта пересечения
1) a_j <= a_i and b_j >= b_i
2) a_j >= a_i and b_j <= b_i
Пусть мы в i-той позиции, так как мы отсортировали все по a нас интересует максимальный b_j. Максимальный b_j можно хранить в отдельной переменной во время обхода обновляя. Таким образом мы должны просто проверить правда ли max_b >= b_i.
Аналогично давайте пройдемся справа налево, но уже будем хранить минимальный b справа. Для каждой позиции i проверяем min_b <= b_i.
Асимптотика O(N logN).
Код в комментариях.
Дается N пар чисел a_i, b_i.
Вы строите N отрезков, где концы i-того отрезка находятся в (a_i, 0) и (1, b_i).
Найти количество отрезков этого множества, которые не пересекаются с другими отрезками.
Например
a = [1, 2, 3, 4, 5]
b = [4, 5, 1, 5, 6]
Ответ 1
Только последний отрезок не пересекается.
Решение:
Теперь подумаем, когда отрезок (a_i, 0), (1, b_i) пересекается с другим отрезком j.
У нас два варианта пересечения
1) a_j <= a_i and b_j >= b_i
2) a_j >= a_i and b_j <= b_i
Пусть мы в i-той позиции, так как мы отсортировали все по a нас интересует максимальный b_j. Максимальный b_j можно хранить в отдельной переменной во время обхода обновляя. Таким образом мы должны просто проверить правда ли max_b >= b_i.
Аналогично давайте пройдемся справа налево, но уже будем хранить минимальный b справа. Для каждой позиции i проверяем min_b <= b_i.
Асимптотика O(N logN).
Код в комментариях.
🔥10❤3🤔1
Академия Бэкенда Тинькофф
Бесплатная образовательная программу по бэкенд-разработке. Длительность курса -1.5 года.
Обучение будет проходить по 4 направлением.
Java, Golang, Python, Scala.
С программой Академии бэкенда можно ознакомиться здесь. Конкурировать с такой программой может только ШАД по направлению инфраструктура больших данных.
Чего только стоит "Компьютерные сети", "Асинхронный обмен сообщениями", "Балансировка нагрузки", SRE курс. Не каждый опытный разработчик знает такие технологии.
Первый семестр не такой крутой, а больше нацелен, чтобы сравнить всех по знаниям и дать хорошую базу в разработке.
Второй семестр действительно крутой на самостоятельное изучения, которых вы потратите много лет. А если вы хотите стать крутым разработчиком, то знания которые дают на втором семестре must have.
SRE курс - курс достаточно короткий, в этом плане курс ШАДа намного сильнее, но будем честны, знания в SRE курсы вы не можете спокойно получить в интернете. Очень мало практических заданий и материалов.
Также нужно понимать, что это Тинькофф и программа бесплатная, значит велик шанс столкнуться с некоторым количеством кринжа. Например, ручная проверка всех ДЗ: понятно, что кураторам никто особо не платит, у них своих дел куча, поэтому ревьюить особо не будут. Или например препод отказывается делать записи занятий, мол их должны посещать. Или не любит, когда к нему пишут в тг аккаунты без реальных имен и фамилий) Про порой мало качественный материал, наверное, и говорить не стоит: опять же у преподавателей особо мотивации нет, вдобавок на последние занятия никто обычно не ходит.
Кому подходит Академия ?
-Отлично подходит для тех кто уже работает бэкенд разработчиком и хочет быстро апгрейдить свои знания, и сильно повысить зарплату. Занятость спокойно позволяет совмещать учебу и работу.
-Для студентов вуза с плохим программированием. К сожалению во многих вузах нет курса по разработке... Академия является отличной возможностью найти хорошую работаю по окончанию универа.
-Для тех кто решил поменять стэк/направление.
Поступление.
-Заполнить анкету до 22 июля. Как заполнить смотрим здесь.
-Написать 4-5 часовой контест по алгоритмам. Кстати подготовиться к нему поможет наш курс по алгоритмам.
-Языковая секция: вам предложат практическое задание, которое нужно выполнить на языке программирования, выбранном для курса.
Пример 2023 года по алгоритмическому контесту. Задачи чуть легче чем отбор на стажировку.
Пример 2023 года языковой секции на GO.
Отбор действительно непростой. С одной стороны вы должны знать хорошо алгоритмы, а с другой уже иметь опыт в разработке. Конкуренция высокая. Только не переусердствуйте с анкетой, а то вдруг организаторы подумают, что вы слишком круты для них и уже все знаете, откажут (такие случаи были).
Но пробовать однозначно стоит!
Бесплатная образовательная программу по бэкенд-разработке. Длительность курса -1.5 года.
Обучение будет проходить по 4 направлением.
Java, Golang, Python, Scala.
С программой Академии бэкенда можно ознакомиться здесь. Конкурировать с такой программой может только ШАД по направлению инфраструктура больших данных.
Чего только стоит "Компьютерные сети", "Асинхронный обмен сообщениями", "Балансировка нагрузки", SRE курс. Не каждый опытный разработчик знает такие технологии.
Первый семестр не такой крутой, а больше нацелен, чтобы сравнить всех по знаниям и дать хорошую базу в разработке.
Второй семестр действительно крутой на самостоятельное изучения, которых вы потратите много лет. А если вы хотите стать крутым разработчиком, то знания которые дают на втором семестре must have.
SRE курс - курс достаточно короткий, в этом плане курс ШАДа намного сильнее, но будем честны, знания в SRE курсы вы не можете спокойно получить в интернете. Очень мало практических заданий и материалов.
Также нужно понимать, что это Тинькофф и программа бесплатная, значит велик шанс столкнуться с некоторым количеством кринжа. Например, ручная проверка всех ДЗ: понятно, что кураторам никто особо не платит, у них своих дел куча, поэтому ревьюить особо не будут. Или например препод отказывается делать записи занятий, мол их должны посещать. Или не любит, когда к нему пишут в тг аккаунты без реальных имен и фамилий) Про порой мало качественный материал, наверное, и говорить не стоит: опять же у преподавателей особо мотивации нет, вдобавок на последние занятия никто обычно не ходит.
Кому подходит Академия ?
-Отлично подходит для тех кто уже работает бэкенд разработчиком и хочет быстро апгрейдить свои знания, и сильно повысить зарплату. Занятость спокойно позволяет совмещать учебу и работу.
-Для студентов вуза с плохим программированием. К сожалению во многих вузах нет курса по разработке... Академия является отличной возможностью найти хорошую работаю по окончанию универа.
-Для тех кто решил поменять стэк/направление.
Поступление.
-Заполнить анкету до 22 июля. Как заполнить смотрим здесь.
-Написать 4-5 часовой контест по алгоритмам. Кстати подготовиться к нему поможет наш курс по алгоритмам.
-Языковая секция: вам предложат практическое задание, которое нужно выполнить на языке программирования, выбранном для курса.
Пример 2023 года по алгоритмическому контесту. Задачи чуть легче чем отбор на стажировку.
Пример 2023 года языковой секции на GO.
Отбор действительно непростой. С одной стороны вы должны знать хорошо алгоритмы, а с другой уже иметь опыт в разработке. Конкуренция высокая. Только не переусердствуйте с анкетой, а то вдруг организаторы подумают, что вы слишком круты для них и уже все знаете, откажут (такие случаи были).
Но пробовать однозначно стоит!
👍13🔥4❤1
Таблица задач с алго собесов Яндекса со всей актуальной информацией: ссылка на leetcode, частота, процентов принятия.
Именно эти задачи будут подробно разобраны на нашем предстоящем курсе по алгоритмам (код + видео) как бонус!
Яндекс наверное самая популярная компания, где открыта куча вакансий от стажера до лида, потому будем активно развивать эту отдельную страничку на нашем сайте. Обязательно делитесь табличкой с друзьями, будем активно дополнять и расширять, мест в Яндексе хватит на всех!
Именно эти задачи будут подробно разобраны на нашем предстоящем курсе по алгоритмам (код + видео) как бонус!
Яндекс наверное самая популярная компания, где открыта куча вакансий от стажера до лида, потому будем активно развивать эту отдельную страничку на нашем сайте. Обязательно делитесь табличкой с друзьями, будем активно дополнять и расширять, мест в Яндексе хватит на всех!
❤13🔥5👍1
Задача Яндекса.
Дается строка, найти наибольший палиндромную подстроку.
Давно такая задача не встречалась на собесах, но недавно дали на собесе в яндекс.
Решение:
Наверное самое тупое решение - это зафиксировать длину подотрезка, пусть это число len. Теперь надо перебрать начало отрезка длины len, то есть зафиксировать [i, i + len - 1]. После нужно проверить правда ли этот подотрезок палиндром. Такое решение займет O(n^3) времени.
Скорее всего после такого решения вас не позовут дальше.....
Теперь обсудим решение, которое примут.
Переберем длину подотрезка len, после переберем начало подотрезка.
То есть зафиксировав len и i, мы получим отрезок [i, i + len - 1]. Остается вопрос, а как узнать правда ли подотрезок палиндром.
Во первых необходимо, что буквы s[i] и s[i + len - 1] были равны (иначе подотрезок точно не палиндром)
Во вторых нам важно чтобы подотрезок [i + 1, i + len - 2] был палиндром.
Если мы рассматриваем подотрезки по возрастанию длин (то есть по len), то по факту информацию о том, что подотрезок [i + 1, i + len - 2] является палиндромом, мы уже давно посчитали.
Пусть dp[l][r] = 1 если отрезок [l, r] палиндром.
В таком случае мы говорим, что dp[i][i + len - 1] = 1, если s[i] == s[i + len - 1] и dp[i + 1][i + len - 2] = 1.
Время работы алгоритма O(n^2).
Код в комментариях.
Эту задачу видел в Yandex Leetcode. Так что, если вы готовитесь к собеседованию, то имеет смысл прорешать Yandex Leetcode.
Также мы запускаем два курса по алгоритмам.
Если задачи на БП, два указателя, одномерные дпшки для тебя простые, то на продвинутом курсе по алгоритмам мы прорешаем ~200 задач на БОР, ДП по поддеревьям, игры и стратегии, bit manipulation.....
Если ты новичок в алгоритмах и хочешь хорошенько подтянуть за лето алгоритмы то тебе стоит взять основной курс по алгоритмам.
Дается строка, найти наибольший палиндромную подстроку.
Давно такая задача не встречалась на собесах, но недавно дали на собесе в яндекс.
Решение:
Скорее всего после такого решения вас не позовут дальше.....
Теперь обсудим решение, которое примут.
Переберем длину подотрезка len, после переберем начало подотрезка.
То есть зафиксировав len и i, мы получим отрезок [i, i + len - 1]. Остается вопрос, а как узнать правда ли подотрезок палиндром.
Во первых необходимо, что буквы s[i] и s[i + len - 1] были равны (иначе подотрезок точно не палиндром)
Во вторых нам важно чтобы подотрезок [i + 1, i + len - 2] был палиндром.
Если мы рассматриваем подотрезки по возрастанию длин (то есть по len), то по факту информацию о том, что подотрезок [i + 1, i + len - 2] является палиндромом, мы уже давно посчитали.
Пусть dp[l][r] = 1 если отрезок [l, r] палиндром.
В таком случае мы говорим, что dp[i][i + len - 1] = 1, если s[i] == s[i + len - 1] и dp[i + 1][i + len - 2] = 1.
Код в комментариях.
Эту задачу видел в Yandex Leetcode. Так что, если вы готовитесь к собеседованию, то имеет смысл прорешать Yandex Leetcode.
Также мы запускаем два курса по алгоритмам.
Если задачи на БП, два указателя, одномерные дпшки для тебя простые, то на продвинутом курсе по алгоритмам мы прорешаем ~200 задач на БОР, ДП по поддеревьям, игры и стратегии, bit manipulation.....
Если ты новичок в алгоритмах и хочешь хорошенько подтянуть за лето алгоритмы то тебе стоит взять основной курс по алгоритмам.
❤14👍2👏1🤔1
Вот и задания на академию бэкенда Тинькофф! Конечно, в плане образовательного контента спорно, но участников академии активно хантят HRы на стажировки и позиции в штат, потому не упускаем еще одну возможность получить заветный оффер уже этой осенью😎😎
Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!
Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!
Т‑Образование
Образовательная программа Т-Академия: обучение разработке и аналитике
Вас ждет 1,5 года онлайн-обучения, наставничество от экспертов Т-Банка, лекции и домашние задания, реальные задачи и шанс попасть в команду Т-Банка
🔥26❤2
Продолжаем обновлять и расширять раздел алгоритмов на нашем сайте: добавили задачи с алго собесов VK group, Авито, обновили задачи Яндекса и добавили контесты с решениями!
Все для вас, товарищи, сохраняйте, пользуйтесь на здоровье и обязательно делитесь с друзьями такой годнотой!
А если вы хотите добавить задачи на сайт или поделиться тестовыми заданиями (на любую позцию), то пишите @vice22821, сочтемся!
Все для вас, товарищи, сохраняйте, пользуйтесь на здоровье и обязательно делитесь с друзьями такой годнотой!
А если вы хотите добавить задачи на сайт или поделиться тестовыми заданиями (на любую позцию), то пишите @vice22821, сочтемся!
❤7🆒1
Вот и разбор алгоритмов на Академию Бэкенда Тинькофф! Обязательно делимся с друзьями. Ждём 15 тыс просмотров на ютуб ролике и выкладываем матешу.
Смотрим! Смотрим! https://www.youtube.com/watch?v=xEgHBTy0BH0
Смотрим! Смотрим! https://www.youtube.com/watch?v=xEgHBTy0BH0
YouTube
Разбор алгоритмов на Академию Алгоритмов Тинькофф!!
Код и условия: https://news.1rj.ru/str/botalkaaa/36099
Подробней о курсах: https://news.1rj.ru/str/postypashki_old/1198
Подробней о курсах: https://news.1rj.ru/str/postypashki_old/1198
🔥9❤1
Задача бэкенд Тинькофф (Hard).
Представьте, что у вас есть матрица из 0 и 1 размера n * m, где n * m <= 1e6. В матрице на каждом столбце есть ровно один непрерывный отрезок из единичек.
Например:
0 1 1
0 0 1
1 0 0
За одну операцию вы можете выбрать отрезок из единиц (по столбцу) и переместить их наверх/вниз на один, если не выйдете за пределы массива.
Например я из примера выше могу получить за одну операцию
0 1 0
0 0 1
1 0 1
Расстановка является хорошей, если можно из каждой единицы добраться до каждой другой единицы двигаясь в соседние клетки по 4 сторонам.
Ваша задача за минимальное количество действий получить хорошую расстановку.
Решение:
Пусть, dp[i][j] - минимальное количество операций необходимое, чтобы получить хорошую расстановку для столбцов 1, 2, 3, ..., i, но так, чтобы отрезок из единиц на i-том столбце покрывал позицию (i, j).
Давайте научимся обновлять дпшку. Пусть на i том столбце единички изначально находятся в позициях [s, e] (У нас же единички - это непрерывный отрезок по каждому столбцу).
Как обновляется dp[i][j], если s <= j <= e ?
Конечно же через min(dp[i - 1][s], dp[i - 1][s + 1], ..., dp[i - 1][e])
Отлично, а как быть с остальными j, которые лежат вне отрезка [s, e] ?
Давайте начнем наш отрезок двигать вверх, то есть наш отрезок [s, e] переместиться в [s - 1, e - 1], потом в [s-2, e-2] и так далее. По факту мы ходим скользящим окном и нам надо быстро узнавать минимум на отрезке для dp[i - 1], например, когда отрезок переместился на [s-1, e-1] мы обновляем нашу дпшку через 1 + min(dp[i-1][s-1], dp[i-1][s], ..., dp[i-1][e-1]).
Задача сводится к тому, чтобы быстро находить минимум на в скользящем окне.
ДО - не рекомендуется писать, так как будет TL.
Монотонный стек или Sparce Table самое то!
Если хочешь научиться решать такие задачи то приходи на курсы Алгоритмы Хард, которые начнутся 28 июля.
Асимптотика алгоритма O(n*m)
Код в комментариях
Представьте, что у вас есть матрица из 0 и 1 размера n * m, где n * m <= 1e6. В матрице на каждом столбце есть ровно один непрерывный отрезок из единичек.
Например:
0 1 1
0 0 1
1 0 0
За одну операцию вы можете выбрать отрезок из единиц (по столбцу) и переместить их наверх/вниз на один, если не выйдете за пределы массива.
Например я из примера выше могу получить за одну операцию
0 1 0
0 0 1
1 0 1
Расстановка является хорошей, если можно из каждой единицы добраться до каждой другой единицы двигаясь в соседние клетки по 4 сторонам.
Ваша задача за минимальное количество действий получить хорошую расстановку.
Решение:
Давайте научимся обновлять дпшку. Пусть на i том столбце единички изначально находятся в позициях [s, e] (У нас же единички - это непрерывный отрезок по каждому столбцу).
Как обновляется dp[i][j], если s <= j <= e ?
Конечно же через min(dp[i - 1][s], dp[i - 1][s + 1], ..., dp[i - 1][e])
Отлично, а как быть с остальными j, которые лежат вне отрезка [s, e] ?
Давайте начнем наш отрезок двигать вверх, то есть наш отрезок [s, e] переместиться в [s - 1, e - 1], потом в [s-2, e-2] и так далее. По факту мы ходим скользящим окном и нам надо быстро узнавать минимум на отрезке для dp[i - 1], например, когда отрезок переместился на [s-1, e-1] мы обновляем нашу дпшку через 1 + min(dp[i-1][s-1], dp[i-1][s], ..., dp[i-1][e-1]).
Задача сводится к тому, чтобы быстро находить минимум на в скользящем окне.
ДО - не рекомендуется писать, так как будет TL.
Монотонный стек или Sparce Table самое то!
Если хочешь научиться решать такие задачи то приходи на курсы Алгоритмы Хард, которые начнутся 28 июля.
Асимптотика алгоритма O(n*m)
Код в комментариях
🔥16❤3👍1🤔1
от и возможность для школьников познакомиться с работой в IT! Открыт набор в онлайн-лагерь «IT-дайвинг» — бесплатную программу от VK Education для учеников 7-11 классов. Здесь можно будет узнать о востребованных цифровых направлениях — от ML и разработки до креатива и управления проектами. А еще участников ждет работа над кейсами в выбранном направлении, обратная связь и мастер-классы от экспертов VK. Чтобы попасть в программу, нужно зарегистрироваться в чат-боте до 11 августа.
❤4👍2
Вот и задания на все открытые финтех курсы Тинькофф! Конечно, в плане образовательного контента спорно, но участников академии активно хантят HRы на стажировки и позиции в штат, потому не упускаем еще одну возможность получить заветный оффер уже этой осенью😎😎
Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!
Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!
🔥17❤3
Полный цикл отбора в Яндекс (Бэкенд 2024)
Продолжаем сопровождать наших выпускников и радовать вас инсайдами, товарищи.
Вступительный контест
Подавался на бэкенд С++, сначала скинули ссылку на контест. Задания нашел тут, просто прорешал заранее и сдал. Первую задачу мне решил ГПТ. Вторая задача была на хэш-таблицу + строки. Третья задача была сортировка + префикс сумма. Четвертая задача была одной из самых сложных, но решалась через префикс суммы. Пятая задача была на алгоритм БОР.
Кстати, товарищи, на курсе бэкенд разработка вы найдете подробный разбор (видео + код) этих задач.
В ту же неделю пришло письмо с приглашением на собеседование, списались с HR по тг. HR оказался приятным, на все мои вопросы подробно отвечал и не игнорил.
Алгоритмическая секция 1
Задача 1: дается массив из 0 и 1. Нужно за один проход поставить все нули в начало массива. Задача баян, в группе выкладывали задачу.
Задача 2: дается массив 0 и 1. Найти длину максимального подотрезка, состоящего из 1, после удаления ровно одного нуля. Решил быстро, и в запасе оставалось еще 20 минут.
Собеседующий решил просто так не сидеть и дал 3 задачу.
Задача 3: дается строка, найти максимальную по длине подотрезок, состоящий не более чем из k различных букв. Тоже какая-то баянистая задача на два указателя...
Остается 5 минут, и собеседующий говорит: «Го, еще одну задачу, достаточно, чтобы ты рассказал идею».
Задача 4: дается массив чисел. Найти наибольший по длине подотрезок, что сумма чисел в этом подотрезке равно 0. Ну и я ему предлагаю решения с префикс-суммой и хеш-таблицей за O(1).
Алгоритмическая секция 2
Задача 1: Дается массив из 0 и 1. Найти такую позицию нуля, что расстояние до ближайшей единицы максимально возможное. Рассказываю решения за линию и пишу код.
Задача 2: Дается бинарное дерево поиска, проверить, что это дерево является сбалансированным.
Рассказываю линейное решение, пишу код, исправляю пару багов. Остается еще 15 минут, я 5 минут позадавал ему вопросов по компании, и на этом разошлись.
Алгоритмическая секция 3
Задача 1: Условие было длинное, единственное, что запомнил, что там были отрезки (как временные интервалы), которые были даны в отсортированном порядке, и нужно было написать бинпоиск)
Задача 2: Дается натуральное число n. Нужно представить число n в виде суммы квадратов. Написать программу, которая находит количество представлений числа n.
Если честно, был удивлен, что предложили такую задачу, так как она решается простой баянистой дпшкой за n*sqrt(n), к счастью, оказывается, это же решение от меня ожидали.
Приходит HR с обратной связью. Говорит, что теперь будут подбирать мне команды. Кидается 4 ссылки на команды, говорит, выбирай, что интересно, я сказал, что хочу во все попробовать. Мне начали по очереди ставить собесы в команды.
Собес 1
Пришел лид одной команды, сказал, что ему важно, чтобы хорошо знали ООП на С++.... Он начал спрашивать все по ООП, показывал примеры кодов и задавал, сколько раз какой-то объект скопируется и т. д.
В общем, собес состоял только из ООП.
Собес 2
Пришли собесить два парня, такие разговорчивые. Начали узнавать, чем занимался, есть ли у меня опыт по БД, Linux. Потом дали около алгоритмическую задачу, в которой нужно было использовать map и указатели.
Собес 3
Интервьюер Говорит, что в его команду нужен человек, который знает многопоточности. У меня от этого слова уже в глазах потемнело.... Потом он сказал, что понимает такие темы, скорее всего, стажеры не знают....
И начинает по поверхности многопоточности задавать вопросы, я, конечно же, ничего ему не отвечаю.
После он мне дает задачу и говорит: «Давайте попытаемся решить многопоточностью, есть у вас идеи?» Я говорю: «Нет», и собес на этом заканчивается.
Собес 4
Сходу мне дает задачу:
Поступают запросы вида:
+ x (Добавить число x в множество)
- x (Удалить число x из множества)
get min (вернуть минимальный элемент из множества)
get max (вернуть максимум из множества)
Такое решение нужно написать за линию. При этом в множестве могут быть повторы.
В итоге два приглашения и два отказа. Чисто хватило алгосов.
Продолжаем сопровождать наших выпускников и радовать вас инсайдами, товарищи.
Вступительный контест
Подавался на бэкенд С++, сначала скинули ссылку на контест. Задания нашел тут, просто прорешал заранее и сдал. Первую задачу мне решил ГПТ. Вторая задача была на хэш-таблицу + строки. Третья задача была сортировка + префикс сумма. Четвертая задача была одной из самых сложных, но решалась через префикс суммы. Пятая задача была на алгоритм БОР.
Кстати, товарищи, на курсе бэкенд разработка вы найдете подробный разбор (видео + код) этих задач.
В ту же неделю пришло письмо с приглашением на собеседование, списались с HR по тг. HR оказался приятным, на все мои вопросы подробно отвечал и не игнорил.
Алгоритмическая секция 1
Задача 1: дается массив из 0 и 1. Нужно за один проход поставить все нули в начало массива. Задача баян, в группе выкладывали задачу.
Задача 2: дается массив 0 и 1. Найти длину максимального подотрезка, состоящего из 1, после удаления ровно одного нуля. Решил быстро, и в запасе оставалось еще 20 минут.
Собеседующий решил просто так не сидеть и дал 3 задачу.
Задача 3: дается строка, найти максимальную по длине подотрезок, состоящий не более чем из k различных букв. Тоже какая-то баянистая задача на два указателя...
Остается 5 минут, и собеседующий говорит: «Го, еще одну задачу, достаточно, чтобы ты рассказал идею».
Задача 4: дается массив чисел. Найти наибольший по длине подотрезок, что сумма чисел в этом подотрезке равно 0. Ну и я ему предлагаю решения с префикс-суммой и хеш-таблицей за O(1).
Алгоритмическая секция 2
Задача 1: Дается массив из 0 и 1. Найти такую позицию нуля, что расстояние до ближайшей единицы максимально возможное. Рассказываю решения за линию и пишу код.
Задача 2: Дается бинарное дерево поиска, проверить, что это дерево является сбалансированным.
Рассказываю линейное решение, пишу код, исправляю пару багов. Остается еще 15 минут, я 5 минут позадавал ему вопросов по компании, и на этом разошлись.
Алгоритмическая секция 3
Задача 1: Условие было длинное, единственное, что запомнил, что там были отрезки (как временные интервалы), которые были даны в отсортированном порядке, и нужно было написать бинпоиск)
Задача 2: Дается натуральное число n. Нужно представить число n в виде суммы квадратов. Написать программу, которая находит количество представлений числа n.
Если честно, был удивлен, что предложили такую задачу, так как она решается простой баянистой дпшкой за n*sqrt(n), к счастью, оказывается, это же решение от меня ожидали.
Приходит HR с обратной связью. Говорит, что теперь будут подбирать мне команды. Кидается 4 ссылки на команды, говорит, выбирай, что интересно, я сказал, что хочу во все попробовать. Мне начали по очереди ставить собесы в команды.
Собес 1
Пришел лид одной команды, сказал, что ему важно, чтобы хорошо знали ООП на С++.... Он начал спрашивать все по ООП, показывал примеры кодов и задавал, сколько раз какой-то объект скопируется и т. д.
В общем, собес состоял только из ООП.
Собес 2
Пришли собесить два парня, такие разговорчивые. Начали узнавать, чем занимался, есть ли у меня опыт по БД, Linux. Потом дали около алгоритмическую задачу, в которой нужно было использовать map и указатели.
Собес 3
Интервьюер Говорит, что в его команду нужен человек, который знает многопоточности. У меня от этого слова уже в глазах потемнело.... Потом он сказал, что понимает такие темы, скорее всего, стажеры не знают....
И начинает по поверхности многопоточности задавать вопросы, я, конечно же, ничего ему не отвечаю.
После он мне дает задачу и говорит: «Давайте попытаемся решить многопоточностью, есть у вас идеи?» Я говорю: «Нет», и собес на этом заканчивается.
Собес 4
Сходу мне дает задачу:
Поступают запросы вида:
+ x (Добавить число x в множество)
- x (Удалить число x из множества)
get min (вернуть минимальный элемент из множества)
get max (вернуть максимум из множества)
Такое решение нужно написать за линию. При этом в множестве могут быть повторы.
В итоге два приглашения и два отказа. Чисто хватило алгосов.
👏18❤6👍5
Все задачи, которые встретились на собесе ШАДа 2024 года.
1) Дается массив/строка и число k. Найти максимальный по длине подотрезок в котором <=k различных элементов.
Решать нужно за O(n) а памятью O(min(k, количество различных букв)). Также могли спросить как работает словарь если использовали словарь.
2) Дается массив чисел. Вернуть true, если за один swap можно массив сделать отсортированным по возрастанию.
Очень жаль людей, которым попалась эта задача, так как некоторым попадались холявке, а эта я считаю сложной задачей для собеса, так как очень много подводных камней.
3) Даются две строки s, p. Найти все позиции в строке s, что подстрока s[i: i + len(p)] является анаграммой для строки p.
Решать за линию использую словарь. Некоторых спрашивали как работает словарь.
4) Даются два массива a, b. Длина массива b равно k. Найти количество подпоследовательностей массива a, что они равны массиву b.
То есть найти количество различных множеств (i1, i2, ..., ik), что a[i1] = b[0], a[i2] = b[1], ..., a[ik] = b[k-1]
-Решение за квадрат удовлетворит собеседующих.
Хотя-бы одна из этих задача будет и в следующем году, так что рекомендую разобрать все задачи если поступаешь в след году.
(Если вам попалась другая задача то поделитесь условием в комментариях)
1) Дается массив/строка и число k. Найти максимальный по длине подотрезок в котором <=k различных элементов.
Решать нужно за O(n) а памятью O(min(k, количество различных букв)). Также могли спросить как работает словарь если использовали словарь.
2) Дается массив чисел. Вернуть true, если за один swap можно массив сделать отсортированным по возрастанию.
Очень жаль людей, которым попалась эта задача, так как некоторым попадались холявке, а эта я считаю сложной задачей для собеса, так как очень много подводных камней.
3) Даются две строки s, p. Найти все позиции в строке s, что подстрока s[i: i + len(p)] является анаграммой для строки p.
Решать за линию использую словарь. Некоторых спрашивали как работает словарь.
4) Даются два массива a, b. Длина массива b равно k. Найти количество подпоследовательностей массива a, что они равны массиву b.
То есть найти количество различных множеств (i1, i2, ..., ik), что a[i1] = b[0], a[i2] = b[1], ..., a[ik] = b[k-1]
-Решение за квадрат удовлетворит собеседующих.
Хотя-бы одна из этих задача будет и в следующем году, так что рекомендую разобрать все задачи если поступаешь в след году.
(Если вам попалась другая задача то поделитесь условием в комментариях)
❤13🔥7👍1
Какие языки ботать Backend разработчику
Если вы начинающий специалист, то здесь есть некий парадокс.
По-хорошему нужно покопаться в C++ / C, ведь они довольно низкоуровневые и с помощью этих языков можно лучше понять, как устроена память, некоторые процессоры, concurrency, да и немного покопаться в операционных системах. На этих языках можно поперекладывать сырые байтики, поставлять туда ассемблерных вставок, повызывать всякие syscall’ы, почитать код Linux ядрa - часто хорошие учебные курсы тесно связаны с данной парой языков, а выучить какой-либо язык после плюсов не составит труда.
На этих языках было написано много классического и они полезны для изучения и понимания, но на рынке на них довольно сложно найти вакансии, а нормальные вакансии - в особенности. Это касается и стажировок: на плюсах их очень мало. На ум приходят лишь что-то специфичное в духе Kaspersky, Quantitative research. В каком-то сезоне в Тинькофф открыли лишь 5 вакансий. В тот же Яндекс можно попасть, зная лишь С++, но на чистых плюсах вакансий реально немного и поиск может затянуться. Нередко по моим наблюдениям и скромному мнению плюсы используются там, где они не нужны, где легче было бы написать проект на Go.
Также, разработчику когда-нибудь нужно будет настрочить что-нибудь на Python: какой-нибудь тупой скриптец или же написать на нем тесты. Так что знать его тоже полезно. Но на вакансии, где вы будете писать только на Питоне лучше не идти: на нем никогда не будут писаться какие-то серьезные проекты. Если проект и написан на питоне, то скорее всего это либо какой-нибудь вялый питон джанго, либо какой-нибудь легаси проект. На такое не ведитесь — будете ощущать себя макакой!
Как мне кажется один из самых лучший языков для изучения — это Go. Сейчас все новые и крутые проекты пишутся на нем, с ним не так сложно найти работу, как на плюсах, он прост и красив в изучении, также полезен, если разобраться в том, как он устроен изнутри.
Касаемо поиска работа, например, у меня была ученица с питерского ПМИ ФКН, у которой за плечами был лишь годовой курс плюсов. Она быстро прошла все собесы на стажера Яндекс, но долго ждала, когда поставят финальные собесы. По итогу HR увидела на ее гитхабе какой-то скромный пет проект, написанный на Go и предложила попробоваться, сказав "у нас здесь так много вакансий на Go". Затем девушку ждал тупой собес с руководителем и релокейт в Москву.
Также, можно попробовать что-то поклацать на Java. Язык также "старый" и буквально любая микроволновка была написана на нем, поэтому с ним вы точно не пропадете. Если наступят тяжелые времена, то можно начать писать на нем моды для майнкрафта.
Все же, нужно понимать, что язык — это лишь инструмент. Не нужно его выбирать, как жену — одну на всю жизнь! Главное — знания и понимания того, как устроен компьютер и распределенные бекенд системы, инженерия. Всему этому мы уделяем большое внимание на нашем курсе по бэкенд разработке, ведь в основном, языки похожи друг на друга, поэтому перейти на новый язык на хорошем уровне для хорошего инженера— это дело максимум недели, а для выпускников наших курсе— дело двух минут!
Если вы начинающий специалист, то здесь есть некий парадокс.
По-хорошему нужно покопаться в C++ / C, ведь они довольно низкоуровневые и с помощью этих языков можно лучше понять, как устроена память, некоторые процессоры, concurrency, да и немного покопаться в операционных системах. На этих языках можно поперекладывать сырые байтики, поставлять туда ассемблерных вставок, повызывать всякие syscall’ы, почитать код Linux ядрa - часто хорошие учебные курсы тесно связаны с данной парой языков, а выучить какой-либо язык после плюсов не составит труда.
На этих языках было написано много классического и они полезны для изучения и понимания, но на рынке на них довольно сложно найти вакансии, а нормальные вакансии - в особенности. Это касается и стажировок: на плюсах их очень мало. На ум приходят лишь что-то специфичное в духе Kaspersky, Quantitative research. В каком-то сезоне в Тинькофф открыли лишь 5 вакансий. В тот же Яндекс можно попасть, зная лишь С++, но на чистых плюсах вакансий реально немного и поиск может затянуться. Нередко по моим наблюдениям и скромному мнению плюсы используются там, где они не нужны, где легче было бы написать проект на Go.
Также, разработчику когда-нибудь нужно будет настрочить что-нибудь на Python: какой-нибудь тупой скриптец или же написать на нем тесты. Так что знать его тоже полезно. Но на вакансии, где вы будете писать только на Питоне лучше не идти: на нем никогда не будут писаться какие-то серьезные проекты. Если проект и написан на питоне, то скорее всего это либо какой-нибудь вялый питон джанго, либо какой-нибудь легаси проект. На такое не ведитесь — будете ощущать себя макакой!
Как мне кажется один из самых лучший языков для изучения — это Go. Сейчас все новые и крутые проекты пишутся на нем, с ним не так сложно найти работу, как на плюсах, он прост и красив в изучении, также полезен, если разобраться в том, как он устроен изнутри.
Касаемо поиска работа, например, у меня была ученица с питерского ПМИ ФКН, у которой за плечами был лишь годовой курс плюсов. Она быстро прошла все собесы на стажера Яндекс, но долго ждала, когда поставят финальные собесы. По итогу HR увидела на ее гитхабе какой-то скромный пет проект, написанный на Go и предложила попробоваться, сказав "у нас здесь так много вакансий на Go". Затем девушку ждал тупой собес с руководителем и релокейт в Москву.
Также, можно попробовать что-то поклацать на Java. Язык также "старый" и буквально любая микроволновка была написана на нем, поэтому с ним вы точно не пропадете. Если наступят тяжелые времена, то можно начать писать на нем моды для майнкрафта.
Все же, нужно понимать, что язык — это лишь инструмент. Не нужно его выбирать, как жену — одну на всю жизнь! Главное — знания и понимания того, как устроен компьютер и распределенные бекенд системы, инженерия. Всему этому мы уделяем большое внимание на нашем курсе по бэкенд разработке, ведь в основном, языки похожи друг на друга, поэтому перейти на новый язык на хорошем уровне для хорошего инженера— это дело максимум недели, а для выпускников наших курсе— дело двух минут!
❤13👍2🔥1😁1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Полный цикл отбора в Яндекс (МЛ 2024)
Сейчас студенты наших прошлых курсов под моим чутким сопровождением ломанулись проходить отборы в Яндекс, поэтому продолжаю радовать вас инсайдами и актуальными вопросами.
Далее представлен слегка отредактированный текст нашего выпускника.
Вступительный контест
Задания нашел тут, просто прорешал заранее и сдал, но зашли только 4 задачи. Первую и пятую мне решил ГПТ, только нужно было поправлять. Шестая просто посчитаит количество вхождений конкретных слов, а потом сортируем. Вторую мне скинул знакомый. Этого хватило, а знакомому хватило трех задач.
Кстати, товарищи, на курсе машинное обучение вы найдете подробный разбор (видео + код) этих задач.
МЛ секция
Сначала дали очень простую задачу на два указателя: в строке найти длину наибольшей подстроки, состоящей не более чем из двух уникальных символов. Я даже растерялся и начала копать не туда. Интервьюер предложил рассмотреть на примере и я сразу сообразил. Потом была простая задача по мл. Она разобрано здесь. И немного поспрашивали базу про классификацию, про линейную регрессию и регуляризацию.
Алгоритмическая секция
Первая задача: сжимать список целых чисел в диапазоны, которые там встречаются. Например, [1, 3, 2, 8, 11, 9, 0] -> "0-3, 8-9, 11".
Вторая задача: для множества точек на плоскости с целыми координатами определить есть ли у них вертикальная ось симметрии.
Для тех, кто в теме, задачи довольно баянистые. Их даже можно найти здесь.
Задачи я решил быстро и еще оставалось время, собеседующий дал мне задачу: написать бинарный поиск.
Дальше ждали собесы с командами.
Собес 1 (Яндекс Доставка)
Лайтово. Спросили просто про опыт, чем занимался. Поговорили про хакатоны, мои пет проекты. Мог только похвастаться кредитным скорингом и рекомендацией фильмов, которые я стырил и адаптировал по заветам Поступашек🙈😎.
Рассказали про себя и чем предстоит заниматься. Нужно выдумывать всякие фичи в катбуст, чтобы в реальном времени предсказывать приедет курьере или нет.
Собес 2 (Яндекс Деньги)
Здесь уже было потновато. Сначала попросили рассказать про случайный лес и градиентный бустинг, уточняющие вопросы по теории. Дальше попросили рассказать в общих чертах про АВ тесты и заострили внимание на ошибке 1го и 2го рода, p-value, мощность. Спрашивали про опыт работы в линуксе и написания скриптов на баше, попросили написать простой SQL запрос в блокнотике (есть табличка - фио, зарплата, отдел, надо вывести людей получающих минимальную зарплату в своем отделе). Затем был мл кейс: какие вопросы (из 100 имеющихся) задавать пользователю для идентификации мошенника. Чем-то подобным и предстоит заниматься в команде: по поведению пользователя на сайте и в приложении научиться понимать, бот это или нет. Поговорили про метрики классификации, а также про реализацию моего решения.
Вообще для подготовки к мл кейсам, помимо бота классической теории, советую смотреть всякие статьи на Хабре, конференции от Яндекса, Тинькофф и тд. Понятно, что в первую очередь смотреть выступления конкретной команды, с которой будет собес, и выступления левых команд, но в той же области.
Собес 3 (Яндекс Музыка)
Было много вопросов про метрики, какие знаю, физический смысл ROC-AUC. Дальше спросили: есть одна фича и один таргет, обучили регрессию, но весь тест лежит правее всего трейна— что выдаст линейная регрессия, KNN и случайный лес? И затем мл кейс, как сделать рекомендации плейлиста на сегодняшний день. Все основные повороты описаны здесь
В итоге три приглоса. На собесах ожидал хоть один вопрос по глубокому обучению, но его не было.
Сейчас студенты наших прошлых курсов под моим чутким сопровождением ломанулись проходить отборы в Яндекс, поэтому продолжаю радовать вас инсайдами и актуальными вопросами.
Далее представлен слегка отредактированный текст нашего выпускника.
Вступительный контест
Задания нашел тут, просто прорешал заранее и сдал, но зашли только 4 задачи. Первую и пятую мне решил ГПТ, только нужно было поправлять. Шестая просто посчитаит количество вхождений конкретных слов, а потом сортируем. Вторую мне скинул знакомый. Этого хватило, а знакомому хватило трех задач.
Кстати, товарищи, на курсе машинное обучение вы найдете подробный разбор (видео + код) этих задач.
МЛ секция
Сначала дали очень простую задачу на два указателя: в строке найти длину наибольшей подстроки, состоящей не более чем из двух уникальных символов. Я даже растерялся и начала копать не туда. Интервьюер предложил рассмотреть на примере и я сразу сообразил. Потом была простая задача по мл. Она разобрано здесь. И немного поспрашивали базу про классификацию, про линейную регрессию и регуляризацию.
Алгоритмическая секция
Первая задача: сжимать список целых чисел в диапазоны, которые там встречаются. Например, [1, 3, 2, 8, 11, 9, 0] -> "0-3, 8-9, 11".
Вторая задача: для множества точек на плоскости с целыми координатами определить есть ли у них вертикальная ось симметрии.
Для тех, кто в теме, задачи довольно баянистые. Их даже можно найти здесь.
Задачи я решил быстро и еще оставалось время, собеседующий дал мне задачу: написать бинарный поиск.
Дальше ждали собесы с командами.
Собес 1 (Яндекс Доставка)
Лайтово. Спросили просто про опыт, чем занимался. Поговорили про хакатоны, мои пет проекты. Мог только похвастаться кредитным скорингом и рекомендацией фильмов, которые я стырил и адаптировал по заветам Поступашек🙈😎.
Рассказали про себя и чем предстоит заниматься. Нужно выдумывать всякие фичи в катбуст, чтобы в реальном времени предсказывать приедет курьере или нет.
Собес 2 (Яндекс Деньги)
Здесь уже было потновато. Сначала попросили рассказать про случайный лес и градиентный бустинг, уточняющие вопросы по теории. Дальше попросили рассказать в общих чертах про АВ тесты и заострили внимание на ошибке 1го и 2го рода, p-value, мощность. Спрашивали про опыт работы в линуксе и написания скриптов на баше, попросили написать простой SQL запрос в блокнотике (есть табличка - фио, зарплата, отдел, надо вывести людей получающих минимальную зарплату в своем отделе). Затем был мл кейс: какие вопросы (из 100 имеющихся) задавать пользователю для идентификации мошенника. Чем-то подобным и предстоит заниматься в команде: по поведению пользователя на сайте и в приложении научиться понимать, бот это или нет. Поговорили про метрики классификации, а также про реализацию моего решения.
Вообще для подготовки к мл кейсам, помимо бота классической теории, советую смотреть всякие статьи на Хабре, конференции от Яндекса, Тинькофф и тд. Понятно, что в первую очередь смотреть выступления конкретной команды, с которой будет собес, и выступления левых команд, но в той же области.
Собес 3 (Яндекс Музыка)
Было много вопросов про метрики, какие знаю, физический смысл ROC-AUC. Дальше спросили: есть одна фича и один таргет, обучили регрессию, но весь тест лежит правее всего трейна— что выдаст линейная регрессия, KNN и случайный лес? И затем мл кейс, как сделать рекомендации плейлиста на сегодняшний день. Все основные повороты описаны здесь
В итоге три приглоса. На собесах ожидал хоть один вопрос по глубокому обучению, но его не было.
👍21❤8
Вот и разбор алгоритмов на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 5 тыс просмотров на ютуб ролике и выкладываем аналитику.
Смотрим! Смотрим! https://youtu.be/AdfjZ4u8GLg
Смотрим! Смотрим! https://youtu.be/AdfjZ4u8GLg
YouTube
Разбор алгоритмов на стажировку в Яндекс!!
Код и условия: https://news.1rj.ru/str/botalkaaa/38944
Как точно попасть на стажировку: https://news.1rj.ru/str/postypashki_old/1198
Как точно попасть на стажировку: https://news.1rj.ru/str/postypashki_old/1198
❤7🔥1🥱1
Задача для тех кто пишет на С++.
Это одна из задач, которая попалась во время собеседования.
Задача:
Вам приходят запросы двух видов.
1) Добавить в конец элемент 'x'
2) Удалить самое ранее добавленное число.
(По факту у нас очередь)
Вам можно пользоваться только одним std::vector. Но вам известно, что в любой момент времени в очереди могут находиться не более n чисел.
Имея один вектор размера не более n научитесь обрабатывать все запросы.
Решение:
Давайте создадим вектор a размера n. Будем циклически записывать числа в массив.
https://en.wikipedia.org/wiki/Circular_buffer
Вот такое вот решение господа
Думаю будем полезно всем кто будет проходить собес на С++.
Это одна из задач, которая попалась во время собеседования.
Задача:
Вам приходят запросы двух видов.
1) Добавить в конец элемент 'x'
2) Удалить самое ранее добавленное число.
(По факту у нас очередь)
Вам можно пользоваться только одним std::vector. Но вам известно, что в любой момент времени в очереди могут находиться не более n чисел.
Имея один вектор размера не более n научитесь обрабатывать все запросы.
Решение:
Вот такое вот решение господа
Думаю будем полезно всем кто будет проходить собес на С++.
🔥9👍3❤2👏1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Эти пет проекты должен сделать каждый ML специалист
Устроиться можно попасть и без проектов, но если у вас их нет, то мл кейсы будут решаться неуверенно и на финалах будете выглядеть слабее других. Никто не ждет гениального проекта с инфраструктурой— реализовать какие-то бейзлайны и понимать специфику задач уже достаточно для стажера и джуна.
Уже делали подобную подборку для аналитиков здесь, советую присмотреться.
1. Кредитный скоринг
Стоит ли давать кредит— довольно популярная задача и отличный выбор для новчиков, чтобы самостоятельно проделать все этапы. Сначала берем любой датасет на kaggle по запросу Credit Scoring. Проводим EDA, генерируем гипотезы, фичи, готовим данные для модели и делаем бейзлайн: логистическая регрессия. Затем уже можно попробовать случайный лес, градиентный бустинг, KNN или еще что по вкусу— сравниваем метрики. И на последок не забываем проанализировать результаты и культурно презентовать. Можно провести АВ тест на смой первой модели.
Все варианты решения и реализации можно найти в интернетах: GitHub, Хабр. Очень полезным будет посмотреть всякие выступления на конференциях по этой теме для вдохновения, да и это очень поможет на мл кейсах.
2. Наивный Байесовский классификатор (НБК)
Для конкретики будем классифицировать письма на спам. Опять же обработаем данные: удаляем числа, знаки препинания, стоп-слова, стемминги, лемматизацию.
Объединяем все методы предварительной обработки и создаём словарь слов и счётчик каждого слова в наборе данных для обучения:
1. Вычисляем вероятность для каждого слова в тексте и отфильтровываем слова со значением вероятности меньше порогового. Такие слова будут нерелевантными.
2. Для каждого слова в словаре создаём вероятность, что это слово окажется в спаме. Определяем условную вероятность для использования её в НБК.
3. Вычисляем прогнозируемый результат с помощью условных вероятностей.
НБК реализовать не сложно. Куда интересней погрузиться во всю теорию, которая за этим стоит, в вероятностные модели. К тому же, кейс фильтрации спама и подобного часто встречается на собесах.
3. MLOps
Можно наладить какой-то минимальный прод для проектов: например телеграм бот или FastAPI. Можно еще автоматизировать пайплайн с помощь AirFlow и попробовать запустить инфраструктуру не только локально, но и облаке. Конечно нужно будет поизучать Docker, Cuber, Hadoop, Spark, HDFS, Kafka. Но на самом деле ничего трудного— после нашего курса дата инженер будете делать такие вещи по щелчку пальцев.
4. Ранжирование и матчинг
Для начала лучше пробежаться глазами по статье и посмотреть, что пишут в интернетах. Можно выделить три подхода к задаче: поточечный, попарный, списочный. Советую начать с первого как самого простого. Для конкретики будем предсказать оценку релевантности для запросов тестового датасета. Здесь можно кстати поучиться парсить web-страниц и собирать сырые данные, размечать их с помощью какого-нибудь Яндекс-Толока. Делаем регрессию, а затем Random Forest Regressor, XGBoost, lightGBM, CatBoost.
Совсем продвинутые могут попробовать языковые модели в духе FastText, Word2Vec, DSSM и более сложные: BERT, можно даже попробовать архитектуру трансформеров.
5. Рекомендашки
Очень популярный кейс на собесах. Для начала лучше пробежаться глазами по этому разделу и посмотреть, что пишут в интернетах. Затем начинаем реализовывать самое простое как бейзлайн, например, content-based рекомендации, KNN. Дальше можно попробовать факторизации матрицы рейтингов по svd разложению или по более эффективной als архитектуре и функции ошибок bpr. Затем можно попробовать W2V подход, чтобы использовать последовательность взаимодействий пользователя для построения рекомендации следующего предмета.
Для знатоков DL можно попробовать DSSM, SasRec/Bert4Rec, MultVAE, Merlin или графовые нейронки: GCN-подобные архитектуры.
Также стоит попробовать обучение с подкреплением: многоруких бандитов.
Ну и конечно рекомендательные системы можно попробовать рассмотреть как задачу ранжирования.
Устроиться можно попасть и без проектов, но если у вас их нет, то мл кейсы будут решаться неуверенно и на финалах будете выглядеть слабее других. Никто не ждет гениального проекта с инфраструктурой— реализовать какие-то бейзлайны и понимать специфику задач уже достаточно для стажера и джуна.
Уже делали подобную подборку для аналитиков здесь, советую присмотреться.
1. Кредитный скоринг
Стоит ли давать кредит— довольно популярная задача и отличный выбор для новчиков, чтобы самостоятельно проделать все этапы. Сначала берем любой датасет на kaggle по запросу Credit Scoring. Проводим EDA, генерируем гипотезы, фичи, готовим данные для модели и делаем бейзлайн: логистическая регрессия. Затем уже можно попробовать случайный лес, градиентный бустинг, KNN или еще что по вкусу— сравниваем метрики. И на последок не забываем проанализировать результаты и культурно презентовать. Можно провести АВ тест на смой первой модели.
Все варианты решения и реализации можно найти в интернетах: GitHub, Хабр. Очень полезным будет посмотреть всякие выступления на конференциях по этой теме для вдохновения, да и это очень поможет на мл кейсах.
2. Наивный Байесовский классификатор (НБК)
Для конкретики будем классифицировать письма на спам. Опять же обработаем данные: удаляем числа, знаки препинания, стоп-слова, стемминги, лемматизацию.
Объединяем все методы предварительной обработки и создаём словарь слов и счётчик каждого слова в наборе данных для обучения:
1. Вычисляем вероятность для каждого слова в тексте и отфильтровываем слова со значением вероятности меньше порогового. Такие слова будут нерелевантными.
2. Для каждого слова в словаре создаём вероятность, что это слово окажется в спаме. Определяем условную вероятность для использования её в НБК.
3. Вычисляем прогнозируемый результат с помощью условных вероятностей.
НБК реализовать не сложно. Куда интересней погрузиться во всю теорию, которая за этим стоит, в вероятностные модели. К тому же, кейс фильтрации спама и подобного часто встречается на собесах.
3. MLOps
Можно наладить какой-то минимальный прод для проектов: например телеграм бот или FastAPI. Можно еще автоматизировать пайплайн с помощь AirFlow и попробовать запустить инфраструктуру не только локально, но и облаке. Конечно нужно будет поизучать Docker, Cuber, Hadoop, Spark, HDFS, Kafka. Но на самом деле ничего трудного— после нашего курса дата инженер будете делать такие вещи по щелчку пальцев.
4. Ранжирование и матчинг
Для начала лучше пробежаться глазами по статье и посмотреть, что пишут в интернетах. Можно выделить три подхода к задаче: поточечный, попарный, списочный. Советую начать с первого как самого простого. Для конкретики будем предсказать оценку релевантности для запросов тестового датасета. Здесь можно кстати поучиться парсить web-страниц и собирать сырые данные, размечать их с помощью какого-нибудь Яндекс-Толока. Делаем регрессию, а затем Random Forest Regressor, XGBoost, lightGBM, CatBoost.
Совсем продвинутые могут попробовать языковые модели в духе FastText, Word2Vec, DSSM и более сложные: BERT, можно даже попробовать архитектуру трансформеров.
5. Рекомендашки
Очень популярный кейс на собесах. Для начала лучше пробежаться глазами по этому разделу и посмотреть, что пишут в интернетах. Затем начинаем реализовывать самое простое как бейзлайн, например, content-based рекомендации, KNN. Дальше можно попробовать факторизации матрицы рейтингов по svd разложению или по более эффективной als архитектуре и функции ошибок bpr. Затем можно попробовать W2V подход, чтобы использовать последовательность взаимодействий пользователя для построения рекомендации следующего предмета.
Для знатоков DL можно попробовать DSSM, SasRec/Bert4Rec, MultVAE, Merlin или графовые нейронки: GCN-подобные архитектуры.
Также стоит попробовать обучение с подкреплением: многоруких бандитов.
Ну и конечно рекомендательные системы можно попробовать рассмотреть как задачу ранжирования.
❤10🔥4👍2
Вот и разбор аналитики на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 5 тыс просмотров на ютуб ролике и выкладываем МЛ. Советую поторопиться: контест вот-вот обновят.
Смотрим! Смотрим! https://www.youtube.com/watch?v=k4C9aWR6YJ4
Смотрим! Смотрим! https://www.youtube.com/watch?v=k4C9aWR6YJ4
YouTube
Разбор аналитики на стажировку в Яндекс!! (Весна-Лето 2024)
Подробней о курсах: https://news.1rj.ru/str/postypashki_old/1076
Код и условия задач: https://news.1rj.ru/str/botalkaaa/39301
Код и условия задач: https://news.1rj.ru/str/botalkaaa/39301
❤4
Задача Яндекса.
В последние дни все чаще встречается задача:
Дается массив из целых чисел длины n > 1. Вы должны вернуть минимальное произведение, которое можно получить из двух чисел массива. (позиции чисел должны быть уникальны)
Решение:
Конечно нужно решать за линию.
Пусть max1, max2 - два максимальных числа из массива, при этом max1 >= max2.
Пусть min1, min2 - два минимальных числа из массива, при том min1 <= min2.
Если min1 <= 0 и max1 >= 0 то ответом будет min1 * max1
Иначе мы получаем два варианта:
1) Все элементы положительные, в таком случае нужно вернуть min1 * min2
2) Все элементы отрицательные, в таком случае вернем max1 * max2
Именно так лаконично рассмотреть случае.
Частые ошибки:
Не умение находить два максимальных/два минимальных числа за один проход циклом за линию.
Запутаться со случаями, когда в массиве нет отрицательного/положительного числа, но есть ноль.
Время работы алгоритмы O(n)
В последние дни все чаще встречается задача:
Дается массив из целых чисел длины n > 1. Вы должны вернуть минимальное произведение, которое можно получить из двух чисел массива. (позиции чисел должны быть уникальны)
Решение:
Пусть max1, max2 - два максимальных числа из массива, при этом max1 >= max2.
Пусть min1, min2 - два минимальных числа из массива, при том min1 <= min2.
Если min1 <= 0 и max1 >= 0 то ответом будет min1 * max1
Иначе мы получаем два варианта:
1) Все элементы положительные, в таком случае нужно вернуть min1 * min2
2) Все элементы отрицательные, в таком случае вернем max1 * max2
Именно так лаконично рассмотреть случае.
Частые ошибки:
Не умение находить два максимальных/два минимальных числа за один проход циклом за линию.
Запутаться со случаями, когда в массиве нет отрицательного/положительного числа, но есть ноль.
Время работы алгоритмы O(n)
❤29🔥6👏1😁1