Otázky z programování s AI: příklady a procvičování

Znalost názvů algoritmů vám nemusí pomoci rozhodnout, jak přistoupit k novému problému. Tato cvičná zadání propojují konkrétní vstupy s volbou řešení, mezemi složitosti a krajními případy, které byste měli vysvětlit nahlas.

• Two Sum: vraťte dva různé indexy, jejichž hodnoty dávají cílový součet. Pro [3, 3] a cíl 6 řešení použije obě pozice. Procházejte pole s hashovací mapou dříve nalezených hodnot, před uložením aktuální hodnoty vždy vyhledejte její doplněk. Tím zabráníte opakovanému použití stejného indexu. Očekávaná časová složitost je O(n) a dodatečná prostorová složitost O(n). Ujasněte si, co vrátit, pokud žádný pár neexistuje.
• Najděte nejdelší podřetězec bez opakujících se znaků. Pro 'abba' je délka 2. Sledujte poslední pozici každého znaku a udržujte okno bez duplicit. Levá hranice se nesmí posunout zpět, pokud starší výskyt leží mimo aktuální okno. Očekávaná časová složitost je při vyhledávání v hashovací mapě O(n). Ujasněte si, co se považuje za znak.
• Slučte překrývající se uzavřené intervaly. Pro [1, 3], [3, 5] a [8, 10] vraťte [1, 5] a [8, 10]. Seřaďte je podle začátku a poté aktuální interval rozšiřte, nebo začněte nový. Řazení dává časovou složitost O(n log n). Uzavřené intervaly se společným krajním bodem se překrývají; zeptejte se, zda to odpovídá definici v zadání.
• Obraťte acyklický jednosměrně vázaný seznam. Před změnou ukazatele aktuálního uzlu na další uzel si další uzel uložte. Iterativní řešení má časovou složitost O(n) a dodatečnou prostorovou složitost O(1). Projděte si prázdný seznam, jeden uzel a dva uzly. Vysvětlete, která část seznamu je po každé iteraci již obrácená.
• Vraťte hodnoty binárního stromu po jednotlivých úrovních. Použijte frontu a před přechodem na další úroveň zpracujte počet uzlů aktuální úrovně. Časová složitost je O(n); pomocná prostorová složitost fronty je O(w), kde w označuje maximální šířku úrovně bez započtení vráceného výstupu. Otestujte prázdný strom a strom, který má na každé úrovni pouze jednoho potomka.
• Rozhodněte, zda lze dokončit všechny kurzy při daných prerekvizitách. Modelujte prerekvizity jako orientovaný graf a použijte topologické řazení. Pokud zpracujete méně než V vrcholů, v grafu zůstává orientovaný cyklus. Časová složitost je O(V + E). Otestujte nespojené komponenty, izolovaný kurz a závislost kurzu na sobě samém.
• Najděte nejmenší počet mincí potřebných k dosažení částky. Předpokládejte neomezený počet mincí s kladnými celočíselnými nominálními hodnotami. Pro [1, 3, 4] a částku 6 vyžaduje postup od největší mince tři mince; 3 + 3 vyžaduje dvě. Definujte stav dynamického programu jako minimální počet mincí pro každou částku a začněte nulovým počtem mincí pro nulovou částku. Pro cílovou částku A a c nominálních hodnot má standardní přístup časovou složitost O(Ac) a prostorovou složitost O(A). Nedosažitelné částky ošetřete explicitně.

Další cvičení uspořádaná podle role a tématu najdete v knihovně otázek k pohovorům.

Zvažte toto zadání: Spočítejte neprázdná souvislá podpole, jejichž součet se rovná cílové hodnotě, přičemž jsou povoleny záporné hodnoty. Pro [1, -1, 1] a cíl 1 je výsledkem 3: buď jedno z jednoprvkových podpolí [1], nebo celé pole.

Začněte základním řešením: vyberte každou počáteční pozici a postupně posouvejte koncovou pozici, přičemž udržujte průběžný součet. To vyžaduje čas O(n²) a dodatečný prostor O(1). Obvyklý přístup se zmenšujícím se oknem zde není spolehlivý, protože záporné hodnoty narušují předpoklad, že rozšířením okna jeho součet vzroste.

Rychlejší přístup používá prefixové součty a mapu četností. Pokud je aktuální prefixový součet s, každý dřívější prefix rovnající se s - cíl určuje podpole s požadovaným součtem. Mapu inicializujte jedním výskytem nulového prefixového součtu, který představuje prázdný prefix před začátkem pole.

