interviewstreet mediana wyzwanie

Question

problem Mediana liczb M została określona jako 1) jeśli M jest nieparzystą liczbą środkowy po sortowaniu je w celu 2) jeśli M jest również średnia liczba środkowych 2 numery (ponownie po sortowaniu) Najpierw masz pustą listę numerów. Następnie możesz dodać lub usunąć kilka numerów z listy. Dla każdej operacji dodawania lub usuwania wypisz medianę liczb na liście.

Przykład: Dla zbioru m = 5 liczb, {9, 2, 8, 4, 1} mediana jest trzecią liczbą w posortowanym zbiorze {1, 2, 4, 8, 9}, która wynosi 4. Podobnie dla zbioru m = 4, {5, 2, 10, 4}, mediana jest średnią drugiego i trzeciego elementu w posortowanym zbiorze {2, 4, 5, 10}, który wynosi (4 + 5)/2 = 4,5

Moje podejście Myślę, że problem może być rozwiązany w ten sposób .. pomysłem jest użycie poprzednią wartość mediany i wskaźnik znaleźć nową wartość mediany zamiast przeliczania na każdym dodać lub usunąć operacji.

1) Użyj multisetów, które zawsze zachowują porządek i pozwalają na duplikaty. Innymi słowy, posortuj listę posortowaną.

2) Jeżeli operacja jest dodać

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) Jeżeli operacja usunięcia

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. 

Oto kod roboczych ... http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html. Jakie są twoje poglądy na temat tego podejścia?

Answer 1

Jeśli lista jest sortowana, a następnie można obliczyć medianę w stałym czasie ze sposobem podobnym do następującego pseudo-kodu

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

Dlatego właśnie utrzymanie posortowana lista na każdej wkładce/usunąć. Możesz wykonywać te operacje w czasie O(n), przechodząc przez listę, aż znajdziesz się pomiędzy elementem, który jest < dodanym elementem i takim, który jest> = dodanym elementem. Możesz rzeczywiście wstawiać/usuwać w czasie O(log n), jeśli zaczniesz od środka listy, a następnie zdecydujesz, czy Twój element jest mniejszy czy większy od środkowego elementu. Weź tę połowę i zacznij w środku tego i powtórz.

Twój problem nie określa wymagań dotyczących wydajności, ale cała sprawa nie zawsze może się zdarzyć w stałym czasie, o ile wiem. Implementacja ta ma następujące osiągi

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

Answer 2

Twoje podejście wydaje się to może działać, ale z opisu i kodu, można powiedzieć, że istnieje wiele spraw prowadzonych zaangażowany. Nie chciałbym być tym, który musi to debugować! Pozwól, że przedstawię ci alternatywne rozwiązanie, które powinno obejmować mniej przypadków, a co za tym idzie, prostsze rozwiązanie.

Zachowaj dwa multiseksy (ten algorytm działa również z dwiema priorytetowymi kolejkami, ponieważ przyjrzymy się tylko skrajnościom każdego z nich). Pierwsza, minset, zachowa najmniejszą liczbę n/2, a druga, maxset, będzie zapisywać ostatnie liczby n/2.

Kiedykolwiek dodać numer:

• Jeżeli jest ona większa niż max(minset), dodaj go do maxset
• W przeciwnym razie, należy dodać go do minset

Zauważ, że to nie gwarantuje Warunek n/2. Dlatego należy dodać jeden dodatkowy „fixing” krok:

• Jeśli maxset.size() > minset.size(), usunąć najmniejszy element z maxset i włóż ją do minset.
• Jeśli minset.size() > minset.size() + 1, usuń największy element z minset i wstaw go do maxset.

Po tym wszystkim musimy uzyskać medianę. To powinno być naprawdę łatwe do wykonania dzięki naszej strukturze danych: w zależności od tego, czy bieżący n jest równy czy nieparzysty, jest to albo max(minset) albo średnia między max(minset) i min(maxset).

W przypadku operacji wyjmowania, po prostu spróbuj ją wyjąć z dowolnego zestawu i następnie zamocuj.

Answer 3

Głównym problemem związanym z kodem jest porównanie każdej nowej pozycji z bieżącą medianą, która może być obliczoną wartością średnią. Zamiast tego należy porównać nowy element z wartością z poprzedniego środka (*prev w kodzie). W takim przypadku, po otrzymaniu sekwencji 1 i 5, twoja wartość mediana wyniesie 3. Jeśli następna wartość wynosi 2 lub 4, powinna ona stać się nową medianą, ale ponieważ twój kod podąża inną ścieżką dla każdego z nich, jeden z wyniki są błędne.

Łatwiej byłoby ogólnie po prostu śledzić środkową lokalizację, a nie bieżącą medianę. Zamiast obliczać medianę na koniec każdego dodać/usunąć pracy:

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

Answer 4

Myślę, że można spróbować zweryfikować dwa przypadki:

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

2) two big integer whose sum will exceed max int 

Answer 5

Kod ten rozwiązuje medianę starciu 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

Jest to rozwiązanie dla mediany wyzwanie w Javie przy użyciu 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)); 
       } 
     } 
    } 
}