interviewstreet desafío mediana

Question

Problema La mediana de los números M se define como la 1) si M es el número medio extraño después de la clasificación en orden 2) si M es incluso el número promedio de los 2 números del medio (de nuevo después de ordenar) Al principio tiene una lista de números vacía. Luego puede agregar o eliminar un número de la lista. Para cada operación de agregar o eliminar, muestra la mediana de los números en la lista.

Ejemplo: Para un conjunto de m = 5 números, {9, 2, 8, 4, 1} la mediana es el tercer número del conjunto ordenado {1, 2, 4, 8, 9} que es 4. De manera similar para el conjunto de m = 4, {5, 2, 10, 4}, la mediana es el promedio del segundo y tercer elemento del conjunto ordenado {2, 4, 5, 10} que es (4 + 5)/2 = 4,5

Mi enfoque Creo que el problema puede resolverse de esta manera .. idea es utilizar el valor de la mediana anterior y el puntero para encontrar nuevo valor de la mediana en lugar de volver a calcular en cada operación de añadir o eliminar.

1) Utilice multisectos que siempre mantienen los elementos en orden y permiten duplicados. En otras palabras, mantener lista ordenada de alguna manera.

2) Si la operación es añadir

2.1) Insert this element into set and then calculate the median 

2.2) if the size of set is 1 then first element will be the median 

2.3) if the size of set is even, then 

      if new element is larger then prev median, new median will be avg of prev median 

       and the next element in set. 

      else new median will be avg of prev median and previous of prev element in the set. 

2.4) if the size is odd, then 

      if new element is larger then prev median 

       if also less then 2nd element of prev median (2nd element used to calculate avg 

        of prev median) then this new element to be added will be new median 

       else median will be 2nd element use to calculate the avg during last iteration prev 

        median. 

      else 

       new median will be previous of prev median element in the set 

3) Si la operación es eliminar

3.1) First calculate the new median 

3.2) If the size of set is 0 can't remove 

3.3) If the size is 1 if the first element is the element to be removed, remove it else can't remove. 

3.4) If the size of set is even, then 

      if the element to be deleted is greater than or equal to 2nd element of prev median, then 

       1st element of prev median will be new median 

      else 2nd element of prev median will be the new median 

3.5) If the size of set is odd, then 

      if the element to be deleted is the prev median then find the avg of its prev and next element. 

      else if the element to be deleted is greater then prev median, new median will be avg of prev median and previous to prev median 

      else median will be avg of prev median and next element to prev median. 

3.6) Remove the element. 

Aquí está el código de trabajo ... http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html. ¿Cuáles son sus puntos de vista sobre este enfoque?

Answer 1

Si la lista está ordenada, a continuación, se puede calcular la mediana de tiempo constante con un método similar al siguiente pseudo-código

if list.length % 2 == 0 
    median = (list[list.length/2 - 1] + list[list.length/2])/2 
else 
    median = list[list.length/2] 

Por lo tanto, simplemente mantener una lista ordenada en cada extracción/inserción. Puede hacer estas operaciones en el tiempo O(n) al recorrer la lista hasta que se encuentre entre un elemento que es < el elemento agregado y otro que es> = el elemento agregado. De hecho, puede hacer estas inserciones/eliminaciones en el tiempo O(log n) si comienza en el medio de la lista y luego decide si su elemento es menor o mayor que el elemento medio. Toma esa media lista y comienza en el medio de eso y repite.

Su problema no indica cuáles son los requisitos de rendimiento para esto, pero todo el asunto no siempre puede ocurrir en un tiempo constante hasta donde yo sé. Esta aplicación tiene el siguiente comportamiento

Insert O(log n) 
Remove O(log n) 
Median O(1) 

Answer 2

Su enfoque parece que podría funcionar, pero a partir de la descripción y el código, se puede decir que hay una gran cantidad de trabajo de casos involucrados. ¡No me gustaría ser el que tenga que depurar eso! Así que déjame darte una solución alternativa que debería involucrar menos casos, y por lo tanto ser mucho más simple de hacer las cosas bien.

Conserve dos multiestratos (este algoritmo también funciona con dos colas de prioridad, ya que solo veremos los extremos de cada una). El primero, minset, mantendrá los n/2 números más pequeños, y el segundo, maxset, almacenará los últimos n/2 números.

Cada vez que añade un número:

• Si es mayor que max(minset), añadirlo a maxset
• De lo contrario, lo agrega a minset

Tenga en cuenta que esto no garantiza la n/2 condición. Por lo tanto, hay que añadir un extra de "fijar" paso:

