interviewstreet medianen Herausforderung

Question

Problem Der Median von M Ziffern als 1) definiert ist, wenn M in sie nach dem Sortieren, um 2) ungeradee mittlere Zahl ist, wenn M auch die durchschnittliche Anzahl der Mitte 2 Zahlen ist (wieder nach dem Sortieren) Sie haben zunächst eine leere Nummernliste. Dann können Sie eine Nummer aus der Liste hinzufügen oder entfernen. Geben Sie für jeden Vorgang zum Hinzufügen oder Entfernen den Median der Zahlen in der Liste aus.

Beispiel: Für eine Menge von m = 5 Zahlen {9, 2, 8, 4, 1} ist der Median die dritte Zahl in der sortierten Menge {1, 2, 4, 8, 9}, also 4. Ähnlich für den Satz von m = 4, {5, 2, 10, 4}, ist der Median der Durchschnitt des zweiten und des dritten Elements in der sortierten Menge {2, 4, 5, 10}, was (4 + 5)/2 = 4,5

Mein Ansatz ich denke, das Problem auf diese Weise gelöst werden kann .. Idee ist vorherigen Medianwert und Zeiger zu finden neuen Medianwert statt neu zu berechnen bei jedem hinzufügen oder entfernen von Betrieb zu verwenden.

1) Verwenden Sie Multi-Sets, die immer Elemente in Reihenfolge halten und Duplikate zulassen. Mit anderen Worten, sortierte Liste irgendwie beibehalten.

2) Wenn die Operation

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) ist hinzuzufügen, wenn der Betrieb

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. 

Hier entfernen, ist der Arbeits Code ... http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html. Was halten Sie von diesem Ansatz?

Answer 1

Wenn Ihre Liste sortiert ist, dann können Sie den Median in konstanter Zeit mit einem Verfahren ähnlich den folgenden Pseudocode

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

Daher berechnen, halten nur eine sortierte Liste auf jedem Einsatz/entfernen. Sie können diese Vorgänge unter O(n) ausführen, indem Sie die Liste schrittweise durchlaufen, bis Sie sich zwischen einem Element befinden, das < das hinzugefügte Element ist, und einem Element, das> = das hinzugefügte Element ist. Sie können diese Insert/Removes in O(log n) Zeit tatsächlich tun, wenn Sie in der Mitte der Liste beginnen, dann entscheiden, ob Ihr Element kleiner oder größer als das mittlere Element ist. Nimm diese halbe Liste und beginne in der Mitte und wiederhole es.

Ihr Problem gibt nicht an, was die Leistungsanforderungen für dieses sind, aber die ganze Sache kann nicht immer in konstanter Zeit geschehen, soweit mir bekannt ist. Diese Implementierung hat die folgende Leistung

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

Answer 2

Ihr Ansatz scheint, wie es funktionieren kann, aber aus der Beschreibung und den Code können Sie sagen, dass es eine Menge Fallarbeit ist beteiligt. Ich möchte nicht derjenige sein, der das debuggen muss! Also lassen Sie mich Ihnen eine alternative Lösung geben, die weniger Fälle beinhalten sollte und daher viel einfacher sein sollte, um richtig zu werden.

Behalten Sie zwei Multisets (dieser Algorithmus funktioniert auch mit zwei Prioritätswarteschlangen, da wir nur auf die Extreme jedes einzelnen schauen). Der erste, minset, wird die kleinsten n/2 Zahlen behalten, und der zweite, maxset, wird die letzten n/2 Zahlen speichern.

Jedes Mal, wenn Sie eine Nummer hinzufügen:

• Wenn er größer als max(minset) ist, fügen Sie es maxset
• es sonst in den minset

Beachten Sie, dass dies die nicht gewährleistet n/2 Zustand. Deshalb sollten wir eine extra „Fixierung“ Schritt:

• Wenn maxset.size() > minset.size(), entfernen Sie das kleinste Element von maxset und es minset einzufügen.
• Wenn minset.size() > minset.size() + 1, entfernen Sie das größte Element von minset und fügen Sie es zu maxset.

Nachdem dies erledigt ist, müssen wir nur den Median bekommen. Dies sollte mit unserer Datenstruktur sehr einfach sein: Je nachdem, ob das aktuelle n gerade oder ungerade ist, ist es entweder max(minset) oder der Durchschnitt zwischen max(minset) und min(maxset).

Für den Entfernungsvorgang, versuchen Sie einfach, es aus irgendeinem der Sätze zu entfernen, und reparieren Sie danach.

Answer 3

Das Hauptproblem mit Ihrem Code ist der Vergleich jedes neuen Elements mit dem laufenden Median, der ein berechneter Durchschnittswert sein kann. Stattdessen sollten Sie den neuen Artikel mit dem Wert in der vorherigen Mitte (*prev in Ihrem Code) vergleichen. Nach dem Empfang der Sequenz von 1 und 5 ist Ihr Medianwert 3. Wenn der nächste Wert 2 oder 4 ist, sollte er der neue Median werden, aber da Ihr Code für jeden von diesen einen anderen Pfad verfolgt, einer von Die Ergebnisse sind falsch.

Es wäre insgesamt einfacher, nur den mittleren Ort und nicht den laufenden Median zu verfolgen. Stattdessen berechnen den Mittelwert am Ende jeden Hinzufügen/Entfernen Betrieb:

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

Answer 4

Ich glaube, Sie können versuchen, zwei Fälle zu überprüfen:

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

2) two big integer whose sum will exceed max int 

Answer 5

Dieser Code löst die mittlere Herausforderung auf 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

Dies ist die Lösung für mittlere Herausforderung in Java Collections.sort (Liste)

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