Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.
Anscheinend ergreifen viele Ingenieure Maßnahmen auf der Website namens LetCode.
Es ist eine Site, die die algorithmische Leistung trainiert, die dem Codierungstest standhält, der in der frühen Geschichte durchgeführt wird, und es ist ein unvermeidlicher Weg für diejenigen, die eine Karriere bei einem ausländischen Technologieunternehmen aufbauen möchten.
Ich habe es großartig geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.
Als IT-Ingenieur wäre es jedoch besser, die gleiche Algorithmusleistung wie eine Person zu haben. Daher möchte ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Ich löse es mit Python3.
Letztes Mal Leet Code Day 79 ab Null "1282. Gruppieren Sie die Personen mit der Gruppengröße, zu der sie gehören"
Twitter Ich mache es.
** Technischer Blog Gestartet! !! ** **. Ich denke, die Technologie wird über LetCode, Django, Nuxt usw. schreiben. ** Dies ist schneller zu aktualisieren **, vielen Dank für Ihre Mitarbeit!
#Problem 703. Kth Largest Element in a Stream Der Schwierigkeitsgrad ist einfach.
Das Problem ist, eine Klasse zu entwerfen, die das k-größte Element im Stream findet. Beachten Sie, dass dies das k-größte Element in der sortierten Reihenfolge ist, nicht das k-te andere Element.
KthLargest hat einen Konstruktor, der die Ganzzahl k und das Ganzzahlarray nums akzeptiert, die die Anfangselemente des Streams enthalten. Jedes Mal, wenn Sie die Methode KthLargest.add aufrufen, repräsentiert sie das kth größte Element im Stream. Gibt das Element zurück.
Example:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
Der Punkt ist, bitte implementieren Sie den Konstruktor und die add Methode.
Ich habe mich mit diesem Problem befasst, weil es in der LetCode-Problemsammlung aufgeführt ist, die von denjenigen empfohlen wurde, die das Codierungsinterview von Google bestanden haben.
Leet Code 60-Fragen, die Sie für die Codierung der Interviewvorbereitung lösen möchten
Es sieht interessant aus, also denke ich, ich werde versuchen, es zu lösen. Ich habe in letzter Zeit nur neue Probleme gelöst, und es sieht so aus, als ob es zum ersten Mal seit einiger Zeit eine interessante Initiative sein wird.
Wegen des Heap-Problems benutze ich den Heap leise. Es wird auch als Prioritätswarteschlange bezeichnet.
Auf den ersten Blick scheint dieses Problem einfach zu sein.
Nachdem Sie jedes Mal ein Element hinzugefügt haben, sortieren Sie es und geben Sie das k-1-Element zurück, oder? Es scheint, dass es so sein wird, aber da der Prozess des Sortierens schwer ist, denke ich, dass die Zeit normal ablaufen wird.
Zum Beispiel ist die Verarbeitung wie folgt.
def add(val):
lists.append(val)
self.lists.sort()
return self.lists[self.num-1]
Dies wird jedes Mal sortiert, wenn "add" aufgerufen wird. Je mehr Elemente vorhanden sind, desto schwerer wird es.
Wenn Sie also ein Element von Anfang an hinzufügen und es mit einer Warteschlange mit Priorität verwalten, müssen Sie sich nicht die Mühe machen, es zu sortieren, oder? Das ist.
Ich habe den folgenden Code unter der Annahme geschrieben, dass er den Heap verwendet.
import heapq
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.lists,self.num = [],k
for i in nums:
self.add(i)
def add(self, val: int) -> int:
heapq.heappush(self.lists, val)
if len(self.lists) > self.num:
heapq.heappop(self.lists)
return self.lists[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
# Runtime: 136 ms, faster than 45.40% of Python3 online submissions for Kth Largest Element in a Stream.
# Memory Usage: 17.6 MB, less than 78.45% of Python3 online submissions for Kth Largest Element in a Stream.
Auf diese Weise werden alle Elemente des ersten angegebenen Elements als Heap behandelt, und bis der Wert der Länge von "Listen" dem Wert von "num", "pop" entspricht, wird der Mindestwert aus der Liste extrahiert. Der Prozess ist sehr reibungslos.
Ich dachte, ich schreibe es, aber ich habe das Gefühl, dass ich es kaum auf dem Haufen geschrieben habe, also war es eine gute Studie, um es zu überprüfen.
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts