Algorithmus für Vorstellungsgespräche?

Question

UPDATE: Kann jemand bitte meinen letzten Kommentar zu n beantworten? Antwort von 'Pronomen' m.?

Bitte beachten Sie: Ich habe dies bereits gefragt, aber es war ein komplettes Durcheinander, daher schreibe ich es mit mehr Details und in der Originalform.

Frage:

Ich verwalte ein Abstimmungssystem zwischen N Teilnehmern (jeder von 1 bis N indiziert), bei dem ich die folgenden Funktionen unterstützen möchte:

1. Init (N) - Initialisiert die Datenstruktur. -O (1)
2. Abstimmung (j, i) - Fügen Sie der Ergebnistabelle hinzu, dass Person j (genau 1) zu Person i gewählt hat - wobei es niemandem gestattet ist, selbst abzustimmen. -O (1)
3. Wähler (i) - Gibt die Anzahl der Personen zurück, die für i gestimmt haben. -O (1)
4. Herkunft (j) - Gibt die Anzahl der Stimmen zurück, die die Person j anderen gegeben hat. -O (1)
5. Bevorzugt (k) - Druckt die Top-Teilnehmer (in absteigender Reihenfolge) entsprechend der Anzahl der Stimmen, die sie erhalten haben. -In Ordnung)
6. Avoided () - Druckt alle Teilnehmer aus, die keine Stimme erhalten haben. -O (r) wobei r die Anzahl der gedruckten Teilnehmer ist

In dieser Frage sollte die Raumkomplexität O (N) sein .

Nur die Verwendung von Arrays und (doppelt) verknüpften Listen erlaubt.

---

Was ich getan habe? Ich habe 1-4 so einfach gelöst, indem ich ein Array deklariert habe, dessen Größe N ist und jede Zelle Werte enthält. gotund sent. Wenn iStimmen zu jI erhöhen, bekam Wert für jund schickte Wert für ium eins.

Ich habe immer noch keine Ahnung, wie ich 5 und 6 in der erforderlichen Komplexität lösen soll.

Hinweis: Ich suche eher nach dem Algorithmus / der Idee als nach einem tatsächlichen Code.

Answer 1

Beachten Sie, dass der Kandidat, für den gestimmt wurde, für jede Operation seine Punktzahl um genau eins erhöht hat.

Dies eröffnet eine neue Strategie - anstatt einen Kandidaten seiner Punktzahl zuzuordnen, ordnen Sie eine Punktzahl der Liste der Kandidaten mit dieser Punktzahl zu.

Dies kann ganz einfach als Liste von Listenkandidaten implementiert werden: (in vorlagenähnlicher Syntax :) list<list<Candidate>>.

Behalten Sie außerdem ein Array bei, das jede Kandidatennummer dem Zeiger des tatsächlichen CandidateElements zuordnet .

Die Liste der Kandidaten mit 0 wird zunächst implizit auf alle Kandidaten festgelegt, ähnlich wie Sie ein Array in O (1) initialisieren .

• Wenn eine Stimme abgegeben wird:

1. Sie finden den Kandidaten aus der Referenz: O (1)
2. Sie entfernen es aus der aktuellen Liste und fügen es der nächsten Liste hinzu: O (1)
3. Zur Unterstützung Avoided()in O(r): Wenn die Anzahl der Elemente in der „0“ Liste kleiner als die Hälfte ist, ändern Sie es stattdessen eine reguläre Liste.
4. Wenn das vorherige Element, das eine Punktzahl darstellt, jetzt keine Kandidaten mehr hat, lassen Sie es fallen und verknüpfen Sie die vorherige Punktzahl direkt mit der nächsten (dh wenn kein Kandidat mit Punktzahl 3 eine Verbindung herstellt 2<->4). Dies stellt O(n)Platz sicher , da nicht zu viele leere Listenknoten vorhanden sind.

• Das Erhalten von topK ist jetzt einfach und erledigt, O(k)indem die Punkteliste von Ende zu Anfang wiederholt wird (Anhalten nach Ausgabe der kKandidaten)
• Vermeidet wird nun, O(n) = O(r)wenn mehr als die Hälfte der Kandidaten vermieden wurden oder O(r)anderweitig dank Optimierung (3) beim Einfügen.

Answer 2

Hier ist eine alternative Möglichkeit, Avoided () zu implementieren. Ordnen Sie jeder Person, die gewählt wurde, zwei Nummern zu, den Start des Laufs und das Ende des Laufs. Zu Beginn werden alle Elemente auf gesetzt None(kann mit dem O (1) Array-Initialisierungstrick durchgeführt werden).

Wenn die Person mzum ersten Mal gewählt wird, Update startOfRunund endOfRunArrays:

if startOfRun[m-1] != None and startOfRun[m+1] == None
   endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
   startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
   endOfRun[startOfRun[m-1]] = endOfRun[m+1]
   startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
   startOfRun[m] = m
   endOfRun[m] = m

(Randbedingungen der Kürze halber weggelassen).

Jetzt haben Sie Läufe von Personen, die gewählt wurden, und Sie können leicht vom Anfang bis zum Ende jedes Laufs gelangen. Die Zahlen in den Läufen sind alle falsch, aber wir kümmern uns nicht um sie. Es gibt O (r) -Läufe, sodass Sie alle überspringen können, für die in O (r) gestimmt wurde.

---

Hier ist eine alternative Möglichkeit, Favored () zu implementieren. Haben Sie zwei Arrays, (1) ein expandierendes Array von Personen, sortiert nach Punktzahl, und (2) eine Karte von einer Punktzahl zum Index der letzten Person im ersten Array mit einer Punktzahl, die nicht geringer ist als diese (wenn keine solche Person, dann None) . Anfangs ist das erste Array leer und das zweite enthält Nones. Beispiel:

(array 1)
(index)       1 2 3 4 5 6 7 8 9
person        3 6 5 1 4 2 8 9 7
score         7 7 7 5 5 3 2 2 2

(array 2)
score         1 2 3 4 5 6 7 8 9
index in 1st  9 9 6 5 5 3 3 - -

Sobald eine Person zum ersten Mal gewählt wurde, wird sie am Ende des Arrays mit der Punktzahl 1 hinzugefügt und array2[1]aktualisiert. Sobald die Person erneut gewählt wurde, wird sie gegen die erste Person im Array mit derselben Punktzahl ausgetauscht, die Punktzahl wird erhöht und das zweite Array wird aktualisiert (wir müssen nur ein Element aktualisieren, das dem neuen entspricht Ergebnis).