Интервью вопросов ранжирования FizzBuzz (1), реализации malloc (10) [закрыто]

10

Мне бы хотелось узнать ваше мнение о сложности следующего вопроса для интервью:

Найти непрерывный подмассив с максимальной суммой в массиве целых чисел за O (n) времени.

Эта тривиальная проблема звучания стала известной Джону Бентли в его книге «Программирование жемчуга», где он использовал ее для демонстрации методов проектирования алгоритмов.

В масштабе 1-10, 1 - тест FizzBuzz (или HoppityHop ), а 10 - реализация функции C stdlib malloc (), как бы вы оценили вышеуказанную проблему?

Я думаю, что люди, которые могут лучше всего ответить на этот вопрос, это те, кто читал Программирование Жемчуг и пытался решить эту проблему самостоятельно. Чтобы мотивировать тех, кто не знает, «Программирование жемчужин» многократно фигурирует в списке «10 лучших книг по программированию».

Несколько комментариев могут помочь получить лучший рейтинг:

  • Реализация malloc () не так грозна, как кажется. См., Например, язык программирования K & R's C. Это иногда спрашивают в Microsoft .

  • Наблюдение CLRS по решению проблем: зачастую решить проблему с нуля сложнее, чем проверить четко представленное решение, особенно при работе в условиях ограниченного времени .

books interview algorithms БЛРС
источник
12
Трудность здесь в том, что целые числа могут быть отрицательными? (в противном случае весь массив всегда является наибольшим подмассивом, поэтому O (1) :-P)
Macke
4
Задача должна сказать: «Найти смежный подмассив ...»
v64
6
Я бы не стал "в O (N)" требование в интервью. Вы можете начать с наивного решения, а затем уточнить его, если хотите, но я не ожидаю, что кто-то сможет получить решение O (n) в течение 1-часового интервью без предварительного ознакомления с этим алгоритмом.
Дин Хардинг
2
Правильно. Это простая проблема, если вы разрешите O (n²) решения.
Ден04
@ Дин, я надеюсь, что они смогут переместить текущую сумму типа aveerage из местоположения j в j + 1 в O (1). Возможно, чтобы быть справедливым, это может быть предоставлено в качестве подсказки. (Я предполагаю, что длина подмассива была заранее определена)
Омега Центавра

Ответы:

17

Это действительно зависит от разработчика.

Если бы malloc было 10, то я бы оценил эту проблему как 20. Но опять же, я делал malloc раньше и, вероятно, мог бы сделать это снова.

Кто-то, кто сделал эту проблему или знает соответствующий алгоритм вершины головы, сделает его 5, а malloc () - 10.

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

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

Мартин Йорк
источник
погода -> будь то в четвертом абзаце (и извините за шум, у меня нет представителя, чтобы делать опечатки ...)
Матье М.
Мартин, я думаю, что это зависит от типа приложения, для которого ты проводишь собеседование. Для типов систем malloc довольно прост. Для меня - я застрял, [я предполагаю, что адрес и длина стека были намеренно скрыты от меня] с malloc, но проблема с подрешеткой почти тривиальна. Ключом является соответствие вопросов с потребностями работы.
Омега Центавра
8

Думаю, рейтинг должен быть как минимум двухмерным. FizzBuzz - mallocописывает диапазон по одной оси, я бы назвал это «технологической сложностью». Но этого единственного измерения, безусловно, недостаточно для описания проблемы. Чтобы решить данную проблему, разработчик должен думать больше, чем код , в то время как реализация mallocтребует большей дисциплины кодирования, чем создания сложных алгоритмов.

Вот как я бы устроил эти проблемы:

введите описание изображения здесь

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

П Швед
источник
2

Я думаю, что это значительно сложнее, чем FizzBuzz или HoppityHop - эти два не более, чем простой if-else или switch-case в цикле.

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

По вашей шкале от 1 до 10 я бы, вероятно, поставил оценку от 3 до 5.

* Пока сервер не работал, я обнаружил, что у проблемы максимального подмассива есть своя собственная страница в Википедии.

oosterwal
источник
Может кто-нибудь объяснить, зачем нужен алгоритм, описанный в википедии, когда у меня работает следующий концептуально гораздо более простой алгоритм: за один проход вычислите кумулятивную сумму, найдя минимум и максимум обычным способом. Последовательная последовательность с максимальной суммой начинается после минимального совокупного индекса и продолжается вплоть до максимального совокупного индекса.
Бен Фойгт
2
@Ben Voigt: попробуйте последовательность {+2, -4, +1} или {+1, +1, -1, -1, -1, -1, +1}. На самом деле, метод Кадане очень прост - он сканирует массив только один раз и обновляет три переменные в стиле дианмического программирования.
rwong
@ rwong: ну ладно, Кадане нужен в том случае, когда минимум идет после максимума. И я считаю 5 переменных, а не 3, плюс индекс цикла.
Бен Фойгт
@Ben: вы правы, это 5 переменных плюс индекс цикла.
Rwong
1

Я даю это 3. Помимо большинства программистов, с которыми я брал интервью, но это легкая проблема для тех, кого я рекомендовал нанять.

Кевин Клайн
источник