Algorithmus Interview von Google

Question

Ich bin eine lange Zeit Lurker und hatte gerade ein Interview mit Google, wo sie mir diese Frage gestellt:

Verschiedene Künstler wollen in der Royal Albert Hall führen und Sie sind verantwortlich für die Planung ihrer Konzerte. Anfragen für die Auftritte in der Halle sind nach dem Grundsatz "Wer zuerst kommt, mahlt zuerst" . Nur eine Leistung ist möglich, pro Tag und darüber hinaus gibt es keine Konzerte sein kann stattfindet innerhalb von 5 Tagen voneinander

einen gewünschten Zeitraum d gegeben, die nicht möglich ist (dh innerhalb von 5 Tagen nach einem bereits sched- Uled Leistung), geben Sie einen O (log n) -Zeitalgorithmus, um den nächsten verfügbaren Tag d2 (d2> d) zu finden.

Ich hatte keine Ahnung, wie ich es lösen soll, und jetzt, da das Interview vorbei ist, möchte ich herausfinden, wie ich es lösen kann. Ich weiß, wie schlau die meisten von euch sind, ich habe mich gefragt, ob Sie mir hier helfen können. Dies ist NICHT für Hausaufgaben oder etwas in dieser Art. Ich möchte nur lernen, wie ich es für zukünftige Interviews lösen kann. Ich habe versucht, Nachfragen zu stellen, aber er sagte, das ist alles, was ich Ihnen sagen kann.

Answer 1

Speichern Sie die geplanten Konzerte in einem binary search tree und finden Sie eine praktikable Lösung, indem Sie eine binäre Suche durchführen.

Etwas wie folgt aus:

FindDateAfter(tree, x): 
    n = tree.root 
    if n.date < x 
    n = FindDateAfter(n.right, x) 
    else if n.date > x and n.left.date < x 
    return n 
    return FindDateAfter(n.left, x) 

FindGoodDay(tree, x): 
    n = FindDateAfter(tree, x) 
    while (n.date + 10 < n.right.date) 
    n = FindDateAfter(n, n.date + 5) 
    return n.date + 5 

Answer 2

denke ich, alles, was er gefragt wird, ist eine binäre Suche Implementierung. Finde das Element, das das nächsthöhere ist. Dies kann dem gleichen Mechanismus folgen wie die Standard-Binärsuche, aber wenn Sie ein sortiertes Array verwalten müssen, dann können Sie einen Baum verwenden, wie gesagt. Für die aktuelle Frage im Interview hätte eine B-Recherche genügt.

Answer 3

Sie benötigen einen normalen binären Suchbaum mit Intervallen verfügbarer Daten. Suchen Sie einfach nach dem Intervall mit d. Wenn es nicht existiert, nehmen Sie das Intervall als nächstes (in der richtigen Reihenfolge) bis zu dem Punkt, an dem die Suche gestoppt wurde.

Hinweis: zusammenhängende Intervalle müssen in einem einzigen Knoten zusammengeführt werden. Beispiel: Die Intervalle für verfügbare Daten {2 - 15} und {16 - 23} sollten zu {2 - 23} werden. Dies kann passieren, wenn eine Konzertbuchung abgebrochen wurde.

Alternativ kann stattdessen eine Baumstruktur mit nicht verfügbaren Daten verwendet werden, vorausgesetzt, zusammenhängende nicht verfügbare Intervalle werden miteinander verbunden.

Answer 4

Speichern Sie die Anzahl der genutzten Nächte pro Jahr, Quartal und Monat. Um eine freie Nacht zu finden, finden Sie das erste Jahr, das nicht ausgebucht ist, dann das Quartal innerhalb dieses Jahres, dann den Monat. Dann überprüfen Sie jede der Nächte in diesem Monat.

Unregelmäßigkeiten im Kalendersystem machen dies ein wenig schwierig, anstatt die Jahre und Monate zu verwenden, können Sie die Idee für Einheiten von 4 Nächten als "Monat", 16 Nächte als "Viertel" und so weiter anwenden.

Answer 5

Warum nicht versuchen, Union-Find zu verwenden? Sie können jeden Konzerttag + die nächsten 5 Tage als Teil eines Sets gruppieren und dann am angegebenen Tag eine SUCHE durchführen, die die nächste Set-ID zurückgibt, die Ihr nächstes Konzertdatum wäre.

Bei Implementierung mit einem Baum ergibt sich eine O (log n) -Zeitkomplexität.

Answer 6

