Задача из Собеседования в Amazon за 5 минут

[@sashalukin]

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

[@АлексРоман-й9ю]

На собеседовании в амазон: -Вы умеете не ходить в туалет 12 часов? -Да -Вы приняты.

[@and7770999]

На собеседовании в ЕА Games - Вы радикальная феминистка? - Да - Вы приняты.

[@lockstock5357]

После того когда находишь более менее краткий путь к нужному результату всегда так на душе приятно становится. Внутренний перфекционист удовлетворен.

[@igor_yanovich]

Неприятно только одно, чтобы найти этот краткий путь, пришлось перебрать все пути не краткие 🤣

[@СаняДоцент]

И всегда найдётся азиат, который сделает это быстрее и лучше)

[@and7770999]

Только под массовость такое решение не подойдет. А значит придется писать отдельный код под разные матрицы

[@and7770999]

Самый лучший путь решения - отдать любому индусу на аутсорс))

[@philipp4631]

5:10 ну как так-то хоть бы на словах надо было метод золотого сечения упомянуть да и вообще можно тупо делить пополам.

[@igor_yanovich]

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

[@andrewmurruvyov4359]

Вероятность появления такой пары оригинальных (преподаватель;вопрос) мала, поэтому метод опроса надежен

[@igor_yanovich]

@@andrewmurruvyov4359 Это я к тому, что нафига вообще рассматривать методы решения задач, ну вот знаете вы как решить эту конкретную задачу в гугл на миллион долларов в год, а дай вам новую как всё хорошее и закончится, и нифига вы её уже не решите, потому что вы как этот парень из универа, вместо того чтобы учиться решать самому, тупо спрашивал у всех и перебирал все возможные варианты, а сам решать так и не научился, надо учится самому решать, а не смотреть на решения других людей и думать что теперь я мега умный и сам смогу решить такую задачу. Как говорится: всё просто когда знаешь как, а если не знаешь, то и таблица умножения кажется мега сложной задачей.

[@andrewmurruvyov4359]

Экзамен сдаёт не тот кто умеет решать, а кто умеет сдавать, и на работу устраивается не тот кто может работать, а кто может проходить интервью

[@igor_yanovich]

@@andrewmurruvyov4359 как правило такие говноработники которые не умеют работать, а умеют устраиваться, потом долго не работают. потому что потом уже НАДО РАБОТАТЬ, а не сдавать 🤣🤣🤣

[@СтаниславВокеутов-ю2э]

@@andrewmurruvyov4359 а как этому научиться, если ты бездарь?

[@baksonyan4ik]

Офигеть, до твоих видео вообще не решал алгоритмы и оказывается они намного легче чем я думал. Да и это видео просто change my mind

[@freedomtv2295]

Когда объяснение под рукой то кажется легче, чем есть на самом деле На самом деле самому решать не так легко

[@Hello-g5b3p]

А что забавнее, что эти задачи мало кто решает так изящно сам по себе, фактически все учат только принципы и шаблоны, которых не так много. Это большой труд, но как это помогает определить хорошего программиста - вопрос :)

[@baksonyan4ik]

@@Hello-g5b3p не программисту будет лень

[@Монологиожелезках]

@@Hello-g5b3p, всё зависит от того, для решения каких задач нужен программист. Хороший программист для одних, ужасен для других. Скажем, задача та же, только у в распоряжении лишь три регистра и только один из них имеет ёмкость достаточную для указания на ячейку в матрице, при этом никто не лимитирует алгоритм по времени. Практическое применение: микроконтроллер без ОЗУ, все прочие регистры заняты другими данными всей микропрограммы, а её частью является алгоритм, микроконтроллер может 16 MIPS, а управляет дверным замком (то есть, даже если на сравнение уйдёт 30000 выполненных операций для матрицы 6*7, то это всего лишь задержка 0,001875 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере. Так что, да, очень актуальен вопрос - как определить хорошего программиста?

[@kirillschcerbinin7068]

как всегда кайф смотреть, хорошо сделано! подача отличная, даже я всё понял, не зная ничего об этом! давай еще и побольше лайв контента!)

[@Nikolas_Z]

Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация

[@The14Some1]

опиши алгоритм

[@РоманБондарь-м3е]

При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла. Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.

[@Magicrafter]

@@РоманБондарь-м3е Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.

[@Монологиожелезках]

Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами". Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.

[@AHTOHMAK]

Я тоже не понял разницы начинать именно справа

[@whitesteel2909]

проблема взялась из ниоткуда и мужественно решена ... браво

[@SDesuu]

Так суть программирования в том что всегда появляются "проблемы" которые нужно "мужественно" решать)

[@andreyradostny]

Такая чистая, приятная и понятная подача, спасибо!

[@artemspiridovich2695]

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

[@martintopchyan4399]

we can do 2 binary searches, firstly we can go through the rows and find the right row(if the target is greater than the midRow's last element then startRow=midRow+1), and then do a binary search only for that row, in that case we will have O(logn + logm).

[@DavidPotskhishvili-gp1km]

This won't work. Try to find 8 using your algorithm in the example provided in the video.

[@dmitryzhuk220]

Однако решить с такой сложностью всё таки можно если заметить, что для произвольного элемента m[i][j]

[@mrseeker9075]

@@dmitryzhuk220 Не скажу что быстрее чем в видео нельзя решить, я как раз сейчас думаю над этим, но если элемент m[i][j] < k, то можно сказать лишь что наш элемент находится НЕ выше и левее, а иначе НЕ ниже и правее, то есть мы можем отрезать прямоугольную подматрицу в которой элемент не находится, но не выделить онную

[@dmitryzhuk220]

@@mrseeker9075 о, действительно, спасибо за уточнение

[@kiryl5476]

​@@mrseeker9075по идее матрицу можно нарезать на 4 меньшие матрицы (относительно ключевого элемента в центре) а потом рекурсивно повторять алгоритм до размера в 1 элемент и просто проверять этот 1 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах

[@shadow_blader192]

2:39 def searchMatrix(matrix,k): return any([k in row for row in matrix]) Решение в строку

[@sunrizz]

Удивительно, но почему то сразу пришел к такому решения 😮 Задача крута! Спасибо!

[@diplodogs]

Примерно такое же решение с поиском таргетного числа вокруг текущего в голову пришло, Только мне пришло в голову стартовой точкой задать не верхний правый угол а середину (по аналогии с бинарным поиском). В результате при прогоне данной матрицы от 0 до 36, разница в шагах внутри цикла составила 214 (твое решение со стартовой точкой в углу) против 127 со стартовой точкой в центре. Центр находил абсолютно банально через Math.floor(arr.length / 2) и Math.floor((arr[0].length - 1) / 2); Вроде как шустрее почти в два раза получается :) Спасибо за задачу!

