Тренировки по алгоритмам от Яндекса. Лекция 2: «Линейный поиск»

Расписание тренировок доступно по ссылке: yandex.ru/yaintern/algorithm-...
Чат в Телеграме для общения и вопросов о тренировках: t.me/joinchat/Ve7wRegrZtI0NjIy

[@h1gfun4]

У человека талант педагога) очень приятно смотреть и слушать мастера своего дела, ОЧЕНЬ ОЧЕНЬ! Надеюсь в будущем еще увижу его в роли педагога!!! Благодарю за ваш труд

[@vladimirmaksimov3938]

Ну не зря наверно студенты ВШЭ по 500 к в год платят

[@valeriyemelyanov9090]

Задача 1: зачем продолжать поиск, после того как найден ответ (первое вхождение!)? Вариант решения без лишних переменной, проверки и итераций def findx(seq, x): for i in range(len(seq)): if seq[i] == x: return i return -1

[@user-hv9pk2nu8t]

тот же вопрос возник

[@nikprilutskiy7064]

Поддержу. Зачем весь список пробегать, если результат уже найден. Это как минимум не эффективно.

[@ilikecola378]

как зачем, чтобы рассказать как эффективно использовать -1.😜

[@namesurname4406]

Может чтобы решение обеих задач было как-то консистентно. Но там не обработано условие с положительными числами.

[@kosbarable]

походу ошибка в условии, нужно не крайнее левое вхождение, а крайнее правое, потому что тот код, что приводит ведущий не выводит крайнее левое, а находит и выводит крайнее правое.

[@egorkalmykov4003]

Спасибо огромное за информативную и полезную лекцию !!!

[@esergey12]

08.07.2021 Прекрасные видео, спасибо лектору. Очень круто обьясняет.

[@esergey12]

0:32 О чем лекция. План. 1:00 Классические задачи линейного поиска. 1:04 Что такое Линейный поиск. 1:43 Задача 1. Найти первое вхождение. 5:48 Задача 2. Найти последнее вхождение. 7:51 Задача 3. Найти максимальное число. 12:50 Задача 3. Пояснение сложности сравнения. Лексикографический порядок. 15:44 Задача 3. Зачем сохранять индексы. Сложность копирования. 18:48 Задача 4. Два максимума. 26:17 Задача 5. Минимальное четное. 30:44 Двухпроходные алгоритмы. 30:48 Задача 6. Вывести самые короткие слова 35:28 Задача 7. Сколько блоков воды. 44:00 Задача с собеседования. RLE 51:22 Ответы на вопросы.

[@iworeushankaonce]

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

[@devchernov3521]

Курс объединён в плейлист kzbin.info/aero/PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5

[@MsNameness]

В задаче 4. Обязательно писать range(2, len(seq)). Иначе в последовательности [5,9,7,8,1,7,4,1,7] вернет (9, 9) вместо (9, 8) потому что алгоритм с самого начала проходит последовательность, и elif seq[i] > max2 встречает 9ку, макс2 записывает 9ку вместо 5ки.

[@Zaqer84]

Вы не совсем правы. В этом алгоритме гораздо больше ошибок, чем вы указали. И ваша правка не спасет ситуацию. [5,9,7, 9,1,7,4,1,7] при ваших правках тоже вернет (9, 9). А еще [9,9,7,4,1,7,4,1,7] тоже вернет (9,9). В программе не верна и логика выбора начальных значений и алгоритм замены. Вот так будет работать: def foo(lst): if len(lst) < 2: return 'error' max1 = max2 = min(lst) for i in lst: if i > max2: if i > max1: max2, max1 = max1, i elif i < max1: max2 = i return max1, max2

[@skylud]

ответ (9, 9) правильный, поскольку нам нужно найти не второе по величине число, а максимум из последовательности если из неё вычеркнуть первый максимум

[@mberdyshev]

@@Zaqer84 Согласен с предыдущим оратором. При обсуждении задачи (19:38) чётко обсуждался этот момент.

[@mberdyshev]

Да, он это упоминает во время вопросов (1:03:56)

