trabajar - Pregunta de la entrevista de AMAZON
prueba tecnica amazon (7)
Prueba de corrección de la respuesta aceptada (solución de Terminal)
Supongamos que el algoritmo encuentra una serie A = <A [1], A [2], ..., A [N]> que no es la solución óptima (R).
Considere el índice j en R, tal que el elemento R [j] es el primer elemento entre R que el algoritmo examina y lo reemplaza con el siguiente elemento en su fila.
Dejemos que A ''denote la solución candidata en esa fase (antes de la sustitución). Dado que R [j] = A ''[j] es el valor mínimo de A'', también es el mínimo de R. Ahora, considere el valor máximo de R, R [m]. Si A ''[m] <R [m], entonces R puede mejorarse reemplazando R [m] con A'' [m], lo que contradice el hecho de que R es óptimo. Por lo tanto, A ''[m] = R [m]. En otras palabras, R y A ''comparten el mismo máximo y mínimo, por lo tanto son equivalentes. Esto completa la prueba: si R es una solución óptima, entonces el algoritmo está garantizado para encontrar una solución tan buena como R.
Dada una N matrices de tamaño K cada una ... cada uno de estos elementos K en las N matrices se ordenan, cada uno de estos elementos N * K es único. Elija un solo elemento de cada una de las N matrices, del subconjunto elegido de N elementos. Resta el elemento mínimo y máximo. Ahora, esta diferencia debería ser lo menos posible Mínimo ... Espero que el problema esté claro :) :)
Muestra:
N=3, K=3
N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100
aquí, si se eligen 16, 17, 15, obtenemos la diferencia mínima como 17-15 = 2.
Aquí está mi lógica sobre cómo resolver este problema, teniendo en cuenta que debemos elegir un elemento de cada una de las N matrices (para calcular el mínimo)
// 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.
Paso 1 :
1 3 2 3 1 2 1 2 3
6 10 11 15 16 17 67 68 100
|
5
leastMinumum = 5
Paso 2:
3 1 2 1 2 3
15 16 17 67 68 100
|
2
leastMinimum = min(2, leastMinumum) // which is equal 2
Paso 3:
1 2 3
67 68 100
33
leastMinimum = min(33, leastMinumum) // which is equal to old leastMinumum which is 2
Ahora: Suponemos que tenemos elementos de la misma matriz que están muy cerca uno del otro (k = 2 esta vez, lo que significa que solo tenemos 3 conjuntos con dos valores):
// 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
Nota: Otro enfoque que consume más memoria consistiría en crear N subarreglos a partir de los cuales compararíamos el máximo - mínimo
Entonces, a partir de la siguiente matriz de valores ordenados y su correspondiente matriz de índices, extraemos otras tres subarreglas:
1 3 2 3 1 2 1 2 3
6 10 11 15 16 17 67 68 100
Primera matriz:
1 3 2
6 10 11
11-6 = 5
Segunda matriz:
3 1 2
15 15 17
17-15 = 2
Tercera matriz:
1 2 3
67 68 100
100 - 67 = 33
Así que aquí hay un algoritmo para resolver este problema en dos pasos:
El primer paso es combinar todas sus matrices en una matriz ordenada que se vería así:
combined_val [] - que contiene todos los números
combined_ind [] - que contiene el índice de la matriz a la que pertenecía originalmente este número
este paso se puede hacer fácilmente en O (K * N * log (N)) pero creo que puede hacerlo mejor que eso también (tal vez no, puede buscar variantes de tipo de combinación porque sí lo son)
Ahora segundo paso:
es más fácil simplemente poner el código en lugar de explicarlo, así que aquí está el 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 < 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] < 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)
}
}
}
El resultado está en mindiff.
El tiempo de ejecución del segundo paso es O (N * K). Esto se debe a que el índice "cabeza" solo se moverá N * K veces el máximo. por lo que el bucle interno no hace que esto sea cuadrático, todavía es lineal.
Por lo tanto, el tiempo total de ejecución del algoritmo es O (N * K * log (N)), sin embargo, esto se debe a la combinación de pasos. Si puede encontrar un mejor paso de fusión, probablemente pueda reducirlo a O (N * K).
Este problema es para los gerentes.
Tiene 3 desarrolladores (N1), 3 probadores (N2) y 3 DBA (N3) Elija el equipo menos divergente que puede ejecutar un proyecto con éxito.
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);
}
Puedo pensar en la solución O (N * K * N) (editada después de haber sido señalada correctamente por zivo, no es una buena solución ahora :().
1. Tome el puntero N que apunta inicialmente al elemento inicial de cada una de las N matrices.
6, 16, 67
^
11,17,68
^
10, 15, 100
^
2. Averigua el elemento más alto y más bajo entre el puntero actual O (k) (6 y 11) y encuentra la diferencia entre ellos. (5)
3. Incremente el puntero que apunta al elemento más bajo en 1 en esa matriz.
6, 16, 67
^
11,17,68
^
10, 15, 100 (difference:5)
^
4. Siga repitiendo los pasos 2 y 3 y almacene la diferencia mínima.
6, 16, 67
^
11,17,68
^
10,15,100 (difference:5)
^
6, 16, 67
^
11,17,68
^
10,15,100 (difference:2)
^
Lo anterior será la solución requerida.
6, 16, 67
^
11,17,68
^
10,15,100 (difference:84)
^
6, 16, 67
^
11,17,68
^
10,15,100 (difference:83)
^
Y así......
EDITAR:
Su complejidad se puede reducir utilizando un montón (como lo sugiere Uri). Pensé en ello pero enfrenté un problema: cada vez que se extrae un elemento del montón, se debe encontrar su número de matriz para poder incrementar el puntero correspondiente a esa matriz. Una forma eficiente de encontrar el número de matriz puede reducir definitivamente la complejidad a O (K * N log (K * N)) . Una forma ingenua es usar una estructura de datos como esta
Struct
{
int element;
int arraynumer;
}
y reconstruir los datos iniciales como
6|0,16|0,67|0
11|1,17|1,68|1
10|2,15|2,100|2
Inicialmente, mantenga el máximo actual para la primera columna e inserte los elementos puntiagudos en el montón. Ahora, cada vez que se extrae un elemento, se puede encontrar su número de matriz, el puntero en esa matriz se incrementa, el elemento recién señalado se puede comparar con el máximo actual y el puntero máximo se puede ajustar en consecuencia.
Tengo O (K * N * log (K)), con mucho menos la ejecución típica. Actualmente no se puede pensar nada mejor. Primero explicaré lo más fácil de describir (ejecución algo más larga):
- Para cada elemento f en la primera matriz (bucle a través de K elementos)
- Para cada matriz, a partir de la segunda matriz (bucle a través de matrices N-1)
- Haga una búsqueda binaria en la matriz y encuentre el elemento más cercano a f. Este es tu elemento (Log (K))
Este algoritmo se puede optimizar, si para cada matriz, agrega un nuevo Índice de Piso. Cuando realice la búsqueda binaria, busque entre ''Piso'' y ''K-1''. Inicialmente, el índice del piso es 0 y, para el primer elemento, busca en todas las matrices. Una vez que encuentre un elemento más cercano a ''f'', actualice el Índice de piso con el índice de ese elemento. Lo peor es que el mismo (el piso puede no actualizarse, si el elemento máximo de la primera matriz es más pequeño que cualquier otro mínimo), pero el caso promedio mejorará.
para cada elemento en la 1ª matriz
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);
complejidad: O (k ^ 2 * n)