День четыреста девятый. #Оффтоп #ЗадачиНаСобеседовании
Давненько у нас не было задачек с собеседований. Сегодня относительно простая.
Дан массив длины N, который содержит числа в диапазоне от 1 до N, найдите число, дубликат которого встречается первым. Другими словами, если имеется более 1 дублированного числа, нужно вернуть число, для которого второе вхождение имеет наименьший индекс. Если таких элементов нет, вернуть -1.
Например:
Для
Для
Есть 2 дубликата: числа 2 и 3. Второй вхождение числа 3 имеет меньший индекс, чем второе вхождение числа 2, поэтому ответ 3.
Усложнённый вариант: Написать решение со сложностью
Как обычно, приглашаю всех предлагать варианты решения в чате @netdeveloperschat
Давненько у нас не было задачек с собеседований. Сегодня относительно простая.
Дан массив длины N, который содержит числа в диапазоне от 1 до N, найдите число, дубликат которого встречается первым. Другими словами, если имеется более 1 дублированного числа, нужно вернуть число, для которого второе вхождение имеет наименьший индекс. Если таких элементов нет, вернуть -1.
Например:
Для
[2, 4, 3, 5, 1] вывод должен быть -1.Для
[2, 3, 3, 1, 5, 2] вывод должен быть 3.Есть 2 дубликата: числа 2 и 3. Второй вхождение числа 3 имеет меньший индекс, чем второе вхождение числа 2, поэтому ответ 3.
Усложнённый вариант: Написать решение со сложностью
O(n) по времени и O(1) по памяти.Как обычно, приглашаю всех предлагать варианты решения в чате @netdeveloperschat
День четыреста десятый. #ЗадачиНаСобеседовании
Ответ на задачу
Как я и говорил, задача была довольно простая, и в чате быстро предложили решение. Поэтому давайте на этом примере рассмотрим советы, которые помогут решать такие задачи.
1. Найдите решение «в лоб» (brute-force).
Чаще всего это не должно быть проблемой. В нашем случае можно для каждого элемента перебирать массив (после этого элемента) и искать индекс следующего за ним дубликата. Ищем наименьший индекс дубликата. В конце выдаём элемент по найденному индексу. Это вполне рабочее решение, но его сложность по времени будет O(n!): для первого элемента перебираем N-1 элементов, для второго N-2 и т.д.
2. Рассмотрите более простой вариант проблемы.
В данном случае это уже есть в задании. Допустим, у нас нет ограничения по использованию памяти.
3. Изучите (хотя бы в общих чертах) алгоритмы и структуры данных.
Например, знание того, что коллекция HashSet вне зависимости от размера имеет постоянное время на поиск вхождения элемента, очень поможет в данном случае. Мы можем перебирать массив и добавлять найденные элементы в коллекцию HashSet. Одновременно проверяем, есть ли текущий элемент уже в коллекции. И если есть, то первый найденный в коллекции элемент и будет ответом. Сложность этого алгоритма O(N) по времени и O(N) по памяти, т.к. нам нужно будет хранить дополнительную коллекцию элементов.
4. Визуализируйте проблему.
Изобразите проблему на рисунке. Убедитесь, что вы правильно понимаете задание. Например, что в данном массиве
5. Придумайте несколько простых примеров и попытайтесь найти закономерность.
В этом конкретном случае этот совет мало полезен. Но в других задачах, например, про лестницу, очень может помочь. Рассмотрите простейший вариант, затем чуть более сложный, ещё более сложный. Что изменилось? Заметна ли закономерность? Изобразите решения графически, возможно, это поможет.
6. Перечитайте условие задачи, учли ли вы все нюансы?
В условии задачи сказано, что значения элементов находятся в диапазоне от 1 до N. Значит мы можем использовать для «запоминания» индексы элементов массива, которые тоже в диапазоне от 1 до N. Идея в том, чтобы, двигаясь по массиву «помечать» элемент по индексу, равному значению текущего элемента. Допустим, для массива
Посмотрим дальше: второй элемент 3 (по модулю), элемент с индексом 3 положительный, значит «помечаем» его
Замечания:
- в коде, конечно, нужно будет учесть, что индексы начинаются с 0 и отнимать 1 при обращении по индексу.
- в реальных условиях мы изменяем элементы массива, поэтому после нахождения ответа, возможно, нужно будет пройтись по массиву ещё раз сменить знак отрицательных элементов обратно.
7. Испытайте ваше решение на нескольких примерах, чтобы убедиться в его правильности.
Источники:
- Видео с подробным объяснением решения
- Видео с советами и ещё одной задачей и решением
Ответ на задачу
Как я и говорил, задача была довольно простая, и в чате быстро предложили решение. Поэтому давайте на этом примере рассмотрим советы, которые помогут решать такие задачи.
1. Найдите решение «в лоб» (brute-force).
Чаще всего это не должно быть проблемой. В нашем случае можно для каждого элемента перебирать массив (после этого элемента) и искать индекс следующего за ним дубликата. Ищем наименьший индекс дубликата. В конце выдаём элемент по найденному индексу. Это вполне рабочее решение, но его сложность по времени будет O(n!): для первого элемента перебираем N-1 элементов, для второго N-2 и т.д.
2. Рассмотрите более простой вариант проблемы.
В данном случае это уже есть в задании. Допустим, у нас нет ограничения по использованию памяти.
3. Изучите (хотя бы в общих чертах) алгоритмы и структуры данных.
Например, знание того, что коллекция HashSet вне зависимости от размера имеет постоянное время на поиск вхождения элемента, очень поможет в данном случае. Мы можем перебирать массив и добавлять найденные элементы в коллекцию HashSet. Одновременно проверяем, есть ли текущий элемент уже в коллекции. И если есть, то первый найденный в коллекции элемент и будет ответом. Сложность этого алгоритма O(N) по времени и O(N) по памяти, т.к. нам нужно будет хранить дополнительную коллекцию элементов.
4. Визуализируйте проблему.
Изобразите проблему на рисунке. Убедитесь, что вы правильно понимаете задание. Например, что в данном массиве
[2, 3, 1, 3, 5, 2]ответом будет 3 (дубликат с наименьшим индексом), а не 2 (дубликат элемента с наименьшим индексом).
5. Придумайте несколько простых примеров и попытайтесь найти закономерность.
В этом конкретном случае этот совет мало полезен. Но в других задачах, например, про лестницу, очень может помочь. Рассмотрите простейший вариант, затем чуть более сложный, ещё более сложный. Что изменилось? Заметна ли закономерность? Изобразите решения графически, возможно, это поможет.
6. Перечитайте условие задачи, учли ли вы все нюансы?
В условии задачи сказано, что значения элементов находятся в диапазоне от 1 до N. Значит мы можем использовать для «запоминания» индексы элементов массива, которые тоже в диапазоне от 1 до N. Идея в том, чтобы, двигаясь по массиву «помечать» элемент по индексу, равному значению текущего элемента. Допустим, для массива
[2, 3, 1, 3, 5, 2]первый элемент 2, тогда мы «помечаем» элемент с индексом 2. Это будет первая тройка. Проще всего сделать значение отрицательным. Получим
[2, -3, 1, 3, 5, 2]Двигаясь дальше, проверяем, не «помечен» ли уже элемент с индексом равным текущему значению. И если он помечен, значит такое число уже встречалось ранее, и это первый дубликат.
Посмотрим дальше: второй элемент 3 (по модулю), элемент с индексом 3 положительный, значит «помечаем» его
[2, -3, -1, 3, 5, 2]Третий элемент 1. Первый элемент положительный, «помечаем»:
[-2, -3, -1, 3, 5, 2]Четвёртый элемент 3. Третий элемент отрицательный (уже помечен), значит первый дубликат 3. Таким образом мы решили задачу за один проход массива - O(N) по времени и не используя дополнительную память – O(1) по памяти.
Замечания:
- в коде, конечно, нужно будет учесть, что индексы начинаются с 0 и отнимать 1 при обращении по индексу.
- в реальных условиях мы изменяем элементы массива, поэтому после нахождения ответа, возможно, нужно будет пройтись по массиву ещё раз сменить знак отрицательных элементов обратно.
7. Испытайте ваше решение на нескольких примерах, чтобы убедиться в его правильности.
Источники:
- Видео с подробным объяснением решения
- Видео с советами и ещё одной задачей и решением