[@ТёмикГоловин-й8ц]

Тоже самое подумал, про центр сразу. Да и к тому же можно внести ещё одну оптимизацию, тем более если известен характер чисел (насколько случайные числа были отсортированы и какая случайность использовалась) Можно брать не крайний верхний угол, а относительный порядковый номер диагонали беря во внимание крайние значения таблицы. К примеру видим что таблица начинается с 1 и заканчивается 36. А надо найти число 14, тогда делим искомое число, на разницу начального числа таблицы и конечного. Получаем 0.4. Далее умножаем 0.4 на размерность таблицы и далее округляем числа. И получаем координату оптимального старта поиска, чем линейнее распределение, тем точнее будет координата старта.

[@The14Some1]

@@ТёмикГоловин-й8ц Никто не обещал линейного распределения. А где такие задания на собеседования даются?

[@ТёмикГоловин-й8ц]

@@The14Some1 Понятное дело не обещал. Просто так алгоритм будет работать быстрее на больших размерностях и при разных функциях распределениях и незначительно медленнее на малых размерностях и не линейных функциях распределения

[@yjrus1807]

Блин, это так просто и так гениально... мне стыдно, что я не додумался до такого решения сам

[@noki1614]

жиза

[@alexanders8928]

ты просто всю жизь не курил и не бухал и мухоморы не жевал. А Бог - есть!

[@AwakenDrow]

@@alexanders8928 Обычно, когда вспоминаешь все мухоморные дела, ты уже сеньор))

[@and7770999]

Еще проще решение - копируешь цифры в чат gpt и просишь его найти нужное))

[@opusmode]

Это вообще не гениально. Это очень даже тупо.

[@artemspiridovich2695]

но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз

[@Meafel]

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

[@47clere]

Сразу подумал что нужно идти по диагонали. Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим. Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2 Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.

[@ildarfattahov6441]

Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM

[@denisgluk431]

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

[@nester7315]

А зачем бинарный поиск? Мы по порядку идём. Он на больших массивах только замедлит.

[@and7770999]

А если матрица с рандомными числами будет? Придется переделывать

[@oleksiikolotylenko1004]

Ага)

[@dmytrozazulin1858]

Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.

[@iqfunru]

А мне показалось, что надо начинать с середины матрицы по типу двоичного поиска: 16 > 14, поэтому примерно четверть матрицы вправо и вниз от 16-ти не подходит. И т.д....

[@lironblank6204]

если постараться можно уменьшить до O(log(n)+log(m)) для этого надо заменить нахождение спомощю шагов на два бинарных поиска

[@desmosmech7037]

Если постараться... Как ты поймешь что пора заканчивать делать бин. поиск по текущей оси и пора начинать делать бин. поиск по другой?

[@smarthedgehog3185]

@@desmosmech7037 Признак конца поиска по строкам это два соседа один меньше другой больше бери меньший и ищи в этой строке

[@roket132]

@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)

[@a_alex_l2041]

Мне кажется человек не понял задачу. Но чтоб получить такую асимптотику надо сделать мёрдж, в один массив, но без пред обработки удачи.

[@smarthedgehog3185]

@@roket132 Мы ищем сначало строку а потом в строке нужное поле. В строке между 10 и 18 есть 14. 14 какраза в строе с 10

[@IlyaBoltaev]

можно еще бинарным поиском попрбовать. Делим на 4 квадранта, смотрим в каждом из них левое верхнее и правое нижнее, и сравниваем с искомым. Например, если первоначальным разбиением взять за центр 16, то правый нижний квадрант можно отсечь и левый верхний квадрант можно отсечь. Далее рекурсивно ищем в правом верхнем и в левом нижнем.

[@VishnevskyMike]

Тоже об этом подумал. Тогда сложно сложность О(log_2(m+n)). Еще быстрее выходит.

[@denisgluk431]

@@VishnevskyMike в две подматрицы залядывать часто придётся.. а это всё равно на начальную оценку похоже.. O(n)

[@IlyaBoltaev]

@@denisgluk431 нет. Даже если в 3 подматрицы придется заглядывать, оценка будет логарифмической, так как на каждой итерации пространство поиска сужается на множитель, а не на константу. А в более чем 3 подматрицы смотреть гарантированно будет не нужно.

[@alexnedelin7646]

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

[@Hello-g5b3p]

Найди по этому алгоритму число 7 или 11

[@The14Some1]

не работает. Тебя может увести слишком далеко вправо, или слишком далеко вниз.

[@ILikeActions]

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

[@goldstein1]

С возвращением, Саша. Так мало качественных разборов нынче!

[@yoptaman9000]

Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.

[@OstapP]

Ваш алгоритм даст быстрый неправильный овет для 11, 12, 15, 16, ....

[@yoptaman9000]

@@OstapP я написал не то что подумал, бинарным поиском искать и столбец и строку. Ответ будет правильным так как и там и там отсортированные множества

[@OstapP]

@@yoptaman9000 , можно этапно? Я не понял ваш алгоритм.

[@TheAstralopitek]

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

[@oleksandr2234]

Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже. А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.

[@TheAstralopitek]

@@oleksandr2234 да, я тоже об этом подумал, но в целом ожидаю что ускорение до 2 раз реально

[@danila_firstt]

отличное объяснение, надо больше таких накидать Александр)

[@RedBallOfLove]

Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.

[@The14Some1]

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

[@ИванПетров-й3г6ъ]

Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю. Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска. Спасибо за задачу! Понравилась.

[@Anton_K15]

Я так же подумал, но понял что делается одно лишнее движение каретки с лева на право. А потом в итоге каретка движется с права на лево и в низ.

[@ОлегКуликов-ж7щ]

Чувак, я ничего не понял что ты сказал. Но когда ты стал говорить, ты достучался до моего сердца

[@bel8504]

Круто. А главное красиво.Лично мне первое пришедшее в голову решение было: 1) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё. В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.

[@hod-pj]

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

[@QuarkWasp]

Да, этот способ является самым эффективным и называется двоичным поиском.

[@OstapP]

​@@QuarkWasp, двоичный поиск работает с линейными массивами. Такую матрицу к линейному массиву свести очень дорого.

[@artempogorelov1934]

Чем бинарный поиск числа с минимальной разницей от искомого по строке и столбцу хуже? Таким образом находится следующая строка и столбец. O(log n + log m), разве нет?

[@zemamba]

Александр, крутые видео, записывай ещё ) интересно было бы про все этапы собеседования услышать в одном ролике

[@Vitek_23]

До такого решения не додумался бы сам, по крайней мере за 10 минут. Спасибо за пример!

[@vasiliypupkin6311]

❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.

[@DragonsLord76]

