DSA állásinterjú-kérdések

Már néhány száz feladatot megoldottál, mégis felkészületlennek érzed magad, ami általában azt jelenti, hogy a gyakorlás rossz felét gyakoroltad. Ez a rész megnevezi, mit értékelnek, hogy a gyakorlás ehhez igazodhasson.

Egy élő adatstruktúra- és algoritmus-forduló négy dolgot mér egyszerre: felismered-e, melyik mintához tartozik a feladat, meg tudod-e fogalmazni a megközelítést kód írása előtt, helyes-e a megvalósítás a szélsőséges eseteknél, és tudsz-e hangosan gondolkodni a komplexitásról. A jelöltek a harmadikat optimalizálják, a másodikat elhanyagolják, majd alacsonyabb pontszámot kapnak egy helyes megoldásért, amely magyarázat nélkül érkezett.

A felismerési lépés az oka annak, hogy a mintagyakorlás felülmúlja a mennyiséget. A feladatok ritkán igazán újak; rekombinációk. Amint az első percen belül ki tudod mondani, hogy ez egy sliding window egy gyakorisági térkép felett, a többi már kivitelezés. A nyelv és szerepkör szerinti kapcsolódó kérdésbankok a állásinterjú-kérdések központjában találhatók.

Ezek a minták adják a feltett kérdések nagy részét. Tanuld meg felismerni a jelet, amely mindegyikre utal.

• Two pointers. Rendezett bemenet, párösszegek, in-place particionálás, palindrom-ellenőrzések.
• Sliding window. A leghosszabb vagy legrövidebb összefüggő résztömb egy megkötés mellett.
• Számlálás hash map-pel. Anagrammák, duplikátumok, gyakorisági összehasonlítások, első egyedi elem.
• Bináris keresés. Rendezett tömbök, valamint keresés a válaszok terében, ha a tömb nem rendezett.
• Szélességi és mélységi keresés. Fák, rácsok, összefüggő komponensek, legrövidebb súlyozatlan út.
• Kupac és prioritási sor. Top-k feladatok, rendezett folyamok összefésülése, futó mediánok.
• Intervallumok. Összefésülés, beszúrás és átfedés-észlelés a kezdőpont szerinti rendezés után.
• Dinamikus programozás. Átfedő részfeladatok: lépcsőmászás, aprópénz-visszaadás, szerkesztési távolság, részsorozatok.
• Backtracking. Permutációk, kombinációk, részhalmazok, megkötéses rejtvények.
• Gráfalgoritmusok. Topologikus rendezés, union find, legrövidebb súlyozott út.

Reprezentatív feladatok, úgy megfogalmazva, ahogyan az interjúztatók megfogalmazzák őket:

• Találj két számot egy tömbben, amelyek összege egy célérték, majd tedd ezt extra hely nélkül.
• Add vissza a leghosszabb, ismétlődő karakter nélküli részlánc hosszát.
• Egy elforgatott, rendezett tömb esetén találj egy célértéket logaritmikus időben.
• Fésülj össze átfedő intervallumokat, és magyarázd el, miért éri meg a rendezés a költségét.
• Fordíts meg egy bináris fát, majd találd meg a maximális mélységét.
• Validálj egy bináris keresőfát, és mondd meg, mit hagy figyelmen kívül egy naiv ellenőrzés.
• Számold meg a szigeteket egy rácson, majd mondd el, hogyan kezelnél egy memóriához túl nagy rácsot.
• Találd meg a k leggyakoribb elemet, és indokold az adatstruktúra választását.
• Számítsd ki a minimális érmeszámot egy összeghez, és add meg a rekurenciát.
• Észlelj ciklust egy láncolt listában, majd add vissza a csomópontot, ahol elkezdődik.
• Szerializálj és deszerializálj egy bináris fát.
• A kurzusok előfeltételei alapján dönts arról, lehetséges-e az órarend.

Egy frissdiplomás, aki backend szerepkörre interjúzik, megkapja a részlánc-feladatot, és azonnal elkezd gépelni. A kód majdnem helyes, de az interjúztató a fordulót azzal tölti, hogy megkérdezi, mit csinál, és az értékelés a csendet tükrözi, nem a hibát. Az a jelölt, aki negyven másodpercet szán arra, hogy elmondja: ablak egy karaktertérkép felett, jobbra bővítem, balról szűkítem duplikátumnál, követem a maximumot, már túl van a legnehezebben behozható részen.

A csendben történő megoldás rossz reflexet épít ki. Az élő forduló egyidejű narrációt és kódolást igényel, és ez külön képesség mindkettőtől önmagában.

Változtasd meg a gyakorlatot, ne a feladatkészletet. Mielőtt bármit is leírnál, mondd ki hangosan a mintát, a megközelítést és a várt komplexitást. Írd a kódot, miközben folytatod a narrálást. Amikor végzel, mondd ki újra a komplexitást, és nevezz meg egy szélsőséges esetet, amelyet kezeltél, és egyet, amelyről kérdeznél. Ha ezt tíz feladaton csinálod, több interjúképességet épít, mint ötven csendben megoldott feladat.

Egy próbainterjú foglalkozás megadja az utókérdéseket, azt a részt, amelyet nem lehet egyedül gyakorolni, és felvételt ad a saját narrálásodról, hogy átnézhesd. Egy őszinte korlát mindenhol érvényes: egy írásbeli, böngészőben végzett, felügyelt kódolási értékelés nem beszélgetés, és egyetlen élő asszisztensnek sincs helye benne. Az interjútípusok központja bemutatja, mely kódolási formátumok élők, és melyek automatizáltak.