• Si maxset.size() > minset.size(), retire el elemento más pequeño de maxset e insertarlo a minset.
• Si minset.size() > minset.size() + 1, retire el elemento más importante de minset e insertarlo a maxset.

Una vez hecho esto, solo tenemos que obtener la mediana. Esto debería ser realmente fácil de hacer con nuestra estructura de datos: dependiendo de si la n actual es par o impar, es max(minset) o el promedio entre max(minset) y min(maxset).

Para la operación de eliminación, sólo tratar de eliminarlo de cualquiera de los conjuntos y hacer la fijación después.

Answer 3

El principal problema con el código es la comparación de cada nuevo elemento con la mediana móvil, que puede ser un valor medio calculado. En su lugar, debe comparar el nuevo elemento con el valor en el medio anterior (*prev en su código). En este caso, después de recibir la secuencia de 1 y 5, su valor mediano será 3. Si el siguiente valor es 2 o 4, se convertirá en la nueva mediana, pero dado que su código sigue un camino diferente para cada uno de ellos, uno de ellos los resultados son incorrectos

sería más sencillo en general sólo para mantener un seguimiento de la ubicación central y no a la mediana móvil. En su lugar, el cálculo de la mediana al final de cada operación de añadir/quitar:

if size == 0 
    median = NaN 
else if size is odd 
    median = *prev 
else 
    median = (*prev + *(prev-1))/2 

Answer 4

Creo que se puede tratar de verificar dos casos:

1) negative number 
4 
a -1 
a 0 
a 0 
r 0 

2) two big integer whose sum will exceed max int 

Answer 5

Este código resuelve el reto de mediana interviewStreet.

# this code solves the median challenge on interviewStreet. 
# logic is simple. insert the numbers into a sorted sequence in place. 
# use bisection to find the insert index(O(logn)). keep a count of no. of elements in 
# the list and print the median using it(O(1)). 
!/bin/python 
from bisect import bisect_left 
List = [] 
nnode = 0 

def printMed(): 
if nnode>0: 
    if nnode%2 == 0 : 
    if (0.5*(List[nnode/2]+List[(nnode/2)-1])).is_integer(): 
     print int(0.5*(List[nnode/2]+List[(nnode/2)-1])) 
    else: 
     print 0.5*(List[nnode/2]+List[(nnode/2)-1]) 
    else: 
    print List[nnode/2] 
else: 
    print "Wrong!" 

def rem(val): 
global nnode 
try: 
     List.remove(val) 
except: 
    print "Wrong!" 
else: 
    nnode = nnode-1 
    printMed() 

if __name__ == "__main__": 
    n = int(raw_input()) 
for i in range(0,n): 
    l = raw_input().split() 
    if(l[0] == 'r'): 
     rem(int(l[1])) 
    else: 
    index = bisect_left(List , int(l[1])) ; 
    List.insert(index ,int(l[1])) 
    nnode = nnode+1 
    printMed() 

Answer 6

Esta es la solución para el desafío medio en Java utilizando Collections.sort (lista)

import java.util.*; 
public class SolutionMedian{ 
    ArrayList<Integer> sortedList = new ArrayList<Integer>(); 

    public static void main(String args[]){ 

     SolutionMedian m = new SolutionMedian(); 

     Scanner in = new Scanner(System.in); 
     int n = in.nextInt(); 

     char[] op = new char[n]; 
     int[] val = new int[n]; 
     for(int i=0; i<n; i++){ 
      op[i] = in.next().charAt(0); 
      val[i] = in.nextInt(); 
     } 

     for(int i=0; i<n; i++) 
      if(op[i] == 'a') 
       m.add(val[i]); 
      else 
       m.remove(val[i]); 
    } 

void add(int val){ 
     sortedList.add(val); 
     getMedian(); 
    } 

    void remove(int val){ 
     int index = sortedList.indexOf(val); 
     if(index>=0){ 
      sortedList.remove(index); 
      getMedian(); 
     }else{ 
      System.out.println("Wrong!"); 
     } 
    } 

    void getMedian(){ 
     Collections.sort(sortedList); 
     int size = sortedList.size(); 
     switch(size){ 
      case 0: 
       System.out.println("Wrong!"); 
       break; 
      case 1: 
       System.out.println(sortedList.get(0)); 
       break; 
      default: 
       if(size%2 == 0) {//even size 
        int halfIndex = size/2; 
        long sum = sortedList.get(halfIndex) 
           + sortedList.get(halfIndex-1); 
        if(1==(sum&1)) 
         System.out.println((sum/2)+".5"); 
        else 
         System.out.println(sum/2); 
       }else{//odd size 
        System.out.println(sortedList.get((size-1)/2)); 
       } 
     } 
    } 
}