Можно ещё быстрее, если начинать проверку с любой цифры в центре матрицы. Тогда ты найдёшь ответ в среднем В ДВА РАЗА БЫСТРЕЕ, чем ты показал. Это вааще очевидно.

[@maksimkolokater6376]

а нельзя ли тут дважды воспользоваться бинпоиском (по столбцам и строкам), тогда O(log n + log m) будет, что быстрее, чем O(n + m)? @СашаЛукин

[@fallerviktor]

А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?

[@chalex2k]

А идея хорошая, если это правильный алгоритм, сложность будет log(n+m). По сути бинпоиск по диагонали

[@iGeen7]

с какого перепугу O(n+m) это оптимальное решение?

[@АлександрКраснов-н5ж]

Друг, есть более быстрый способ. Первое, проверяем число в ячейке 1,1 и m,n убеждаемся что число К в середине и переборку начинаем с середины в таком случае получаем O((m+n)/2). Можно конечно и не проверять начало с концом тогда, тогда, если брать худший сценарий будет еще быстрее, однако если брать лучший сценарий то можно и без переборки сказать что нет числа в матрице

[@Rofelka]

Что есть середина матрицы 2х10? Мы должны курсор поставить в 1,5? А, может, в 2,6? Но мысль красивая с проверкой 1,1 и m,n. Если искомое число не в матрице (меньше наименьшего элемента или больше наибольшего), то выполним за 1 или 2 операции)

[@АлександрКраснов-н5ж]

@@Rofelka в предложенной Вами матрице 1,5 1,6 2,5 2,6 равнозначны

[@SayXaNow]

@@АлександрКраснов-н5ж Допустим дана матрица 100х200, надо найти число К=14. Вы начали с середины, там число 50. Все что вы теперь знаете, это то, что правую нижнюю часть можно отбросить. Но куда теперь вам дальше двигаться? Число К может быть в любой из трёх оставшихся областей. Причем оно может быть как левее середины, так и правее, как ниже середины, так и выше.

[@АлександрКраснов-н5ж]

@@SayXaNow точно, мой способ получается О(1.5 (m+n))

[@leofender5753]

@@SayXaNow а если дальше опять повторить ход в середину оставшейся области? то есть по сути всегда делим на 2 и сверяем....и того вместо 7 будет 5 ходов

[@Kozlov_Production]

А почему не пойти из левого верхнего угла по столбцам вниз? Как дойдём до 18, вернуться назад к 10ти и пойти вправо до 14ти.

[@niqr7800]

Можно так же с левого нижнего угла начинать. Там работают теже правила, только в другом направлении

[@kaxan1407]

С левого верхнего угла тоже можно.

[@niqr7800]

@@kaxan1407 Вообще-то нет)) У тебя с обоих сторон числа больше в таком случае. Ты просто не можешь определить, куда идти

[@kaxan1407]

@@niqr7800 да, я понел что в общем случае это не сработает минут через 5 после написания коммента

[@AlexanderZinchenko]

Давно ли трудоёмкость считается по максимальному количеству шагов, а не по среднему среди набора различных исходных данных? Трудоёмкость равна O((m + n) / 2).

[@SayXaNow]

все хорошо, но только O((m + n) / 2) = O(m + n), равно как и O(100n + 2000) = O(n). Я понимаю, что ты пытаешься сказать, но О() обозначает временную сложность алгоритма и характеризует степень роста времени в зависимости от входных данных. И временные затраты для среднего случая при увеличении m и n увеличатся во столько же раз, во сколько раз увеличатся временные затраты для худшего случая. Поэтому говорят, что у них одинаковая временная сложность. Но если ты хочешь найти и оценить среднее время работы алгоритма, тебе тогда не следует употреблять запись О().

[@AlexanderZinchenko]

@@SayXaNow Несогласен я. Первое, разве "трудоёмкость" и "время работы алгоритма" не одно и тоже в данном контексте? Второе, есть задачи, где трудоёмкость не зависит от исходных данных. Например, в данной задаче будем дальше строить змейку из чисел до левого нижнего угла. Тогда трудоёмкость всегда будет O(m+n). По вашему выходит, что трудоёмкость обоих задач одинакова, но это же не так. Или более наглядный пример, трудоёмкость пузырька O(n*n/2) всегда, а qsort средняя O(n*log(n)) максимальная O(n*n). Я считаю, что qsort быстрее, а по вашей логике - пузырёк (!).

[@SayXaNow]

@@AlexanderZinchenko какая-то каша у вас в голове. Вы не знаете определения временной сложности. И занимаетесь какой-то нелепой подменой понятий. Перечитайте мой довод выше, а лучше загуглите, что такое O(). Если лень вот цитата: "Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты" Чувствуете? Вся соль в конечной записи, чтобы оценить как растут временные затраты с увеличением N, а не фактическое количество шагов. Для асимптоматики нет разницы между O(100(M+N)), O((M+N)/2) и O(M+N) - у алгоритмов разное фактическое время работы, но все это линейная сложность и записывается единой оценкой O(M+N). Еще раз - запись O() применяется, чтобы понять поведение временных затрат при изменении входных данных , а не вычислить их точно. Ваш пример с пузырьком не понятен, согласно моей логике (хотя это не моя логика, а общепринятая нотация) среднее время пузырька O(N*(N-1)/2) = O(N^2), худшее O(N*(N-1)/2) = O(N^2) квиксорт среднее O(N*log(N)). худшее O(N^2) где вы увидели, что пузырек лучше? для худшего случая временные сложности одинаковы O(N^2), для среднего они разные O(N*log(N)) - линейно-логарифмическая лучше, чем O(N^2) - квадратичная. Разумеется что O(N*log(N)) не эквивалентно O(N^2) - это два разных класса сложности. А то, что вы пытаетесь сказать, к О() нотации никакого отношения не имеет. Ваша неизвестно откуда взятая трудоёмкость еще и непонятно что характеризует. Количество шагов? Пример: средне количество шагов для нашей матрицы M х N равно (M+N)/2, средне количество шагов для последовательного поиска в одномерном неупорядоченном массиве длиной M+N тоже (M+N)/2, но поиск в одномерном массиве всегда быстрее. Но как так? Трудоёмкость же одинакова. Или заполнение массива M+N числом имеет количество шагов M+N, но будет выполнятся быстрее, чем поиск в матрице с (M+N)/2 шагами. Тоже парадокс, согласно вашей "трудоемкости" все должно быть наоборот. Поэтому все, что мы можем сказать, это что они одинаковой временной сложности O(M+N). Держите в голове тот факт, что O() - это абстрактное понятие, тип сложности, а не точное время выполнения.

[@kpa3uk]

а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)

[@Morideca]

Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор) ТЕм более что условие задачи поставило конкретное число, а не рандомное

[@chalex2k]