[@TopUser2022]

Вот такая же программа на Паскале program max; uses crt; label l; var arr: array of integer; i, len, max1, max2: integer; begin l: writeln('Input the array length: '); readln(len); if len < 2 then goto l; setlength(arr, len); writeln('Input the array: '); for i := 1 to len do read(arr[i]); if arr[0] > arr[1] then begin max1 := 0; max2 := 1; end else begin max1 := 1; max2 := 0; end; for i := 0 to length(arr) do begin if arr[i] > arr[max1] then begin max2 := max1; max1 := i; end; if (arr[i] = arr[max1]) and (i max1) then max2 := max1; if (arr[i] < arr[max1]) and (arr[i] > arr[max2]) then max2 := i; end; writeln('Max 1 is: ', arr[max1], ' Max 2 is: ', arr[max2]); readkey; end.

[@user-hv9rc7bm2f]

Задача №6 Написано : if len(word)

[@user-hv9rc7bm2f]

Возьмите работать в Яндекс

[@scufidon]

@@user-hv9rc7bm2f ахахаа красава

[@adilkumashev8964]

@@user-hv9rc7bm2fпреподавать в ВШЭ*

[@Irades]

Спасибо ❤

[@lippogoo]

findmax2 - если в нее передать следующую последовательность {-2,-4,-6} и начать проход по всей последовательности, то что мы получаем, в первый if не заходим, а во втором max2 становится равным -2 и функция вернет {-2, -2}

[@EgorPifagor]

У вас в задаче на вывод слов с минимальной длиной опечатка: вы присваиваете счётчику минимальной длины размер заданного массива, а не длину слова

[@user-ud9tt5hh1p]

Крутое объяснение! Спасибо! Но информации очень много, не каждый воспримет

[@i17talk8]

55:34 Категорически не согласен с тем, что continue и break затрудняют понимание. continue уменьшает вложенность, что как раз значительно облегчает понимание и немного ускоряет выполнение, а break значительно ускоряет и также облегчает понимание. Хотя, это у кого как. Разумеется, необходимо во второй задаче идти справа налево и делать break, либо заранее разворачивать список. Нелюбовь к этим конструкциям будет заставлять делать процессор тупую работу, когда можно было бы её не делать. Например, как в ещё одной приведённой задаче, искать минимальную длину слова до конца массива, когда она уже == 1. И функция для осмысливания не на экран должна помещаться, а в голову. Успехов.

[@valeriyemelyanov9090]

насчет continue и break поддерживаю на все 100

[@user-dk2mn6fx7y]

А мне кажется, или в 6 задаче в 5 строке решения должно быть len(word) вместо len(words)?

[@LastFreeEagle]

Не кажется

[@ntvisigoth]

Да, тоже бросилось в глаза и думал показалось ))) Начал искать ответ, чтоб не на плодить еще одного замечания про это

[@pas777777]

В python минус бесконечность можно задать как -float('inf')

[@mak_whisk]

Спасибо

[@iptashR]

В задаче на собеседование можно счётчик добавить, и если встретили новый символ,добавить цифру в выходную строку, а счётчик обнулить?

[@evgeny8popov]

Имена переменных вызывают вопросы, конечно. В python snake case принято использовать.

[@gotrax2661]

Небольшая помарка по 6 задаче. В условии сказано, что слова нужно вывести через пробел, если запустим финальное решение на список слов, слова будут просто выведены через пробел. Чтобы исправить это, можно добавить запятую в кавычки join, т.е ' '.join(ans) -> ', '.join(ans)

[@gooddha]

в задаче с двумя проходами первый вариант добавинт пробел в конце строки, поэтому решение не прошло бы тест

[@Mikola1982Lt]

Привет! Я чего-то не понимаю, но зачем в задаче 1 перебирать массив дальше, если первое вхождение числа было найдено? Ведь можно сразу вернуть искомое и не нужны будут заморочки с -1-кой и дополнительной переменной? Понятно что скорость алгоритма останется O(n) для наихудшего случая, и по памяти почти нет выигрыша но..... алгоритм станет проще на мой взгляд....