Angenommen, auf Stufe 1 sind alle Zeitplandetails verfügbar. Gruppenzeitplan von 16 Tagen auf Ebene 2. Gruppe 16 Stufe 2 Status auf Stufe 3. Gruppe 16 Stufe 3 Status auf Stufe 4. Abhängig von der Anzahl der Tage, die Sie erweitern möchten, erhöhen Sie das Niveau.

Jetzt von höherer Ebene suchen und binäre Suche am Ende durchführen.

Answer 7

Asymtotische Komplexität: - Es bedeutet, dass sich die Laufzeit ändert, wenn die Eingabe zunimmt. Angenommen, wir haben eine Eingabezeichenfolge "abcd". Hier durchqueren wir jedes Zeichen, um seine Länge zu finden, also ist die Zeit proportional zur Anzahl der Zeichen in der Zeichenkette wie n no of char. Also O (n). aber wenn wir die Länge der Zeichenkette "abcd" in eine Variable eingeben, dann können wir immer noch die Länge der Zeichenkette finden, indem wir die Variable len betrachten. (len = 4). ex: zurück 23. egal, was Sie eingeben, haben wir immer noch die Ausgabe als 23. so ist die Komplexität O (1). Somit wird das Programm in einer konstanten Zeit bezüglich der Eingangsgröße laufen. für O (log n) - die Operationen erfolgen in logarithmischen Schritten.

https://drive.google.com/file/d/0B7eUOnXKVyeERzdPUE8wYWFQZlk/view?usp=sharing

das Bild in dem obigen Link beachten. Hier sehen wir die gebogene Linie (logarithmische Linie). Hier können wir sagen, dass für kleinere Eingaben die O (log n) -Notation gut funktioniert, da die benötigte Zeit geringer ist, als in der gebogenen Linie zu sehen ist, aber wenn die Eingabe wächst, wird die lineare Notation, d. H. O (n), als besser angesehen. Es gibt auch die besten und schlimmsten Szenarien zu sehen. Wie im obigen Beispiel.

Sie können auch für die Algorithmen auf diesen Cheat verweisen: http://bigocheatsheet.com/

Answer 8

Es wurde bereits oben erwähnt, aber es ist im Grunde einfach halten mit einem binären Baum. Sie wissen, dass ein Binärbaum log N Komplexität hat. Sie wissen also bereits, welchen Algorithmus Sie verwenden müssen. Alles, was Sie tun müssen, ist, eine Baumknotenstruktur zu erstellen und den Binärbaumeinfügungsalgorithmus zu verwenden, um das nächste verfügbare Datum zu finden: Eine mögliche: Der Baumknoten hat zwei Attribute: d (Datum des Konzerts) und d + 5 (Enddatum für die Sperrfrist von 5 Tagen). Verwenden Sie erneut einen Zeitstempel für die zwei Datumsattribute, um es einfach zu halten. Nun ist es trivial, das nächste verfügbare Datum zu finden, indem der Binary-Tree-Inorder-Einfügealgorithmus mit der Anfangsbedingung root = null verwendet wird.

Answer 9

Ich habe einen binären Suchbaum (BST) verwendet, der die Bereiche für gültige freie Tage enthält, die für Leistungen eingeplant werden können. Einer der Bereiche muss mit int.MaxValue enden, da wir unendlich viele Tage haben, sodass er nicht gebunden werden kann.

Der folgende Code sucht nach dem nächsten Tag zum angeforderten Tag und gibt ihn zurück.

Die Kompliziertzeit O (H) wenn H die Baumhöhe (normalerweise H = log (N), aber H = N in einigen Fällen werden kann.). Die Raumkomplexität ist die gleiche wie die Zeitkomplexität.

public static int FindConcertTime(TreeNode<Tuple<int, int>> node, int reqDay) 
{ 
    // Not found! 
    if (node == null) 
    { 
     return -1; 
    } 
    Tuple<int, int> currRange = node.Value; 
    // Found range. 
    if (currRange.Item1 <= reqDay && 
     currRange.Item2 >= reqDay) 
    { 
     // Return requested day. 
     return reqDay; 
    } 
    // Go left. 
    else if (currRange.Item1 > reqDay) 
    { 
     int suggestedDay = FindConcertTime(node.Left, reqDay); 
     // Didn't find appropriate range in left nodes, or found day 
     // is further than current option. 
     if (suggestedDay == -1 || suggestedDay > currRange.Item1) 
     { 
      // Return current option. 
      return currRange.Item1; 
     } 
     else 
     { 
      // Return suggested day. 
      return suggestedDay; 
     } 
    } 
    // Go right. 
    // Will always find because the right-most node has "int.MaxValue" as Item2. 
    else //if (currRange.Item2 < reqDay) 
    { 
     return FindConcertTime(node.Right, reqDay); 
    } 
}