Вау! Красивое решение! Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.

[@ПетроМетро-я6г]

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

[@denisgluk431]

Пойму тут O(n) получается, т.е. максимальный путь 2n.. меньше не придумаешь

[@АлГрин-з2ш]

@@denisgluk431 В этом алгоритме. Если начинать не с правого верхнего, а n/2 в первой строке и также потом, при спуске. Пример, n=1000, m=2

[@НикитаВладиславовичБерезников]

Почему нельзя проверить сразу число по средине. Если К больше того, что по середине, идти нужно к правому, если оно меньше правого, то прочёсываем числа вверх по матрице?

[@_Kio_]

Самое быстрое решение, которое я смог найти, вот такое: Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа. Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части. Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.

[@astashch]

мне тоже кажется делить на квадраты интересная идея, первое что пришло на ум, до просмотра решения)

[@diplodogs]

Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим

[@yuvis_cr]

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

[@allex-all]

Как я и думал, можно за log(m+n)

[@lotgon911]

Ты можешь исключить только один квадрат за шаг

[@КсенияЛабутина-к3с]

А почему не сделать бинпоиск по главной диагонали, за log(n) найти пару чисел на главной диагонали (x, y) и (x+1, y+1), между которыми расположено наше и дальше наше искомое число может находиться либо в строке x+1, либо в столбце y+1, и там и там делаем также бинпоиск. Получается 2 log(n) + log(m), то есть O(log(n) + log(m))

[@SayXaNow]

Потому что искомое число может находится справа от столбца y+1 вплоть до последнего, а так же ниже строки x+1 вплоть до самой нижней строки. А значит проверка только строки x+1 и столбца y+1 гарантированно число не найдёт.

[@gameflamedev]

То, что сразу полезло в голову: 1) Проходимся по каждому элементу первой строки и ищём первое число, которое будет больше k 2) Делаем то же, но для первого столбца 3) Ограничиваем область поиска k найденными ранее элементами массива 4) Используем любой поиск. В худшем случае ограничение у нас займёт O(n+m), а поиск - O(n1 * m1), где n1 и m1 - элементы-ограничители (при прохождении по каждому элементу).

[@ДаниилЧерных-к1б]

Ух-ты, тоже это в голову пришло

[@realvaniog]

Можно еще ограничивать область если найти число которое меньше k (не рассматривать левую верхнюю область). И тогда такое решение может быть даже быстрее чем то которое рассказали.

[@OstapP]

​@@realvaniog, объясните пошагово. Звучит как бред.

[@OstapP]

В худшем случае (k>18), а это почти половина возможных k, размер матрицы не уменьшается. Но ваше решение натолкнуло меня на другое. Нужно, чтобы опытный алгоритмист проверил, может я тоже не прав. Решение: 1) в первой строке доходим до последнего =к. Зачеркиваем для себя все, что ниже. 3) в уже ограниченой матрице идем по первому столбцу до последнего =к. Зачеркиваем для себя, все что левее. Проходки логично делать бинарным поиском. Если я все правильно понимаю по крайней мере в этой таблице за эти 4 этапа находим наше число. Если таблица больше надо пример, чтобы понять что дальше делать, но так мы гарантированно сильно уменьшаем зону поиска. Получается 2log(m) + 2log(n)

[@realvaniog]

@@OstapP Если нашли число меньшее k, то нам не подходят все числа которые (одновременно) левее и выше этого найденного числа (там все числа меньше k). Аналогично с числом большим k. Т.о любое число неравное k ограничивает нашу область поиска.

[@MrYuriyP]

Если на то пошло, то оптимальней сначала найти угол с наиболее близким числом и плясать от него. Код увеличится, зато выпоняться будет быстрее всего для любого числа.

[@dmytrozazulin1858]

бред

[@core2mind]

Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 1e12 x 1e12 (абстрактная большая цифра). Может стоить добавить в код условие про то, что если k < верхнего левого угла || k > нижнего правого угла, то искать нет смысла (false).

[@VasillaRobocraft]

Ну как раз на этом этапе можно использовать бинарный поиск

[@dmytrozazulin1858]

В этой матрице выполняется условие, что все элементы левее и выше меньше или равно текущего элемента, а все элементы правее и ниже - больше текущего элемента. Об элементах левее и ниже и правее и выше ничего однозначно сказать нельзя. Среди них могут встречаться меньшие, равные или большие. Поэтому матрицу надо проходить до конца.

[@core2mind]

@@dmytrozazulin1858 , по-моему вы либо не так интерпретируете мое сообщение, или не так интерпретируете условие. Простой вопрос: Если в правом нижнем углу матрицы значение, равное 500, может ли в матрице быть значение, например, 501? Если да, составьте пример такой матрицы, я посмотрю, как вы это сделаете, не нарушая условий

[@dmytrozazulin1858]

@@core2mind Ясно, я думал вы хотите внести коррективы в сам процесс поиска. А это просто проверка вырожденного случая.

[@core2mind]

@@dmytrozazulin1858 , ну это по сути внесение изменений в алгоритм поиска, но не в алгоритм скана матрицы самой. Если у нас матрица триллион x триллион, есть ли смысл долго по ней ходить, если за константное время можно сразу сделать вывод, что ходить по ней нет смысла. Я это хотел донести, если что. В алгоритме, представленном в видео, уже есть предварительные проверки перед сканированием матрицы, мой поинт был лишь в том, что возможно стоит расширить эти проверки.

[@ypolonskiy]

Probably we can go under linear complexity, to the log(sqrt(a^2+b^2))

[@ПростоЧеловек-н7э]

Изменено: не работает( Мне кажется есть не менее эффективный способ, хотя хз насколько он будет лучше в коде. 1) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3) 2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10) 3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14. 4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось. В чем же преимущество этого метода? Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36) В случае описанном в видео 10. (Если ищем число 18)

[@desmosmech7037]

Найди число 11 по даному алгоритму

[@smarthedgehog3185]

@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет. Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину. В Численных методах этот метод ещё называли поиском льва в пустыне :) Грубо говоря там можно и площади делить отрезком. Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.

[@ПростоЧеловек-н7э]

@@desmosmech7037 верно, спасибо что сказал.

[@ПавелМельников-х8м]