• Pořadí zpracování: Přičtěte aktuální hodnotu k prefixovému součtu, spočítejte odpovídající dřívější prefixy a poté aktuální prefix zaznamenejte. Pokud byste jej zaznamenali jako první, chybně byste započítali prázdné podpole, když je cíl nulový.
• Invariant: Před zaznamenáním aktuálního prefixu obsahuje mapa četnosti všech prefixů končících před aktuální pozicí.
• Složitost: Každý prvek vyžaduje konstantní počet operací s mapou. Očekávaná časová složitost je O(n), pokud předpokládáme očekávanou konstantní dobu hashovacích operací; dodatečná prostorová složitost je O(n).
• Kontroly: Prázdné pole vrátí 0. Pro [0, 0] a cíl 0 vraťte 3. U celočíselných typů s pevnou šířkou zvažte přetečení kumulativního součtu i počtu výsledků.

Užitečnou doplňující otázkou je, zda zadání vyžaduje počet, nebo samotná podpole. Vrácení všech odpovídajících podpolí přináší náklady na výstup: pole tvořené samými nulami má při nulovém cíli n(n + 1)/2 odpovídajících neprázdných podpolí.

Než požádáte o pomoc, zkuste úlohu vyřešit sami. Poté požádejte o nejmenší zásah, který vám umožní pokračovat. Následující pokyny promění rozhovor s AI v ověřitelné procvičování.

• Požádejte o jednu nápovědu: Dej mi jednu nápovědu, jaké informace mám ukládat. Zatím neposkytuj kód ani název celého algoritmu.
• Prověřte odůvodnění: Zde je invariant mé smyčky. Najdi vstup, při kterém ho moje implementace porušuje, nebo vysvětli, proč ho každá aktualizace zachovává. Odpověď sami ověřte; souhlas modelu není důkazem správnosti.
• Prověřte složitost: Spočítej práci prováděnou řezy, řazením, operacemi s kontejnery a rekurzivními voláními v této implementaci. Známý název algoritmu neurčuje složitost vašeho skutečného kódu.
• Vytvořte testy: Navrhni případy pro prázdný vstup, duplicity, hraniční hodnoty a nemožné výsledky. U každého vysvětli očekávanou odpověď. Než je použijete jako testovací orákulum, odvoďte odpovědi samostatně.
• Změňte jednu podmínku: Jak se řešení změní, pokud je vstup seřazený, nelze ho upravit nebo přichází jako proud? Před přepsáním kódu vysvětlete nový kompromis.

Představte si backendovou vývojářku, která se připravuje na seniorní pozici u poskytovatele cloudových služeb. Po vyřešení úlohy s grafem prerekvizit požádá partnera AI pro procvičování o nespojený graf obsahující cyklus. Poté projde frontu a bez nahlédnutí do nápovědy vysvětlí, proč počet zpracovaných vrcholů odhaluje cyklus.

Po přečtení úplného řešení ho zavřete a zpaměti znovu sestavte algoritmus, invariant a testy. Schopnost reprodukovat kód je méně užitečná než schopnost vysvětlit, proč funguje, a přizpůsobit ho změněné podmínce.

Chcete-li si procvičit vysvětlování svých úvah v rozhovoru, navštivte stránku simulovaného pohovoru.

SubcueAI nabízí dvě rozhraní pro živou asistenci. Jeho hlavní nativní aplikace pro macOS a Windows snímá systémový zvuk a váš mikrofon a asistenci zobrazuje v plovoucím místním překryvu. Funguje s desktopovými klienty pro schůzky, včetně Zoom a Microsoft Teams.

Rozšíření pro prohlížeče poskytuje živou asistenci také prostřednictvím bočního panelu v prohlížečích založených na Chromiu, včetně Chrome a Edge. Snímá pouze zvuk karty se schůzkou, takže podporuje hovory v kartě prohlížeče, například Google Meet. Slyší tazatele prostřednictvím této karty, nikdy nesnímá váš mikrofon a nepřepisuje řeč uchazeče. Verze pro Firefox je určena pouze k simulovanému procvičování.

Žádné z těchto rozhraní nepřidává do hovoru bota ani nevkládá do stránky schůzky obsahový skript. U programovacích úloh rozlišujte mluvený a psaný kontext: samotné snímání zvuku neposkytne zadání ani kód zobrazený pouze v editoru. Každý návrh porovnejte s přesným zadáním, omezeními a implementací.

Před použitím živé asistence si ověřte pravidla pohovoru. SubcueAI není za všech okolností neodhalitelný. Sdílení obrazovky, nahrávání, kontrolovaná hodnocení a zařízení spravovaná společností nespadají pod záruky skrytí. Sdílená nebo nahrávaná obrazovka může odhalit překryv či boční panel a ovládací prvky zařízení nebo kontrolního softwaru mohou monitorovat aktivitu.

Pokyny k nastavení dostupných rozhraní najdete v průvodci SubcueAI.