https://t.me/ctci_chat_ru/38942

Спасибо! А расскажи пожалуйста, как ты харды решал? Я только начинаю, у меня уходит пара часов как минимум допереть до решения самостоятельно. Это норм стратегия?

Спасибо! А расскажи пожалуйста, как ты харды решал? Я только начинаю, у меня уходит пара часов как минимум допереть до решения самостоятельно. Это норм стратегия?

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

Какой город и что за вакансия?

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

Бектрекинг нормальный вариант, только не уверен, что память можно оценить как N + M

На эту похоже https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ ?

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

Похоже, но мне поиск не кратчайшего, а любого надо. А решение - не число, а массив. Это прям дает сильно отличие в решении, хотя набор подходов не отличается

Бред. У тебя может быть просто змейкой из края в край идти путь, и он уже будет N*M. Т.е. интервьюер сам не понял что захотел. Ответ минимум N*M.

Я этот же пример привел, не убедило)))

Конченный интервьюер. Как это не переубедило? Я бы сразу после интервью написал бы рекрутёру, что чел под наркотой меня собесил, посмотрите реплей

Ну там можно запоминать пути по которым ходил

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

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

Но его нет 😃

Надо рекрутеру написать

Просто если N + M, то это как будто у тебя есть жадный алгоритм для выбора куда двигаться, так что в пределе нет такого, что ты проверяешь все клетки

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

А под углом 45 можно переходить на соседнюю ячейку?

Сегодня проходил собес в мете, попалась следующая задача Нужно было найти любой путь в гриде из левого верха до правого низа, где 1 - стенка, 0 - ячейка, по ктр можно ходить. В качестве ответа возвращать null, если пути не существует, иначе массив координат любого пути я решил через dfs рекурсивный, но интервьюер не принял решение, т.к. я сказал, что по памяти это O(n*m), где n - колво строк в гриде, m - колво столбцов в гриде. При этом по времени O(n*m) устроило Рассуждая вслух: - bfs не подошел, потому что для каждой позиции надо было хранить промежуточный путь, что по памяти было бы еще хуже - мб итеративный dfs со стеком был бы лучше по памяти? По намекам ощущение, что напрашивалось O(m+n) доп памяти Есть какие-нибудь предложения?

Я бы двигался только вниз или вправо, зачем в три?

Эм... Но ведь dfs не будет по времени O(n*m) 😄 dfs перебирает все возможные траектории, пока не встретит нужную. Если нужной нет, то вообще все возможные и, кажется, их типа 3^(n+m), т.к. из каждой ячейки мы можем в 3 стороны пойти в общем случае. Но по памяти dfs оптимален - хранит только текущий путь. Как выше написали, путь асимптотически, это O(n*m). Меньше он может быть только если мы можем идти только вниз и вправо, тогда будет O(n+m), но тогда алгоритм менять не надо - мы больше памяти и не потратим в dfs. А если хочется быстрее, но памяти не жалко, можно заделать bfs, будет O(n*m) по сложности (в каждой ячейке мы побываем с алгоритмом максимум 1 раз), а по памяти не больше O((n*m)^2) Ну или можно в dfs запоминать "плохие" вершины, т.е. те, в которые мы заходили, и через которые точно не проходит оптимальный путь. Тогда в каждой вершине мы побываем до 4 раз и тогда сложность снова будет О(n*m). По памяти будет O(n*m). Может ты такое решение написал?

предположим у нас грид 3x3 |0|1|0| |0|0|1| |1|0|0| (3,3) - верхняя левая кордината, из этой точки можем пойти или книз или вправо, тоесть только в две координаты (2,3) или (3,2)(только надо ещё дополнительно проверить, что значение в ячейке в которую перешли не равно 1) Итого можно построить двоичное дерево перемещения(сразу скажу визуализация так себе):

предположим у нас грид 3x3 |0|1|0| |0|0|1| |1|0|0| (3,3) - верхняя левая кордината, из этой точки можем пойти или книз или вправо, тоесть только в две координаты (2,3) или (3,2)(только надо ещё дополнительно проверить, что значение в ячейке в которую перешли не равно 1) Итого можно построить двоичное дерево перемещения(сразу скажу визуализация так себе):

А если грид 000 110 000 011 000 ?) А если 000 000 001 ?

лана я работать

000 110 000 011 000 ?) - ну так в этом случаи нет MxN, тут что то среднее

Типо много "умного" текста, но базовый случай когда у тебя весь путь состоит из посещения N*M клеток эллэгантно проигнорировался

ОООО. Сразу видно, человек на Литкоде решения со своей сложностью не выставлял. Там очередь из людей которые ведро дерьма готовы за такие рассуждения вылить. Сложность всегда худшая считается. Редко средняя, но это для алгоритмов сортировки

000 110 000 011 000 ?) - ну так в этом случаи нет MxN, тут что то среднее