Задача из Собеседования в 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 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере.
Так что, да, очень актуальен вопрос - как определить хорошего программиста?
Удивительно, но почему то сразу пришел к такому решения 😮 Задача крута! Спасибо!
❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.
С возвращением, Саша. Так мало качественных разборов нынче!
До такого решения не додумался бы сам, по крайней мере за 10 минут. Спасибо за пример!
Спасибо. С нетерпением жду следующего разбора.
а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)
Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор)
ТЕм более что условие задачи поставило конкретное число, а не рандомное
Блин, это так просто и так гениально... мне стыдно, что я не додумался до такого решения сам
жиза
ты просто всю жизь не курил и не бухал и мухоморы не жевал. А Бог - есть!
@@alexanders8928 Обычно, когда вспоминаешь все мухоморные дела, ты уже сеньор))
Еще проще решение - копируешь цифры в чат gpt и просишь его найти нужное))
Это вообще не гениально. Это очень даже тупо.
Красиво! Спасибо за разбор, все четко и по делу.
Классное решение! Побольше таких видео :)
А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?
А идея хорошая, если это правильный алгоритм, сложность будет log(n+m). По сути бинпоиск по диагонали
Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация
опиши алгоритм
При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла.
Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.
@@user-jc6fo7gf4w Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.
Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами".
Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.
Я тоже не понял разницы начинать именно справа
Отличный формат!
эх, не удалось решить самому так элегантно, не додумался до возможности начать справа сверху, только левый верх и правый низ рассматривал) отличный разбор!
Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM
помойму можно матрицу намутить, в который ты больше одного шага по прямой не сможешь сделать
А зачем бинарный поиск? Мы по порядку идём. Он на больших массивах только замедлит.
А если матрица с рандомными числами будет? Придется переделывать
Ага)
Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.
Отлично, первая же идея была довольно близка. Осталось самую малость, научиться кодить 😅
Просто и при этом очень круто! Спасибо!
с какого перепугу O(n+m) это оптимальное решение?
не знаю почему, но думаю это решение можно назвать одним из оптимальных. Как вариант можно использовать информацию, что за числа находятся на вершинах это матрицы и основываясь на этом принимать решение откуда начинать двигаться
Пойму тут O(n) получается, т.е. максимальный путь 2n.. меньше не придумаешь
@@denisgluk431 В этом алгоритме.
Если начинать не с правого верхнего, а n/2 в первой строке и также потом, при спуске.
Пример, n=1000, m=2
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 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах
Уточнение по условию задачи. Если двигаться по диагонали до первого большего всегда ли искомое будет в этом же столбце или в этой де строке?
проблема взялась из ниоткуда и мужественно решена ... браво
Так суть программирования в том что всегда появляются "проблемы" которые нужно "мужественно" решать)
если постараться можно уменьшить до O(log(n)+log(m)) для этого надо заменить нахождение спомощю шагов на два бинарных поиска
Если постараться...
Как ты поймешь что пора заканчивать делать бин. поиск по текущей оси и пора начинать делать бин. поиск по другой?
@@desmosmech7037 Признак конца поиска по строкам это два соседа
один меньше
другой больше
бери меньший и ищи в этой строке
@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)
Мне кажется человек не понял задачу.
Но чтоб получить такую асимптотику надо сделать мёрдж, в один массив, но без пред обработки удачи.
@@roket132 Мы ищем сначало строку а потом в строке нужное поле.
В строке между 10 и 18 есть 14. 14 какраза в строе с 10
но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз
проблема идти по диагонали в том, что ты не знаешь куда поворачивать как только найдешь значение больше искомого, а значит придется запоминать в какой момент ты повернул и в какую сторону, если же идти по вертикали/горизонтали и влево-вправо/вверх-вниз, то ничего запоминать не придется
все круто , он видео почаще бы )
отличное объяснение, надо больше таких накидать Александр)
с левого верхнего угла на каждом шаге выбирать элемент правее и элемент ниже. сравнивать эти 2 соседних элемента и двигаться по пути наименьшего из выбранных пока не пересечемся с искомым или не превысим его значение. подход аналогичен описанному но только более понятен
Найди по этому алгоритму число 7 или 11
не работает. Тебя может увести слишком далеко вправо, или слишком далеко вниз.
Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.
Странно, меня вот в одном из собеседований на трейни отшили именно по причине, что я не пользовался модулями и недостаточно явно поделил логику и вывод. А в другом отшили за то, что я это сделал, а они выбрали кандидатов, предпочёвших более простые решения.
Спасибо за видео
Всё очень доступно
Красивое решение, класс!
Можно так же с левого нижнего угла начинать. Там работают теже правила, только в другом направлении
С левого верхнего угла тоже можно.
@@kaxan1407 Вообще-то нет)) У тебя с обоих сторон числа больше в таком случае. Ты просто не можешь определить, куда идти
@@niqr7800 да, я понел что в общем случае это не сработает минут через 5 после написания коммента
оптимальное решение быстрее. основная логика та же, но начинать надо не с левого верхнего угла, а с "середины"матрицы. правда надо будет немного заморочиться с обработкой вариантов. зато средняя скорость решения примерно в 2 раза выше получится.
Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже.
А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.
@@oleksandr2234 да, я тоже об этом подумал, но в целом ожидаю что ускорение до 2 раз реально
Жара! Нравится мне программирование.
Класс, я бы никогда так не догадался сделать, хотя очень правильный шаг
Друг, есть более быстрый способ. Первое, проверяем число в ячейке 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) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё.
В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.
была детская задачка отгадать число от 1 до 1024 за 10 попыток. тебе говорят больше или меньше задуманного то что ты назвал. лень проверять, но думаю такой способ более эффективен чем предложенный.
Да, этот способ является самым эффективным и называется двоичным поиском.
@@QuarkWasp, двоичный поиск работает с линейными массивами. Такую матрицу к линейному массиву свести очень дорого.
А что если по главной диагонали спуститься до числа превосходящего заданное. И потом проверить числа слева и сверху?
ЛЕГЕНДА
В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 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 - тут даже обсуждать нечего - только бинарный поиск.
Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.
Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 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) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3)
2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10)
3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14.
4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось.
В чем же преимущество этого метода?
Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36)
В случае описанном в видео 10. (Если ищем число 18)
Найди число 11 по даному алгоритму
@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет.
Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину.
В Численных методах этот метод ещё называли поиском льва в пустыне :)
Грубо говоря там можно и площади делить отрезком.
Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.
@@desmosmech7037 верно, спасибо что сказал.
Оч классно , спасибо 🔥
Саша у меня Математика 00 как я могу научиться Алгоритмам с нуля до про и как где откуда надо начат ?
Самое быстрое решение, которое я смог найти, вот такое:
Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа.
Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части.
Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.
мне тоже кажется делить на квадраты интересная идея, первое что пришло на ум, до просмотра решения)
Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим
квадраты получаются только не квадратные в данной матрице
Как я и думал, можно за log(m+n)
Ты можешь исключить только один квадрат за шаг
Сильно сложный алгоритм поиска, и не факт, что он применим для разных вариантов этой матрицы, мне кажется, что по этой причине тут и повторяются числа.
Классная задача, спасибо
Есть подозрение что можно ещё улучшить алгоритм до log(m+n) ?
Да, есть. Подсказка: возьмите произвольный элемент матрицы, сравните с k и скажите где после этого может быть искомый элемент. Ну а дальше √2 и ничего сверх сложного
Первая (и последняя идея)
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)
я новичек, не судите строго за вопрос, : каким образом мы определяем направление поиска? или мы просто идем по диагонали?
Ловко ты мне в рекомендациях попался, не зря в гугле работаешь)
да, так же подумал как в решении, только сравнивать не "то что меньше", а "то что больше" (возможно менее эффективное решение). Т.е. если K больше чем a(n-1,m) то двигаться вниз. И еще я бы ввел проверку на "крайние" условия типа к !=0 и a(n,m) >=k
Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.
Ваш алгоритм даст быстрый неправильный овет для 11, 12, 15, 16, ....
@@OstapP я написал не то что подумал, бинарным поиском искать и столбец и строку. Ответ будет правильным так как и там и там отсортированные множества
@@ilyat2925 , можно этапно? Я не понял ваш алгоритм.
Чем бинарный поиск числа с минимальной разницей от искомого по строке и столбцу хуже? Таким образом находится следующая строка и столбец.
O(log n + log m), разве нет?
а с левого нижнего угла не быстрее получится?
хочу быть таким же умным парнем как ты✊
Вау! Красивое решение!
Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.
За 15 мин надо готовый рабочий код написать или только логику решения предоставить?
А почему не пойти из левого верхнего угла по столбцам вниз? Как дойдём до 18, вернуться назад к 10ти и пойти вправо до 14ти.
Почему нельзя проверить сразу число по средине. Если К больше того, что по середине, идти нужно к правому, если оно меньше правого, то прочёсываем числа вверх по матрице?
А почему отправной точкой является верхнее правое число? Почему другие углы не подойдут?
Вопрос, а почему time complexity O(n+m) ?
Добрый вечер. В чём принципиальная разница между обходом массива с конца и с начала?
Ни в чем, здесь главное- принцип найти. Представь что в конце квадрильон на мультимильон- идти к началу будешь дольше в поисках 1. Задача симметричная и решение тоже) и я бы проверил сначала, откуда начинать поиск- в известной матрице больших размеров можно искать методом наименьших квадратов 😊
Удобство формулы. Если начинаем с последнего - можем двигаться по-диагонали всегда по-одному принципу: если необходимое число больше текущего - мы всегда идем вниз, если меньше - всегда влево.
Если вы начнете с первого столбца - то подобной элементарной удобной формулы у нас не будет.
Просто огонь!
что будет если начать из другого угла?
смысл давать задачи на собеседовании в режиме онлайн, если их все равно готовят заране?е
Мне кинули задачку.
Дан csv файл со списком категорий и подкатегорий
_______________
id,name,parent
------------------------
данные в файле в разброс, вложенность неограниченна. Нужно построить дерево без рекурсии. Как это возможно сделать?
Привет! А почему так мало видосов на канале?
Ну в принципе можно и с единицы начать, всё получается, главное придумать свои правила вычисления!
а что мешает и в этом решении начать не с верхнего правого угла, а с середины матрицы?
С верзнего-правого или нижнего-левого получаем простую формулу: если нужное число менье текущего - идем всегда влево, если больше - всегда вниз..
С середины мы такую формулу не получим, тк у нас нет однозначного ответа - идти от числа 16 вверх, или налево (или от числа 9 - вниз или вправо).
Респект!
Красавчик. Подскажите, а вы менторством занимаетесь ?
Сразу подумал что нужно идти по диагонали.
Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим.
Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2
Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.
Коды читать и писать не умею, но решение 1 в 1. Вот только пришлось подержать паузу подольше. Есть вопрос к условию задачи...
Получается нам важно только наличие числа (true/false)? Амазон дополнительно не интересовались сколько чисел "K" в матрице (ведь их в диагональ может быть очень много)?
Я конечно не эксперт, но я сразу нашел число 14. Было трудно, просто включил монитор на котором смотрел это увлекательное видео.
а если попробовать бинарным поиском сначал искать строку, в которой 0-вой элемент ближе всех к К, но меньше K, а потом уже бинарный поиск по этой строке? тогда получится log(n) + log(m), что меньше, чем n+m
Я тоже именно так и подумал
Вы на верном пути, дам подсказку: log(n) + log(m) у вас не выйдет, т.к. вы не сможете гарантированно за два бинарных поиска найти число, но вот log(n)*log(m) - один из лучших вариантов. Про окончательный ответ из видео забудьте. Последовательный поиск вместо бинарного в упорядоченной последовательности - это провал собеседования. Хуже только перебор всех значений, зато в одну строчку.
@@SayXaNow почему за суму логов не выйдет?
@@SayXaNow можно ведь найти число не точно искомое, но рядом с ним стоящее за лог
@@mzmzmzmzmq за первый лог N для строки вы нашли максимально близкое к К и знаете теперь ограничение конца строки - допустим это индекс I. За второй лог по М вы нашли в столбце I максимально близкое к К число и знаете теперь ограничение длинны столбца, допустим это индекс J.
Вы использовали два лога, но у вас еще осталась непроверенная область [0, 0, J, I] дл которой нужно повторить операцию. Так понятнее? За сумму логов вы лишь сократите область поиска, но гарантированно К не найдете.
начинать перебирать массив с левого верхнего или с правого, вопрос не принципиальный т.к число К может быть любым
я думаю, с правого верхнего будет проще сам код выглядеть, потому что всегда после первого шага (нахождения столбца в первой строке) смещаешься влево
1. вариант смотрим строку начальное и конечное значение так понимаем есть ли в этой строке искомое число, далее когда поняли какая строка тем же бинарным поиском воспользуемся что бы найти число.
2. Взять самое левое число, самое правое, и так же самое нижнее левое, самое нижнее правое. На основе этого прикинуть в каком примерно месте распологается искомое число.
На основе этого нужен хитрый рандомизатор который из получившегося множества будет выдавать индекс, и там уже сомтреть подходит ли этот индекс. Ну либо в получившемся регионе использовать вариант 1
а вообще можно совместить и сделать тройное решение тобишь находить быстро точку входа допустим цифру 17 потом от нее идти влево вниз и одновременно вверх вправо
на каком языке нужно искать ответ?
а почему искать нужно начинать с угла? почему не с "условного" центра матрицы?
а какие языки программирования надо знать чтоб попасть в известные IT компании (google,amazon и.тд)?
английский
Петросян@@redrusher
Ахуенное решение, спасибо за видос, ты ГЕНИЙ!
Саша, не понял, зачем начинать именно с правого верхнего угла. Почему не с левого?
Я б начинал сверху откуда-нить из
m*(14-a_11)/(a_m1-a_11), где m - число столбцов
Привет, если я вообще ноль в задачках, ну не даются они мне, хотя айти тема очень нравится, что мне делать с чего начать?
Учить информатику начиная со школьной
А что если перебирать не всю матрицу? Можно исключить некоторые столбцы и строки
Как ты это программе объяснишь?
Как увидел, сразу начал по диагонали, но не с того угла. Немного недодумал)) Тем не менее, внутренний "я" доволен собой xD
Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю.
Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска.
Спасибо за задачу! Понравилась.
Я так же подумал, но понял что делается одно лишнее движение каретки с лева на право. А потом в итоге каретка движется с права на лево и в низ.
Бинарный поиск?