DSA-intervjufrågor

Du har löst några hundra problem och känner dig ändå inte redo, vilket oftast betyder att du har övat på fel hälft av övningen. Det här avsnittet namnger vad som bedöms, så att övningen kan matcha det.

En direktomgång i datastrukturer och algoritmer mäter fyra saker samtidigt: om du känner igen vilket mönster problemet tillhör, om du kan formulera ansatsen innan du skriver kod, om implementationen är korrekt vid gränsfallen, och om du kan resonera högt om komplexitet. Kandidater optimerar det tredje och försummar det andra, och blir sedan nedvärderade för en korrekt lösning som kom utan förklaring.

Igenkänningssteget är anledningen till att mönsterövning slår volym. Problem är sällan verkligt nya; de är rekombinationer. Så snart du kan säga inom första minuten det här är ett sliding window över en frekvenskarta, är resten genomförande. Relaterade frågebanker efter språk och roll finns i intervjufrågehubben.

Dessa mönster står för merparten av det som frågas. Lär dig känna igen signalen som pekar mot varje mönster.

• Two pointers. Sorterad indata, parsummor, in-place-partitionering, palindromkontroller.
• Sliding window. Längsta eller kortaste sammanhängande subarray under ett villkor.
• Räkning med hash map. Anagram, dubbletter, frekvensjämförelser, första unika elementet.
• Binärsökning. Sorterade arrayer, och sökning i svarsrymden när arrayen inte är sorterad.
• Bredden-först- och djupet-först-sökning. Träd, rutnät, sammanhängande komponenter, kortaste oviktade väg.
• Heap och prioritetskö. Top-k-problem, sammanslagning av sorterade strömmar, löpande medianer.
• Intervall. Sammanslagning, infogning och upptäckt av överlapp efter sortering på startpunkt.
• Dynamisk programmering. Överlappande delproblem: trappklättring, växelpengar, redigeringsavstånd, delsekvenser.
• Backtracking. Permutationer, kombinationer, delmängder, pussel med villkor.
• Grafalgoritmer. Topologisk sortering, union find, kortaste viktade väg.

Representativa uppgifter, formulerade som intervjuare formulerar dem:

• Hitta två tal i en array vars summa är ett mål, och gör det sedan utan extra utrymme.
• Returnera längden på den längsta delsträngen utan upprepade tecken.
• Givet en roterad sorterad array, hitta ett mål i logaritmisk tid.
• Slå ihop överlappande intervall och förklara varför sorteringen är värd sin kostnad.
• Vänd ett binärt träd upp och ner, hitta sedan dess maximala djup.
• Validera ett binärt sökträd, och säg vad en naiv kontroll missar.
• Räkna öar i ett rutnät, säg sedan hur du skulle hantera ett rutnät för stort för minnet.
• Hitta de k vanligaste elementen och motivera din datastruktur.
• Beräkna det minsta antalet mynt för ett belopp, och ange rekursionen.
• Upptäck en cykel i en länkad lista, returnera sedan noden där den börjar.
• Serialisera och deserialisera ett binärt träd.
• Givet kursförkunskapskrav, avgör om schemat är möjligt.

En nyexaminerad som intervjuas för en backendroll får delsträngsproblemet och börjar skriva direkt. Koden är nästan rätt, men intervjuaren ägnar omgången åt att fråga vad den gör, och poängen speglar tystnaden snarare än buggen. En kandidat som lägger fyrtio sekunder på att säga fönster över en teckenkarta, expandera höger, dra ihop vänster vid en dubblett, håll koll på maximum har redan klarat den delen som är svårast att återhämta sig från.

Att lösa tyst bygger fel reflex. Direktomgången kräver berättande och kod samtidigt, och det är en separat färdighet från vardera för sig.

Ändra övningen, inte problemuppsättningen. Innan du skriver något, säg mönstret, ansatsen och den förväntade komplexiteten högt. Skriv koden medan du fortsätter berätta. När du är klar, ange komplexiteten igen och namnge ett specialfall du hanterat och ett du skulle fråga om. Att göra detta på tio problem bygger mer intervjuförmåga än att lösa femtio i tystnad.

En session med mock-intervju ger följdfrågorna, den del som inte kan övas på egen hand, och ger dig en inspelning av ditt eget berättande att granska. En ärlig gräns gäller genomgående: en skriven, i-webbläsaren-baserad kodningsbedömning med övervakning är inte ett samtal, och ingen direktassistent hör hemma där. Intervjutypshubben går igenom vilka kodningsformat som är direkta och vilka som är automatiserade.