Задачи с собеседований по максимальным числам: как решить?

Question

[Nik_Set_7]

Существует такая задача:
нужно написать функцию, которая принимает на вход массив чисел (неотсортированных, допустим целых), возвращает также массив в котором содержатся:
- максимальное число А1
- три других максимальных числа А2, А3, А4, которые при перемножении дают А1

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

Comments

[Роман]

Не вижу тут возможности для примененичя/использования регулярок.

[sim3x]

Дайте пример массивов и результатов

В массиве гарантированно есть все 4 числа?

[Roman]

В лоб сортировка и окно на 3 элемента сдвиг 1.

[Сергей Соколов]

А1 – обязательно наибольшее во всём входном массиве или только наибольшее из тех, что можно получить умножением трёх других?

[Сергей Соколов]

Roman, [21,20,5,3,2,2] облом. Решение 20 = 5*2*2

[Ivan Yakushenko]

что будет слишком много условий и проверок.

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

[mactep3230]

а что значит

три других максимальных числа А2, А3, А4, которые при перемножении дают А1

?
к примеру - 7,6,2 и 7,4,3 какие из них максимальные?

[Сергей Соколов]

Кстати формально можно просто вернуть исходный массив, т.к. в условии не сказано, что кроме числе A1..A4 в выходном массиве ничего не содержится, также не указан их порядок - они должны лишь «содержаться» ; )
Правда, придётся сначала убедиться, что решение в массиве всё же содержится.

[Сергей Соколов]

mactep3230, 7,6,2 круче, т.к. сумма чисел больше)

[Nik_Set_7]

Ivan Yakushenko, Спасибо батюшка за наставления)))

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

Сорян, но эти мысли относятся к junior Frontend
Если какой-то товарищ задаст подобную задачу, то от человека будет ожидаться положительный ответ
А не то, как он думает, обдумывает и пр.
По крайне мере в большинстве контор именно так

Хотя я слышал, что где-то существуют конторы, где интересуются тобой, твоей личностью и как ты мыслишь

[Nik_Set_7]

Сергей Соколов, "максимальное число А1"
Это максимальное число во всём массиве

[Nik_Set_7]

mactep3230, 7,6,2

[Nik_Set_7]

Сергей Соколов, Тут не проверяется сумма чисел
6>4
поэтому 7,6,2

[Roman]

Сергей Соколов, в окне могут быть любые три элемента.
Самое первое сочетание, дающее искомый результат и будет ответом, при условии упорядоченности множества.
Это верхний уровень. А как строить сочетания без повторений из n по k алгоритм всем известный.

A1 >= A2 >= A3 >= A4 ...

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

https://ru.wikipedia.org/wiki/Задача_о_сумме_подмн...
https://ru.wikipedia.org/wiki/Задача_о_рюкзаке

но понял, что будет слишком много условий и проверок.

три цикла и один предикат.

[Roman]

Nik_Set_7,

его руководитель тоже ломал голову над ней.

https://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP

[Nik_Set_7]

Roman, Шикарно, почитаю, спасибо

[Adamos]

Признаться, в упор не понимаю, зачем полный перебор для поиска множителей.
1. Находите А1.
2. Раскладываете А1 на множители (это куда быстрее перебора всего массива на комбинации из трех элементов).
3. Составляете все варианты получения А1 из трех множителей (это перебор по очень небольшому объему данных).
4. Сортируете их по фактору "максимальности", который тут забыли уточнить (тоже вряд ли потребует диких вычислений).
5. И проходите по ним один раз, пока не обнаруживаете наличие всех трех в массиве (можно отсортировать или индексировать его для простоты поиска, но это уже экономия на спичках).

[Roman]

Adamos, п.2 тогда еще проверку на простоту нужно делать. Хотя ее в любом случае полезно сделать)

[Adamos]

Roman, не понял. При чем тут простота?

[Roman]

Adamos, https://ru.wikipedia.org/wiki/Простое_число

[Adamos]

Roman, это не ответ. Вариант "А1, 1, 1" - валиден по условию задачи, например.
Ну, и неудачное разложение на множители - это довольно убедительная проверка на простоту...

[PavelLevskiy]

Автор топика выложи свое решение плз.

