Pytania rekrutacyjne DSA

Rozwiązałeś już kilkaset zadań i wciąż czujesz się nieprzygotowany, co zwykle oznacza, że ćwiczyłeś niewłaściwą połowę tego ćwiczenia. Ta sekcja nazywa to, co jest oceniane, aby praktyka mogła to odzwierciedlać.

Żywa rozmowa ze struktur danych i algorytmów mierzy jednocześnie cztery rzeczy: czy rozpoznajesz, do którego wzorca należy zadanie, czy potrafisz przedstawić podejście przed napisaniem kodu, czy implementacja jest poprawna na przypadkach brzegowych, i czy potrafisz rozumować na głos o złożoności. Kandydaci optymalizują trzeci punkt, a zaniedbują drugi, po czym są oceniani niżej za poprawne rozwiązanie, które pojawiło się bez wyjaśnienia.

Krok rozpoznawania jest powodem, dla którego ćwiczenie wzorców pokonuje objętość. Zadania rzadko są naprawdę nowe; to rekombinacje. Gdy tylko potrafisz powiedzieć w pierwszej minucie to jest sliding window na mapie częstości, reszta jest wykonaniem. Powiązane bazy pytań według języka i roli znajdują się w centrum pytań rekrutacyjnych.

Te wzorce odpowiadają za większość zadawanych pytań. Naucz się rozpoznawać sygnał wskazujący na każdy z nich.

• Two pointers. Posortowane dane wejściowe, sumy par, partycjonowanie in-place, sprawdzanie palindromów.
• Sliding window. Najdłuższy lub najkrótszy ciągły podciąg spełniający ograniczenie.
• Zliczanie z hash mapą. Anagramy, duplikaty, porównania częstości, pierwszy unikalny element.
• Wyszukiwanie binarne. Posortowane tablice, a także wyszukiwanie w przestrzeni odpowiedzi, gdy tablica nie jest posortowana.
• Przeszukiwanie wszerz i w głąb. Drzewa, siatki, spójne składowe, najkrótsza ścieżka bez wag.
• Kopiec i kolejka priorytetowa. Zadania top-k, scalanie posortowanych strumieni, bieżące mediany.
• Przedziały. Scalanie, wstawianie i wykrywanie nakładania po posortowaniu według początku.
• Programowanie dynamiczne. Nakładające się podproblemy: wchodzenie po schodach, wydawanie reszty, odległość edycyjna, podciągi.
• Backtracking. Permutacje, kombinacje, podzbiory, łamigłówki z ograniczeniami.
• Algorytmy grafowe. Sortowanie topologiczne, union find, najkrótsza ścieżka z wagami.

Przykładowe polecenia, sformułowane tak, jak formułują je rekruterzy:

• Znajdź dwie liczby w tablicy, których suma równa się celowi, a następnie zrób to bez dodatkowej pamięci.
• Zwróć długość najdłuższego podciągu bez powtarzających się znaków.
• Mając obróconą posortowaną tablicę, znajdź cel w czasie logarytmicznym.
• Scal nakładające się przedziały i wyjaśnij, dlaczego sortowanie jest warte swojego kosztu.
• Odwróć drzewo binarne, a następnie znajdź jego maksymalną głębokość.
• Zwaliduj drzewo poszukiwań binarnych i powiedz, co pomija naiwne sprawdzenie.
• Policz wyspy na siatce, a następnie powiedz, jak obsłużyłbyś siatkę zbyt dużą dla pamięci.
• Znajdź k najczęściej występujących elementów i uzasadnij dobór struktury danych.
• Oblicz minimalną liczbę monet dla danej kwoty i podaj rekurencję.
• Wykryj cykl na liście jednokierunkowej, a następnie zwróć węzeł, w którym się zaczyna.
• Zserializuj i zdeserializuj drzewo binarne.
• Mając wymagania wstępne kursów, zdecyduj, czy plan zajęć jest możliwy.

Świeżo upieczony absolwent na rozmowie o stanowisko backendowe dostaje zadanie z podciągiem i od razu zaczyna pisać kod. Kod jest niemal poprawny, ale rekruter spędza całą rundę, pytając, co on robi, a ocena odzwierciedla ciszę, a nie błąd. Kandydat, który poświęca czterdzieści sekund na powiedzenie okno na mapie znaków, rozszerzam w prawo, zwężam w lewo przy duplikacie, śledzę maksimum, ma już za sobą najtrudniejszą do odrobienia część.

Ciche rozwiązywanie buduje niewłaściwy odruch. Żywa runda wymaga jednoczesnej narracji i kodu, a to osobna umiejętność w stosunku do każdej z nich z osobna.

Zmień ćwiczenie, a nie zestaw zadań. Zanim cokolwiek napiszesz, powiedz na głos wzorzec, podejście i oczekiwaną złożoność. Pisz kod, kontynuując narrację. Gdy skończysz, podaj złożoność ponownie i nazwij jeden przypadek brzegowy, który obsłużyłeś, oraz jeden, o który byś zapytał. Zrobienie tego na dziesięciu zadaniach buduje więcej umiejętności rekrutacyjnych niż ciche rozwiązanie pięćdziesięciu.

Sesja symulowanej rozmowy kwalifikacyjnej dostarcza pytań dodatkowych, czyli części, której nie da się przećwiczyć samemu, i daje nagranie własnej narracji do przejrzenia. Jedno uczciwe ograniczenie obowiązuje wszędzie: pisemna, nadzorowana ocena kodowania w przeglądarce nie jest rozmową, i żaden żywy asystent nie powinien w niej uczestniczyć. Centrum rodzajów rozmów kwalifikacyjnych opisuje, które formaty kodowania są na żywo, a które automatyczne.