Organización de resultados de clasificación

Question

Me hicieron esta pregunta en la entrevista de Adobe:

Tenemos una matriz de enteros ordenada en orden ascendente. También tenemos 3 enteros A, B y C. Necesitamos aplicar A*x*x + B*x + C para cada elemento x en la matriz y devolver la matriz ordenada correspondiente.

Ejemplo I se le dio:

Input array = -1 0 1 2 3 4 
A = -1, B = 2, C = -1` 

resultado de aplicar la fórmula a cada elemento = -4 -1 0 -1 -4 -9
resultado Así esperado = -9 -4 -4 -1 -1 0 (ordenados)

Mi mejor solución era aplicar la fórmula y ordenarla dando como resultado la solución O(nlogn). No podría hacerlo mejor.

Cualquier orientación para mejorarlo es útil.

Answer 1

Puede hacerlo en O(n). Encontrar el valor mínimo del polinomio que tiene lugar cuando

2 * A * x + B = 0 

modo que

x_min = -B/2 * A. 

A continuación, recorrer la matriz hasta que encuentre el número entero más cercano a x_min. Esto es O(n). Desde aquí, elija sucesivamente desde la izquierda o la derecha de este elemento, dependiendo de si |x_min - left| es menor o mayor que |x_min - right|. Devuelve los valores de evaluación del polinomio en estos puntos en el orden resultante. Esto es O(n).

Esto supone que A es positivo. Puede manejar el caso de A negativo de manera similar.

Ejemplo:

input array = -1 0 1 2 3 4 A = -1, B = 2, C = -1 

Aquí, el valor máximo se produce en x_max = -2/2 * -1 = 1. Desde la matriz de entrada, el valor más cercano es 1, el tercer elemento. Luego, sucesivamente, seleccionamos los elementos en el siguiente orden en función de su distancia al 1.

1, 0, 2, -1, 3, 4 

Entonces, porque A es negativo, tenemos que ejecutar estos en orden inverso

4, 3, -1, 2, 0, 1 

y evaluar el polinomio en ellos

-9, -4, -4, -1, -1, 0 

Done.

Tenga en cuenta que estamos explotando una propiedad especial de parábolas. A saber, para x menos de x_extreme y A positivo, aplicar el polinomio a tal x es una función decreciente de x. Para x mayor que x_extreme y A positivo, aplicar el polinomio a tal x es una función creciente de x.(Se aplica un razonamiento similar si A es negativo.) Por lo tanto, particione la matriz en dos partes, aquellas x menos que x_extreme y aquellas x mayor que x_extreme. A continuación, aplique el polinomio a estas dos piezas para terminar con dos matrices que se ordenan. Ahora aplique la fusión ordenada a estas matrices ordenadas. Tenga en cuenta que la descripción anterior es efectivamente el tipo de fusión.

Answer 2

La ecuación dada es parabolic. Por lo tanto, el resultado de aplicarlo a una matriz ordenada dará como resultado una matriz que tendrá un máximo/mínimo con las sub-matrices a su izquierda y derecha ordenadas.

En su caso, el máximo es 0 y el sub matriz a su izquierda [-4 -1] se ordena en orden ascendente y el sub-matriz a su derecha [-1 -4 -9] se ordena en orden descendente.

Todo lo que necesita hacer es de combinación de estos conjuntos ordenados que es lineal en el tiempo.

Así que el algoritmo es:

1. Aplicar la ecuación en cada elemento
2. Búsqueda máximo/mínimo
3. Combinar subarreglos

Answer 3

Se puede reconocer que el resultado de aplicar el segundo grado a la los datos están casi clasificados (como se describe en las respuestas anteriores, o al reconocer que la derivada de un polinomio de grado n es continua, de grado n - 1 y tiene como máximo n ceros).

Si tiene una rutina de clasificación en su biblioteca que hace algo inteligente con datos casi ordenados (como un mergesort que lo tenga en cuenta), puede simplemente arrojar los datos y esperar un rendimiento lineal. La búsqueda en la web encuentra Which sort algorithm works best on mostly sorted data? que apunta a http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Answer 4

La solución es O(N) y no hay necesidad de realizar ningún cálculo, aunque ayuda a comprender la forma de la curva.

Las respuestas anteriores están haciendo lo más intuitivo y resolver la ecuación para encontrar el mínimo o máximo y luego dividir la lista.

Hay una ventaja en el cálculo de la primera derivada, pero no es necesario hacerlo, ni necesitamos encontrar el punto máximo o mínimo en este momento.

Simplemente sepa que podría moverse en una dirección y luego retroceder en la otra dirección, pero nunca cambiará de dirección más de una vez.

Vamos a comenzar en cada extremo e iterar a través de ambos lados hasta que nos fusionamos en algún lugar en el medio. Antes de hacer cualquier otra cosa, debemos verificar la dirección en cada extremo, lo cual haremos simplemente comparando los dos elementos finales. Entonces vemos si un extremo se mueve hacia arriba y el otro hacia abajo.

Si tenemos N elementos Supongamos que disponemos de datos X[0] y X[N-1] así calcular f(X[0]) y f(X[N-1]) y f(X[1]) y f(X[N-2]). Si f(X[0]) < f(X[1]) y f(X[N-1]) > f(X[N-2]) entonces en realidad todos nuestros datos están a un lado del máximo/mínimo y por lo tanto ya están clasificados. Lo mismo si las comparaciones son en la otra dirección.(Una dirección puede requerir un reverso).

De lo contrario, simplemente realice la combinación desde ambos extremos, así f(X[0]) y f(X[N-1]) son máximos o mínimos de sus subvaciamientos (lo sabemos por las comparaciones anteriores) y cree la lista combinada de la dirección que corresponda.

Aplicando a sus datos:

-1 0 1 2 3 4 
A = -1, B = 2, C = -1` 

f = [ -4, -1, 0, -1, -4, -9 ] 

-4 < -1 y -9 < -4 así que hacer cruzar el punto y tenemos mínimos en cada extremo.

-9 is lower than -4 
-4 and -4 are equal so push both 
-1 and -1 are equal so push both 
0 remains. 

our sequence is [-9, -4, -4, -1, -1, 0 ]