Ваше решение занимает, на данном примере, 7 шагов. Мое 5-6. Именно с угла, откуда, по Вашим словам, нет смысла начинать. А именно. Смотрим первую цифру. Если =14, то тру. Если больше - фолз. Если меньше - делаем шаг n+1 и m+1. Т.е. по диагонали. Те же условия, за исключением того, что если больше 14, то проверяем 2 числа по краям диагонали. Итого, в конкретном примере, Ваше решение идет по числам 16-15-11-12-16-9-14, выдавая "тру" с седьмой проверки. Мое идет по 1-5-9-17-16-14 (или 1-5-9-17-14) выдавая результат с 5-6 раза. Всего, максимум шагов, для проверки всех чисел матрицы, у Вас может быть 10 (кратчайший прямой путь от верхнего правого до нижнего левого угла). В моем случае - 7. 5 на диагональ - 2 на проверку рядом с диагональю. (в данном примере, после числа 30 проверяется 36 и 27, если они были бы меньше или равны 14). Отсюда вывод - Ваше решение не оптимально. Могу кодом, если так проще воспринимать.

[@SayXaNow]

k = 18. Алгоритм за 7 шагов сказал, что такого числа нет. Двигатель шаттла №18 не запустился, ракета упала.

[@ПавелМельников-х8м]

@@SayXaNow примерно так, да. Проглючило. Даже не задумался, что оно не на диагонали может быть) Сам потом понял, но уже не стал ничего удалять)

[@Proezdom-zx2tl]

В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 16. Ну и идти придётся не в одну сторону, а в зависимости от сравнения. В данном конкретном случае дойдём до 14 за 2 хода 🙂

[@Mustitz]

Ну да, первое желание всё-таки получить $O(\ln n + \ln m)$, а не $O(n+m)$...

[@SayXaNow]

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

[@dmitry7464]

@@SayXaNowтоже подумал о бинарном поиске

[@Proezdom-zx2tl]

@@SayXaNow Я вот как думаю: - В принципе даже условие задачи не совсем строгое - что такое самый быстрый (или оптимальный) алгоритм поиска? - В общем случае я вижу как минимум 2 интерпретации. - 1 - Минимальное количество шагов в среднем. - 2 - Минимизировать количество шагов для самого плохого случая. Очевидно, что алгиритмы получатся разные. Для второго алгоритма, особенно для большого количества рядов (например 1 000 000 000) не оптимально двигаться последовательно по лесенке. Надо целый массив разбивать на кучки (на 2, а лучше на 3), проверять граничные условия прыгая из одной в другую и убирать целые кучки (суб массивы). Когда осталась кучка небольшого размера (надо считать какого), тогда уже можно идти по лесенке от верхнего правого угла... Ну может я и не прав???

[@SayXaNow]

@@Proezdom-zx2tl Ну задача с подвохом. я всегда топил и топлю за бинарный алгоритм. В матрице случайных упорядоченных значений размером 2500х10000 он показывает скорость нахождения любого элемента в среднем за 67 шагов. Казалось бы - фантастика, ну что за лохи вообще топят за этот линейный аутизм, ведь налицо логарифмическая скорость. Но надо учесть один нюанс. могут попадаться квадратные блоки данных, в которых числа расположены особым образом и полностью удовлетворяют условию задачи (правее всегда числа больше, снизу от любого числа тоже всегда больше), но для которых не существует в принципе алгоритма быстрее, чем линейный ступеньками. И если вдруг в моей матрице мне попался именно такой блок размером 2500х2500 то максимально неудачный расклад для бинарного поиска составит 50000 шагов и примерно 15000 в среднем для любого числа такого блока. Не трудно посчитать что неторопливый линейный тут покажет лучший результат. И т.к. никаким способом нельзя быстро проверить попался нам такой блок или нет, я бы не рискнул использовать быструю бинарку для слишком больших квадратных матриц. Сначала бы убедился что большая сторона M превосходит меньшую N хотя бы в 5 раз. А если ярко выраженная прямоугольная длинная типа 1000х17000 - тут даже обсуждать нечего - только бинарный поиск. Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.

[@poster-bot]

а можно ведь и за 2*log(N). В начале бинарный поиск по колонке, проверяем верхнюю и нижнюю колонку. Если два последних числа в верхней и нижней колонке больше искомого идем внизу, если оба меньше вверх. Если в верхней колонке число меньше искомого, а в нижней нет - мы нашли нужную колонку за O(n) А дальше уже стандартный бинарный поиск по столбцу

[@inanimatorum]

Отлично, первая же идея была довольно близка. Осталось самую малость, научиться кодить 😅

[@kostyajan]

Правый верхний угол можно найти дихотомией, что даст еще меньшую оценку, О(logn + m). Далее идти по "диогоналям" можно не поэлементно а также дихотомией, что в общем случае даст O(log n + log m). Такое конечно за 15 минут не написать, но устно я бы обязательно упомянул про более оптимальные пути поиска.

[@АнтонДанильченко-е6н]

А зачем нужно первое отсечение? Есть инсайдерская информация, что мы так большую часть матрицы выкинем? Дихотомия по диагоналям мне то же пришла в голову, но сложность такого алгоритма останется прежней - O(n+m). Однако ожидаемая сложность такого подхода будет меньше, но не O(log(n)+log(m)), а O(log(n)*log(m)).

[@kostyajan]

@@АнтонДанильченко-е6н, первым отсечением мы сразу уменьшим прямоугольник с m * n до (m-k) * n. В примере на видео - верхний правый элемент с которого можно начинать это 11 (первый элемент меньше 14). Но да, точно, согласен, в случае дихатомаии , оценка будет O(log(m) * log(n)).

[@SayXaNow]

Совершено все верно. Использование дихотомии есть самый эффективный метод. Сам решил дихотомией через диагонали, не так сложно как кажется на первый взгляд, ибо алгоритм дихотомии всем известен наизусть. Диагональная дихотомия - эффективность log(n)^2, где n - наименьшая сторона. Но алгоритм требует рекурсии, т.к. матрица разбивается на каждом шаге на две валидных области, в которых снова применяем алгоритм. Чередующаяся дихотомия по строкам и столбцам - эффективность log(n)*log(m). Код чуть длиннее, но пишется по факту быстрее и понимается лучше. Не требует рекурсии - что огромнейший плюс. Окончательный вариант из видео - это фиаско. Применять последовательный поиск в упорядоченной последовательности - это провал собеседования.

[@АнтонДанильченко-е6н]

@@kostyajan Если по диагоналям отсекать оказывается эффективней, то зачем нужен первый шаг, который может отрезать неопределённое кол-во столбцов (в том числе и 0)?

[@lalkaveka4417]

Первая (и последняя идея) 1)Проверить первый столбец и первую строку на наличие цифр больше 14 и отсечь их. В нашем случае матрица станет 4 на 4. 2) проверить в обратном порядке последний столбец и строку новой матрицы (4 на 4) и отсечь все, что меньше 14. (Осталось 2 на 2) 3) оставшуюся маленькую матрицу просто перебрать А потом я досмотрел видео и в очередной раз понял, что я тупой

[@rumstas1381]

