По условию задачи любое число этого ряда должно представлять собой произведение 3^a · 5^b · 7^c.

Давайте посмотрим на список чисел, удовлетворяющих нашим требованиям:

Поскольку 3^a-1 · 5^b · 7^c < 3^a · 5^b · 7^c, то число 3^a-1 · 5^b · 7^c должно попасть в список, как и все перечисленные далее числа:

• 3^a-1 · 5 · 7^c
• 3^a · 5^b-1 · 7^c
• 3^a · 5^b · 7^c-1

Другой способ — представить каждое число в следующем виде:

• 3 · (некоторое предыдущее число из числового ряда);
• 5 · (некоторое предыдущее число из числового ряда);
• 7 · (некоторое предыдущее число из числового ряда).

Мы знаем, что A_k можно записать как (3, 5 или 7) · (некоторое значение из { A₁, …, A_k-1}). Мы также знаем, что A_k является следующим числом в данном ряду. Поэтому A_k должно быть наименьшим «новым» числом, которое может быть получено умножением каждого значения в списке на 3, 5 или 7.

Как найти A_k? Мы можем умножить каждое число в списке на 3, 5 или 7 и найти наименьший новый результат. Но такое решение потребует O(k²) времени. Неплохо, но можно сделать и лучше.

Вместо умножения всех элементов списка на 3, 5 или 7 можно рассматривать каждое предыдущее значение как основу для расчета трёх последующих значений. Таким образом, каждое число A_i может использоваться для формирования следующих форм:

• 3 · A_i
• 5 · A_i
• 7 · A_i

Эта идея поможет нам спланировать все заранее. Каждый раз, когда мы добавляем в список число A_i, мы держим значения 3A_i, 5A_i и 7A_i в «резервном» списке. Чтобы получить A_i+1, достаточно будет найти наименьшее значение во временном списке.

Наш код может быть таким:

public static int removeMin(Queue<integer> q) {
    int min = q.peek();
    for(Integer v : q) {
        if (min >v){
            min=v;
        }
    }
    while (q.contains(min)) {
        q.remove(min);
    }
    return min;
}
 
public static void addProducts(Queue<Integer> q, int v) {
    q.add(v * 3);
    q.add(v * 5);
    q.add(v * 7);
}
 
public static int getKthMagicNumber(int k) {
    if (k < 0) return 0;
    
    int val = 1;
    Queue<Integer> q = new LinkedList<Integer>();
    addProducts(q, 1);
    for(int i = 0; i < k; i++) {
        val = removeMin(q);
        addProducts(q, val);
    }
    return val;
}

Данный алгоритм гораздо лучше предыдущего, но все еще не идеален.

Для генерирования нового элемента A_i мы осуществляем поиск по связному списку, где каждый элемент имеет вид:

• 3 · предыдущий элемент;
• 5 · предыдущий элемент;
• 7 · предыдущий элемент.

Давайте уберем избыточные расчеты. Допустим, что наш список имеет вид:

q₆ = {7A₁, 5A₂, 7A₂, 7A₃, 3A₄, 5A₄, 7A₄, 5A₅, 7A₅}

Когда мы ищем минимальный элемент в списке, то проверяем сначала 7A₁ < min, а затем 7A₅ < min. Глупо, не правда ли? Поскольку мы знаем, что A₁ < A₅, то достаточно выполнить проверку 7A₁ < min.

Если бы мы разделили список по постоянным множителям, то должны были бы проверить только первое из произведений на 3, 5 и 7. Все последующие элементы будут больше.

Таким образом, наш список принимает вид:

• Q36 = {3A₄}
• Q56 = {5A₂, 5A₄, 5A₅}
• Q76 = {7A₁, 7A₂, 7A₃, 7A₄, 7A₅}

Чтобы найти минимум, достаточно проверить начало каждой очереди:

Y = min(Q3.head(), Q5.head(), Q7.head())

Как только мы вычислим y, нужно добавить 3y в список Q3, 5y в Q5 и 7y в Q7. Но мы хотим вставлять эти элементы, только если они отсутствуют в других списках.

Как, например, 3y может попасть в какой-нибудь другой список? Допустим, элемент y был получен из Q7, это значит, что y = 7x. Если 7x — наименьшее значение, значит, 3x уже было задействовано. А как мы действовали, когда увидели 3x? Правильно, мы вставили 7 · 3x в Q7. Обратите внимание, что 7 · 3x = 3 · 7x = 3y.

