Der algorithmische Abschnitt mit dem Schreiben von Code auf eine Tafel oder ein Papier ist eine der wichtigsten Phasen eines Vorstellungsgesprächs für Entwickler, um einen Job in Yandex zu bekommen. Wir haben uns entschlossen, detaillierter darüber zu sprechen, wie diese Abschnitte organisiert sind, um zukünftigen Kandidaten bei der Vorbereitung zu helfen. Außerdem hoffe ich, dass viele von denen, die es nicht wagen, zu einem Interview nach Yandex zu kommen, aus Angst vor zu schwierigen Tests, nach dieser Geschichte verstehen, dass in Wirklichkeit nicht alles so beängstigend ist!
Deshalb haben wir folgende Materialien für Sie vorbereitet:
- Ein spezieller Wettbewerb mit ähnlichen Aufgaben wie für das Interview.
- Dieser Beitrag . Es wird erklärt, warum Sie solche Abschnitte durchführen und alle Aufgaben des Wettbewerbs verstehen müssen.
- Zwei Videos, in denen Aufgaben aus dem Wettbewerb aussortiert werden: In der ersten - die Aufgabe ist einfacher, in der zweiten - sind zwei Aufgaben schwieriger. In diesen Videos erfahren Sie mehr über typische Fehler, die beim Durchlaufen der algorithmischen Abschnitte und beim Schreiben von Produktionscode gemacht wurden.
Wie wir Entwickler interviewen
Ein Interview mit einem Entwickler besteht aus mehreren Phasen:
- vorläufiger Abschnitt mit einem Personalvermittler;
- technisches Skype-Interview;
- mehrere Vollzeitabschnitte;
- abschließende Interviews mit Personalchefs.
Im vorläufigen Abschnitt lernt der Personalvermittler den Kandidaten kennen, lernt seine Interessen und Motive kennen, um zu verstehen, in welchen Positionen es sinnvoll ist, ihn zu berücksichtigen. Ein technisches Skype-Interview dient der vorläufigen Beurteilung der Fähigkeiten eines Kandidaten und eliminiert diejenigen, die definitiv nicht in der Lage sind, Vollzeitabschnitte zu bewältigen.
Vollzeitabschnitte - die Hauptbühne. Es sind Vollzeitabschnitte, die eine Antwort auf die Frage geben, was ein Kandidat tun kann. Der algorithmische Abschnitt ist einer der technischen Vollzeitbereiche. Neben dem Algorithmus gibt es noch weitere persönliche Tests: Kandidaten für leitende Entwickler müssen beispielsweise den Architekturbereich durchlaufen, und zukünftige Führungskräfte beantworten auch Fragen zur Verwaltung von Teams und Projekten. Wenn ein Kandidat in einem bestimmten Bereich (maschinelles Lernen, Optimierung auf niedriger Ebene, Entwicklung hoch belasteter Systeme, mobile Entwicklung oder andere) eine gewisse Stärke besitzt, organisieren wir im Allgemeinen einen Abschnitt mit einem spezialisierten Spezialisten.
Der algorithmische Abschnitt prüft, ob der Kandidat in der Lage ist, Algorithmen zur Lösung einfacher Probleme zu entwickeln, die Komplexität dieser Algorithmen zu bewerten und fehlerfrei zu implementieren, während ein Gleichgewicht zwischen der Qualität des Tests und der Geschwindigkeit der Lösung aufrechterhalten wird.
Warum Code auf eine Tafel oder Papier schreiben?
Ein natürlicher Zustand für einen Programmierer ist das Programmieren in einer integrierten Entwicklungsumgebung mit Syntaxhervorhebung und Rückverfolgbarkeit. Daher erscheint die Idee bei einem Interview, Code auf eine Tafel oder ein Papier zu schreiben, zunächst nicht allzu natürlich. Mit dieser Methode können Sie jedoch zwei Eigenschaften überprüfen, die für jeden Entwickler sehr wichtig sind.
Die erste davon ist die Fähigkeit, die Leistung des Codes schnell "per Auge" zu bewältigen. Stellen Sie sich vor, der Entwickler muss beim Schreiben jedes Zyklus, der im Programm angezeigt wird, Zeit damit verbringen, seine Leistung durch Nachverfolgung zu überprüfen. oder wenn ein Dienst in der Produktion abstürzt, muss er den Code immer unter dem Debugger ausführen. Es ist klar, dass das Schreiben und Debuggen selbst einfacher Programme unannehmbar lange dauern wird. Natürlich ist es nützlich, den Code mit Codeüberprüfungen lesen zu können.
Die zweite wichtige Eigenschaft ist die Fähigkeit, einen Lösungsplan im Voraus zu überdenken und ihn dann zu befolgen. Wenn es keinen Plan gibt, führt dies zu einer großen Anzahl von Korrekturen, Durchstreichungen (auf Papier) und dem Umschreiben großer Codeteile. Im wirklichen Leben verlangsamt dies die Entwicklung erheblich, wird jedoch teilweise durch die Arbeitsgeschwindigkeit im Code-Editor verdeckt. Karton und Papier sind in diesem Sinne gnadenlose Oberflächen.
Natürlich berücksichtigen wir, dass das Schreiben von Code von Hand nicht zu schnell ist. Daher umfassen unsere Aufgaben normalerweise das Lösen von nicht viel mehr als einem Dutzend Zeilen, und die Anzahl der Aufgaben, die in einem Abschnitt gelöst werden müssen, beträgt normalerweise zwei oder drei.
Algorithmische Abschnitte und Sportprogrammierung
Sportprogrammierung entwickelt sich unter anderem in Zukunft für Entwickler und die Fähigkeit, schnell und fehlerfrei einfache Algorithmen nach einem vorgegebenen Plan zu implementieren. Daher machen Kandidaten mit Erfahrung in der Sportprogrammierung wirklich gute Arbeit mit den algorithmischen Abschnitten in Interviews. Oft kann man eine Situation beobachten, in der zukünftige Auszubildende den algorithmischen Teil problemlos bewältigen und alle Probleme in 15 bis 20 Minuten lösen können, während erfahrene Programmierer die ganze Stunde mit denselben Aufgaben verbringen.
Gleichzeitig ist der algorithmische Abschnitt mit dem Schreiben von Code nur einer der Abschnitte, in denen die für jeden Entwickler erforderlichen Mindestfähigkeiten getestet werden. Dieser Abschnitt wird nicht nur von Olympiadenprogrammierern, sondern auch von erfahrenen Industrieentwicklern bearbeitet. Der zukünftige leitende Entwickler oder Teamleiter wartet sicherlich auf die Architekturabteilung, in der er seine Stärken offenbaren kann. Natürlich wird dieser Abschnitt niemals an Auszubildende und Nachwuchsentwickler vergeben.
Interviewvorbereitungswettbewerb
Insbesondere damit Sie sich den Inhalt der Aufgaben, die wir in den algorithmischen Abschnitten geben, grob vorstellen können, haben wir einen Wettbewerb zusammengestellt , der zur Vorbereitung von Interviews verwendet werden kann. Versuchen Sie, alle Probleme zu lösen, ohne den Debugger einmal auszuführen. Schreiben Sie eine Lösung in Notepad ohne Hervorhebung der Syntax. Überlegen Sie sich die kürzestmögliche Lösung, die alle Tests besteht. Denken Sie im Voraus über alle möglichen Probleme nach und geben Sie die Lösung beim ersten Mal weiter.
Der Wettbewerb enthält fünf Aufgaben. Sie können versuchen, sie selbst zu lösen, oder Sie können die Analyse im Voraus lesen: Es wird immer noch nützlich sein, weil Sie können Ihre Fähigkeiten zur fehlerfreien Codierung eines zuvor bekannten Algorithmus trainieren.
Analyse der WettbewerbsaufgabenAufgabe A. Steine und Schmuck
Es werden zwei Zeilen mit lateinischen Kleinbuchstaben angegeben: Zeichenfolge J und Zeichenfolge S. Die in Zeichenfolge J enthaltenen Zeichen sind „Juwelen“ und in Zeichenfolge S sind „Steine“. Es muss ermittelt werden, wie viele Zeichen aus S gleichzeitig „Juwelen“ sind. Einfach ausgedrückt, müssen Sie überprüfen, wie viele Zeichen von S in J enthalten sind.
Dies ist eine sehr einfache Aufwärmaufgabe, die Lösungen in mehreren Programmiersprachen enthält, damit sich die Teilnehmer an das Testsystem gewöhnen können.
Der Algorithmus ist recht einfach: Sie müssen ein Set aus einer Linie mit "Juwelen" erstellen, dann entlang der Linie mit "Steinen" gehen und jedes Zeichen auf Aufnahme in dieses Set überprüfen. Verwenden Sie eine solche Implementierung des Satzes, um die lineare Komplexität der resultierenden Lösung zu gewährleisten, obwohl die Eingabezeilen sehr kurz sind und es daher möglich ist, auch einen Algorithmus mit quadratischer Komplexität zu übergeben.
Problem B. Aufeinanderfolgende Einheiten
Es ist erforderlich, die längste Folge von Einheiten im Binärvektor zu finden und seine Länge auszudrucken.
Der Lösungsalgorithmus lautet wie folgt: Gehen Sie durch alle Elemente des Arrays; Wenn Sie einen treffen, müssen Sie den Zähler für die Länge der aktuellen Sequenz erhöhen, und wenn Sie Null treffen, müssen Sie diesen Zähler zurücksetzen. Am Ende müssen Sie das Maximum der Werte anzeigen, die der Zähler angenommen hat.
Überprüfen Sie, ob Sie mit der Situation umgehen, in der das Array mit der gewünschten Abfolge von Einheiten endet. Bei sorgfältiger Implementierung erfordert diese Situation keine spezielle Verarbeitung.
Versuchen Sie, nur die konstante Menge an zusätzlichem Speicher zu verwenden.
Aufgabe C. Doppelte Entfernung
Es wird ein Array von 32-Bit-Ganzzahlen angegeben, die in nicht abnehmender Reihenfolge angeordnet sind. Es ist erforderlich, alle Wiederholungen daraus zu entfernen.
Der richtige Algorithmus verarbeitet die Elemente des Arrays nacheinander und vergleicht sie mit der letzten Ausgabe. Sie müssen daran denken, die Variable mit dem zuletzt angezeigten Element zu aktualisieren und bei der Verarbeitung des letzten Elements keinen Fehler zu machen.
Um dieses Problem zu lösen, müssen Sie keinen zusätzlichen Speicher verwenden.
Aufgabe D. Generierung von Klammersequenzen
Gegeben eine ganze Zahl . Es ist erforderlich, alle korrekten Klammerfolgen der Länge zu drucken lexikografisch bestellt (siehe https://ru.wikipedia.org/wiki/Lexographic_order ). In der Aufgabe werden nur Klammern verwendet.
Dies ist ein Beispiel für ein relativ komplexes algorithmisches Problem. Wir werden eine Folge von einem Zeichen erzeugen; In jedem Moment können wir der aktuellen Sequenz entweder eine öffnende oder eine schließende Klammer zuweisen. Sie können eine öffnende Klammer hinzufügen, wenn zuvor weniger als n öffnende Klammern hinzugefügt wurden, und eine schließende Klammer, wenn in der aktuellen Sequenz die Anzahl der öffnenden Klammern die Anzahl der schließenden Klammern überschreitet. Ein solcher Algorithmus garantiert bei sorgfältiger Implementierung automatisch die lexikografische Reihenfolge in der Antwort. arbeitet in einer Zeit proportional zum Produkt der Anzahl der Elemente in der Antwort auf n; Dies erfordert eine lineare Menge zusätzlichen Speichers.
Ein Beispiel für einen ineffektiven Algorithmus wäre das Folgende: Wir generieren alle möglichen Klammersequenzen und geben dann nur diejenigen aus, die sich als korrekt herausstellen. Gleichzeitig erlaubt das Volumen der Antwort nicht, das Problem schneller zu lösen als der oben resultierende Algorithmus.
Problem E. Anagramme
Diese eher einfache Aufgabe ist ein typisches Beispiel für ein Problem, für dessen Lösung assoziative Arrays verwendet werden müssen. Bei der Entscheidung müssen Sie berücksichtigen, dass Zeichen wiederholt werden können, sodass Sie keine Mengen, sondern Wörterbücher verwenden müssen. Daher lautet die Lösung wie folgt: Wir stellen aus jeder Zeile ein Wörterbuch zusammen, in dem für jedes Zeichen die Anzahl seiner Wiederholungen gespeichert wird. Vergleichen Sie dann die resultierenden Wörterbücher. Wenn sie übereinstimmen, muss eine Einheit gedruckt werden, andernfalls - Null.
Alternative Lösung: Sortieren Sie die Eingabezeilen und vergleichen Sie sie. Diese Lösung ist insofern schlechter, als sie langsamer läuft und auch die Eingabe ändert. Diese Lösung verwendet jedoch keinen zusätzlichen Speicher.
Wenn Sie während des Interviews mehrere Lösungen hatten, die sich in ihren Eigenschaften unterscheiden, teilen Sie uns dies mit. Es ist immer dann großartig, wenn der Entwickler verschiedene Möglichkeiten zur Lösung des Problems kennt und über seine Stärken und Schwächen sprechen kann.
Aufgabe F. Zusammenführen sortierte Listen
Gegeben Arrays nicht negativer Ganzzahlen, sortiert in nicht abnehmender Reihenfolge, von denen jede 100 nicht überschreitet. Es ist erforderlich, das Ergebnis ihrer Fusion zu konstruieren: ein Array, das in nicht absteigender Reihenfolge sortiert ist und alle Elemente des Originals enthält Arrays. Die Länge jedes Arrays überschreitet nicht .
Erstellen Sie für jedes Array einen Zeiger. Anfänglich befindet sich jeder Zeiger am Anfang des entsprechenden Arrays. Wir werden die Elemente, die den Positionen der Zeiger entsprechen, in jede Datenstruktur einfügen, die die Extraktion eines Minimums unterstützt - es kann sich um ein Multiset oder beispielsweise einen Heap handeln. Als nächstes extrahieren wir das minimale Element aus dieser Struktur, setzen es als Antwort ein, verschieben die Position des Zeigers im entsprechenden Array und platzieren das nächste Element aus diesem Array in der Datenstruktur.
Bei dieser Aufgabe haben viele Schwierigkeiten mit dem Eingabeformat. Bitte beachten Sie, dass die ersten Elemente der Zeilen nicht die Elemente von Arrays beschreiben, sondern die Länge von Arrays!
FAQ zum Wettbewerb
A: Ich habe definitiv den richtigen Code geschrieben, aber die Tests schlagen fehl. wahrscheinlich ein Fehler in ihnen?
F: Nein, alle Tests sind korrekt. Denken Sie: Sie haben wahrscheinlich keine ungewöhnliche Situation vorausgesehen.
A: Ich schreibe in X, es braucht definitiv mehr Speicher in Aufgabe Y. Erhöhen Sie die Grenzen!
F: Alle Grenzwerte sind so festgelegt, dass eine Lösung mit einer der verfügbaren Sprachen möglich ist. Versuchen Sie zu überprüfen, ob Sie bei Aufgaben mit strengen Speicherbeschränkungen versehentlich die gesamte Eingabedatei gelesen haben.
A: Einige Aufgaben können aufgrund der angegebenen Einschränkungen viel einfacher gelöst werden. Warum machst du das?
F: Wir haben die Eingabe in einigen Aufgaben speziell vereinfacht, damit sich die Teilnehmer leichter auf die Implementierung des Algorithmus konzentrieren können und nicht beispielsweise an die Geschwindigkeit des Herunterladens von Daten oder an andere Dinge denken, die für die Sportprogrammierung wichtig sind. Versuchen Sie, genau die von uns empfohlenen Algorithmen zu implementieren. Nur in dieser Situation können Sie den maximalen Nutzen aus dem Wettbewerb ziehen.
A: Ich möchte den Wettbewerb nicht bestehen. Kann ich nicht
F: Natürlich! Der Wettbewerb ist nicht für alle Kandidaten bindend. Ich empfehle jedoch weiterhin, das Problem zu beheben: Es wird auf jeden Fall nützlich sein.
A: Was würden Sie zur Vorbereitung noch empfehlen?
F: Lesen Sie unsere Tipps auf der offiziellen Seite zu Interviews in Yandex: https://yandex.ru/jobs/ya-interview . Ich möchte selbst hinzufügen, dass das Lösen von Problemen auf leetcode.com für jeden praktizierenden Entwickler äußerst nützlich ist, unabhängig davon, ob er in naher Zukunft ein Interview führen oder an Programmierwettbewerben teilnehmen möchte. Schon ein wenig Übung ermöglicht es Ihnen, sich bei der Lösung von Arbeitsaufgaben sicherer zu fühlen.
Fazit
Ich nehme oft an Konferenzen für Entwickler und Entwicklungsmanager teil, bin Mitglied vieler Entwicklungschats, habe mehrere hundert Interviews geführt und eine große Anzahl von Entwicklern für Yandex eingestellt. Die Erfahrung zeigt, dass algorithmische Abschnitte mit dem Schreiben von Code auf eine Tafel oder ein Papier häufig Fragen aufwerfen. Abschließend werde ich die beliebtesten beantworten.
Warum unter Bedingungen interviewen, die sich von den tatsächlichen Arbeitsbedingungen des Entwicklers unterscheiden?
Auf diese Weise können Sie nachvollziehen, ob der Kandidat Probleme in Programmen finden kann, ohne den Debugger zu starten. ob er im Voraus einen Plan des Algorithmus erstellen und ihn dann genau befolgen kann; Kann er einen kleinen, aber ausreichenden Satz von Tests erstellen und dann seine Implementierung anhand dieses Satzes von Tests überprüfen?
Verschaffen solche Abschnitte Sportprogrammierern einen unfairen Vorteil?
Sportprogrammierung entwickelt einige sehr nützliche Fähigkeiten in Entwicklern, so dass Teilnehmer an Programmierolympiaden in algorithmischen Abschnitten wirklich gut abschneiden. Es gibt also einen Vorteil, aber es ist fair. Der algorithmische Abschnitt ist nur einer von vielen, sodass jeder Kandidat genügend Möglichkeiten hat, seine Stärken zu zeigen!
Warum algorithmische Abschnitte durchführen, wenn alle Algorithmen schon lange implementiert wurden und Sie nur in der Lage sein müssen, ihre Implementierung in vorgefertigten Bibliotheken zu suchen?
In den algorithmischen Abschnitten, die allen Entwicklern gemeinsam sind, testen wir nur die minimal erforderlichen Fähigkeiten: die Fähigkeit, mit und ohne Fehler einen einfachen Algorithmus zu implementieren, der Schleifen enthält, Bedingungen überprüft und möglicherweise die Verwendung von assoziativen Arrays erfordert. Diese Art von Code wird ständig geschrieben, um Benutzerdienste zu implementieren.
Was ist der Punkt in einem Abschnitt, in dem nicht viele Entwicklerfähigkeiten getestet werden?
Der algorithmische Abschnitt überprüft in der Tat nur die Mindestanforderungen, die für einen Entwickler erforderlich sind. Wir testen andere Fähigkeiten mit Hilfe anderer Abschnitte.
Führen Sie algorithmische Abschnitte für Entwickler aller Fachrichtungen durch?
Ja Algorithmische Abschnitte werden für Backend-Entwickler, Analysten, Mobile- und Front-End-Entwickler, Entwickler von Infrastruktur- und maschinellen Lernmethoden usw. bereitgestellt.