Вот честно поставил на паузу на 2:24: я бы использовал что-то типа волнового алгоритма. Начинаем с элемента (0;0) и смотрим всех его соседей (по 8 направлениям, где это возможно), если среди соседей нет числа К, то перемещаемся на позицию максимального числа; в нашем случае (1;1) со значением 5 и так до тех пор пока у текущего элемента не будет соседа со значением 5, ну плюс ещё условие выхода из цикла со значением false, если вдруг текущее значение стало больше К. Теперь по честному нажимаю play и смотрю дальше 😀

[@SentoxV]

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

[@alexkine8343]

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

[@oleksandr2234]

С последнего столбца начинать удобнее, тк можно двигаться всего по-одному принципу: если необходимое число больше текущего - мы всегда идем вниз, если меньше - всегда влево. Если вы начнете с первого столбца - вам придется либо менять формулу в процессе, либо усложнять ее.

[@vtemv]

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

[@kirpayti]

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

[@MrJloa]

Видимо мы думаем по-разному. Двигаемся с 0,0 по главной диагонали пока значение ячейки не станет больше искомого (17) Далее просто проверяем все значения строки, столбца (17).

[@Selavy82]

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

[@ДимаРубин-т6с]

В худшем случае нет. В худшем следующий левый/нижний будет подходящим, а это уже выйдет в O(mlogm + nlogn)

[@namelessboar]

​@@ДимаРубин-т6с omnomnomnomnom

[@spirridd]

Верхний столбец... Интересно, надо записать.

[@DarthYodaDarth]

А почему отправной точкой является верхнее правое число? Почему другие углы не подойдут?

[@MasterSergius]

Пфф, нашел за секунду: вот оно число, на четвёртой строчке, в третьем столбце

[@anatolyshkerin3569]

Кажется, что задачу можно решить за О(log(m+n)). Надо в упорядоченной линии, которая похожа на диагональ матрицы( длина m+n) найти наибольшее число меньше искомого( это называется правосторонний поиск ). Следующее число будет больше искомого. Вместе они образуют матрицу 2х2. Осталось проверить оставшиеся два элемента матрицы на совпадение с искомым.

[@pavelsologubov4988]

Что насчет такова варианта? (Python) def funk(matrix, target): for i in range(len(matrix)): if sum(matrix[i]) / 4

[@mzmzmzmzmq]

а если попробовать бинарным поиском сначал искать строку, в которой 0-вой элемент ближе всех к К, но меньше K, а потом уже бинарный поиск по этой строке? тогда получится log(n) + log(m), что меньше, чем n+m

[@sangoforto3589]

Я тоже именно так и подумал

[@SayXaNow]

Вы на верном пути, дам подсказку: log(n) + log(m) у вас не выйдет, т.к. вы не сможете гарантированно за два бинарных поиска найти число, но вот log(n)*log(m) - один из лучших вариантов. Про окончательный ответ из видео забудьте. Последовательный поиск вместо бинарного в упорядоченной последовательности - это провал собеседования. Хуже только перебор всех значений, зато в одну строчку.

[@mzmzmzmzmq]

@@SayXaNow почему за суму логов не выйдет?

[@mzmzmzmzmq]

@@SayXaNow можно ведь найти число не точно искомое, но рядом с ним стоящее за лог

[@SayXaNow]

@@mzmzmzmzmq за первый лог N для строки вы нашли максимально близкое к К и знаете теперь ограничение конца строки - допустим это индекс I. За второй лог по М вы нашли в столбце I максимально близкое к К число и знаете теперь ограничение длинны столбца, допустим это индекс J. Вы использовали два лога, но у вас еще осталась непроверенная область [0, 0, J, I] дл которой нужно повторить операцию. Так понятнее? За сумму логов вы лишь сократите область поиска, но гарантированно К не найдете.

[@progressiveaccount3270]

Отличный формат!

[@AlexeyMihaylovBSS]

Задача понятна. Возникает вопрос, а почему идём с правого верхнего угла? Чисто логически можно идти с любого угла. Принцип одинаковый. С другой стороны если вопрос стоит в скорости то можно попробовать идти с центра. Это если требуется среднюю скорость поиска уменьшить.

[@nikolayvavilin583]

Если идти допустим с левого верхнего. Видим 1, а надо найти 14. Куда идти? Вправо или вниз?

[@oleksandr2234]

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

[@leonidalexeev4098]

Для любого числа можно уменьшить фактическое время вычисления. Если определить с верхнего правого угла или с нижнего левого угла начать выполнение представленного алгоритма. Путем сравнения в два шага. Да, добавляется несколько действий. Но статистически это ухудшит время только для чисел, находящихся по центру. А фактически это увеличит скорость для всех остальных случаев, когда искомое находится дальше центра при отсчете с верхнего угла (начала пути алгоритма).

[@leofender5753]

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

[@leonidalexeev4098]

@@leofender5753 это алгоритм поиска кратчайшего пути. Более оптимизированный чем в видео.

[@leofender5753]

@@leonidalexeev4098 да, но при рандоме есть шанс найти нужное число вообще за 1 ход)))

[@leonidalexeev4098]

@@leofender5753 так я предложил вариант не по рандому, а по алгоритму. За 10000 проходов матрицы размером больше 5 будет более быстрое выполнение.

[@MrAlexVelik]

Сделал эту задачу в JavaScript таким образом до того, как посмотрел решение Саши. Как думаете, тут есть O(n+m)? Мне кажется, что это тоже самое, только без цикла while. Всегда ли вложенный массив приведёт в итоге к O(m*n)? Потому что в моём решении нет итераций вообще по всем элементам массива. const findK = (arr, k) => { let row = 0; let column = arr[row].length - 1; for (row; row < arr.length; row++) { for (column; column >= 0; column--) { if (arr[row][column] === k) { return true; } if (k > arr[row][column]) { break; } } } return false; };

[@Антон-ъ6ж2е]

Сделал без while, но с двумя for. Предложенное в видео решение выглядит читабельнее. Сложность обоих решений одинаковая - O(m + n)

[@k083r]

Можно сделать функцию, которая ищет в упорядоченном массиве заданное число, если не находит, то возвращает следующее по убыванию и его индекс. Тогда алгоритм выглядел бы так: делаем поиск в первой строчке [1..16] находим 11 и его индекс 3 делаем поиск в первом столбце [1..18] находим 10 и индекс 3 останется сделать поиск заданного числа в подстолбце (0, 3)-(3, 3) это числа [11, 12, 16, 17] и в подстрочке (3, 0)-(3, 3), где значения [10, 13, 14, 17] сложность не умею точно считать, но вроде должно быть в среднем 1.5*O(log n) + 1.5*O(log m), о том что можно идти змейкой как-то не догадался)

[@nakolenke]

