Хитрый вопрос Google интервью

Question

Мой друг берет интервью на работу. Один из вопросов на собеседовании заставил меня задуматься, просто хотелось получить обратную связь.

Есть 2 неотрицательных целых числа: i и j. Учитывая следующее уравнение, найдите (оптимальное) решение для итерации по i и j таким образом, чтобы вывод был отсортирован.

2^i * 5^j

Итак, первые несколько раундов будут выглядеть так:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

Как ни старайся, я не вижу узора. Ваши мысли?

Answer 1

Дейкстра получает красноречивое решение в «Дисциплине программирования».Он приписывает проблему Хэммингу.Вот моя реализация решения Дейкстры.

int main()
{
    const int n = 20;       // Generate the first n numbers

    std::vector<int> v(n);
    v[0] = 1;

    int i2 = 0;             // Index for 2
    int i5 = 0;             // Index for 5

    int x2 = 2 * v[i2];     // Next two candidates
    int x5 = 5 * v[i5];

    for (int i = 1; i != n; ++i)
    {
        int m = std::min(x2, x5);
        std::cout << m << " ";
        v[i] = m;

        if (x2 == m)
        {
            ++i2;
            x2 = 2 * v[i2];
        }
        if (x5 == m)
        {
            ++i5;
            x5 = 5 * v[i5];
        }
    }

    std::cout << std::endl;
    return 0;
}

Answer 2

вот более изощренный способ сделать это (более изощренный, чем мой предыдущий ответ):

представьте, что числа помещены в матрицу:нужно «пройтись» по этой матрице, начиная с (0,0).Вы также должны отслеживать, каковы ваши возможные следующие шаги.Когда вы начинаете с (0,0), у вас есть только две опции: (0,1) или (1,0): поскольку значение (0,1) меньше, вы выбираете это.затем сделайте то же самое для вашего следующего выбора (0,2) или (1,0).Пока у вас есть следующий список: 1, 2, 4.Ваш следующий ход - (1,0), поскольку его значение меньше (0,3).Однако теперь у вас есть три выбора для вашего следующего хода: либо (0,3), либо (1,1), либо (2,0).

Вам не нужна матрица для получения списка, но вам нужно следить за всеми вашими выборами (то есть, когда вы наберете 125+, у вас будет 4 варианта).

Answer 3

Используйте Min-heap.

Положите 1.

extract-Min.Скажем, вы получаете x.

Вставьте 2x и 5x в кучу.

Повтор.

Вместо сохранения x = 2 ^ i * 5 ^ j, вы можете сохранить (i, j) и использовать пользовательскую функцию сравнения.

Answer 4

Для решения на основе FIFO требуется меньше места для хранения.Код Python.

F = [[1, 0, 0]]             # FIFO [value, i, j]
i2 = -1; n2 = n5 = None     # indices, nexts
for i in range(1000):       # print the first 1000
    last = F[-1][:]
    print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
    if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
    if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
    F.append(min(n2, n5))

вывод:

  0.                     1 = 2^0 * 5^0
  1.                     2 = 2^1 * 5^0
  2.                     4 = 2^2 * 5^0
 ...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17

Answer 5

Это очень легко сделать O(n) на функциональных языках.Список l из 2^i*5^j чисел может быть просто определен как 1, а затем 2*l и 5*l объединены.Вот как это выглядит в Haskell:

merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)   
  | a < b   = a : (merge as (b:bs))
  | a == b  = a : (merge as bs)
  | b > a   = b : (merge (a:as) bs)

xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)

Функция merge дает вам новое значение в постоянном времени.То же самое map и, следовательно, то же самое l.

Answer 6

Вы должны следить за отдельными показателями их, и какова их сумма будет

так что вы начинаете с f(0,0) --> 1 теперь вам нужно увеличить один из них:

f(1,0) = 2
f(0,1) = 5

поэтому мы знаем, что следующим является 2 - мы также знаем, что можем увеличивать показатель i до тех пор, пока сумма не превысит 5.

Вы продолжаете идти вперед и назад, пока не достигнете нужного количества раундов.

Answer 7

Используя динамическое программирование, вы можете сделать это в O (n).Основная истина заключается в том, что никакие значения i и j не могут дать нам 0, и чтобы получить 1, оба значения должны быть 0;

TwoCount[1] = 0
FiveCount[1] = 0

// function returns two values i, and j
FindIJ(x) {
    if (TwoCount[x / 2]) {
        i = TwoCount[x / 2] + 1
        j = FiveCount[x / 2]
    }
    else if (FiveCount[x / 5]) {
        i = TwoCount[x / 2]
        j = FiveCount[x / 5] + 1
    }
}

При каждом вызове этой функции проверяют, установлены ли i и j, еслине нуль, затем заполните TwoCount и FiveCount

---

C ++ ответ.Извините за плохой стиль кодирования, но я тороплюсь: (

#include <cstdlib>
#include <iostream>
#include <vector>

int * TwoCount;
int * FiveCount;

using namespace std;

void FindIJ(int x, int &i, int &j) {
        if (x % 2 == 0 && TwoCount[x / 2] > -1) {
                cout << "There's a solution for " << (x/2) << endl;
                i = TwoCount[x / 2] + 1;
                j = FiveCount[x / 2];
        } else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
                cout << "There's a solution for " << (x/5) << endl;
                i = TwoCount[x / 5];
                j = FiveCount[x / 5] + 1;
        }    
}

int main() {
        TwoCount = new int[200];
        FiveCount = new int[200];

        for (int i = 0; i < 200; ++i) {
                TwoCount[i] = -1;
                FiveCount[i] = -1;
        }

        TwoCount[1] = 0;
        FiveCount[1] = 0;

        for (int output = 2; output < 100; output++) {
                int i = -1;
                int j = -1;
                FindIJ(output, i, j);
                if (i > -1 && j > -1) {
                        cout << "2^" << i << " * " << "5^" 
                                     << j << " = " << output << endl;
                        TwoCount[output] = i;
                        FiveCount[output] = j;
                }
        }    
}

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

Answer 8

Эта является соответствующей записью в OEIS.

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

1 2 4 5

, а затем, начиная со второго слагаемого, умножьте на 4 и 5, чтобы получить следующие два

1 2 45 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

и т. Д. *

Интуитивно, это кажется правильным, но, конечно, доказательства отсутствуют.

Answer 9

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

for x = 1 to n
{
  i=j=0
  y=x
  while ( y > 1 )
  {
    z=y
    if y divisible by 2 then increment i and divide y by 2
    if y divisible by 5 then increment j and divide y by 5

    if y=1 then print i,j & x  // done calculating for this x

    if z=y then exit while loop  // didn't divide anything this loop and this x is no good 
  }
}

Answer 10

Моя реализация основана на следующих идеях:

• Используйте две очереди Q2 и Q5, обе из которых инициализированы 1. Мы будем держать обе очереди в отсортированном порядке.
• На каждомшаг, удалите наименьший элемент числа MIN из Q2 или Q5 и распечатайте его.Если оба Q2 и Q5 имеют одинаковый элемент - удалите оба.Распечатайте этот номер.По сути, это объединение двух отсортированных массивов - на каждом шаге выбирайте наименьший элемент и переходите вперед.
• Поставьте в очередь от MIN * 2 до Q2 и от MIN * 5 до Q5.Это изменение не нарушает сортируемый инвариант Q2 / Q5, потому что MIN больше, чем предыдущий номер MIN.

Пример:

Start with 1 and 1 (to handle i=0;j=0 case):
  Q2: 1
  Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
  Q2: 2
  Q5: 5
Pick 2 and add 2*2 and 2*5:
  Q2: 4
  Q5: 5 10
Pick 4 and add 4*2 and 4*5:
  Q2: 8
  Q5: 5 10 20
....

Код в Java:

public void printNumbers(int n) {
    Queue<Integer> q2 = new LinkedList<Integer>();
    Queue<Integer> q5 = new LinkedList<Integer>();
    q2.add(1);
    q5.add(1);
    for (int i = 0; i < n; i++) {
        int a = q2.peek();
        int b = q5.peek();
        int min = Math.min(a, b);
        System.out.println(min);
        if (min == a) {
            q2.remove();
        }
        if (min == b) {
            q5.remove();
        }
        q2.add(min * 2);
        q5.add(min * 5);
    }
}