Задачи с собеседований по максимальным числам: как решить?
Существует такая задача:
нужно написать функцию, которая принимает на вход массив чисел (неотсортированных, допустим целых), возвращает также массив в котором содержатся:
- максимальное число А1
- три других максимальных числа А2, А3, А4, которые при перемножении дают А1
Начал писать функцию с выделением max и сортировкой, потом начал писать вложенные циклы, но понял, что будет слишком много условий и проверок.
Есть мысль, что тут могут помочь регулярки, но пока не знаю, как это реализовать.
Это не всегда плохо. Это показывает то, что ты знаешь принцип решения подобных задач, но не так хорошо знаком с языком программирования, что бы решать такие задачи "красиво". Если ты будешь готовиться к собеседованиям, что бы максимально хорошо их пройти, то можешь столкнуться на работе с задачей, которую не сможешь решить и тебя выпрут. При этом если на собеседовании ты покажешь свои реальные знания и работодателя это устроит, то проблем у тебя не будет - будешь спокойно себе работать и развиваться.
Кстати формально можно просто вернуть исходный массив, т.к. в условии не сказано, что кроме числе A1..A4 в выходном массиве ничего не содержится, также не указан их порядок - они должны лишь «содержаться» ; )
Правда, придётся сначала убедиться, что решение в массиве всё же содержится.
Как бэ я уже работаю, а данная задача была задана моему знакомому на должность middle frontend разработчика. При этом он не смог решить задачу, его руководитель тоже ломал голову над ней.
Сорян, но эти мысли относятся к junior Frontend
Если какой-то товарищ задаст подобную задачу, то от человека будет ожидаться положительный ответ
А не то, как он думает, обдумывает и пр.
По крайне мере в большинстве контор именно так
Хотя я слышал, что где-то существуют конторы, где интересуются тобой, твоей личностью и как ты мыслишь
Сергей Соколов, в окне могут быть любые три элемента.
Самое первое сочетание, дающее искомый результат и будет ответом, при условии упорядоченности множества.
Это верхний уровень. А как строить сочетания без повторений из n по k алгоритм всем известный.
A1 >= A2 >= A3 >= A4 ...
да кстати еще может быть целочисленное переполнение при умножении.
и крайние случаи когда в последовательности есть нули, единицы и со знаком минус.
Признаться, в упор не понимаю, зачем полный перебор для поиска множителей.
1. Находите А1.
2. Раскладываете А1 на множители (это куда быстрее перебора всего массива на комбинации из трех элементов).
3. Составляете все варианты получения А1 из трех множителей (это перебор по очень небольшому объему данных).
4. Сортируете их по фактору "максимальности", который тут забыли уточнить (тоже вряд ли потребует диких вычислений).
5. И проходите по ним один раз, пока не обнаруживаете наличие всех трех в массиве (можно отсортировать или индексировать его для простоты поиска, но это уже экономия на спичках).
Roman, это не ответ. Вариант "А1, 1, 1" - валиден по условию задачи, например.
Ну, и неудачное разложение на множители - это довольно убедительная проверка на простоту...
три других максимальных числа А2, А3, А4, которые при перемножении дают А1
я б сначала выяснил, что это означает. Например, 20, -1, -3 > 10, 3, 2 или нет? Тут 20 > 10, но -1 < 3 и -3 < 2. В принципе, можно найти с равными суммами (тут выше кто-то предположил, что речь о суммах)