[John_Nash]

три других максимальных числа А2, А3, А4, которые при перемножении дают А1

я б сначала выяснил, что это означает. Например, 20, -1, -3 > 10, 3, 2 или нет? Тут 20 > 10, но -1 < 3 и -3 < 2. В принципе, можно найти с равными суммами (тут выше кто-то предположил, что речь о суммах)

[Nik_Set_7]

John_Nash, числа целые, положительные
[20,400,1,100500,2,13,...]

[Roman]

John_Nash, без разницы сложение умножение. Алгоритм не меняется. Меняется знак операции.

Answer 1

[Сергей Соколов]

Отсортировать по убыванию и двумя циклами – некошерно?

на JS

const maxprod = arr => {
  const a = arr.slice().sort((a, b) => b - a);
  const max = a[0];
  const len = a.length;
  let iter = 0;
    
  for (let i = 1; i < len - 2; i++) {
    iter++;
    const A2 = a[i];
    const x2 = max / A2;
    if (!Number.isInteger(x2)) continue;
      
    for (let j = i + 1; j < len - 1; j++) {
      iter++;
      const A3 = a[j];
      const x3 = x2 / A3;
      if (!Number.isInteger(x3)) continue;
      
      if (!!~a.indexOf(x3)) {
        return [max, A2, A3, x3, iter]);
      }
    }
  }
  
  return false;
}

По сути циклов три, т.к. indexOf() всё равно перебирает массив.

Из оптимизаций только отсечение мелких хвостов, когда произведение становится меньше искомого.
И проверка каждого кандидата на делимость.
В хвост результата пихается ещё число итераций.

Тесты

[
  [20,5,3,2,2], // [ 20, 5, 2, 2, 3 ]
  [7,9,4,60,5,3,2,2], // [ 60, 5, 4, 3, 4 ]
  [1,2,3,199], // false
  [2430,2431,2431,2431,1,1,1,2,3,5,7,9,11,13,15,17,19,23], // [ 2431, 17, 13, 11, 8 ]
].forEach(test => console.log(test, maxprod(test)));

Comments

[Nik_Set_7]

Вообще не кошерно
Но за неимением другого - ок
Примерно такое же решение у меня
Спасибо

[Сергей Соколов]

Nik_Set_7, может, есть какие-то референсные метрики тру-кошерных решений? Типа, вот с таким массивом решение находится за N итераций при потреблении всего X памяти.

[Сергей Соколов]

upd. на каждом очередном числе проверять делимость на него А1 или результата деления на выбранные ранее А2, А3;

[PavelLevskiy]

Тест массива arr = [12,6,2,1]; не проходит...
Массив [12,12,1,1,1]; не проходит!

[Сергей Соколов]

PavelLevskiy, действительно. Спасибо, убрал проверки на ===1, они ни к чему.

Answer 2

[Andrey Tsvetkov]

Накидал решение "влоб". Работает 100% правильно, если я правильно понял суть задачи. Требует дополнительной памяти https://play.golang.com/p/ics2FIIFw7b

Comments

[Andrey Tsvetkov]

Я там забыл проверить на ноль. Исправился
https://play.golang.com/p/O1CJSYlKegP

Answer 3

[⚡ Kotobotov ⚡]

регулярки тебе никак не помогут в этой задаче
вот тут почитай про этот тип задач

Comments

[Nik_Set_7]

Да, согласен, скорее всего не помогут

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

Answer 4

[#]

Adamos,

2. Раскладываете А1 на множители (это куда быстрее перебора всего массива на комбинации из трех элементов).

все зависит от размеров чисел. для больших чисел это может быть сверсхложной задачей

Nik_Set_7, пока не заметил уточнения - гарантированно ли присутствие делителей в общем списке?
в общем случае, максимальное находится за один полный проход. это необходимо, но и достаточно.

а пляски с делителями зависят от нюансов - размер списка? он помещается оперативной памяти? или доступен только последовательно, из медленного источника?.. если делители гарантировано присутствуют, их можно найти за.. думаю количество проходов однозначно будет меньше чем для любого алгоритма сортировки )) upd если список существенно длинне 3х элементов ))