[@user-sg4kc5cx5v]

В задаче 8 - обязательно нужно начинать итерацию с 0 элемента, иначе не обработаем ситуацию когда строка в 1 символ, например text = "A"

[@Khanalas]

Нет, тогда работает append после цикла и ответ всё равно будет 'A'

[@sashavpope]

Идеально на 1.5х смотреть. Как и все остальные.

[@i17talk8]

2x норм. Жаль, нет 3x

[@deniskhakimov]

@@i17talk8 давненько добавил себе ссылочку в браузере для 3x :D URL должен быть чем-то вроде: javascript:document.querySelector('video').playbackRate = 3; Это если лень открывать консоль каждый раз.

[@i17talk8]

@@deniskhakimov Спасибо, сработало. В FF только через консоль получилось. Закладка меняет весь body на "3"

[@user-yg6ne8cc3x]

@@deniskhakimov в video speed controller - можно более гибко скорость менять, всё-таки у всех разная дикция и скорость речи.

[@deadproxcee4322]

Знаю, что пишу уже поздно, но может кто нибудь ответит. Хорошо ли решать эту задачу с собеседования используя словарь, в котором ключ это индекс строки, а значение сколько раз она встретилась. А в конце собрать строку обращаясь к исходной через индекс из словаря и количество из значения? Я предполагаю, что по памяти возможно будет хуже, чем предложенное решение, но всё же. def update_str(string: str) -> str: def pack(s, count): if count > 1: s += str(count) return s if string == '': return string current_index = 0 count_chars = {0: 1} for i in range(1, len(string)): if string[i] != string[current_index]: count_chars[i] = 1 current_index = i elif string[i] == string[current_index]: count_chars[current_index] = count_chars[current_index] + 1 return ''.join([pack(string[key], value) for key, value in count_chars.items()])

[@travaler5235]

Задача 3 "Зачем сохранять индексы. Сложность копирования." 18:17 Мне кажется, для корректной работы строку if seq[i] > seq[ans]: нужно заменить на if seq[i] > seq[0]:

[@LastFreeEagle]

Тогда у тебя будет происходить сравнение остальных элементов только с первым, и программа будет выдавать последнее число из последовательности, которое больше первого

[@kotiko_oks]

5 задача не решается при всех чётных отрицательных числах, исправить можно убрав из условия вторую часть после and и записать ещё один вложенный if ans == -1 : ans=seq[i] elif ans

[@relax_FM_1]

задача 7 требует дополнительного описания, так как не рассмотрен случай, когда "график" имеет несколько максимумов (несколько паттернов подъема и спуска "ступенек")

[@einesAbends]

В задаче ищется первый максимум. Все другие максимумы будут справа. Последний максимум в ходе цикла станет nowm. Про числовое значение h[maxpos] по факту можно забыть после первого цикла - теперь это чисто элемент-ограничитель для воды, гарантирующий, что она не перельется. Попробуйте запустить код в песочнице с тестовыми примерами, он верный.

[@outofthebag849]

Добрый день. А если в задаче с островом несколько одинаково больших вершин? Тогда как?

[@vladnoov1561]

Задача про RLE решена неверно: в исходной формулировке просят генерировать ошибку, если приходит невалидная строка, а в реализации проверки, что s[i] >='A' && s[i]

[@denchik5188]

Попробуй использовать vector (динамический массив, к нему нужно дополнительно подключать библиотеку #include , чтобы узнать как с ним работать рекомендую погуглить). Но, если я ничего не путаю, строка в плюсах работает не так как в питоне. В плюсах это динамический массив чаров и в большинстве случаев добавление происходит за константу, а log н раз копирование. Если интересно что у это структуры ,,под капотом,, рекомендую почитать про Array List. Удачи в изучении)

[@EaSy64region]

Что это за чудо-лампа?

[@user-bi4wd8hr2r]

50:10 15FullHD или 24-4k ? :)

[@jimmycaldwell2012]

