AMAZON Wywiad Pytanie

Oto algorytm do rozwiązania tego problemu w dwóch krokach:

Pierwszym krokiem jest połączenie wszystkich tablic w jedną posortowaną tablicę, która wyglądałaby tak:

Combined_val [] - który zawiera wszystkie liczby
combined_ind [] - która przechowuje indeks, do której tablicy pierwotnie należała ta liczba

Ten krok można łatwo zrobić w O(K*N*log (N)), ale myślę, że możesz zrobić lepiej niż to zbyt (może nie, można wyszukać warianty sortowania scalonego, ponieważ robią krok podobny do tego)

Teraz drugi krok:

Łatwiej jest po prostu umieścić kod zamiast wyjaśniać, więc tutaj jest 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)
    }
  }
}

Wynik jest w mindiff.

Czas trwania drugiego kroku wynosi O (N * K). Dzieje się tak dlatego, że indeks "head" przesunie się maksymalnie O N*K razy. tak więc wewnętrzna pętla nie czyni tego kwadratowego, jest nadal liniowa.

Więc całkowity czas działania algorytmu wynosi O( N * K * log(N)), jednak jest to spowodowane krokiem scalania, jeśli można wymyślić lepsze krok scalania możesz prawdopodobnie sprowadzić go do O ( N * K).

Ten problem jest dla menedżerów

Masz 3 programistów (N1), 3 testerów (N2) i 3 DBAs (N3) Wybierz mniej rozbieżny zespół, który może pomyślnie uruchomić projekt.

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);
}

Mam O (K*N * log (K)), z typowym wykonaniem znacznie mniej. Obecnie nie może myśleć nic lepszego. Wyjaśnię najpierw łatwiejsze do opisania (nieco dłuższe wykonanie):

1. dla każdego elementu f w pierwszej tablicy (Pętla przez elementy K)
2. dla każdej tablicy, począwszy od drugiej tablicy (Pętla przez N-1 tablic)
3. Wykonaj wyszukiwanie binarne na tablicy i znajdź element najbliższy f. jest to twój element(Log (K))

Algorytm ten można zoptymalizować, jeśli dla każda tablica dodaje nowy indeks podłogi. Podczas przeszukiwania binarnego Szukaj między 'Floor' A 'K-1'. Początkowo indeks podłogi wynosi 0, a dla pierwszego elementu przeszukujemy całe tablice. Gdy znajdziesz element najbliższy 'f', zaktualizuj indeks podłogi o Indeks tego elementu. Gorsze przypadki są takie same (Floor może nie aktualizować, jeśli maksymalny element pierwszej tablicy jest mniejszy niż jakiekolwiek inne minimum), ale średnia wielkość liter poprawi się.

Dowód poprawności zaakceptowanej odpowiedzi (rozwiązanie Terminala)

Załóżmy, że algorytm znajduje szereg A= co nie jest optymalnym rozwiązaniem (R).

Rozważmy indeks j W R, taki, że pozycja R [j] jest pierwszą pozycją spośród r, którą algorytm bada i zastępuje ją następnym elementem w swoim wierszu.

Niech A ' oznacza rozwiązanie kandydata na tym etapie (przed zastąpieniem). Ponieważ R [j]=A '[j] jest minimalną wartością A', jest również minimum R. Teraz rozważmy maksymalną wartość R, R[M]. Jeśli A '[m]

Dla każdego elementu w 1. tablicy

    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);

Złożoność: O (k^2 * n)

Oto moja logika, jak rozwiązać ten problem, pamiętając, że musimy wybrać jeden element z każdej tablicy N (aby obliczyć najmniejsze minimum)

// 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.

Krok 1:

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

Krok 2:

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

Krok 3:

1   2   3
67  68  100

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

Teraz: Zakładamy, że mamy elementy z tej samej tablicy, które są bardzo blisko siebie (k = 2 Tym razem, co oznacza, że mamy tylko 3 zbiory o dwóch wartościach) :

// 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

Uwaga: Inne podejście, które zużywa więcej pamięci, polegałoby na tworzeniu N pod-tablic, z których porównywalibyśmy maksimum-minumum

Tak więc z poniższej posortowanej tablicy wartości i odpowiadającej jej tablicy indeksów wyodrębniamy trzy inne tablice podrzędne:

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

Pierwsza Tablica:

1   3   2 
6   10  11

11-6 = 5

Druga Tablica:

3   1   2
15  15  17

17-15 = 2

trzeci Array:

1   2   3
67  68  100

100 - 67 = 33