Техническое интервью. Правильный ли мой подход?

Question

Недавно я взял интервью у компании-разработчика программного обеспечения. Я не прошел через сам первый раунд.

Может быть, я слишком медленно формировал идеи или решал проблемы и был недостаточно хорош для компании, для которой я брал интервью. Я хотел бы получить второе мнение о моем интервью, и я не могу найти кого-то лучше, чем Сообщество stackoverflow.

Так что это интервью было основным

1. Введение
2. Почему вы подали заявку на эту должность?
3. Один технический вопрос (подробности ниже)
4. Какое худшее программное обеспечение вы использовали? Зачем? Улучшение
5. Какое лучшее программное обеспечение вы использовали? зачем улучшать?

Оригинальный технический вопрос (по заданию интервьюера)

Учитывая диапазон чисел M ..... M + N-1, я создаю массив размером N и заменяю один из элементов в этом массиве числом. Как вы узнаете, какой элемент заменен?

Я попросил его повторить вопрос еще раз, так как я думал, что ввода недостаточно для решения проблемы. Он повторил заявление то же самое

Q. Тогда я спросил его, массив ли вы получили из диапазона числа в отсортированном порядке?
Опрашивающий: не обязательно

Q Мы знаем массив перед тем, как заменить элемент?
Опрашивающий: Нет

Затем я начал писать псевдокод (при этом громко размышляя). Я сразу понял, что это не будет работать, если исходный массив имел дубликаты. Так что я застрял на некоторое время, думая, как, черт возьми, это решить. Затем, наконец, я задал вопросы, которые имели значение

Q Как вы выбираете элементы из диапазона для формирования массива?
Интервьюер: У меня есть диапазон чисел M, M + 1, M + 2 .... M + N-1. Число выбирается только один раз. И я формирую массив размером N. (что, по сути, означает отсутствие дубликатов и выбор всех элементов в диапазоне)

Q А как насчет номера, которым вы его заменяете? Он лежит в том же диапазоне?
Опрашивающий: Да, это так.

Тогда все стало ясно

Вот что он имел в виду:
Q У меня есть диапазон чисел, начиная с M, например, M, M + 1, M + 2, M + 3 ... M + N. Я формирую массив размера N, так что каждый элемент выбирается только один раз, а исходный массив не имеет дубликатов. Я заменяю один из элементов в массиве числом в том же диапазоне. Узнайте, что я выбрал из диапазона для замены?

Это эквивалентно поиску дубликатов в массиве. Здесь после замены будет только одна пара дубликатов. Мы можем легко узнать это за O (N ^ 2) или O (nlogn) время. Я дал ему оба алгоритма.

В конце концов, я не удержался и спросил его: «Как я справился с этим вопросом?

Очевидно, он не был удовлетворен моим подходом к этому вопросу.
Как вы думаете, что я должен был сделать по-другому, отвечая на этот вопрос?

Answer 1

Если я правильно понял вопрос, вы можете решить его за O (n) раз.

1. найти два одинаковых элемента, используя "хэш" размера N
2. установить один из этих элементов на 0.
3. сделать сумму элементов и вычесть из вычисленной суммы, и у вас есть отсутствующий / замененный элемент (сумма элементов (2M + N-1) * (N) / 2

EDIT:

Объяснение 1. точки (найдите два одинаковых элемента, используя «хэш» размера N)

1. Если вы не знаете, M найти его (найти наименьший элемент O (n), только один цикл)
2. Выделить массив h размера N и установить элементы в 0 (может быть типа BOOL)
3. пройти через стол и проверить 1 в соответствующем месте от h
4. если это 1, то у вас есть коллизия, в противном случае установите 1.

код для последней части:

for(i=0;i<N;i++)
{
    if(h[a[i]-M] == 1) return i;
    h[a[i]-M] == 1;
}

Answer 2

Это классическое интервью «Загадка». На самом деле это довольно легко решить в O (n), используя описанный трюк ralu.

Одна из вещей, которую мы учим в Структурах данных 1, заключается в том, что когда ваш домен ограничен, возможно, можно использовать это для функции лучше, чем O (nlogn) [очевидно, сортировка домена без каких-либо дополнительных знаний невозможна сделано меньше, чем это. Поэтому, когда вы знаете свой домен, в вашей голове должна быть включена маленькая красная лампочка :-)

Я думаю, что вы должны были сразу же указать на вопрос о дубликатах. Было бы ясно, что вопрос не очень хорошо сформирован. Иначе он просто подумал, что ты медленный (хотя на самом деле это его вина ...).

Я также считаю, что вопросы 4,5 - это хорошие вопросы. Они показывают, какой опыт имеет заявитель, и как он думает. Таким образом, возможно, что вы провалили собеседование из-за того, что вы там сказали.

Answer 3

Поскольку для объема памяти, который вам разрешено использовать, не задано никаких ограничений, существует решение O (N): инициализировать массив A размером N со всеми нулями. Посмотрите на каждый элемент b в списке и отметьте A [b - M] = 1. Затем обойдите A и верните c, если A [c] == 0.

Answer 4

O (nlogn) Решение Использование деревьев B: ..

Предполагая, что мы создаем двоичное дерево, так как массив тоже сделан ... поскольку сложность построения двоичного дерева составляет O (n). Другое предположение состоит в том, что любой элемент, меньший, чем находится слева от двоичного дерева.

Здесь мы проверяем каждый элемент в массиве, чтобы его левый узел совпадал с родительским узлом для каждого поддерева. Чтобы пройти по дереву, требуется время O (logn). Мы пытаемся найти дубликат для каждого из n элементов. Следовательно, общее время O (nlogn).

O (n) Решение с использованием B-деревьев и рекурсии:

Мы можем построить btree, как упомянуто выше, используя те же предположения. Проверьте, чтобы каждый оставшийся ребенок был таким же, как родитель. Сделайте то же самое с обоими детьми. Условие остановки рекурсии: если child равен NULL. Следовательно, каждый узел проверяется один раз. Таким образом, общее время занимает O (n).

Answer 5

Абсолютно невозможно, чтобы кто-то здесь правильно ответил на ваш вопрос. Вы пишете это после факта ясным образом.

• возможно, вы бродили в своем интервью или не выражали себя так ясно, как в этом вопросе!
• возможно, вы не задавали правильные вопросы достаточно быстро
• возможно, вы не так быстро освоились после получения указателей (или не так быстро, как ваши конкуренты)
• возможно, интервьюеру не понравилось то, что вы начали писать код, прежде чем обдумать проблему

Я дал множество интервью, где я чувствовал, что человек, с которым я беру интервью , знает ответ на вопрос, который я задаю . Они просто не могут сказать мне: они растеряны или смущены в своем мышлении. Мыслительные процессы некоторых людей явно опережают их уста, и они смущают. Держу пари, что некоторые из них уйдут и составят идеальные ответы, как у вас ...

Я не могу сказать вам, делали ли вы эти вещи; возможно, ваш интервьюер был неразумным. Я знаю, что у меня были интервью, которые не были настолько хороши, потому что я чувствовал, что это не моя вина. Но в данный момент я думаю о таких вещах, как:

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