Спасибо за дополнение. Можно по аналогии со слиянием двух отсортированных массивов решать.
Комментарий не про разбор всех возможных решений конкретной задачи, а про влияние соотношения входных данных на рассуждения. Рассуждения при M >> N справедливы и для этого решения.
Пример двух входных массивов M >> N: M: 1, 2, 3, 4, ... , 999 999 999 999, 1 000 000 000 000 N: 1, 1 000 000 000 000
Merge будет работать за O(M), бинарный поиск за O(lgM).
Задача на поиск дубликатов в двух отсортированных массивах. N – первый массив, M – второй.
Рассмотрим два решения. В оценке памяти не буду учитывать хранение результата:
Через хеш-таблицу. Сложность O(N + M) по времени и O(min(N, M)) по дополнительной памяти.
Через бинарный поиск. Сложность O(min(N, M) * lg(max(N, M))) по времени и O(1) по дополнительной памяти.
По оценке сложности первое решение быстрее.
Допустим, вы задали интервьюеру вопрос про соотношение размеров N и M. Он ответил, что M >> N, то есть N пренебрежимо мало относительно M. Тогда N из оценки можно убрать. Получим O(M) по времени и O(1) по памяти для первого решения и O(lgM) по времени и O(1) по памяти для второго. Оценка сложности для второго решения стала лучше при этом условии.
Далее можно обсудить с интервьюером, что первое решение работает для неотсортированных массивов, легче кодируется и читается.
С точки зрения собеседований в любом FAANG предложат минимум Python, Java, C++. Точные возможности надо обсуждать с рекрутером. Маловероятно, что согласятся собеседовать на непопулярных языках. Я готовился и проходил собеседования на Python.
В работе язык может быть другой. Время изучить и освоиться дадут.
Получилось уделить этому контесту где-то час времени. Реализовал алгоритм A*. Веса ребер на основе текущей ситуации на доске. Кажется, что алгоритмы на графах тоже были перспективны в данном контесте. По поводу необходимости писать симуляцию — не соглашусь, контесты CodinGame выгодно отличаются тем, что вполне допускают конкурентноспособную эвристику. В топе есть участник Khao (9 место) — он принципиально пишет эвристику на js. От себя добавлю, если есть цель попасть в топ 20, то это практически всегда бешеные трудозатраты.
Спасибо за дополнение. Можно по аналогии со слиянием двух отсортированных массивов решать.
Комментарий не про разбор всех возможных решений конкретной задачи, а про влияние соотношения входных данных на рассуждения. Рассуждения при M >> N справедливы и для этого решения.
Пример двух входных массивов M >> N:
M: 1, 2, 3, 4, ... , 999 999 999 999, 1 000 000 000 000
N: 1, 1 000 000 000 000
Merge будет работать за O(M), бинарный поиск за O(lgM).
Объясню на примере.
Задача на поиск дубликатов в двух отсортированных массивах. N – первый массив, M – второй.
Рассмотрим два решения. В оценке памяти не буду учитывать хранение результата:
Через хеш-таблицу. Сложность O(N + M) по времени и O(min(N, M)) по дополнительной памяти.
Через бинарный поиск. Сложность O(min(N, M) * lg(max(N, M))) по времени и O(1) по дополнительной памяти.
По оценке сложности первое решение быстрее.
Допустим, вы задали интервьюеру вопрос про соотношение размеров N и M. Он ответил, что M >> N, то есть N пренебрежимо мало относительно M. Тогда N из оценки можно убрать. Получим O(M) по времени и O(1) по памяти для первого решения и O(lgM) по времени и O(1) по памяти для второго. Оценка сложности для второго решения стала лучше при этом условии.
Далее можно обсудить с интервьюером, что первое решение работает для неотсортированных массивов, легче кодируется и читается.
С точки зрения собеседований в любом FAANG предложат минимум Python, Java, C++. Точные возможности надо обсуждать с рекрутером. Маловероятно, что согласятся собеседовать на непопулярных языках. Я готовился и проходил собеседования на Python.
В работе язык может быть другой. Время изучить и освоиться дадут.
Спасибо за оценку и дополнение про downgrade.
Да, этот курс. Полезен для знакомства с форматом и популярными задачами.