Otázky na pohovoru DSA

Vyřešili jste už několik set úloh a přesto se necítíte připraveni, což obvykle znamená, že jste trénovali špatnou polovinu cvičení. Tato část pojmenovává, co se hodnotí, aby se s tím praxe mohla srovnat.

Živé kolo o datových strukturách a algoritmech měří čtyři věci najednou: zda poznáte, ke kterému vzoru úloha patří, zda dokážete formulovat postup před psaním kódu, zda je implementace správná na okrajových případech, a zda dokážete nahlas uvažovat o složitosti. Kandidáti optimalizují třetí bod a zanedbávají druhý, a pak jsou hodnoceni hůř za správné řešení, které přišlo bez vysvětlení.

Krok rozpoznání je důvodem, proč trénink vzorů překonává objem. Úlohy jsou málokdy skutečně nové; jsou to rekombinace. Jakmile dokážete v první minutě říct tohle je sliding window nad mapou četností, zbytek je provedení. Související banky otázek podle jazyka a role najdete v centru pohovorových otázek.

Tyto vzory tvoří většinu toho, na co se ptají. Naučte se rozpoznávat signál, který na každý ukazuje.

• Two pointers. Seřazený vstup, součty dvojic, in-place particování, kontroly palindromů.
• Sliding window. Nejdelší nebo nejkratší souvislý podřetězec/podpole při daném omezení.
• Počítání pomocí hash map. Anagramy, duplicity, porovnání četností, první unikátní prvek.
• Binární vyhledávání. Seřazená pole, a vyhledávání v prostoru odpovědí, pokud pole není seřazené.
• Prohledávání do šířky a do hloubky. Stromy, mřížky, souvislé komponenty, nejkratší neohodnocená cesta.
• Halda a prioritní fronta. Úlohy top-k, slučování seřazených proudů, běžící mediány.
• Intervaly. Slučování, vkládání a detekce překryvu po seřazení podle začátku.
• Dynamické programování. Překrývající se podúlohy: výstup po schodech, výměna mincí, editační vzdálenost, podposloupnosti.
• Backtracking. Permutace, kombinace, podmnožiny, hádanky s omezeními.
• Grafové algoritmy. Topologické řazení, union find, nejkratší ohodnocená cesta.

Reprezentativní zadání, formulovaná tak, jak je formulují tazatelé:

• Najděte dvě čísla v poli, jejichž součet je cíl, a pak to udělejte bez dalšího prostoru.
• Vraťte délku nejdelšího podřetězce bez opakujících se znaků.
• Máte-li otočené seřazené pole, najděte cíl v logaritmickém čase.
• Sloučte překrývající se intervaly a vysvětlete, proč se řazení vyplatí.
• Obraťte binární strom a poté najděte jeho maximální hloubku.
• Ověřte binární vyhledávací strom a řekněte, co naivní kontrola přehlédne.
• Spočítejte ostrovy v mřížce a poté řekněte, jak byste zpracovali mřížku příliš velkou pro paměť.
• Najděte k nejčastějších prvků a zdůvodněte svou datovou strukturu.
• Vypočtěte minimální počet mincí pro danou částku a uveďte rekurenci.
• Detekujte cyklus ve spojovém seznamu a poté vraťte uzel, kde začíná.
• Serializujte a deserializujte binární strom.
• Na základě předpokladů kurzů rozhodněte, zda je rozvrh proveditelný.

Čerstvý absolvent, který má pohovor na backendovou pozici, dostane úlohu s podřetězcem a hned začne psát kód. Kód je téměř správný, ale tazatel stráví celé kolo tím, že se ptá, co dělá, a hodnocení odráží mlčení, ne chybu. Kandidát, který věnuje čtyřicet sekund tomu, aby řekl okno nad mapou znaků, rozšiřuji doprava, zužuji doleva při duplicitě, sleduji maximum, už zvládl tu nejtěžší část k dohnání.

Tiché řešení buduje špatný reflex. Živé kolo vyžaduje vyprávění a kód současně, a to je samostatná dovednost oproti oběma zvlášť.

Změňte cvičení, ne sadu úloh. Než cokoli napíšete, řekněte nahlas vzor, postup a očekávanou složitost. Pište kód a přitom pokračujte ve vyprávění. Až skončíte, uveďte složitost znovu a pojmenujte jeden okrajový případ, který jste ošetřili, a jeden, na který byste se zeptali. Dělat to u deseti úloh buduje víc pohovorových dovedností než tiché vyřešení padesáti.

Relace simulovaného pohovoru poskytuje doplňující otázky, tu část, kterou nelze nacvičit sám, a dá vám nahrávku vlastního vyprávění k přehrání. Jedno poctivé omezení platí všude: psané hodnocení kódování v prohlížeči se sledováním není konverzace a žádný živý asistent do ní nepatří. Centrum typů pohovorů popisuje, které formáty kódování jsou živé a které automatizované.