и существует ли гарантия присутствия делителей в списке? если нет +значения не велики +список большой +источник последовательный и медленный, возможно, Adamos будет прав. ну а для значений не более 8 битного целого, скорее будет прав однозначно ))

Comments

[Nik_Set_7]

Ну так можно зайти в дебри)
размер списка конечный, гарантированно будет положительный результат

[#]

Nik_Set_7, вас и заводят в дебри. и смотрят что вы он них знаете?

.. допустим вам предлагается список 5, 7, 11, 13, 17, 19, 23. попробуйте выполнить озвученные условия.. хоть с карандашом на бумажке

[#]

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

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

[#]

Nik_Set_7, если получить подтверждение, о том что:
1 - список состоит из целых не более 32 бит
2 - спирок можно загрузить в оперативную память

то все равно две примерно равноуспешные стратегии:
- в любом случае за один проход нахождение МАКСИМАЛЬНОГО целого

потом можно факторизовать (разложить на множители) и попытаться их искать начиная с максимального. если простых делителей оказалось более 3х - сразу надо проверять возможность, что в списке есть составные делители. но это все можно за еще один проход ))

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

вернемся к реальности - тот же блокчейн биткоина, вы уже не можете скачать за доли секунды, оно довольно велик. и для интенсивного анализа, потребуется приличный объем ОЗУ. и вишенка на тортик - там офигенно большие целые )) .. так что все сказанное выше уже будет не айс ))

[#]

Nik_Set_7, так что у вас только одна определенность - максимальное ищется за один полный проход

.. а дальше сплошное коварство собеседователей.. и кто его знает, какой оно глубины ))

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

[#]

Nik_Set_7, а ну да.. по поводу поиска делителей - поверьте человеку погрызшему факторизацию )).. сортировка исходно списка тут только пустая трата времени ))

Answer 5

[Dimonchik]

допустим целых

хороший прикид

там, случаем, что множители целые "допустим" не отвалилось?

Answer 6

[John_Nash]

числа целые, положительные

Тогда, если считать, что сумма должна быть максимальной. То все просто.
Отсортировать. Взять 1е максимальное. A1
Взять 2е максимальное (цикл от максимума до минимума) A2
Разделить на второе максимальное (текущее). Получить цикл 2го уровня. В нем также брать значения меньше или равн. результата деления
Разделить частное на A3, проверить наличие результата в списке значений.

Как только найдено, можно завершать

Comments

[Сергей Соколов]

вот и текстовое описание моего варианта решения : )

Answer 7

[vvs46]

Если я правильно понял задачу, моё решение в лоб:

Source

#include <iostream>
#include <windows.h>
#include <vector>
std::vector<int> DoTheJob(std::vector<int> v)
{

    int tmp;
    std::vector<int> result;
    bool flagfound = false;


    //sorting
    for(int i=0;i<v.size()-1;i++)
    {
        for (int j=i+1;j<v.size();j++)
        {
            if(v[j]>v[i])
            {
                tmp=v[i];
                v[i]=v[j];
                v[j]=tmp;
            };
        };
    };

    //sorting_end
    result.push_back(v[0]);
    for(int i=1; i<v.size()-2;i++)
    {
        if (flagfound)
                {
                    break;
                }
        for(int j=i+1;j<v.size()-1;j++)

        {
            if (flagfound)
                {
                    break;
                };
            for(int k=j+1;k<v.size();k++)
            {
                if (flagfound)
                {
                    break;
                };
                if(v[0]==v[i]*v[j]*v[k])
                    {
                        result.push_back(v[i]);
                        result.push_back(v[j]);
                        result.push_back(v[k]);
                        flagfound = true;
                    }
            };
        };
    }
    return result;
};
int main()
{   int q = 10;
    std::vector<int> v;
    for (int i=0;i<q;i++)
    {
        v.push_back((GetTickCount()+rand())%10);
        std::cout<< v[i]<<" ";
    };
    std::cout<<std::endl;
    std::vector<int> solution = DoTheJob(v);
    std::cout << "Max element: "<<solution[0];
    if (solution.size()==4)
    {
        std::cout<<", multipliers: "<<solution[1]<<", "<< solution[2]<<", "<<solution[3];
    }
    else
    std::cout<< ", no multipliers.";
    return 0;
}