Тренировки по алгоритмам от Яндекса. Лекция 1: «Сложность, тестирование, особые случаи»
Вставка
- Опубліковано 1 чер 2021
- Расписание тренировок доступно по ссылке: yandex.ru/yaintern/algorithm-...
Чат в Телеграме для общения и вопросов о тренировках: t.me/joinchat/Ve7wRegrZtI0NjIy
Наконец после стольких лет я встретил тебя , мой дорогой учитель по с++
Сначала не мог понять, откуда я его знаю...))
Витя, это ты? Мы учились в НИУ ВШЭ СПБ
Stepik C++!!! :))))
Очч сложный курс, по задачам. Забил пока, изучаю пайтон
xd
На реальной работе алгоритмы применяются по следующему принципу: Если тебе захотелось вложить цикл в цикл, а во внутреннем цикле у тебя ещё запрос в БД - подумай ещё раз
Просто добавляешь ещё один цикл, чтобы запрос остался выше и говоришь "ну смотроите, если бы он лежал в третьем было бы в ^2 раз хуже.
Яндекс настолько замучал всех на собеседовании со своими алгоритмами что уже сделал обучающее видео для кандидатов чтобы прошли собеседования ! 😂 ибо разработчиков все равно нанимать надо 😂😂
Согласен, очередное задротство ради задротства
Не согласен, если человек не знает, что такое красно-черное дерево, то ему не место в программировании
@@maxkinli Держи в курсе! 😂👍
@@maxkinli вау! и как же знание красно черного дерева пригождалось в решении реальных задач? я вот за последние 2-3 месяца даже и не помню такого случая в своей работе которая очень интенсивная, так что тут задротство ради задротства
@@maxkinli по моему ты даже нигде и не работаешь , прошел курсы и теперь умничаешь
Спасибо что выкладывает такие хорошие лекции!
Очень полезен слайд с чеклистом по составлению тестов.
10:40 01. Сложность алгоритмов
15:01 Задача. Поиск самого частого символа
15:32 Решение #1
20:57 Решение #2
24:55 Решение #3
30:39 02. Особые случаи
32:19 Сумма последовательности
33:37 Максимум последовательности
35:04 03. Тестирование
38:11 Советы по составлению тестов
41:36 Покрытие тестами. Квадратное уравнение
42:31 Решение #1
42:57 Решение #2
43:55 Решение #3
44:38 Решение #4
45:58 Решение #5
46:56 Решение #6
47:44 Решение #7
48:54 Решение #8
49:27 Поиск самого частого символа
52:39 Ответы на вопросы
Алекс, спасибо тебе!
благодарочка)
Слушая лектора, кроме курса по алгоритмам захотелось взять у него уроки по умению так хорошо выступать и говорить)
@@spinacker16 Его не знаю, могу Станкевича порекомендовать, думаю в представлении не нуждается. Канал Andrew Stankevich
Спасибо за лекцию! Подробная, понятная даже джунам джуновичам! ❤😊
спасибо за курс на степике по плюсам❤
спасибо за лекции! все понятно и доступно
Мне понравилась концепция использования переменной по умолчанию, чтобы код не падал при, допустим, передаче пустой строки.
Какой же все-таки крутой лектор!
ОООчень хорошо подаёт материал! Михаил! Молодец прям)
супер полезно и супер интересно. огромное спасибо !
Когда мы считываем последовательность чисел, то можно сделать seq = [int(x) for x in input().split()]. Это работает быстрее чем list(map(...)), я замерял)
Если говорить про : "Надо ли знать алгоритмы и структуры данных программисту?". Ответ: "Да!". Прям с вослицательным знаком.
Это очень суровая правда жизни. Я и сам много раз проходил собесы с вопросами про алгоритмы или структуры данных. Это конечно же несколько напрягает, т.к. ты можешь не сообразить здесь и сейчас в виду нахождения в стрессе голова не всегда очень шустро работает, а собес это всегда стресс.
Однако вынужден признать, что после того как начал увлекаться алгоритмами и решать задачки на LeetCode,то голова начала предлагать совершенно другие решения в программировании и разработке. Появились более точные, выверенные решения. Да и саму задачу беру в работу уже совершенно по-другому. Иной раз получается так, что раньше задачу брал от руководителя сразу и брал делать без вопросов, а тут, очень часто показать ему "средний палец" показав те или иные входные данные при которых нам это решать не надо.
Умение мыслить алгоритмами приводит к тому, что сотрудник может технически грамотно послать своего руководителя и у того даже аргументов против не найдется! ;) Однако то, что берется в работу, действительно приносит пользу и работает шустро
Спасибо конечно, реально интересно, однако на 28:00 у вас всегда счетчик символа будет больше или равен нулю, т.е. получать вы будете false. А раз так, то и на вывод вы ничего не получите, т.к. сбор максимального числа будет пропущен. Правильно - dct[key] > anscnt
Густокашин - топ ) Один из моих любимых преподавателей
спасибо, очень интерестно
приятный лектор.
Какая крутая настольная лампа
что за лампа?
Спасибо :)
Жду не дождусь
За Густокашина сразу лайк!
Спасибо за лекции, буду смотреть дальше. Данная задача встречалась на реальном собеседовании. Хотел бы уточнить: я пытаюсь разобрать и исследовать оптимизацию с помощью множества (на языке JavaScript), приведенную в данном примере. Проверял со строками разной длинны, от обычных до нескольких страниц текста, все бенчмарки в пользу обычного решения с вложенным циклом. При использовании нативного new Set() в JS, скорость выполнения в ms больше всегда. Можно ли считать, что данный вид оптимизации в приведенной в этой лекции задачи, подходит не для всех языков? Спасибо.
Ошибка на 27:58 - if dct[key] < anscnt должно быть if dct[key] > anscnt
Таймкоды бы не помешали конечно .....
0
10:40 - 01 - Сложность алгоритмов
30:39 - 02 - Особые случаи
35:04 - 03 - Тестирование
Вторая половина видео понравилась)
Спасибо
Очень годно!
- В какой среде вы кодите?
- В темной комнатушке, закинув ноги на стол.
- Вы нам не подходите.
- Не понятно зачем в первом примере >>> [1]. Без этого, так же легко получается результат максимального числа одинаковых элементов списка.
- Ошибка так же в lambda функции.
Вот мой вариант с лямдой:
s = input()
print(max(map(lambda i: s.count(i), s)))
>>> Hello, world
# Output: 3
Предлагаю такой вариант
f = max((map(lambda y:(s.count(y), y), s)))
Здесь выведется кортеж из строки и числа - самый встречающийся символ и его кол-во.
Есть еще 4ый алгоритм. Вы делаете сортировку, а затем считаете длину повторяющихся символов. У вас не будет тратиться память, но алгоритмическая сложность будет О(nlogn) и тут уже стоит спросить у собеседующего какое решение он выберет? В одном у вас быстрее, но вы используете доп память, в другом чуть медленнее но без памяти.
"делаете сортировку, а затем считаете длину повторяющихся символов" -- то есть вы где-то храните всю последовательность. А значит память будет тратиться: O(N).
@@user-fr6wy4zb2t Сортировать можно "на месте" не выделяя память под новый массив. sort() в js так и работает: сортирует in-place
@@maxkinli Нет, речь про выделение память про исходный массив, а не про второй массив. 3-е решение работает так, что мы можем не сохранять исходный массив (например, если мы читаем по одному символу из потока ввода)
@@maxkinli а сортировка это не цикл?
@@You2Ber42 ну смотря какая сортировка же не? может сортировочка выбором nlogn - это же быстрее, чем те что заявлены в этой задачи (вернее в решениях к этой задаче).
Подскажите плиз- какой планшет используете для работы и вывода презентации?) Контент супер!
Задача. Поиск самого частого символа
24:55 Решение #3
Можно решить без последнего цикла с перебором элементов.
Достаочно хранить последнюю букву с максимальным на тек. момент кол-вом элементов и само это число.
Если новая больше чем предыдущая то записать в переменые.
Т.е. после dct [now] + = 1 добавить строку:
If dct [now] > anscnt:
anscnt = dct [now]
ans = now
И тогда по окончанию единтвенного цикла в anscnt и ans будет результат.
Вариант с SET слишком читерский, так как SET далеко не бесплатно работает и тогда нужно его тоже учитывать в сложности.
dict так же не бесплатно но думаю что тут разарботчики stdlib питона сдлелаи по уму и там нет перебора а идет обращение по указателю.
С таким же успехом можно использовать .count для строки и считать что мы написали алгоритм O(N)
Буфер hashmap (dict) увеличивается экспоненциально. Вставка и поиск амортизировано за константу (в худшем за n, но в питоновском дикте всегда треть свободна, что много больше статистически необходимого)
А где можно почитать почему в словаре поиск за константу?
@@renkow2627 устройство hash table
//Java script
const s = 'asdbsjdhasg21i3hasodhasioehq9dhsiugd8q2y3'
const stack = {} //Можно использовать new Map()
let result = {}
let n = 0
for (let char of s) {
(stack[char]) ? stack[char]++ : stack[char] = 1
if (stack[char] > n) {
result = char
n = stack[char]
}
}
console.log(stack, result)
Второе решение первой задачи ничего не ускоряет. Сложность алгоритма такая же, как и в первом, просто вы опустили часть операций под капот и визуально создали иллюзию оптимизации
Очень понравилось ваше видео подскажите в какой программе вы его снимали?
Про O(N) объяснил так-себе (начиная примерно с 11 минуты)... Если бы я не знал этот материал, то вряд ли бы понял.
но в целом неплохо
Парадокс в том что если бы я так же объяснил решение на собесе в Я. Мне бы впиндюрили no hire.
Ничего не понял.
С++ на Stepik)))
Где такой курс там? )
Клаааасс
А еще можно было не проходиться по словарю а в момент добавления в словарь проверять счетчик и кешировать последнее максимальное значение в 1 задаче и тогда было бы всегда o(n) где n длина строки.
Все лекции будут в открытом доступе на Ютубе?
да, они уже выложили их, я тоже думаю посмотреть и прорешать курсы по алгоритмам
Кажется в вашем коде в 3-ем решении вы сделали ошибку: нужно поменять знак в неравенстве dct[key] < anscnt, мы же ищем самый частовстречаемый
def frequently_occurring(line):
mem = dict()
max_time = 0
max_sym = None
for sym in line:
tmp = mem.get(sym, 0) + 1
if max_time < tmp:
max_time = tmp
max_sym = sym
mem[sym] = tmp
return max_sym
На 38 минуте - а точно что значение словаря должно быть меньше макс выбираемого значения anscnt?
В записи это 33 минута, 38 минута, возможно была в момент живого стрима.. Там действительно ошибка, вместо "if dct[key] < anscnt:" должно быть "if dct[key] > anscnt:", так как ищется наиболее частое вхождение символа в строку (максимумальное значение частотного словаря dct), а не наименьшее.
Решение #3. 29:14. Вопрос:
Внутри первого цикла "for now in set(s)" мы разве каждый раз не пробегаем по словарю, чтобы проверить есть ли там символ "if now not in dct"? Почему сложность O(N + K), а не O(NK + K)?
По -моему, в этом варианте вообще нет K, а сложность 2N
@@ITV-ITV- В О большом нет констант
@@Jorge-dm9sz Прямо в определении Big-O говорится: Т(n) = O (f(n)) тогда и только тогда, когда Т(п) в конечном итоге
ограничена сверху постоянной, кратной функции f(n).
Какие у Вас источники?
@@ITV-ITV- В самом видео об этом сказали
@@Jorge-dm9sz На слайде у инструктора указано: "Константы не так сильно влияют на скорость работы алгоритма при больших параметрах", а говорит он при этом, что константы "абсолютно не влияют на асимптотическую оценку сложности ".
Первое верно - на практике константы можно не учитывать, второе - не верно, для анализа это важно.
Этот момент уже показывает качество курса. Я бы не рекомендовал его для теоретической подготовки.
Я не продолжил смотреть этот курс, несмотря на то, что мне его рекомендовала хороший специалист. Считаю, что переучиваться потом с таких противоречивых знаний будет более затратно, чем сразу учиться по хорошей книге (Skiena, Cormen, Sedgewick). Может быть, примеры из этого курса будут полезны в процессе обучения, но я пока не проверял.
Намекните хоть, как на java можно реализовать 2 и 3 способ?
Где взять такую настольную лампу?😁
30:30 а что, так можно было что ли? "можно строку и не хранить и по одному символу получать". Что-то не понятно, откуда это решение получилось по памяти лучше #2. Должно быть таким же и в каком-то частном случае лучше, и то не очевидно. Это мы рассказывая про ассимптотическую сложность решили начинающего слушателя запутать и от интерфейса countMaxSym(str) перейти к countMaxSym(char)? -- только так могу понять
32:13 - АБОБА
я только не понял зачем в 3 решении еще и цикл по словарю в конце? в худшем случае сложность такого решения будет O(2N)
Лучше создать отдельные переменные (например symb и symbRepeatCount) для хранения самого частого символа и количества его повторов в строке.
тогда на каждой итерации сравниваем количество повторов текущего символа (значение в словаре) со значением в переменной symbRepeatCount. Если значение в словаре больше symbRepeatCount, то присваиваем его symbRepeatCount, а в symb записываем текущий символ
в этом случае сложность будет O(N), даже если все символы в строке разные
а что если использовать готовый метод поиска количества вхождений элемента в строке : print(max([n.count(i) for i in n])) где n исходная строка?
@Болтушка Почему тогда часть операций таких как "словарь", "set" использовали готовые уже из питона.
Как то не понятно где граница проходит.
При этом и первое и второе это сами по себе достаточно сложные алгоритимические задачи.
Тот же set это как минимум один дополнительный цикл, просто спрятанный внутрь оператора.
А про то как работает Dict можно курсовую написать.
Но как то мы все это игнорируем.
Опять же если сдавать задачу роботу то он проверяет только по входу/выходу времени/памяти
Линейная сложность - это сложность которая зависит линейно 🤡 11:39
Насколько честно считать константным поиск элемента в словаре? Ведь если словарь большой, в котором К ключей, не стремится ли это значение к К?
Скорость поиска в словаре O(1). Независимо от размера коллекции, время, необходимое для выполнения операции, константно. Он не перебирает элементы подряд в поиске нужного ключа, как это было бы в массиве, иначе и смысла бы нем не было)
Это абстракция. Вопрос про реально большие таблицы. Ведь если К константа, то поиск в множестве из К элементов также константа. Но в лекции при оценке алгоритма с использованием множества учитывается К, а в словаре не учитывается.
ничего, что запись вида dict[...] подразумевает под собой поиск по словарю? и так и происходит под капотом.
то, о чём идёт речь в третьем варианте решения задачи про поиск наиболее часто встречающегося символа в строке (~27 минута) - фиктивная сложность. на самом деле разумеется в общем худшем случае (для абстрактного ЯП) временная сложность будет опять O(NK).
словари под капотом - хеш таблицы, так что операция обращения к элементу происходит за O(1), так что нет, сложности O(NK) не будет
если конечно докопаться, то в хеш таблице может быть K коллизий, и тогда поиск действительно будет O(K), но это что-то нереально в масштабах этой задачи
Первая лекция зашла! К концу июня буду, как этот чувак в видео)) ua-cam.com/video/KPv6BU2GLLs/v-deo.html
Умоляю, дайте ссылку на такую лампу)
Заяндекси - "Подвесная левитирующая лампа" :) Видов довольно много, но такая как в видео будет в первых ссылках
@@steilseven спасибо добрый человек)
А как у вас на яндекс станции часы появились?
Яндекс Макс
Квадратное уравнение всегда имеет два корня, если не обговорено, что если корни совпадают по значению, то надо вывести один из них, это разве ошибка стажера?
Да, тоже хотел написать, что два одинаковых корня это не один корень.
а разве встроенная функция Set() не делает вложенный неявный цикл!? правда он не усложняет выполнение, но кто знает как он работает на низком уровне.. прозрачнее было бы разобрать задачу из простейшего функционала
Фухх... 10 000 раз вывел Hello world. Меня наконец-то ждет успех
23:38 - а разве не O(N*(K+1))? Set же пробегает N элементов, а после него, мы еще и по каждому символу пробегаем K раз. Или я не прав?
А зачем решение писать на листочке? Чтобы что?
Что-то я не понял, почему на 28:55 сложность O(N+K). Циклы там не вложенные, я бы записал O(N) + O(K) = O(N)
так там, так и написано на 29:31
@@user-dv7yl6kg8y Да, я согласен. Просто как-то понятнее, так как два отдельных цикла, написать O(N) + O(K) = O(N+K) = O(N), а не только последнее равенство.
ABOBA 15:40
У меня тупой вопрос - буква а в разных языках разве не имеет разных байтовый код? То есть все буквы разные получаются в каждом алфавите, даже если для человека выглядят одинаковыми?
Да, каждая буква каждого языка имеет свой байтовый код. Английский алфавит в unicode для обратной совместимости с ASCII всегда находится на нижних границах табилцы кодировки. Например русская и английская "a" хоть и выглядят для нас одинаково, но в русском варианте будет весить 2 байта, тогда как в английском 1 байт.
@@user-ps6bb1fm9u как тогда выполнять задание из видео (первое по-моему)? Получается повторяющихся символов(с точки зрения кодировки) ни в одном языке мира нет
@@TheBaragoz если речь про первое задание с подсчетом букв в строке, то видимо ограничение задачи подразумевается, что на вход подается строка в английском алфавите. Если строка будет смешаной из нескольких языков, то никак не посчитать. Компьютеру не обьяснишь, что для нас английская и русская "а" - "одинаковые".
В решении #2 сложность оценивается как O(nk), но ведь k не является входным параметром, а следствием внутренних вычислений. Так в лучшем случае сложность получается O(n) в худшем O(n^2), может правильней было бы выбрать что-то из этого? Другая мысль в том, что k отражает количество уникальных символов, но как бы мы не старались, максимальное количество уникальных символов ограничено и является константой, тогда сложность образуется в O(n)?
Ничерта непонятно. Почему в первой задачи не учитывается сложность построения set? Ведь чтобы его построить уже уйде N. Почему не учитывается сложность работы со словарем? Создание словаря, поиск по словарю при добавлении нового значения? Если это хеш то где учет проверок коллизий и перехеширования? Автор рассказывает так как будто у него какой-то волшебный язык, в котором все происходит мгновенно, кроме пользовательских циклов, но это же бред.
А у O(n + nk) - какая в итоге сложность-то? Что даст учет построения множества, если сложность в итоге все равно так и останется O(nk), ибо построение множества никак не будет влиять на скорость роста времени выполнения. Похожий случай в видео как раз в примере со словарем разобран, по поводу второго цикла и того, что O(n + n) - это все равно О(n).
Словари - хеш-таблицы. Писали их в Питоне люди не пальцем деланные, поймать на них O(n) очень нужно постараться, и уж точно его не будет на каждом добавлении\поиске, потому всегда рассматривается средний случай - O(1)
По временной сложности пример со словарем в итоге все равно лучше и первого варианта, и варианта со множеством.
Да не народ все просто.. Суть ,истина , и провда.. Всегда решали все вопросы. Если сиогли правильно выстроииь последовательность то вы наконе , нет пробуйте еще... Старо как мир..
Питонячий однострочник в первой задаче уж очень грязный получился. Куда симпатичеее как-то так, даже почти читаемо
max(set(string), key=lambda symbol: string.count(symbol))
Максимальный элемент из уникальных символов строки, максимальность определяется по тому, насколько часто этот элемент встречается в строке.
аааа как же зашакалено качество видео
После пары заданий из домашки я решил их больше не делать. В irb с аргументами или файлами замечательно работает, у них при тестировании ошибка какая-то и хщ на каких аргументах в чём проблема? И постановка задач уё#ская: две цифры дают и надо вычислить какая из них температура в комнате а какая на кондиционере, а в случае когда он может и нагреть и охладить вообще хз.. Ну типа - "10 20 это две температуры, одна в комнате а другая должна стать через час. Кондиционер может в режиме пох и охладить и нагреть но хз что он будет делать. Какая будет температура в комнате через час?" ...
30:55
Еще тише не могли звук сделать ?
да вроде норм звук
@@user-wz7cv4dt6q
нет, не норм.
О, Густокашин!)))
После худших в моём понимании вступительных курсов от яндекс разработки ua-cam.com/video/DMF8lCrf3Qs/v-deo.html&ab_channel=%D0%A0%D0%B0%D0%B7%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B0, переход к ненавистным алгоритмам оказался облегчением, за счет шикарной подачи ведущего с «тёплой атмосферой».
Улыбнуло здесь:
ua-cam.com/video/QLhqYNsPIVo/v-deo.html
кто умеет пишет так:
print(max(s, key=s.count))
Дескриминат дискредитировал диктора. Волнение волной накатывало и отключало мозг: то if забыл он написать, то в циклы он не смог.
первую задачу можно решить еще эффективней, если вместо if использовать try, except. При 10млн элементов (числа 1 до 1000) ваше решение проходит за ~1.08сек, а моё за ~0.85сек:
import random
def ident2(s):
dic = {}
m = 0
for i in s:
try:
dic[i]+=1
except KeyError:
dic[i]=1
for i in dic:
if dic[i] > m:
m = dic[i]
val = i
print(m, val)
l = []
for i in range(10000000):
l.append(random.randint(1, 1000))
ident2(l)
Насчёт лишних ветвлений - следовало бы уточнить, что ветвление для процессора - весьма затратная операция, ибо непонятно что нужно пихать в кеш, например… честно говоря, курсы напоминают что-то ванильное для тех, кто только что разобрался, где собственно кнопка включения у компа. Знакомый плюсовик недавно приобрёл Я курсы по алгоритмам, так это зрелище не для слабонервных. Литкод на среднем уровне минимум.. посмотрим дальше, что будет, мож вырастет грибочек…
у питонщиков названия переменных ппц
29:21: Знак ""
Один из тех случаев, когда автору важнее сложность посчитать и нет дела до того работает его код или нет.
const s = 'asdbsjdhasg21i3hasodhasioehq9dhsiugd8q2y3'
const stack = {}
let result = {}
let n = 0
for (let char of s) {
(stack[char]) ? stack[char]++ : stack[char] = 1
if (stack[char] > n) {
result = char
n = stack[char]
}
}
console.log(stack, result)
А вот и нет. Для строки с применением словаря, все равно эн*ка в худшем случае. Сам механизм мапы ключи перебирает внутри.
Зачем брать примеры на питоне, если потом каждый раз в каждом примере объяснять что вот конкретно эта функция означает?
Чтобы кто пишет на c или на js, понимали алгоритм и могли переписать
@@rusfungame не проще взять или пвсевдо язык, или язык в котором прозрачно все более и не нужно специфику в примерах пояснять?
@@lionstar3189 к чему ты это написал? Это как-то помогло или решило проблемы с пояснениями?
@@AS-nu7ez пайтон и есть псевдоязык. Для знающих английский он выглядит именно так
@@ZZZ5204 тогда если это и есть псевдоязык, почему поясняеися каждая функция как работает? И так должно же быть понятно?
А так, это всё никчёмная информация, для памяти и процессора ВСЁ ровно какие там у вас случаи людишки.
Курс по алгоритмам, но даже ШАЯ, думаю, для автора, если и не ругательство, то точно что-то бессмысленное. Где Вас учат? Зачем Вы лезете в ту область, в которой не разбираетесь? Я имею ввиду преподавание.
что за шая?
@@manOfPlanetEarth Школьный алгоритмический язык
Всё это стремительно устаревает. Алгоритмы - это шаблоны, всё что шаблонизировано, может и должно быть автоматизировано. Процесс разработки будет полностью автоматизирован на горизонте 3 лет. Обучение стрельбе и выживанию будет более продуктивно и перспективно.
Очень монотонный голос - засыпаешь от скуки. Почему на питоне - вроде не курс питона. Может на паскале лучше, с него начинают на олимпиадах. Нудятина. Ужасно.