В общем виде: если мы берем элемент из Q7, он будет иметь вид 7 · suffix. Мы знаем, что 3 · suffix и 5 · suffix уже обработаны, и элемент 7 · 3 ·suffix добавлен в Q7. Единственное значение, которое мы еще не встречали — 7 · 7 · suffix, поэтому добавляем его в Q7.

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

Q3 = 3
Q5 = 5
Q7 = 7
Удаляем min = 3, вставляем 3*3 в Q3, 5*3 в Q5, 7*3 в Q7
Q3 = 3*3
Q5 = 5, 5*3
Q7 = 7, 7*3
Удаляем min = 5. 3*5 – дубль, значит, мы уже обработали 5*3.
Вставляем 5*5 в Q5, 7*5 в Q7
Q3 = 3*3
Q5 = 5*3, 5*5
Q7 = 7, 7*3, 7*5
Удаляем min = 7. 3*7 и 5*7 – дубли,
уже обработали 7*3 и 7*5.
Вставляем 7*7 в Q7
Q3 = 3*3
Q5 = 5*3, 5*5
Q7 = 7*3, 7*5, 7*7
Удаляем min = 3*3 = 9. Вставляем 3*3*3
в Q3, 3*3*5 в Q5, 3*3*7 в Q7.
Q3 = 3*3*3
Q5 = 5*3, 5*5, 5*3*3
Q7 = 7*3, 7*5, 7*7, 7*3*3
Удаляем min = 5*3 =15. 3*(5*3) –
дубль, так как уже обработали 5*(3*3).
Вставляем 5*5*3 в Q5, 7*5*3 в Q7
Q3 = 3*3*3
Q5 = 5*5, 5*3*3, 5*5*3
Q7 = 7*3, 7*5, 7*7, 7*3*3, 7*5*3
Удаляем min = 7*3 = 21. 3*(7*3) и 5*(7*3) – дубли,
уже обработали 7*(3*3) и 7*(5*3). Вставляем 7*7*3 в Q7
Q3 = 3*3*3
Q5 = 5*5, 5*3*3, 5*5*3
Q7 = 7*5, 7*7, 7*3*3, 7*5*3, 7*7*3

Структура нашего алгоритма будет иметь вид:

1. Инициализируем array и очереди Q3, Q5 и Q7.
2. Вставляем 1 в array.
3. Вставляем 1·3, 1·5, 1·7 в Q3, Q5 и Q7 соответственно.
4. Пусть x будет минимальным элементом в Q3, Q5 и Q7.Присоединим x к magic.
5. Если x находится в:
   • Q3 => присоединяем x·3, x·5 и x·7 к Q3, Q5 и Q7. Удаляем x из Q3.
   • Q5 => присоединяем x·5 и x·7 к Q5 и Q7. Удаляем x из Q5.
   • Q7 => присоединяем x·7 к Q7. Удаляем x из Q7.
6. Повторяем шаги 4-6, пока k-й элемент не будет найден.

Следующий код реализует данный алгоритм:

public static int getKthMgicNumber(int k) {
    if (k < 0) {
        return 0;
    }
    int val = 0;
    Queue<Integer> queue3 = new LinkedList<Integer>();
    Queue<Integer> queue5 = new LinkedList<Integer>();
    Queue<Integer> queue7 = new LinkedList<Integer>();
    queue3.add(1);
    
    /* Итерация от 0 до k */
    for (int i = 0; i <= k; i++) {
        int v3 = queue3.size() > 0 ? queue3.peek() :
        Integer.MAX_VALUE;
        int v5 = queue5.size() > 0 ? queue5.peek() :
        Integer.MAX_VALUE;
        int v7 = queue7.size() > 0 ? queue7.peek() :
        Integer.MAX_VALUE;
        val = Math.min(v3,Mathmin(v5, v7));
        if(val == v3){ // ставим в очередь 3, 5 и 7
            queue3.remove();
            queue3.add(3 * val);
            queue5.add(5 * val);
        } else if (val == v5) {
        // ставим в очередь 5 и 7
            queue5.remove();
            queue5.add(5 * val);
        } else if (val == v7) {
        // ставим в очередь Q7
            queue7.remove();
        }
        queue7.add(7 * val);
        // всегда добавляем в очередь Q7
    }
    return val;
}

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

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

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

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации