Интервью с AMAZON

Ответ 1

Я могу думать о O (N * K * N) (отредактированный после правильного указания zivo, а не хорошее решение теперь:() решение. 1. Сначала возьмите N указатель, указав на начальный элемент каждого из N массивов.

6, 16, 67
^ 
11,17,68
^
10, 15, 100
^ 

2. Узнайте наивысший и самый нижний элемент среди текущего указателя O (k) (6 и 11) и найдите разницу между ними. (5) | 3. Увеличьте указатель, который указывает на самый низкий элемент на 1 в этом массиве.

 6, 16, 67
    ^ 
 11,17,68
 ^
 10, 15, 100 (difference:5)
 ^ 

4. Продолжайте повторять шаги 2 и 3 и сохраняйте минимальную разницу.

 6, 16, 67
    ^ 
 11,17,68
 ^
 10,15,100 (difference:5)
    ^ 


 6, 16, 67
    ^ 
 11,17,68
    ^
 10,15,100 (difference:2)
    ^ 

Выше будет требуемое решение.

 6, 16, 67
    ^ 
 11,17,68
    ^
 10,15,100 (difference:84)
       ^ 

 6, 16, 67
        ^ 
 11,17,68
    ^
 10,15,100 (difference:83)
       ^ 

И так далее......

EDIT:

Его сложность может быть уменьшена с помощью кучи (как было предложено Uri). Я думал об этом, но столкнулся с проблемой: каждый раз, когда элемент извлекается из кучи, его номер массива должен быть найден, чтобы увеличить соответствующий указатель для этого массива. Эффективный способ найти номер массива может определенно уменьшить сложность до O (K * N log (K * N)). Один наивный способ - использовать структуру данных, такую ​​как

Struct
{
    int element;
    int arraynumer;
}

и восстановить исходные данные, такие как

 6|0,16|0,67|0

 11|1,17|1,68|1

 10|2,15|2,100|2

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

Ответ 2

Итак, вот алгоритм для решения этой проблемы в два этапа:

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

mixed_val [] - который содержит все числа
integ_ind [] - который содержит индекс, из которого этот массив первоначально принадлежал

этот шаг можно легко сделать в O (K * N * log (N)), но я думаю, что вы можете сделать лучше этого (возможно, нет, вы можете искать варианты сортировки слияния, потому что они делают шаг, подобный этому)

Теперь второй шаг:

проще просто поставить код вместо объяснения, так вот pseduocode:

int count[N] = { 0 }
int head = 0;
int diffcnt = 0;
// mindiff is initialized to overall maximum value - overall minimum value
int mindiff = combined_val[N * K - 1] - combined_val[0];
for (int i = 0; i &lt N * K; i++) 
{
  count[combined_ind[i]]++;

  if (count[combined_ind[i]] == 1) {
    // diffcnt counts how many arrays have at least one element between
    // indexes of "head" and "i". Once diffcnt reaches N it will stay N and
    // not increase anymore
    diffcnt++;
  } else {
    while (count[combined_ind[head]] > 1) {
      // We try to move head index as forward as possible while keeping diffcnt constant.
      // i.e. if count[combined_ind[head]] is 1, then if we would move head forward
      // diffcnt would decrease, that is something we dont want to do.
      count[combined_ind[head]]--;
      head++;
    }
  }

  if (diffcnt == N) {
    // i.e. we got at least one element from all arrays
    if (combined_val[i] - combined_val[head] &lt mindiff) {
      mindiff = combined_val[i] - combined_val[head];
      // if you want to save actual numbers too, you can save this (i.e. i and head
      // and then extract data from that)
    }
  }
}

результат находится в mindiff.

Время выполнения второго шага - O (N * K). Это связано с тем, что индекс "head" будет перемещаться только на максимум N * K. поэтому внутренний цикл не делает это квадратичным, он все еще линейный.

Таким образом, общее время работы алгоритма равно O (N * K * log (N)), однако это происходит из-за слияния шага, если вы можете приступить к лучшему шагу слияния, вы, вероятно, можете свести его к O (N * K).

Ответ 3

Эта проблема для менеджеров

У вас есть 3 разработчика (N1), 3 тестера (N2) и 3 администратора баз данных (N3) Выберите менее расходящуюся команду, которая может успешно выполнить проект.

int[n] result;// where result[i] keeps the element from bucket N_i

int[n] latest;//where latest[i] keeps the latest element visited from bucket N_i

Iterate elements in (N_1 + N_2 + N_3) in sorted order
{
    Keep track of latest element visited from each bucket N_i by updating 'latest' array;

    if boundary(latest) < boundary(result)
    {
       result = latest;
    }
}

int boundary(int[] array)
{
   return Max(array) - Min(array);
}

Ответ 4

У меня O (K * N * log (K)), с типичным исполнением намного меньше. В настоящее время не может думать ничего лучше. Сначала я объясню, что легче описать (несколько более длительное выполнение):

• Для каждого элемента f в первом массиве (цикл через элементы K)
• Для каждого массива, начиная со второго массива (цикл через массивы N-1)
• Сделайте двоичный поиск в массиве и найдите элемент, ближайший к f. Это ваш элемент (Log (K))

Этот алгоритм может быть оптимизирован, если для каждого массива вы добавляете новый индекс Floor. При перформации бинарного поиска найдите между "Этаж" и "К-1". Изначально индекс Floor равен 0, а для первого элемента вы просматриваете все массивы. Когда вы найдете элемент, ближайший к "f", обновите Index Floor с индексом этого элемента. Худший случай тот же (Floor может не обновляться, если максимальный элемент первого массива меньше любого другого минимума), но средний случай улучшится.

Ответ 5

Корректность для принятого ответа (решение терминала)

Предположим, что алгоритм находит ряд A = A lt [A], A [2],..., A [N] > который не является оптимальным решением (R).

Рассмотрим индекс j из R, так что элемент R [j] является первым элементом среди R, который алгоритм исследует и заменяет его следующим элементом в своей строке.

Пусть A 'обозначает решение кандидата на этой фазе (до замены). Так как R [j] = A '[j] - минимальное значение A', то это также минимум R. Теперь рассмотрим максимальное значение R, R [m]. Если A '[m] < R [m], то R можно улучшить, заменив R [m] на A' [m], что противоречит тому, что R является оптимальным. Следовательно, A '[m] = R [m]. Другими словами, R и A 'имеют один и тот же максимум и минимум, поэтому они эквивалентны. Это завершает доказательство: если R - оптимальное решение, то алгоритм гарантированно найдет решение так же хорошо, как R.

Ответ 6

для каждого элемента в 1-м массиве

    choose the element in 2nd array that is closest to the element in 1st array
    current_array = 2;
    do
    {
        choose the element in current_array+1 that is closest to the element in current_array
        current_array++;
    } while(current_array < n);

сложность: O (k ^ 2 * n)

Ответ 7

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

// if we take the above values as an example!
// then the idea would be to sort all three arrays while keeping another
// array to keep the reference to their sets (1 or 2 or 3, could be 
// extended to n sets)      
1   3   2   3   1   2   1   2   3    // this is the array that holds the set index
6   10  11  15  16  17  67  68  100  // this is the sorted combined array.
           |           |   
    5            2          33       // this is the computed least minimum,
                                     // the rule is to make sure the indexes of the values 
                                     // we are comparing are different (to make sure we are 
// comparing elements from different sets), then for example
// the first element of that example is index:1|value:6 we hold 
// that value 6 (that is the value we will be using to compute the least minimum, 
// then we go to the edge of the comparison which would be the second different index, 
// we skip index:3|value:10 (we remove it from the array) we compare index:2|value:11 
// to index:1|value:6 we obtain 5 which would go to a variable named leastMinimum = 5, 
// now we remove the indexes and values we already used,
// and redo the same steps.

Шаг 1:

1   3   2   3   1   2   1   2   3
6   10  11  15  16  17  67  68  100
           |   
5            
leastMinumum = 5

Шаг 2:

3   1   2   1   2   3
15  16  17  67  68  100
           |   
 2          
leastMinimum = min(2, leastMinumum) // which is equal 2

Шаг 3:

1   2   3
67  68  100

    33
leastMinimum = min(33, leastMinumum) // which is equal to old leastMinumum which is 2

Теперь: Мы предположим, что у нас есть элементы из того же массива, которые очень близки друг к другу (k = 2 на этот раз, что означает, что у нас есть только 3 набора с двумя значениями):

// After sorting the n arrays we will have the below indexes array and values array
1   1   2   3   2   3
6   7   8   12  15  16
*       *   *

* we skip second index of 1|7 and we take the least minimum of 1|6 and 3|12 (index:2|value:8 will be removed as it is not at the edges, we pick the minimum and maximum of the unique index subset of n elements)
1   3         
6   12
 =6
* second step we remove the values we already used, so the array become like below:

1   2   3
7   15  16
*   *   * 
7 - 16
= 9

Примечание: Другой подход, который потребляет больше памяти, будет состоять из создания N под-массивов, из которых мы будем сравнивать максимум - minumum

Итак, из массива отсортированных значений и соответствующего массива индексов мы извлекаем три других вспомогательных массива:

1   3   2   3   1   2   1   2   3
6   10  11  15  16  17  67  68  100

Первый массив:

1   3   2 
6   10  11

11-6 = 5

Второй массив:

3   1   2
15  15  17

17-15 = 2

Третий массив:

1   2   3
67  68  100

100 - 67 = 33