Задача из Собеседования в Amazon за 5 минут
Вставка
- Опубліковано 7 тра 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 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере.
Так что, да, очень актуальен вопрос - как определить хорошего программиста?
Удивительно, но почему то сразу пришел к такому решения 😮 Задача крута! Спасибо!
Красиво! Спасибо за разбор, все четко и по делу.
До такого решения не додумался бы сам, по крайней мере за 10 минут. Спасибо за пример!
❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.
С возвращением, Саша. Так мало качественных разборов нынче!
Просто и при этом очень круто! Спасибо!
Классное решение! Побольше таких видео :)
Блин, это так просто и так гениально... мне стыдно, что я не додумался до такого решения сам
жиза
ты просто всю жизь не курил и не бухал и мухоморы не жевал. А Бог - есть!
@@alexanders8928 Обычно, когда вспоминаешь все мухоморные дела, ты уже сеньор))
Еще проще решение - копируешь цифры в чат gpt и просишь его найти нужное))
Это вообще не гениально. Это очень даже тупо.
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 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах
проблема взялась из ниоткуда и мужественно решена ... браво
Так суть программирования в том что всегда появляются "проблемы" которые нужно "мужественно" решать)
Отличный формат!
а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)
Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор)
ТЕм более что условие задачи поставило конкретное число, а не рандомное
Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация
опиши алгоритм
При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла.
Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.
@@user-jc6fo7gf4w Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.
Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами".
Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.
Я тоже не понял разницы начинать именно справа
Спасибо за видео
Всё очень доступно
эх, не удалось решить самому так элегантно, не додумался до возможности начать справа сверху, только левый верх и правый низ рассматривал) отличный разбор!
А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?
А идея хорошая, если это правильный алгоритм, сложность будет log(n+m). По сути бинпоиск по диагонали
если постараться можно уменьшить до O(log(n)+log(m)) для этого надо заменить нахождение спомощю шагов на два бинарных поиска
Если постараться...
Как ты поймешь что пора заканчивать делать бин. поиск по текущей оси и пора начинать делать бин. поиск по другой?
@@desmosmech7037 Признак конца поиска по строкам это два соседа
один меньше
другой больше
бери меньший и ищи в этой строке
@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)
Мне кажется человек не понял задачу.
Но чтоб получить такую асимптотику надо сделать мёрдж, в один массив, но без пред обработки удачи.
@@roket132 Мы ищем сначало строку а потом в строке нужное поле.
В строке между 10 и 18 есть 14. 14 какраза в строе с 10
отличное объяснение, надо больше таких накидать Александр)
Отлично, первая же идея была довольно близка. Осталось самую малость, научиться кодить 😅
Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM
помойму можно матрицу намутить, в который ты больше одного шага по прямой не сможешь сделать
А зачем бинарный поиск? Мы по порядку идём. Он на больших массивах только замедлит.
А если матрица с рандомными числами будет? Придется переделывать
Ага)
Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.
Красивое решение, класс!
Уточнение по условию задачи. Если двигаться по диагонали до первого большего всегда ли искомое будет в этом же столбце или в этой де строке?
не знаю почему, но думаю это решение можно назвать одним из оптимальных. Как вариант можно использовать информацию, что за числа находятся на вершинах это матрицы и основываясь на этом принимать решение откуда начинать двигаться
Пойму тут O(n) получается, т.е. максимальный путь 2n.. меньше не придумаешь
@@denisgluk431 В этом алгоритме.
Если начинать не с правого верхнего, а n/2 в первой строке и также потом, при спуске.
Пример, n=1000, m=2
но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз
проблема идти по диагонали в том, что ты не знаешь куда поворачивать как только найдешь значение больше искомого, а значит придется запоминать в какой момент ты повернул и в какую сторону, если же идти по вертикали/горизонтали и влево-вправо/вверх-вниз, то ничего запоминать не придется
Класс, я бы никогда так не догадался сделать, хотя очень правильный шаг
Круто. А главное красиво.Лично мне первое пришедшее в голову решение было:
1) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё.
В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.
была детская задачка отгадать число от 1 до 1024 за 10 попыток. тебе говорят больше или меньше задуманного то что ты назвал. лень проверять, но думаю такой способ более эффективен чем предложенный.
Да, этот способ является самым эффективным и называется двоичным поиском.
@@QuarkWasp, двоичный поиск работает с линейными массивами. Такую матрицу к линейному массиву свести очень дорого.
с левого верхнего угла на каждом шаге выбирать элемент правее и элемент ниже. сравнивать эти 2 соседних элемента и двигаться по пути наименьшего из выбранных пока не пересечемся с искомым или не превысим его значение. подход аналогичен описанному но только более понятен
Найди по этому алгоритму число 7 или 11
не работает. Тебя может увести слишком далеко вправо, или слишком далеко вниз.
с какого перепугу O(n+m) это оптимальное решение?
Жара! Нравится мне программирование.
Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.
Странно, меня вот в одном из собеседований на трейни отшили именно по причине, что я не пользовался модулями и недостаточно явно поделил логику и вывод. А в другом отшили за то, что я это сделал, а они выбрали кандидатов, предпочёвших более простые решения.
оптимальное решение быстрее. основная логика та же, но начинать надо не с левого верхнего угла, а с "середины"матрицы. правда надо будет немного заморочиться с обработкой вариантов. зато средняя скорость решения примерно в 2 раза выше получится.
Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже.
А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.
@@oleksandr2234 да, я тоже об этом подумал, но в целом ожидаю что ускорение до 2 раз реально
Ловко ты мне в рекомендациях попался, не зря в гугле работаешь)
В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 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 - тут даже обсуждать нечего - только бинарный поиск.
Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.
Можно так же с левого нижнего угла начинать. Там работают теже правила, только в другом направлении
С левого верхнего угла тоже можно.
@@kaxan1407 Вообще-то нет)) У тебя с обоих сторон числа больше в таком случае. Ты просто не можешь определить, куда идти
@@niqr7800 да, я понел что в общем случае это не сработает минут через 5 после написания коммента
Красавчик. Подскажите, а вы менторством занимаетесь ?
Классная задача, спасибо
Друг, есть более быстрый способ. Первое, проверяем число в ячейке 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 ходов
Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 1e12 x 1e12 (абстрактная большая цифра). Может стоить добавить в код условие про то, что если k < верхнего левого угла || k > нижнего правого угла, то искать нет смысла (false).
Ну как раз на этом этапе можно использовать бинарный поиск
В этой матрице выполняется условие, что все элементы левее и выше меньше или равно текущего элемента, а все элементы правее и ниже - больше текущего элемента.
Об элементах левее и ниже и правее и выше ничего однозначно сказать нельзя. Среди них могут встречаться меньшие, равные или большие. Поэтому матрицу надо проходить до конца.
@@dmytrozazulin1858 , по-моему вы либо не так интерпретируете мое сообщение, или не так интерпретируете условие.
Простой вопрос:
Если в правом нижнем углу матрицы значение, равное 500, может ли в матрице быть значение, например, 501?
Если да, составьте пример такой матрицы, я посмотрю, как вы это сделаете, не нарушая условий
@@core2mind Ясно, я думал вы хотите внести коррективы в сам процесс поиска. А это просто проверка вырожденного случая.
@@dmytrozazulin1858 , ну это по сути внесение изменений в алгоритм поиска, но не в алгоритм скана матрицы самой. Если у нас матрица триллион x триллион, есть ли смысл долго по ней ходить, если за константное время можно сразу сделать вывод, что ходить по ней нет смысла. Я это хотел донести, если что.
В алгоритме, представленном в видео, уже есть предварительные проверки перед сканированием матрицы, мой поинт был лишь в том, что возможно стоит расширить эти проверки.
Вау! Красивое решение!
Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.
Оч классно , спасибо 🔥
То, что сразу полезло в голову:
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 ограничивает нашу область поиска.
Первая (и последняя идея)
1)Проверить первый столбец и первую строку на наличие цифр больше 14 и отсечь их. В нашем случае матрица станет 4 на 4.
2) проверить в обратном порядке последний столбец и строку новой матрицы (4 на 4) и отсечь все, что меньше 14. (Осталось 2 на 2)
3) оставшуюся маленькую матрицу просто перебрать
А потом я досмотрел видео и в очередной раз понял, что я тупой
Сделал эту задачу в 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;
};
Сделал без while, но с двумя for. Предложенное в видео решение выглядит читабельнее. Сложность обоих решений одинаковая - O(m + n)
Подскажи, а какой это паттерн на лет код? Жадный алгоритм?
ps ты молодец, реально круто объясняешь, материал топ, не пойму откуда столько хэйта, и комментарии людей которые вообще в этом ничего не понимают
Изменено: не работает(
Мне кажется есть не менее эффективный способ, хотя хз насколько он будет лучше в коде.
1) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3)
2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10)
3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14.
4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось.
В чем же преимущество этого метода?
Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36)
В случае описанном в видео 10. (Если ищем число 18)
Найди число 11 по даному алгоритму
@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет.
Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину.
В Численных методах этот метод ещё называли поиском льва в пустыне :)
Грубо говоря там можно и площади делить отрезком.
Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.
@@desmosmech7037 верно, спасибо что сказал.
Самое быстрое решение, которое я смог найти, вот такое:
Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа.
Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части.
Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.
мне тоже кажется делить на квадраты интересная идея, первое что пришло на ум, до просмотра решения)
Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим
квадраты получаются только не квадратные в данной матрице
Как я и думал, можно за log(m+n)
Ты можешь исключить только один квадрат за шаг
Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.
Ваш алгоритм даст быстрый неправильный овет для 11, 12, 15, 16, ....
@@OstapP я написал не то что подумал, бинарным поиском искать и столбец и строку. Ответ будет правильным так как и там и там отсортированные множества
@@ilyat2925 , можно этапно? Я не понял ваш алгоритм.
все круто , он видео почаще бы )
Сильно сложный алгоритм поиска, и не факт, что он применим для разных вариантов этой матрицы, мне кажется, что по этой причине тут и повторяются числа.
Чувак, я ничего не понял что ты сказал. Но когда ты стал говорить, ты достучался до моего сердца
да, так же подумал как в решении, только сравнивать не "то что меньше", а "то что больше" (возможно менее эффективное решение). Т.е. если K больше чем a(n-1,m) то двигаться вниз. И еще я бы ввел проверку на "крайние" условия типа к !=0 и a(n,m) >=k
Сразу подумал что нужно идти по диагонали.
Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим.
Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2
Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.
хочу быть таким же умным парнем как ты✊
Александр, спасибо! Но я не совсем понял, как выбирать «угол», с которого начинать поиск?
ЛЕГЕНДА
Я конечно не эксперт, но я сразу нашел число 14. Было трудно, просто включил монитор на котором смотрел это увлекательное видео.
Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю.
Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска.
Спасибо за задачу! Понравилась.
Я так же подумал, но понял что делается одно лишнее движение каретки с лева на право. А потом в итоге каретка движется с права на лево и в низ.
Саша, не понял, зачем начинать именно с правого верхнего угла. Почему не с левого?
Я б начинал сверху откуда-нить из
m*(14-a_11)/(a_m1-a_11), где m - число столбцов
Просто огонь!
А почему не пойти из левого верхнего угла по столбцам вниз? Как дойдём до 18, вернуться назад к 10ти и пойти вправо до 14ти.
я новичек, не судите строго за вопрос, : каким образом мы определяем направление поиска? или мы просто идем по диагонали?
Было интересно
Коды читать и писать не умею, но решение 1 в 1. Вот только пришлось подержать паузу подольше. Есть вопрос к условию задачи...
Получается нам важно только наличие числа (true/false)? Амазон дополнительно не интересовались сколько чисел "K" в матрице (ведь их в диагональ может быть очень много)?
А что если по главной диагонали спуститься до числа превосходящего заданное. И потом проверить числа слева и сверху?
За 15 мин надо готовый рабочий код написать или только логику решения предоставить?
Есть подозрение что можно ещё улучшить алгоритм до log(m+n) ?
Да, есть. Подсказка: возьмите произвольный элемент матрицы, сравните с k и скажите где после этого может быть искомый элемент. Ну а дальше √2 и ничего сверх сложного
1. вариант смотрим строку начальное и конечное значение так понимаем есть ли в этой строке искомое число, далее когда поняли какая строка тем же бинарным поиском воспользуемся что бы найти число.
2. Взять самое левое число, самое правое, и так же самое нижнее левое, самое нижнее правое. На основе этого прикинуть в каком примерно месте распологается искомое число.
На основе этого нужен хитрый рандомизатор который из получившегося множества будет выдавать индекс, и там уже сомтреть подходит ли этот индекс. Ну либо в получившемся регионе использовать вариант 1
Саша у меня Математика 00 как я могу научиться Алгоритмам с нуля до про и как где откуда надо начат ?
Блин, а я думал мы умные ) когда 20 лет назад в олимпиаде по матеше участвовал)) Спасибо за видос
Почему нельзя проверить сразу число по средине. Если К больше того, что по середине, идти нужно к правому, если оно меньше правого, то прочёсываем числа вверх по матрице?
2:39
def searchMatrix(matrix,k):
return any([k in row for row in matrix])
Решение в строку
вопрос: а что это за код такой, в котором записывается решение?
а нельзя ли тут дважды воспользоваться бинпоиском (по столбцам и строкам), тогда O(log n + log m) будет, что быстрее, чем O(n + m)? @СашаЛукин
Ну в принципе можно и с единицы начать, всё получается, главное придумать свои правила вычисления!
А почему отправной точкой является верхнее правое число? Почему другие углы не подойдут?
Можно ещё быстрее, если начинать проверку с любой цифры в центре матрицы. Тогда ты найдёшь ответ в среднем В ДВА РАЗА БЫСТРЕЕ, чем ты показал. Это вааще очевидно.
Добрый вечер. В чём принципиальная разница между обходом массива с конца и с начала?
Ни в чем, здесь главное- принцип найти. Представь что в конце квадрильон на мультимильон- идти к началу будешь дольше в поисках 1. Задача симметричная и решение тоже) и я бы проверил сначала, откуда начинать поиск- в известной матрице больших размеров можно искать методом наименьших квадратов 😊
Удобство формулы. Если начинаем с последнего - можем двигаться по-диагонали всегда по-одному принципу: если необходимое число больше текущего - мы всегда идем вниз, если меньше - всегда влево.
Если вы начнете с первого столбца - то подобной элементарной удобной формулы у нас не будет.
Спасибо вам
По первой строке можно добавить двоичный поиск, сильно поможет на больших размерах.
Кстати похоже что на больших матрицах можно выполнять двоичный ограниченный поиск всегда...
Probably we can go under linear complexity, to the log(sqrt(a^2+b^2))
Можно сделать функцию, которая ищет в упорядоченном массиве заданное число, если не находит, то возвращает следующее по убыванию и его индекс.
Тогда алгоритм выглядел бы так:
делаем поиск в первой строчке [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), о том что можно идти змейкой как-то не догадался)
Респект!
Отлично!!!
Александр, спасибо за интересное видео. Но я не согласен с решением от правого угла. Такое решение возможно когда заранее знаешь значения. В общем случае неизвестно с какого места лучше начинать.
Вот честно поставил на паузу на 2:24: я бы использовал что-то типа волнового алгоритма. Начинаем с элемента (0;0) и смотрим всех его соседей (по 8 направлениям, где это возможно), если среди соседей нет числа К, то перемещаемся на позицию максимального числа; в нашем случае (1;1) со значением 5 и так до тех пор пока у текущего элемента не будет соседа со значением 5, ну плюс ещё условие выхода из цикла со значением false, если вдруг текущее значение стало больше К.
Теперь по честному нажимаю play и смотрю дальше 😀
а с левого нижнего угла не быстрее получится?
Спасибо за видео. А объясни, пожалуйста, подробнее, почему в последнем решении был выбран именно правый верхний "угол"?
Почему не левый нижний, например, или тут нет разницы?
А если взять левый верхний (или правый нижний) угол, то сразу можно определить, есть ли вообще искомое число в этой матрице.
Разницы между правым верхним и левым нижним нет, просто идти сверху вниз психологически приятнее (но назад), чем слева направо (но вверх)
можно сравнить размеры сторон и идти по той стороне, где за шаг отбрасывается больше всего элементов (если ширина больше высоты, то отбрасывать строки). А еще начать искать из середины, а не с конца быстрее, сразу отбрасывается 50% матрицы, а не строка/столбец
@@KDR816
Не важно что больше ширина или высота если числа нет в матрице то пройдет m+n действий в независимости что (m или n) больше. Вы все равно идете либо по вертикали либо по горизонтали отбрасывая числа соответственно по вертикали или горизонтали
Что касается середины то особо толком ничего не отбросится. Например вам надо найти число 14 вы тыкаете в середину матрицы а там число 17 (большее) это значит что в четверти матрицы которая ниже и правее таких чисел нет, но туда вы и не попадете при алгоритме который был разобран. Соответствеенно вам надо сделать либо шаг вверх т.к. там число меньше 17 (и также двигаясь попадете в верхний правый угол) либо вам нужно двигаться влево так как там тоже число меньше 17 и таким образом попадете в нижний левый угол, затратив при этом n+m действий
@@imishka как это не попадём в правый нижний угол. В общем случае хоть куда можно попасть так то)
Правый-верхний и левый-нижний тут равнозначны - можно и так, и так - решение будет аналогичное.
Примерно такое же решение с поиском таргетного числа вокруг текущего в голову пришло,
Только мне пришло в голову стартовой точкой задать не верхний правый угол а середину (по аналогии с бинарным поиском).
В результате при прогоне данной матрицы от 0 до 36, разница в шагах внутри цикла составила 214 (твое решение со стартовой точкой в углу) против 127 со стартовой точкой в центре.
Центр находил абсолютно банально через Math.floor(arr.length / 2) и Math.floor((arr[0].length - 1) / 2);
Вроде как шустрее почти в два раза получается :)
Спасибо за задачу!
Тоже самое подумал, про центр сразу. Да и к тому же можно внести ещё одну оптимизацию, тем более если известен характер чисел (насколько случайные числа были отсортированы и какая случайность использовалась) Можно брать не крайний верхний угол, а относительный порядковый номер диагонали беря во внимание крайние значения таблицы. К примеру видим что таблица начинается с 1 и заканчивается 36. А надо найти число 14, тогда делим искомое число, на разницу начального числа таблицы и конечного. Получаем 0.4. Далее умножаем 0.4 на размерность таблицы и далее округляем числа. И получаем координату оптимального старта поиска, чем линейнее распределение, тем точнее будет координата старта.
@@user-of8lf7yj8o Никто не обещал линейного распределения. А где такие задания на собеседования даются?
@@The14Some1 Понятное дело не обещал. Просто так алгоритм будет работать быстрее на больших размерностях и при разных функциях распределениях и незначительно медленнее на малых размерностях и не линейных функциях распределения
А мне показалось, что надо начинать с середины матрицы по типу двоичного поиска: 16 > 14, поэтому примерно четверть матрицы вправо и вниз от 16-ти не подходит. И т.д....
смысл давать задачи на собеседовании в режиме онлайн, если их все равно готовят заране?е
Мне кинули задачку.
Дан csv файл со списком категорий и подкатегорий
_______________
id,name,parent
------------------------
данные в файле в разброс, вложенность неограниченна. Нужно построить дерево без рекурсии. Как это возможно сделать?