Спасибо за видео. А объясни, пожалуйста, подробнее, почему в последнем решении был выбран именно правый верхний "угол"? Почему не левый нижний, например, или тут нет разницы? А если взять левый верхний (или правый нижний) угол, то сразу можно определить, есть ли вообще искомое число в этой матрице.

[@imishka]

Разницы между правым верхним и левым нижним нет, просто идти сверху вниз психологически приятнее (но назад), чем слева направо (но вверх)

[@KDR816]

можно сравнить размеры сторон и идти по той стороне, где за шаг отбрасывается больше всего элементов (если ширина больше высоты, то отбрасывать строки). А еще начать искать из середины, а не с конца быстрее, сразу отбрасывается 50% матрицы, а не строка/столбец

[@imishka]

@@KDR816 Не важно что больше ширина или высота если числа нет в матрице то пройдет m+n действий в независимости что (m или n) больше. Вы все равно идете либо по вертикали либо по горизонтали отбрасывая числа соответственно по вертикали или горизонтали Что касается середины то особо толком ничего не отбросится. Например вам надо найти число 14 вы тыкаете в середину матрицы а там число 17 (большее) это значит что в четверти матрицы которая ниже и правее таких чисел нет, но туда вы и не попадете при алгоритме который был разобран. Соответствеенно вам надо сделать либо шаг вверх т.к. там число меньше 17 (и также двигаясь попадете в верхний правый угол) либо вам нужно двигаться влево так как там тоже число меньше 17 и таким образом попадете в нижний левый угол, затратив при этом n+m действий

[@allex-all]

​@@imishka как это не попадём в правый нижний угол. В общем случае хоть куда можно попасть так то)

[@oleksandr2234]

Правый-верхний и левый-нижний тут равнозначны - можно и так, и так - решение будет аналогичное.

[@sergeymatpoc]

да, так же подумал как в решении, только сравнивать не "то что меньше", а "то что больше" (возможно менее эффективное решение). Т.е. если K больше чем a(n-1,m) то двигаться вниз. И еще я бы ввел проверку на "крайние" условия типа к !=0 и a(n,m) >=k

[@АртёмЗлобин-ю6г]

а что мешает и в этом решении начать не с верхнего правого угла, а с середины матрицы?

[@oleksandr2234]

С верзнего-правого или нижнего-левого получаем простую формулу: если нужное число менье текущего - идем всегда влево, если больше - всегда вниз.. С середины мы такую формулу не получим, тк у нас нет однозначного ответа - идти от числа 16 вверх, или налево (или от числа 9 - вниз или вправо).

[@alexeymironenkov]

Саша, не понял, зачем начинать именно с правого верхнего угла. Почему не с левого? Я б начинал сверху откуда-нить из m*(14-a_11)/(a_m1-a_11), где m - число столбцов

[@tempaccount8189]

Почему не начинать с "условной" середины (floor(n/2), floor(m/2))?

[@oleksandr2234]

Потому, что начиная с правого верхнего угла мы имеем всегда одно правило: если требуемое число меньше текущего - идем влево, если больше - идем вниз. А если вы начнете с условной середины - вы не можете использовать такое правило. Ну и сложность в итоге будет такой же, ведь O(n/2 + m/2) = O(n+m).

[@tempaccount8189]

@@oleksandr2234 Да, пожалуй я ступил. Нужно делать 4-ре условия вместо 2-х и сложность формально сильно не уменьшается. Экономится пара шагов ценой проверки на каждом шаге еще двух условий, но если считать что вся диагональ уже оптимально, то легче реально с угла идти.

[@mirrerror6740]

Написал на Java. Принцип работы - идем по столбцам, перебираем числа в строках каждого столбца. Когда доходим до числа, которое больше K, - переходим на следующий столбец. Если за это время мы находим число, равное K, то возвращаем истину. Если за все итерации не находим число, равное K, то возвращаем ложь. Сам код: public class Main { public static boolean check(int[][] arr, int k) { int column = 0, m = arr[0].length; while(column < m) { for(int[] ints : arr) { if(ints[column] > k) break; if(ints[column] == k) return true; } column += 1; } return false; } public static void main(String[] args) { int k = 14; int[][] arr = { {1, 4, 7, 11, 15, 16}, {2, 5, 8, 12, 19, 22}, {3, 6, 9, 16, 22, 24}, {10, 13, 14, 17, 24, 27}, {18, 21, 23, 26, 30, 36} }; if(check(arr, k)) System.out.println("The given matrix contains the number " + k + "."); else System.out.println("The given matrix doesn't contain the number " + k + "."); } }

[@natielsanti407]

Спасибо. С нетерпением жду следующего разбора.

[@WeAreTeemo]

а почему бы не начать с элемента массива m/2 с отбрасыванием остатка и n/2 тоже с отбрасыванием остатка и делать тоже самое, быстрее не будет? Пока не шарю как записывается это в виде кода, только начал интересоваться и подобные видео выскакивают.

[@alexanders8928]

Что мешает выполнить двумерный бинарный поиск? Думаю решение в видео неоптимально, т.к. в нем идет линейный двумерный спуск. ИМХО.

[@gNikro]

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

[@powerhead]

Почему нет смысла начинать с левого верхнего угла? Сложность будет та же самая если двигаться вниз и вправо

[@АндрейН-я4й]

Коды читать и писать не умею, но решение 1 в 1. Вот только пришлось подержать паузу подольше. Есть вопрос к условию задачи... Получается нам важно только наличие числа (true/false)? Амазон дополнительно не интересовались сколько чисел "K" в матрице (ведь их в диагональ может быть очень много)?

[@ntbatyr]

Мне кинули задачку. Дан csv файл со списком категорий и подкатегорий _______________ id,name,parent ------------------------ данные в файле в разброс, вложенность неограниченна. Нужно построить дерево без рекурсии. Как это возможно сделать?

[@Fritz131415]

А как всё-таки можно додуматься до этого решения? Само решение понятно, элегантно и всё в этом духе. Чисто на опыте догадаться? Или тут суть как раз в том, что, к примеру, после шага с бинарным поиском по строкам, нужно подумать, что будет оптимальнее - O(n+m), понять, что это такое и реализовывать?

[@BukhalovAV]

Эту задачу можно сравнить с олимпиадными задачами по математике и программированию. Во-первых, да, нужен определённый склад ума, способность находить решения для чего-то, что ранее не изучалось. А во-вторых, большинство успешных олимпиадников берут тем, что до этого нарешивали большое количество других олимпиадных задач, на основе которых нарабатывался навык решения нестандартных задач, а также схожие методы решения похожих задач. Мне как бывшему олимпиаднику сейчас очень помогает быстро разбираться в новом для меня материале. Что же касается подобных собеседований, то без такой вот подготовки вряд ли их пройти. Как олимпиадники нарешивают целые сборники задач, так и будущему программисту Амазон придётся искать и решать опубликованные задачи с предыдущих собеседований других программистов.