Зачем в первой задаче проходить полностью по всей последовательности чисел, если можно вернуть найденную позицию сразу как только она будет найдена?

[@FeelUs]

Он в конце видео ответил

[@jimmycaldwell2012]

@@FeelUs нет, не ответил

[@FeelUs]

@@jimmycaldwell2012 52:16

[@jimmycaldwell2012]

@@FeelUs спасибо

[@24Mrnobody]

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

[@user-gu5pz8xf3u]

я потратил кучу времени, чтобы понять, что в качестве аргумента приходит ландшафт без воды. И что вообще является входным аргументом(думал что двумерный массив)

[@DevilAlex03]

@@user-gu5pz8xf3u та же ситуация, хотел решить задачу до разбора, поставил видео на паузу и пошел решать. Из контекста думал что ландшафт представлен двумерным массивом и решал задачу соответственно. Потом начал смотреть разбор и понял, что приходит массив из высот столбцов, и все гораздо проще)

[@user-pg8ry1tm3t]

Задача 7. Имеем последовательность с локальными минимумами. Оцениваем каждый элемент как минимальную разницу между соседями

[@kotifnat]

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

[@kairat_ala]

rle на js, мое решение: function rle(str) { let ans = ''; let curLetter = str[0]; let count = 1; for(let i = 1; i < (str+'_').length; i++) { if (str[i] === curLetter) { count++; } else { ans += curLetter+(count > 1 ? count : ''); count = 1; curLetter = str[i]; } } return ans; }

[@murcha5899]

офигенно!

[@rainysky84]

1) >>>> ans += curLetter+(count > 1 ? count : ''); Привет, O(n^2) по памяти 2) в condition-части цикла вместо _i < (str+'_').length;_ лучше написать _i

[@polrk]

Задачу номер 6 можно решить за один проход. Просто добавлять все слова в мапу => 1: ['a', 'b'], 2: ['ab', 'ba'], ... , после вернуть минимальный ключ

[@user-xf5ry2ig3h]

чтобы вернуть минимальный ключ, надо пройтись циклом по ключам или я не прав?

[@polrk]

@@user-xf5ry2ig3h В переменной

[@eugenesemin4082]

@Мария Кузнецова Если именно для Python, то можно за один цикл: dct = {} for word in words: dct.setdefault(len(word), []).append(word)

[@justyar5781]

Все еще проще: seq = ['aa', 'b', 'cc', 'd'] def shortwords(words): minlen = len(words[0]) ans = [] for word in words: if len(word) < minlen: minlen = len(word) ans = [] ans.append(word) elif len(word) == minlen: ans.append(word) return " ".join(ans) print(shortwords(seq)) # b d - Решение через 1 прохода

[@user-cb6kk7xp2y]

@@justyar5781 Проблема в сложности алгоритма) В вашем решении много раз происходит операция добавления в массив (тк будут записываться слова разной длины) и операции удаления массива. А сложность при 1 проходе массива или 2 проходах примерно одинаковая = O(n). Так что решение с 2 проходами будет быстрее (тк нет удаления и меньше добавления в массив)

[@user-qz3tm9cf8i]

