Задача из Собеседования в Amazon за 5 минут
Vložit
- čas přidán 7. 05. 2023
- Разбираем небольшую задачку, которую спросили на собеседовании в Amazon. Такие задачи надо уметь решать за 10-15 минут, но без опыта решения подобных задач найти самое быстрое решение может быть не просто.
Задача на литкоде: leetcode.com/problems/search-...
Пост на литкоде: leetcode.com/discuss/intervie...
Дисклеймер:
И задача, и пост на литкоде находятся в открытом доступе. Я к посту никакого отношения не имею и не могу гарантировать его правдивость.
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
На собеседовании в амазон:
-Вы умеете не ходить в туалет 12 часов?
-Да
-Вы приняты.
На собеседовании в ЕА Games
- Вы радикальная феминистка?
- Да
- Вы приняты.
После того когда находишь более менее краткий путь к нужному результату всегда так на душе приятно становится. Внутренний перфекционист удовлетворен.
Неприятно только одно, чтобы найти этот краткий путь, пришлось перебрать все пути не краткие 🤣
И всегда найдётся азиат, который сделает это быстрее и лучше)
Только под массовость такое решение не подойдет. А значит придется писать отдельный код под разные матрицы
Самый лучший путь решения - отдать любому индусу на аутсорс))
5:10 ну как так-то хоть бы на словах надо было метод золотого сечения упомянуть да и вообще можно тупо делить пополам.
Все эти задачки мне почему-то напомнили как один парень у нас в универе сдавал зачёты, подходил к одному спрашивал что спрашивает препод, потом к другому, потом к третьему, в общем так он перебирал абсолютно все варианты что спрашивал препод по конкретной лабе и потом сдавал её.
Но стоило преподу однажды перед ним поставить новую задачу, которую он никогда ни у одного студента не спрашивал, как всё хорошее и закончилось.
Вероятность появления такой пары оригинальных (преподаватель;вопрос) мала, поэтому метод опроса надежен
@@andrewmurruvyov4359 Это я к тому, что нафига вообще рассматривать методы решения задач, ну вот знаете вы как решить эту конкретную задачу в гугл на миллион долларов в год, а дай вам новую как всё хорошее и закончится, и нифига вы её уже не решите, потому что вы как этот парень из универа, вместо того чтобы учиться решать самому, тупо спрашивал у всех и перебирал все возможные варианты, а сам решать так и не научился, надо учится самому решать, а не смотреть на решения других людей и думать что теперь я мега умный и сам смогу решить такую задачу.
Как говорится: всё просто когда знаешь как, а если не знаешь, то и таблица умножения кажется мега сложной задачей.
Экзамен сдаёт не тот кто умеет решать, а кто умеет сдавать, и на работу устраивается не тот кто может работать, а кто может проходить интервью
@@andrewmurruvyov4359 как правило такие говноработники которые не умеют работать, а умеют устраиваться, потом долго не работают. потому что потом уже НАДО РАБОТАТЬ, а не сдавать 🤣🤣🤣
@@andrewmurruvyov4359 а как этому научиться, если ты бездарь?
как всегда кайф смотреть, хорошо сделано! подача отличная, даже я всё понял, не зная ничего об этом! давай еще и побольше лайв контента!)
Такая чистая, приятная и понятная подача, спасибо!
Александр, крутые видео, записывай ещё ) интересно было бы про все этапы собеседования услышать в одном ролике
Спасибо. С нетерпением жду следующего разбора.
Удивительно, но почему то сразу пришел к такому решения 😮 Задача крута! Спасибо!
Офигеть, до твоих видео вообще не решал алгоритмы и оказывается они намного легче чем я думал. Да и это видео просто change my mind
Когда объяснение под рукой то кажется легче, чем есть на самом деле
На самом деле самому решать не так легко
А что забавнее, что эти задачи мало кто решает так изящно сам по себе, фактически все учат только принципы и шаблоны, которых не так много. Это большой труд, но как это помогает определить хорошего программиста - вопрос :)
@@Gribozhuy не программисту будет лень
@@Gribozhuy, всё зависит от того, для решения каких задач нужен программист. Хороший программист для одних, ужасен для других.
Скажем, задача та же, только у в распоряжении лишь три регистра и только один из них имеет ёмкость достаточную для указания на ячейку в матрице, при этом никто не лимитирует алгоритм по времени.
Практическое применение: микроконтроллер без ОЗУ, все прочие регистры заняты другими данными всей микропрограммы, а её частью является алгоритм, микроконтроллер может 16 MIPS, а управляет дверным замком (то есть, даже если на сравнение уйдёт 30000 выполненных операций для матрицы 6*7, то это всего лишь задержка 0,001875 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере.
Так что, да, очень актуальен вопрос - как определить хорошего программиста?
Отличный формат!
Красиво! Спасибо за разбор, все четко и по делу.
С возвращением, Саша. Так мало качественных разборов нынче!
❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.
До такого решения не додумался бы сам, по крайней мере за 10 минут. Спасибо за пример!
Просто и при этом очень круто! Спасибо!
Блин, это так просто и так гениально... мне стыдно, что я не додумался до такого решения сам
жиза
ты просто всю жизь не курил и не бухал и мухоморы не жевал. А Бог - есть!
@@alexanders8928 Обычно, когда вспоминаешь все мухоморные дела, ты уже сеньор))
Еще проще решение - копируешь цифры в чат gpt и просишь его найти нужное))
Это вообще не гениально. Это очень даже тупо.
Отлично, первая же идея была довольно близка. Осталось самую малость, научиться кодить 😅
Классное решение! Побольше таких видео :)
Спасибо за видео
Всё очень доступно
Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация
опиши алгоритм
При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла.
Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.
@@user-jc6fo7gf4w Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.
Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами".
Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.
Я тоже не понял разницы начинать именно справа
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).
This won't work. Try to find 8 using your algorithm in the example provided in the video.
Однако решить с такой сложностью всё таки можно если заметить, что для произвольного элемента m[i][j]
@@dmitryzhuk220 Не скажу что быстрее чем в видео нельзя решить, я как раз сейчас думаю над этим, но если элемент m[i][j] < k, то можно сказать лишь что наш элемент находится НЕ выше и левее, а иначе НЕ ниже и правее, то есть мы можем отрезать прямоугольную подматрицу в которой элемент не находится, но не выделить онную
@@mrseeker9075 о, действительно, спасибо за уточнение
@@mrseeker9075по идее матрицу можно нарезать на 4 меньшие матрицы (относительно ключевого элемента в центре) а потом рекурсивно повторять алгоритм до размера в 1 элемент и просто проверять этот 1 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах
Красивое решение, класс!
эх, не удалось решить самому так элегантно, не додумался до возможности начать справа сверху, только левый верх и правый низ рассматривал) отличный разбор!
Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM
помойму можно матрицу намутить, в который ты больше одного шага по прямой не сможешь сделать
А зачем бинарный поиск? Мы по порядку идём. Он на больших массивах только замедлит.
А если матрица с рандомными числами будет? Придется переделывать
Ага)
Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.
с левого верхнего угла на каждом шаге выбирать элемент правее и элемент ниже. сравнивать эти 2 соседних элемента и двигаться по пути наименьшего из выбранных пока не пересечемся с искомым или не превысим его значение. подход аналогичен описанному но только более понятен
Найди по этому алгоритму число 7 или 11
не работает. Тебя может увести слишком далеко вправо, или слишком далеко вниз.
проблема взялась из ниоткуда и мужественно решена ... браво
Так суть программирования в том что всегда появляются "проблемы" которые нужно "мужественно" решать)
Классная задача, спасибо
если постараться можно уменьшить до O(log(n)+log(m)) для этого надо заменить нахождение спомощю шагов на два бинарных поиска
Если постараться...
Как ты поймешь что пора заканчивать делать бин. поиск по текущей оси и пора начинать делать бин. поиск по другой?
@@desmosmech7037 Признак конца поиска по строкам это два соседа
один меньше
другой больше
бери меньший и ищи в этой строке
@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)
Мне кажется человек не понял задачу.
Но чтоб получить такую асимптотику надо сделать мёрдж, в один массив, но без пред обработки удачи.
@@roket132 Мы ищем сначало строку а потом в строке нужное поле.
В строке между 10 и 18 есть 14. 14 какраза в строе с 10
Круто. А главное красиво.Лично мне первое пришедшее в голову решение было:
1) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё.
В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.
была детская задачка отгадать число от 1 до 1024 за 10 попыток. тебе говорят больше или меньше задуманного то что ты назвал. лень проверять, но думаю такой способ более эффективен чем предложенный.
Да, этот способ является самым эффективным и называется двоичным поиском.
@@QuarkWasp, двоичный поиск работает с линейными массивами. Такую матрицу к линейному массиву свести очень дорого.
отличное объяснение, надо больше таких накидать Александр)
Оч классно , спасибо 🔥
не знаю почему, но думаю это решение можно назвать одним из оптимальных. Как вариант можно использовать информацию, что за числа находятся на вершинах это матрицы и основываясь на этом принимать решение откуда начинать двигаться
Пойму тут O(n) получается, т.е. максимальный путь 2n.. меньше не придумаешь
@@denisgluk431 В этом алгоритме.
Если начинать не с правого верхнего, а n/2 в первой строке и также потом, при спуске.
Пример, n=1000, m=2
а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)
Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор)
ТЕм более что условие задачи поставило конкретное число, а не рандомное
все круто , он видео почаще бы )
ЛЕГЕНДА
оптимальное решение быстрее. основная логика та же, но начинать надо не с левого верхнего угла, а с "середины"матрицы. правда надо будет немного заморочиться с обработкой вариантов. зато средняя скорость решения примерно в 2 раза выше получится.
Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже.
А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.
@@oleksandr2234 да, я тоже об этом подумал, но в целом ожидаю что ускорение до 2 раз реально
но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз
проблема идти по диагонали в том, что ты не знаешь куда поворачивать как только найдешь значение больше искомого, а значит придется запоминать в какой момент ты повернул и в какую сторону, если же идти по вертикали/горизонтали и влево-вправо/вверх-вниз, то ничего запоминать не придется
Жара! Нравится мне программирование.
Было интересно
Друг, есть более быстрый способ. Первое, проверяем число в ячейке 1,1 и m,n убеждаемся что число К в середине и переборку начинаем с середины в таком случае получаем O((m+n)/2). Можно конечно и не проверять начало с концом тогда, тогда, если брать худший сценарий будет еще быстрее, однако если брать лучший сценарий то можно и без переборки сказать что нет числа в матрице
Что есть середина матрицы 2х10? Мы должны курсор поставить в 1,5? А, может, в 2,6? Но мысль красивая с проверкой 1,1 и m,n. Если искомое число не в матрице (меньше наименьшего элемента или больше наибольшего), то выполним за 1 или 2 операции)
@@Rofelka в предложенной Вами матрице 1,5 1,6 2,5 2,6 равнозначны
@@user-dh7lr6dm2f Допустим дана матрица 100х200, надо найти число К=14. Вы начали с середины, там число 50. Все что вы теперь знаете, это то, что правую нижнюю часть можно отбросить. Но куда теперь вам дальше двигаться? Число К может быть в любой из трёх оставшихся областей. Причем оно может быть как левее середины, так и правее, как ниже середины, так и выше.
@@SayXaNow точно, мой способ получается О(1.5 (m+n))
@@SayXaNow а если дальше опять повторить ход в середину оставшейся области? то есть по сути всегда делим на 2 и сверяем....и того вместо 7 будет 5 ходов
То, что сразу полезло в голову:
1) Проходимся по каждому элементу первой строки и ищём первое число, которое будет больше k
2) Делаем то же, но для первого столбца
3) Ограничиваем область поиска k найденными ранее элементами массива
4) Используем любой поиск.
В худшем случае ограничение у нас займёт O(n+m), а поиск - O(n1 * m1), где n1 и m1 - элементы-ограничители (при прохождении по каждому элементу).
Ух-ты, тоже это в голову пришло
Можно еще ограничивать область если найти число которое меньше k (не рассматривать левую верхнюю область). И тогда такое решение может быть даже быстрее чем то которое рассказали.
@@realvaniog, объясните пошагово. Звучит как бред.
В худшем случае (k>18), а это почти половина возможных k, размер матрицы не уменьшается. Но ваше решение натолкнуло меня на другое. Нужно, чтобы опытный алгоритмист проверил, может я тоже не прав.
Решение:
1) в первой строке доходим до последнего =к. Зачеркиваем для себя все, что ниже.
3) в уже ограниченой матрице идем по первому столбцу до последнего =к. Зачеркиваем для себя, все что левее.
Проходки логично делать бинарным поиском. Если я все правильно понимаю по крайней мере в этой таблице за эти 4 этапа находим наше число. Если таблица больше надо пример, чтобы понять что дальше делать, но так мы гарантированно сильно уменьшаем зону поиска.
Получается 2log(m) + 2log(n)
@@OstapP Если нашли число меньшее k, то нам не подходят все числа которые (одновременно) левее и выше этого найденного числа (там все числа меньше k). Аналогично с числом большим k. Т.о любое число неравное k ограничивает нашу область поиска.
Класс, я бы никогда так не догадался сделать, хотя очень правильный шаг
Просто огонь!
Можно так же с левого нижнего угла начинать. Там работают теже правила, только в другом направлении
С левого верхнего угла тоже можно.
@@kaxan1407 Вообще-то нет)) У тебя с обоих сторон числа больше в таком случае. Ты просто не можешь определить, куда идти
@@niqr7800 да, я понел что в общем случае это не сработает минут через 5 после написания коммента
В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 16. Ну и идти придётся не в одну сторону, а в зависимости от сравнения.
В данном конкретном случае дойдём до 14 за 2 хода 🙂
Ну да, первое желание всё-таки получить $O(\ln n + \ln m)$, а не $O(n+m)$...
левый нижний и правый верхний углы для линейного алгоритма - это две единственные ключевые точки из которых за одно сравнение существует только один единственный путь движения. для любой другой стартовой точки матрицы таких пути уже два. но нормальные люди в упорядоченных последовательностях ищут бинарным поиском по строкам, начиная с граней
@@SayXaNowтоже подумал о бинарном поиске
@@SayXaNow
Я вот как думаю:
- В принципе даже условие задачи не совсем строгое - что такое самый быстрый (или оптимальный) алгоритм поиска?
- В общем случае я вижу как минимум 2 интерпретации.
- 1 - Минимальное количество шагов в среднем.
- 2 - Минимизировать количество шагов для самого плохого случая.
Очевидно, что алгиритмы получатся разные.
Для второго алгоритма, особенно для большого количества рядов (например 1 000 000 000) не оптимально двигаться последовательно по лесенке.
Надо целый массив разбивать на кучки (на 2, а лучше на 3), проверять граничные условия прыгая из одной в другую и убирать целые кучки (суб массивы).
Когда осталась кучка небольшого размера (надо считать какого), тогда уже можно идти по лесенке от верхнего правого угла...
Ну может я и не прав???
@@Proezdom-zx2tl Ну задача с подвохом. я всегда топил и топлю за бинарный алгоритм. В матрице случайных упорядоченных значений размером 2500х10000 он показывает скорость нахождения любого элемента в среднем за 67 шагов. Казалось бы - фантастика, ну что за лохи вообще топят за этот линейный аутизм, ведь налицо логарифмическая скорость.
Но надо учесть один нюанс. могут попадаться квадратные блоки данных, в которых числа расположены особым образом и полностью удовлетворяют условию задачи (правее всегда числа больше, снизу от любого числа тоже всегда больше), но для которых не существует в принципе алгоритма быстрее, чем линейный ступеньками.
И если вдруг в моей матрице мне попался именно такой блок размером 2500х2500 то максимально неудачный расклад для бинарного поиска составит 50000 шагов и примерно 15000 в среднем для любого числа такого блока. Не трудно посчитать что неторопливый линейный тут покажет лучший результат. И т.к. никаким способом нельзя быстро проверить попался нам такой блок или нет, я бы не рискнул использовать быструю бинарку для слишком больших квадратных матриц. Сначала бы убедился что большая сторона M превосходит меньшую N хотя бы в 5 раз. А если ярко выраженная прямоугольная длинная типа 1000х17000 - тут даже обсуждать нечего - только бинарный поиск.
Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.
Респект!
Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.
Странно, меня вот в одном из собеседований на трейни отшили именно по причине, что я не пользовался модулями и недостаточно явно поделил логику и вывод. А в другом отшили за то, что я это сделал, а они выбрали кандидатов, предпочёвших более простые решения.
А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?
А идея хорошая, если это правильный алгоритм, сложность будет log(n+m). По сути бинпоиск по диагонали
хочу быть таким же умным парнем как ты✊
Первая (и последняя идея)
1)Проверить первый столбец и первую строку на наличие цифр больше 14 и отсечь их. В нашем случае матрица станет 4 на 4.
2) проверить в обратном порядке последний столбец и строку новой матрицы (4 на 4) и отсечь все, что меньше 14. (Осталось 2 на 2)
3) оставшуюся маленькую матрицу просто перебрать
А потом я досмотрел видео и в очередной раз понял, что я тупой
Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 1e12 x 1e12 (абстрактная большая цифра). Может стоить добавить в код условие про то, что если k < верхнего левого угла || k > нижнего правого угла, то искать нет смысла (false).
Ну как раз на этом этапе можно использовать бинарный поиск
В этой матрице выполняется условие, что все элементы левее и выше меньше или равно текущего элемента, а все элементы правее и ниже - больше текущего элемента.
Об элементах левее и ниже и правее и выше ничего однозначно сказать нельзя. Среди них могут встречаться меньшие, равные или большие. Поэтому матрицу надо проходить до конца.
@@dmytrozazulin1858 , по-моему вы либо не так интерпретируете мое сообщение, или не так интерпретируете условие.
Простой вопрос:
Если в правом нижнем углу матрицы значение, равное 500, может ли в матрице быть значение, например, 501?
Если да, составьте пример такой матрицы, я посмотрю, как вы это сделаете, не нарушая условий
@@core2mind Ясно, я думал вы хотите внести коррективы в сам процесс поиска. А это просто проверка вырожденного случая.
@@dmytrozazulin1858 , ну это по сути внесение изменений в алгоритм поиска, но не в алгоритм скана матрицы самой. Если у нас матрица триллион x триллион, есть ли смысл долго по ней ходить, если за константное время можно сразу сделать вывод, что ходить по ней нет смысла. Я это хотел донести, если что.
В алгоритме, представленном в видео, уже есть предварительные проверки перед сканированием матрицы, мой поинт был лишь в том, что возможно стоит расширить эти проверки.
Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.
Ваш алгоритм даст быстрый неправильный овет для 11, 12, 15, 16, ....
@@OstapP я написал не то что подумал, бинарным поиском искать и столбец и строку. Ответ будет правильным так как и там и там отсортированные множества
@@ilyat2925 , можно этапно? Я не понял ваш алгоритм.
Спасибо вам
Самое быстрое решение, которое я смог найти, вот такое:
Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа.
Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части.
Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.
мне тоже кажется делить на квадраты интересная идея, первое что пришло на ум, до просмотра решения)
Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим
квадраты получаются только не квадратные в данной матрице
Как я и думал, можно за log(m+n)
Ты можешь исключить только один квадрат за шаг
Изменено: не работает(
Мне кажется есть не менее эффективный способ, хотя хз насколько он будет лучше в коде.
1) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3)
2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10)
3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14.
4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось.
В чем же преимущество этого метода?
Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36)
В случае описанном в видео 10. (Если ищем число 18)
Найди число 11 по даному алгоритму
@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет.
Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину.
В Численных методах этот метод ещё называли поиском льва в пустыне :)
Грубо говоря там можно и площади делить отрезком.
Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.
@@desmosmech7037 верно, спасибо что сказал.
Все гениальное просто ❤
Отлично!!!
Сильно сложный алгоритм поиска, и не факт, что он применим для разных вариантов этой матрицы, мне кажется, что по этой причине тут и повторяются числа.
Ловко ты мне в рекомендациях попался, не зря в гугле работаешь)
Вау! Красивое решение!
Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.
да, так же подумал как в решении, только сравнивать не "то что меньше", а "то что больше" (возможно менее эффективное решение). Т.е. если K больше чем a(n-1,m) то двигаться вниз. И еще я бы ввел проверку на "крайние" условия типа к !=0 и a(n,m) >=k
Сразу подумал что нужно идти по диагонали.
Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим.
Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2
Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.
Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю.
Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска.
Спасибо за задачу! Понравилась.
Я так же подумал, но понял что делается одно лишнее движение каретки с лева на право. А потом в итоге каретка движется с права на лево и в низ.
Крутой 😊
Красавчик. Подскажите, а вы менторством занимаетесь ?
Ну в принципе можно и с единицы начать, всё получается, главное придумать свои правила вычисления!
1. вариант смотрим строку начальное и конечное значение так понимаем есть ли в этой строке искомое число, далее когда поняли какая строка тем же бинарным поиском воспользуемся что бы найти число.
2. Взять самое левое число, самое правое, и так же самое нижнее левое, самое нижнее правое. На основе этого прикинуть в каком примерно месте распологается искомое число.
На основе этого нужен хитрый рандомизатор который из получившегося множества будет выдавать индекс, и там уже сомтреть подходит ли этот индекс. Ну либо в получившемся регионе использовать вариант 1
Я конечно не эксперт, но я сразу нашел число 14. Было трудно, просто включил монитор на котором смотрел это увлекательное видео.
Подскажи, а какой это паттерн на лет код? Жадный алгоритм?
ps ты молодец, реально круто объясняешь, материал топ, не пойму откуда столько хэйта, и комментарии людей которые вообще в этом ничего не понимают
Ахуенное решение, спасибо за видос, ты ГЕНИЙ!
Блин, а я думал мы умные ) когда 20 лет назад в олимпиаде по матеше участвовал)) Спасибо за видос
По первой строке можно добавить двоичный поиск, сильно поможет на больших размерах.
Кстати похоже что на больших матрицах можно выполнять двоичный ограниченный поиск всегда...
Вот честно поставил на паузу на 2:24: я бы использовал что-то типа волнового алгоритма. Начинаем с элемента (0;0) и смотрим всех его соседей (по 8 направлениям, где это возможно), если среди соседей нет числа К, то перемещаемся на позицию максимального числа; в нашем случае (1;1) со значением 5 и так до тех пор пока у текущего элемента не будет соседа со значением 5, ну плюс ещё условие выхода из цикла со значением false, если вдруг текущее значение стало больше К.
Теперь по честному нажимаю play и смотрю дальше 😀
Поставил на паузу, прошло 5 дней😂😂😂
Можно сделать функцию, которая ищет в упорядоченном массиве заданное число, если не находит, то возвращает следующее по убыванию и его индекс.
Тогда алгоритм выглядел бы так:
делаем поиск в первой строчке [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), о том что можно идти змейкой как-то не догадался)
Уточнение по условию задачи. Если двигаться по диагонали до первого большего всегда ли искомое будет в этом же столбце или в этой де строке?
Ваше решение занимает, на данном примере, 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). Отсюда вывод - Ваше решение не оптимально. Могу кодом, если так проще воспринимать.
k = 18. Алгоритм за 7 шагов сказал, что такого числа нет. Двигатель шаттла №18 не запустился, ракета упала.
@@SayXaNow примерно так, да. Проглючило. Даже не задумался, что оно не на диагонали может быть) Сам потом понял, но уже не стал ничего удалять)
Написал на 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 + ".");
}
}
Как увидел, сразу начал по диагонали, но не с того угла. Немного недодумал)) Тем не менее, внутренний "я" доволен собой xD
Решил меньше чем за минуту, сначала доперев что анализ нужно диагональный проводить и потом уже, что начинать лучше справа налево)
Можно ещё сократить действий, идя бинарным поиском по верхнему столбцу, а не перебором - в общем случае это уменьшит кол-во шагов
В худшем случае нет. В худшем следующий левый/нижний будет подходящим, а это уже выйдет в O(mlogm + nlogn)
@@user-xd8pg7km6f omnomnomnomnom
Верхний столбец... Интересно, надо записать.
Эх если бы видео выходили почаще
Для любого числа можно уменьшить фактическое время вычисления. Если определить с верхнего правого угла или с нижнего левого угла начать выполнение представленного алгоритма. Путем сравнения в два шага. Да, добавляется несколько действий. Но статистически это ухудшит время только для чисел, находящихся по центру. А фактически это увеличит скорость для всех остальных случаев, когда искомое находится дальше центра при отсчете с верхнего угла (начала пути алгоритма).
тогда можно и вовсе чекать ячейки рандомно. Да не самый оптимальный вариант, будет стремится к середине, но зато подойдет для любой не отсортированной матрицы)
@@leofender5753 это алгоритм поиска кратчайшего пути. Более оптимизированный чем в видео.
@@leonidalexeev4098 да, но при рандоме есть шанс найти нужное число вообще за 1 ход)))
@@leofender5753 так я предложил вариант не по рандому, а по алгоритму. За 10000 проходов матрицы размером больше 5 будет более быстрое выполнение.
По красоте! А я только построчную бисекцию поднял. Думал правда может как то её приспособить сразу к двум измерениям.
Александр, спасибо! Но я не совсем понял, как выбирать «угол», с которого начинать поиск?
Получил математический оргазм. Спасибо.
Впервые смог решить задачу сам)
Можно ещё быстрее, если начинать проверку с любой цифры в центре матрицы. Тогда ты найдёшь ответ в среднем В ДВА РАЗА БЫСТРЕЕ, чем ты показал. Это вааще очевидно.
Я бы брал пару iый столбец + iая строка. дальше проверял бы что первый элемент строки (или столбца, что одно и то же) меньше k, а последний - больше. потом бы бинпоиском по столбцу/строке пытался найти число, если не нашел - переходил бы к следующей паре столбец-строка
можно еще бинарным поиском попрбовать. Делим на 4 квадранта, смотрим в каждом из них левое верхнее и правое нижнее, и сравниваем с искомым. Например, если первоначальным разбиением взять за центр 16, то правый нижний квадрант можно отсечь и левый верхний квадрант можно отсечь. Далее рекурсивно ищем в правом верхнем и в левом нижнем.
Тоже об этом подумал. Тогда сложно сложность О(log_2(m+n)). Еще быстрее выходит.
@@VishnevskyMike в две подматрицы залядывать часто придётся.. а это всё равно на начальную оценку похоже.. O(n)
@@denisgluk431 нет. Даже если в 3 подматрицы придется заглядывать, оценка будет логарифмической, так как на каждой итерации пространство поиска сужается на множитель, а не на константу. А в более чем 3 подматрицы смотреть гарантированно будет не нужно.
Красавец, решил задачи, прошел собес и сидишь карточки товаров верстаешь😂
2:39
def searchMatrix(matrix,k):
return any([k in row for row in matrix])
Решение в строку
с какого перепугу O(n+m) это оптимальное решение?
только в начале своего пути становления программистом, логикой сразу решил как и ты(только начал с 1, и не совсем понял почему с 16 начинать выгодней). Но решение я бы наверно часа 2 писал.
с 1 вообще не получится. Ну либо тебе придётся рассматривать аж 8 позиций вокруг текущего элемента.
Ускорил видео в 2 раза, узнал за 2.5 минуты
Можно даже оптимизировать перемещение "указателя", двигая его не наш 1 шаг в сторону, а в середину между указателем и направлением. Типа, используя основу бинарного поиска.
тоже пришло это в голову
Правый верхний угол можно найти дихотомией, что даст еще меньшую оценку, О(logn + m). Далее идти по "диогоналям" можно не поэлементно а также дихотомией, что в общем случае даст O(log n + log m). Такое конечно за 15 минут не написать, но устно я бы обязательно упомянул про более оптимальные пути поиска.
А зачем нужно первое отсечение? Есть инсайдерская информация, что мы так большую часть матрицы выкинем? Дихотомия по диагоналям мне то же пришла в голову, но сложность такого алгоритма останется прежней - O(n+m). Однако ожидаемая сложность такого подхода будет меньше, но не O(log(n)+log(m)), а O(log(n)*log(m)).
@@user-bg8nj8cw7h, первым отсечением мы сразу уменьшим прямоугольник с m * n до (m-k) * n. В примере на видео - верхний правый элемент с которого можно начинать это 11 (первый элемент меньше 14). Но да, точно, согласен, в случае дихатомаии , оценка будет O(log(m) * log(n)).
Совершено все верно. Использование дихотомии есть самый эффективный метод. Сам решил дихотомией через диагонали, не так сложно как кажется на первый взгляд, ибо алгоритм дихотомии всем известен наизусть.
Диагональная дихотомия - эффективность log(n)^2, где n - наименьшая сторона. Но алгоритм требует рекурсии, т.к. матрица разбивается на каждом шаге на две валидных области, в которых снова применяем алгоритм.
Чередующаяся дихотомия по строкам и столбцам - эффективность log(n)*log(m). Код чуть длиннее, но пишется по факту быстрее и понимается лучше. Не требует рекурсии - что огромнейший плюс.
Окончательный вариант из видео - это фиаско. Применять последовательный поиск в упорядоченной последовательности - это провал собеседования.
@@kostyajan Если по диагоналям отсекать оказывается эффективней, то зачем нужен первый шаг, который может отрезать неопределённое кол-во столбцов (в том числе и 0)?
Первое что пришло в голову начинать по диагонали от 1. Тогда максимальная длительность вышла бы 2m+n. На паузу не ставил, вполне вероятно что немного поразмыслив пришел бы к ответу из ролика.
Чувак, я ничего не понял что ты сказал. Но когда ты стал говорить, ты достучался до моего сердца