Pytania na rozmowę z programowania AI: przykłady i ćwiczenia

Znajomość nazw algorytmów może nadal nie wystarczyć, by wiedzieć, jak podejść do nowego problemu. Te zadania ćwiczeniowe łączą konkretne dane wejściowe z wyborem rozwiązania, granicami złożoności i przypadkami brzegowymi, które warto wyjaśniać na głos.

• Two Sum: zwróć dwa różne indeksy, których wartości sumują się do wartości docelowej. Dla [3, 3] i wartości docelowej 6 odpowiedź wykorzystuje obie pozycje. Przejdź po danych, używając mapy haszującej wcześniej napotkanych wartości: przed zapisaniem bieżącej wartości sprawdź, czy istnieje jej dopełnienie. Zapobiega to ponownemu użyciu tego samego indeksu. Oczekiwany czas to O(n), a dodatkowa pamięć to O(n). Wyjaśnij, co zwrócić, jeśli żadna para nie istnieje.
• Znajdź najdłuższy podciąg bez powtarzających się znaków. Dla 'abba' długość wynosi 2. Śledź ostatnią pozycję każdego znaku i utrzymuj okno bez duplikatów. Lewa granica nie może cofać się, gdy starsze wystąpienie znajduje się poza bieżącym oknem. Oczekiwany czas to O(n) przy wyszukiwaniu w mapie haszującej. Wyjaśnij, co jest uznawane za znak.
• Scal nakładające się domknięte przedziały. Dla [1, 3], [3, 5] i [8, 10] zwróć [1, 5] oraz [8, 10]. Posortuj przedziały według początku, a następnie rozszerzaj bieżący przedział lub rozpocznij kolejny. Sortowanie daje czas O(n log n). Domknięte przedziały ze wspólnym punktem końcowym nakładają się; zapytaj, czy odpowiada to definicji problemu.
• Odwróć acykliczną listę jednokierunkową. Zapisz następny węzeł przed zmianą wskaźnika bieżącego węzła na następny element. Rozwiązanie iteracyjne zajmuje O(n) czasu i O(1) dodatkowej pamięci. Prześledź pustą listę, jeden węzeł i dwa węzły. Wyjaśnij po każdej iteracji, która część listy jest już odwrócona.
• Zwróć wartości drzewa binarnego poziom po poziomie. Użyj kolejki i przetwórz liczbę węzłów bieżącego poziomu przed rozpoczęciem następnego. Czas wynosi O(n); pomocnicza kolejka zajmuje O(w) pamięci, gdzie w oznacza maksymalną szerokość poziomu, bez uwzględniania zwracanego wyniku. Przetestuj puste drzewo oraz drzewo z tylko jednym dzieckiem na każdym poziomie.
• Ustal, czy można ukończyć wszystkie kursy przy podanych wymaganiach wstępnych. Zamodeluj wymagania jako graf skierowany i użyj sortowania topologicznego. Jeśli przetworzono mniej niż V wierzchołków, pozostał cykl skierowany. Czas wynosi O(V + E). Przetestuj rozłączne składowe, odizolowany kurs i zależność kursu od samego siebie.
• Znajdź najmniejszą liczbę monet potrzebną do uzyskania danej kwoty. Załóż nieograniczoną liczbę monet o dodatnich nominałach całkowitych. Dla [1, 3, 4] i kwoty 6 wybieranie najpierw największej monety wymaga trzech monet; 3 + 3 wymaga dwóch. Zdefiniuj stan programowania dynamicznego jako minimalną liczbę monet dla każdej kwoty, zaczynając od zera monet dla kwoty zero. Przy celu A i c nominałach standardowe podejście zajmuje O(Ac) czasu i O(A) pamięci. Jawnie obsłuż kwoty niemożliwe do uzyskania.

Więcej powiązanych ćwiczeń uporządkowanych według stanowiska i tematu znajdziesz w bibliotece pytań rekrutacyjnych.

Rozważ następujące zadanie: Policz niepuste spójne podtablice, których suma jest równa wartości docelowej, dopuszczając wartości ujemne. Dla [1, -1, 1] i wartości docelowej 1 odpowiedź wynosi 3: dowolna jednoelementowa podtablica [1] albo cała tablica.

Zacznij od rozwiązania bazowego: wybierz każdą pozycję początkową i przesuwaj pozycję końcową, utrzymując bieżącą sumę. Wymaga to O(n²) czasu i O(1) dodatkowej pamięci. Typowe podejście ze zmniejszanym oknem jest tutaj zawodne, ponieważ wartości ujemne obalają założenie, że rozszerzenie okna zwiększa jego sumę.

Szybsze podejście wykorzystuje sumy prefiksowe i mapę częstości. Jeśli bieżąca suma prefiksowa wynosi s, każdy wcześniejszy prefiks równy s - wartość docelowa wskazuje podtablicę o wymaganej sumie. Zainicjuj mapę jednym wystąpieniem sumy prefiksowej równej zero, reprezentującym pusty prefiks przed początkiem tablicy.

• Kolejność przetwarzania: Dodaj bieżącą wartość do sumy prefiksowej, policz pasujące wcześniejsze prefiksy, a następnie zapisz bieżący prefiks. Zapisanie go wcześniej spowodowałoby błędne policzenie pustej podtablicy, gdy wartość docelowa wynosi zero.
• Niezmiennik: Przed zapisaniem bieżącego prefiksu mapa zawiera częstości wszystkich prefiksów kończących się przed bieżącą pozycją.
• Złożoność: Każdy element wymaga stałej liczby operacji na mapie. Oczekiwany czas to O(n), przy założeniu oczekiwanego stałego czasu operacji haszujących; dodatkowa pamięć wynosi O(n).
• Kontrole: Pusta tablica zwraca 0. Dla [0, 0] i wartości docelowej 0 zwróć 3. Przy typach całkowitych o stałej szerokości uwzględnij przepełnienie zarówno sumy skumulowanej, jak i liczby wyników.

Przydatne pytanie uzupełniające dotyczy tego, czy zadanie wymaga liczby podtablic, czy samych podtablic. Zwrócenie każdej pasującej podtablicy wiąże się z kosztem rozmiaru wyniku: tablica złożona wyłącznie z zer ma n(n + 1)/2 pasujących niepustych podtablic, gdy wartość docelowa wynosi zero.

Najpierw podejmij samodzielną próbę, a potem poproś o najmniejszą pomoc, która pozwoli Ci ruszyć dalej. Poniższe polecenia zamieniają rozmowę z AI w ćwiczenie, które możesz zweryfikować.

• Poproś o jedną wskazówkę: Daj mi jedną wskazówkę dotyczącą informacji, które należy przechowywać. Nie podawaj jeszcze kodu ani nazwy całego algorytmu.
• Podważ tok rozumowania: Oto mój niezmiennik pętli. Znajdź dane wejściowe, dla których moja implementacja go narusza, albo wyjaśnij, dlaczego każda aktualizacja go zachowuje. Samodzielnie sprawdź odpowiedź; zgoda modelu nie jest dowodem poprawności.
• Sprawdź złożoność: Policz operacje wykonywane przez wycinanie fragmentów, sortowanie, operacje na kontenerach i wywołania rekurencyjne w tej implementacji. Znajoma nazwa algorytmu nie określa złożoności Twojego rzeczywistego kodu.
• Wygeneruj testy: Zaproponuj przypadki dla pustych danych wejściowych, duplikatów, wartości granicznych i niemożliwych wyników. Wyjaśnij oczekiwaną odpowiedź dla każdego z nich. Wyprowadź te odpowiedzi niezależnie, zanim użyjesz ich jako wyroczni testowej.
• Zmień jedno ograniczenie: Jak zmieni się rozwiązanie, jeśli dane wejściowe są posortowane, nie można ich modyfikować albo napływają jako strumień? Wyjaśnij nowy kompromis przed przepisaniem kodu.

Wyobraź sobie programistkę backendu przygotowującą się do objęcia starszego stanowiska u dostawcy usług chmurowych. Po rozwiązaniu problemu grafu wymagań wstępnych prosi partnera do ćwiczeń opartego na AI o rozłączny graf zawierający cykl. Następnie śledzi kolejkę i bez zaglądania do wskazówki wyjaśnia, dlaczego liczba przetworzonych wierzchołków ujawnia cykl.

Po przeczytaniu pełnego rozwiązania zamknij je i odtwórz z pamięci algorytm, niezmiennik oraz testy. Umiejętność odtworzenia kodu jest mniej przydatna niż zdolność wyjaśnienia, dlaczego działa, i dostosowania go do zmienionego ograniczenia.

Aby przećwiczyć wyjaśnianie swojego toku rozumowania w rozmowie, odwiedź stronę próbnej rozmowy.

SubcueAI oferuje dwa sposoby korzystania z pomocy na żywo. Jego główna aplikacja natywna dla macOS i Windows przechwytuje dźwięk systemowy oraz mikrofon, a pomoc wyświetla w lokalnej pływającej nakładce. Współpracuje z desktopowymi klientami spotkań, w tym Zoom i Microsoft Teams.

Rozszerzenie przeglądarkowe również zapewnia pomoc na żywo przez panel boczny w przeglądarkach Chromium, w tym Chrome i Edge. Przechwytuje wyłącznie dźwięk karty spotkania, obsługując połączenia w kartach przeglądarki, takie jak Google Meet. Słyszy osobę prowadzącą rozmowę za pośrednictwem tej karty, nigdy nie przechwytuje Twojego mikrofonu i nie transkrybuje kandydata. Wersja dla Firefox służy wyłącznie do próbnych ćwiczeń.

Żadne z tych rozwiązań nie dodaje bota do połączenia ani nie wstrzykuje skryptu treści na stronę spotkania. W przypadku pytań programistycznych odróżnij kontekst mówiony od pisanego: samo przechwytywanie dźwięku nie dostarcza treści zadania ani kodu widocznego wyłącznie w edytorze. Sprawdzaj każdą sugestię względem dokładnej treści zadania, ograniczeń i implementacji.

Przed skorzystaniem z pomocy na żywo potwierdź zasady rozmowy. SubcueAI nie jest zawsze niewykrywalne. Udostępnianie ekranu, nagrywanie, nadzorowane testy i urządzenia zarządzane przez firmę nie są objęte zapewnieniami dotyczącymi ukrycia. Udostępniany lub nagrywany ekran może ujawnić nakładkę albo panel boczny, a mechanizmy kontroli urządzenia lub nadzoru mogą monitorować aktywność.

Instrukcje konfiguracji dostępnych rozwiązań znajdziesz w samouczku SubcueAI.