Михаил очень приятно смотреть твои видео!!! Я про задачу на собеседование сделл в один проход все С++ std::string st = "AAAABBBCCXYZDDDDEEEFFFAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB"; if (!st.empty()) { char last = st[0]; int count = 0; for (auto i : st) { if (i == last) { count += 1; } else { std::cout 1)std::cout

[@alexpizza72]

5:40, а почему не сделать принудительный выход из цикла, если левое значение найдено? зачем дальнейший перебор?

[@namesurname4406]

52:20 ответ

[@FeelUs]

В решении задачи 6 ошибка (в одной букве)

[@alphascorpii8287]

minlen = len(word) должно быть

[@user-tq7xp6ev1y]

"Решение работать будет, но будет работать медленно" - не будет, слона то и не заметили :)

[@Nievni]

В задаче 8 забыли, что строка может быть пустая

[@user-sf9ow6ir3o]

почему в первой просто не брейкнуть как только нашли нужное число?

[@mihailbury240]

тоже подумал об этом, а еще лучше бы сразу вернуть число, тем самым также завершив цикл

[@unpub2]

странное решение первой и второй задачи, в первой после нахождения первого вхождения надо прервать цикл, и сравнивать на -1 не придется, во второй итерацию начинаем с конца списка в обратном направление, и так же выходим из итерации после нахождения. хотя может в петухоне нет операторов прерывания цикла и итерации с конца, не знаком с ним

[@user-sf9ow6ir3o]

есть и то, и другое

[@user-sf9ow6ir3o]

задача 7 - это литкод 42, если кому-то нужно

[@user-pg8ry1tm3t]

Задача с собеса. Куча вопросов. Что с памятью, что со временем. Надо ли запоминать получившуюся строку или просто вывести в консоль?..

[@vladimircreator]

55:50 - тут я выпал с окна 10 этажа

[@v_borovik]

В Java первую задачу начинаем итерацию с начала массива и сразу, как только нашли элемент с нужным значением, возвращаем его индекс и из цикла выходим. Чтобы найти последнее вхождение, надо итерацию начать с конца массива и также вернуть индекс первого встречного элемента с нужным значением, выйти из цикла. Зачем целиком массив перебирать? Лишняя работа. Если переберём весь массив, а элемента с нужным значением не найдём, тогда вернём -1. Я не знаю, конечно, как там в Python с этим дела обстоят, но мне кажется, тоже должны быть такие возможности. Или нет? Если я на позицию Java-разработчика начну минус один городить, меня спросят: "А нафига ты такой фигнёй занимаешься? Это все избыточно". И джуном то даже не возьмут. Скажут, что нифига не понимаю.))

[@namesurname4406]

Можно было также как вы говорите решить и в питоне, и было бы чуть быстрее. Но что в питоне круто, если с джавой сравнивать - можно было вообще это решение в одну строку уместить.

[@user-sj7nr9zd6z]

Первая задача: А что, брейкнуть нельзя цикл без проверки на -1?

[@maxkinli]

Можешь выйти из цикла, а можешь продолжить. Сложность так и останется O(n)

[@i17talk8]

Вот именно. Нафига каждый раз проверять на -1? Кошмарно, если так в яндексе учат и пишут. Академики. Есть ли смысл дальше смотреть? Не научусь ли я у них субоптимальности (тупизне) кода?

[@rusfungame]

@@i17talk8 Не учить вовсе очень плохо

[@i17talk8]

@@rusfungame не учить надо, а понять. Есть же нормальные книги (мануалы, видео), так зачем учиться по плохим? Никто не говорит, что если ты не пользуешься корявыми источниками, то ты не учишься вовсе.

[@user-ts7ok1tx7w]

@@i17talk8 если нашёл скинь пожалуйста

[@user-sf9ow6ir3o]

очень тихо(

[@Timon460]

где домашка то?

[@user-bi4wd8hr2r]

1:08:50 Разрешено более одного максимума. Для этого алгоритма мы получим такой результат. O O OWOWO OWOWO OOOO0O

[@mberdyshev]

Почему?

[@tertiumorganum5665]

ну чел, если есть проблемы с break и continue, даж хз что сказать. кмк это близко к топ 5 вредных советов. цикл мог выйти на 1 итерации, но ок, изза трудностей восприятия мы конечно будем крутиться все 10000 раз 😂

[@ltdsci2171]

00:20:58

[@user-ud2yb8ou7s]

Отлично! на выходные задачек будет) Чувствую буду после курса таким же крутым! kzbin.info/www/bejne/nWaydJxoZd58r8U

[@Sancho_Merka]

Из-за Вашего комментария начал смотреть этот сериал :)

[@user-ud2yb8ou7s]

@@Sancho_Merka Отлично) тебе понравится! в переводе кубик в кубе обязательно

[@user-ud2yb8ou7s]

@@Sancho_Merka только наши ролики не смотри. лучше сначала сам сериал)

[@alekseypavlov2539]