[@ДимаРубин-т6с]

Не совсем. Просто сидишь и микробрейнштормишь, как круче использовать данную информацию и как асимптотически решить быстрее. Например, я был почти полностью уверен, что таска решается за O(n + m), поэтому думал, как решить именно за такое время. Примерно так

[@MichailLLevin]

Как додуматься? Дарю способ: берете матрицу побольше на бумаге, ищите сами глазами, потом думаете, а как вы это сделали. Наверняка вы именно лесенкой и искали.

[@ДимаРубин-т6с]

@@MichailLLevin не, а вот это, кажется, неправда. Проблема такого подхода в том, что человек по дефолту запоминает инфу и может её быстро найти/вспомнить, даже если она находилась посередине массива запомневшегося. Тут это мб и прокатит, но из-за специфики человека сам подход плохой

[@gleblyapunov5527]

Есть решение даже за лог(нм) = лог(н) + лог(м). А именно можно бинарить в бинипоиске, проще говоря бинарить площадь прямоугольника в котором предпологаемое число к, для этого берем центральный столбец и бинарим в нем к, нашли первое i не меньшее к, тогда если поделить условно прямоугольник i-ой строкой и центральным столбцом на 4 четверти (типа декартовых) то к точно нету в 2 и 4 четвертях, тогда рекурсивро запускаемя из полученный прямоугольников в 1 и 3 четвертях и решаем задачу за лог(нм)

[@MichailLLevin]

Я так и написал. Останется аккуратно обработать случай, когда один размер станет 1.

[@asaki1k]

Идея хорошая, но оценка времени работы неправильная. Можно придумать такой тест, что ваш алгоритм всегда будет рекурсивно запускаться из двух примерно равных прямоугольников, тогда время работы на этом тесте будет выражаться рекурретной T(nm) = 2 * T(nm/4) + C = O((nm)^log_4(2)) = O(sqrt(nm)), что сопоставимо O(n + m) при n ~= m. (причём я пренебрёг логарифмом от кол-ва строк в рекурренте - просто константу подставил)

[@gleblyapunov5527]

Да, согласен конечно, протупил, очевидно, что лог(нм / 4) * 2 > лог(нм)

[@АнтонДанильченко-е6н]

У меня почти такая же идея пришла в голову (то есть суть сводится к разбиению на 4 четверти и уменьшению площади в два раза). Но можно алгоритм сделать чуть лучше по мат. ожиданию сложности - резать не центральным столбцом, а делать дихотомию по диагонали (из левого верхнего угла). Сложность худшего случая останется такой же (как верно уточнил solacerxt) - O(n+m). Но ожидаемое время работы такого подхода будет O(log(n)*log(m)). Разрез же центральным столбцом ухудшает ожидаемое время работы и приближает его к О(n+m).

[@timur2887]

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

[@Евгений-ч9х3н]

Класс, я бы никогда так не догадался сделать, хотя очень правильный шаг

[@alexanderspeshilov839]

Бинарным поиском можно, только их не 1, а 4 нужно написать (за 10 минут можно не успеть). Пусть сначала область поиска - весь массив. 1. Находим (бин. поиск) последний элемент в первой строке, не превосходящий искомого. Выкидываем область правее данного элемента (там все элементы больше искомого). 2. Находим (бин. поиск) последний элемент в первом столбце, не превосходящий искомого. Выкидываем область ниже данного элемента (там все элементы больше искомого). 3. Находим (опять бин. поиск) первый элемент в последней строке, который больше или равен искомому. Выкидываем область левее данного элемента (там все меньше). 4. Находим (и опять бин. поиск) первый элемент в последнем столбце, который больше или равен искомому. Выкидываем область выше данного элемента (и там все меньше). Повторяем для полученной меньшей области, пока она не схлопнется до 0 или 1 элемента.

[@algoviator]

Можно быстрее. Если идти по диагонали начиная от верхнего угла вниз, то мы каждый раз уменьшаем матрицу возможных решений по обоим измерениям. В итоге - сложность алгоритма: О(М+2) или О(N+2) Зависит от того, какой параметр больше N или M.

[@sandrok14]

Разве так выйдет. К примеру мы ищем число 27. Доходим по диагонали до числа 30. А что потом делать, идти вверх на 24 или влево на 26? Или такой же вариант если ищем число 23. Доходим до 30, а дальше куда идти, оно может быть как где-то наверху (вместо числа 24 в последнем столбце третьем ряду) так и слева, где оно сейчас.

[@dmitriypolynin7273]

@@sandrok14 если заранее не известен размер матрицы, то матрица разделяется на много квадратов, и в каждом ищем. Но поскольку матрицы индексированны, то по вот этим кускам можно не искать, а сразу пройти по углам с максимальным значением, и понять в какой матрице искать, а далее по диогонали как предложил Algoviator

[@DogmatiGwt]

Тоже хотел предложить этот способ. Но все таки он не быстрее. В диагонали может быть два числа, одно меньше искомого, другое больше. Они выделят из матрицы два участка, которые будут независимы и оба могут содержать искомое. Придется проверять оба и получится тот же m+n. Хотя может это и будет быстрее статистически.

[@lukbesson-l2u]

Если начать с центра матрицы - разве это не ускорит решение? Не проверял, но это первое, о чем подумал...

[@hod-pj]

сначала надо проверить ячейки (0;0) и (m-1;n-1) удовлетворяет ли условиям наше число. а затем в центр и оттуда плясать.

[@Igor-tn7mq]

Подскажи, а какой это паттерн на лет код? Жадный алгоритм? ps ты молодец, реально круто объясняешь, материал топ, не пойму откуда столько хэйта, и комментарии людей которые вообще в этом ничего не понимают

[@AP-SLD]

Почему старт именно от правого угла, если в общем случае работает лишь принцип, что в столбцах и строках матрицы значения идут по нарастающей? Причём шаг и размерность чисел не определены, а матрица на экране обозначена как частный случай. Важна ли точка старта, если мы не пытаемся сравнивать N и M с К для поиска эффективной точки старта, или что числа целые это тоже частный случай? Найти число больше K и от него двигаться в сторону уменьшения, в которой ещё не бывал, пока не найдёшь число меньшее K и от него двигаться в сторону увеличения, в которой ещё не бывал.

[@SayXaNow]

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

[@ascukins]

Если сделать бинарный поиск по диагонали, можно решить и за O log(n+m).

[@АнтонДанильченко-е6н]

Не будет такой сложности. В худшем случае так и останется O(n+m). Можно уменьшить ожидаемую сложность, но опять таки не до O(log(n+m)), а до O(log(n)*log(m)).