//Задача 4 - Java script const arr = [ 5, 9, 7, 9, 1, 7, 4, 1, 7 ] let numbers = [ 0, 0 ] for (let i = 0; i < arr.length; i++) { if (numbers[1] < arr[i]) { numbers[1] = arr[i] } if (numbers[0] < arr[i] && arr[i] < numbers[1]) { numbers[0] = arr[i] } } console.log(numbers)

[@LastFreeEagle]

Зачем так усложнять 4 задачу? Это ведь та же первая, только предыдущее значение перед ответом мы должны запомнить, и еще дополнение: если два одинаковых числа встречаются, то нужно обработать оба, поэтому в ифе больше либо равно вместо строгого равенства def find2max(seq): ans1 = seq[0] for i in range(len(seq)): if seq[i] >= ans1: ans2 = ans1 ans1 = seq[i] return ans1, ans2

[@mberdyshev]

Ваше решение сломается на тестах [5, 4, 3, 2] или [5, 5, 7, 6]

[@LastFreeEagle]

@@mberdyshev Спасибо, видимо, все-таки без мин макс или сортировки не обойтись)

[@RisDeep]

Слишком длинные видео. Поэтому люди будут перелистывать. И 90% времени на экране текст задачи или решение какой-то задачи. Контекст совершенно непонятен. Добавляйте заголовки что за тема задачи и зачем её разбирать. У вас всё равно во многих сценах 50% свободного места на экране

[@Zaqer84]

4 задача решена не верно. Не верно выбираются начальные значения и не верно заменяются значения при переборе. Верный вариант если можно использовать min и max: def foo(lst): if len(lst) < 2: return 'error' max1 = max(lst) max2 = min(lst) for i in lst: if max1 > i > max2: max2 = i return max1, max2 Верный вариант если можно использовать сортировку: def foo(lst): if len(lst) < 2: return 'error' max1, *max2 = sorted(set(lst))[:-3:-1] return max1, max2[0] if max2 else max1

[@MrLuckfinder]

Мда, разжёвываем, разжёвываем простое... Потом сложное - "ну здесь всё понятно, пропускаем" 🤦🤦

[@BetalBerbekov]

перед решением одной задачи, решил свое решение писать и сравнивать с тем что получилось. Это задача в 2 прохода, где нужно найти короткие слова. C 1 циклом получилось и как оказалось быстрее import timeit import copy some_words = 'adasawsd aa asdadsadb csdcc dasaads dd'.split(' ') def short_words_1(words): words = copy.deepcopy(words) count = len(words[0]) ans = [] for w in words: if len(w) > count: continue if len(w) < count: ans.clear() count = len(w) ans.append(w) return ' '.join(ans) def short_words_2(words): words = copy.deepcopy(words) min_len = len(words[0]) for word in words: if len(word) < min_len: min_len = len(word) ans = [] for word in words: if len(word) == min_len: ans.append(word) return ' '.join(ans) ans_1 = short_words_1(some_words) ans_1_time = timeit.timeit(lambda: short_words_1(some_words), number=10000000) ans_2 = short_words_2(some_words) ans_2_time = timeit.timeit(lambda: short_words_2(some_words), number=10000000) print(f'{ans_1}: {ans_1_time}') # aa dd: 29.5462521 print(f'{ans_2}: {ans_2_time}') # aa dd: 29.923632399999995

[@mondegriz]

Вот вам один проход, не тупите. скинет все слова с минимальной длиной за один проход. function linearSearch(strings) { let minLen = strings[0].length; let arr = []; for (const word of strings) { if (word.length < minLen) { minLen = word.length; arr = [word]; } else if (word.length === minLen) { arr.push(word); } } return arr.join(' '); }

[@user-th4qi8iv3q]

Спасибо

[@iptashR]

В задаче на собеседование можно счётчик добавить, и если встретили новый символ,добавить цифру в выходную строку, а счётчик обнулить?

[@iptashR]

В задаче на собеседование можно счётчик добавить, и если встретили новый символ,добавить цифру в выходную строку, а счётчик обнулить?