Obsah[Skrýt][Ukázat]
- 1. Jak definujete pole?
- 2. Dynamická pole: Co to jsou? Co je odlišuje od Basic Arrays?
- 3. Jak se pole a slovník navzájem liší?
- 4. Uveďte některé výhody a nevýhody polí.
- 5. Co znamená „Sparse Array“?
- 6. Kdy byste zvolili propojený seznam před polem?
- 7. Co odlišuje indexované pole od asociativního pole?
- 8. Jaké výhody má Heap oproti tříděným polím?
- 9. Můžeme definovat velikost pole jako zápornou?
- 10. Jak najdete chybějící celé číslo v poli o 1 až 100 prvcích?
- 11. Jak zjistíte index prvku v poli?
- 12. Jak se můžete zbavit konkrétního prvku z pole?
- 13. Jak lze ověřit rovnost dvou polí?
- 14. Když mluvíme o polích, co myslíte frázemi „Dimension“ a „Subscript“?
- Otázky k pohovoru o kódování
- 15. Najděte pár v poli, který má zadaný součet
- 16. Třídění binárních polí s lineárním časem
- 17. Najděte největší dvouintový součin v poli.
- 18. Jak posunout všechny nuly pole na konec
- 19. Jak seřadit pole se dvěma položkami, které se přepínají v jedné operaci.
- 20. Jak spojit dvě setříděná pole na místě.
- 21. Jak změnit pořadí položek ve střídavě vysokých a nízkých pozicích?
- 22. Jak nahradit každý prvek pole bez použití operátoru dělení součinem každého prvku v poli?
- 23. Najděte nejpodivnější prvek v poli v logaritmickém čase
- 24. Jak získat následný větší prvek pro každý prvek v kruhovém poli?
- 25. Najděte počet inverzí pole?
- 26. Jaký je problém zachycování dešťové vody?
- Proč investovat do čističky vzduchu?
Kódovací rozhovory obsahují řadu otázek DSA. Pokud se chystáte na svůj nadcházející technický pohovor s FAANG nebo jiným technologickým podnikem Tier-1, měli byste být zběhlí v polích.
Ve většině rozhovorů o kódování je na druhém místě za strunami. Pole je seskupení souvisejících datových prvků uchovávaných v paměti v těsné blízkosti.
Protože jsou propojeny se všemi programovacími jazyky, jako je C, C++, Java, Python, Perl a Ruby, jsou všude. Pokračujte ve čtení, kde najdete některé praktické problémy s kódováním a otázky a odpovědi na rozhovory založené na polích.
Python bude v tomto příspěvku použit k řešení problémů s kódováním, protože se snadno používá, rozumí a musí být většině z nás známý.
Pojďme začít.
1. Jak definujete pole?
- Skupinou souvisejících datových typů je pole.
- Pole jsou vždy pevná.
- Stejný druh proměnné je uložen na několika místech objekty pole.
- Primitivní typy a odkazy na objekty jsou s ním kompatibilní.
2. Dynamická pole: Co to jsou? Co je odlišuje od Basic Arrays?
Významnou výhodou je automatické škálování, které dynamická pole (v Javě také označovaná jako growable arrays, měnitelná pole, měnitelná pole nebo ArrayLists) poskytují.
Vždy musíte předem vědět, kolik prvků vaše pole uloží, protože pole mají pevnou velikost. Na druhou stranu dynamické pole roste, když do něj přidáváte další členy, takže nemusíte předem znát jeho přesnou velikost.
3. Jak se pole a slovník navzájem liší?
Jedná se o základní řadu otázek pohovoru, které jsou pravidelně kladeny. Níže jsou uvedeny hlavní rozdíly mezi poli a slovníky:
- Pole je uspořádaný seznam podobných položek. Na druhé straně slovník má páry klíč-hodnota.
- Velikosti polí se mohou dynamicky měnit. Takové dynamické myšlenky ve slovnících neexistují.
- Před použitím pole musí být specifikována jeho velikost. Velikosti slovníků není třeba přizpůsobovat.
- Pokud chcete zvětšit velikost pole, použijte příkaz Redim. Ve slovnících lze prvek přidat bez deklarace.
4. Uveďte některé výhody a nevýhody polí.
Výhody:
- Pole mohou třídit několik prvků současně.
- Ostatní datové struktury, jako jsou zásobníky, fronty, propojené seznamy, stromy, grafy atd., mohou být implementovány v poli.
- Index lze použít k dosažení prvku pole.
Nevýhody:
- Velikost pole musí být deklarována předem. V okamžiku deklarace pole si však nemusíme být vědomi požadované velikosti.
- Struktura pole je statická. To znamená, že velikost pole je vždy pevná a že alokaci paměti nelze zvětšit ani zmenšit.
5. Co znamená „Sparse Array“?
Řídké pole je datové pole, které obsahuje mnoho položek s nulovými hodnotami. Naproti tomu husté pole obsahuje většinu svých položek s nenulovými hodnotami. Indexy řídkého pole, které převádí čísla na objekty, mohou obsahovat mezery. Ve srovnání s HashMap jsou paměťově efektivnější.
6. Kdy byste zvolili propojený seznam před polem?
Při použití propojených seznamů místo polí zvažte:
- K náhodnému přístupu nepotřebujete žádné prvky.
- Tam, kde je nezbytná časová předvídatelnost, potřebujete neustálé vkládání a odebírání ze seznamu.
- Chcete-li vytvořit prioritní frontu, možná budete muset umístit položky do středu seznamu.
- Netušíte, jak dlouhý bude seznam. Pokud se velikost pole zvýší, musíte znovu deklarovat a duplikovat paměť, stejně jako u jednoduchých polí.
7. Co odlišuje indexované pole od asociativního pole?
Primární rozdíly mezi asociativními a indexovanými poli jsou uvedeny v následující tabulce.
- K řazení asociativního pole se používá pár klíč–hodnota v textovém nebo číselném formátu. Všechny klíče indexovaného pole jsou číselné a každý klíč je spojen s odlišnou hodnotou.
- V asociativním poli může být klíčem řetězec. Indexované pole s celočíselnými klíči začínajícími na 0.
- Dvousloupcová tabulka napodobuje chování asociativního pole. Podobně jako u jednosloupcové tabulky jsou indexovaná pole.
- Mapy jsou typu asociativního pole. Indexové pole není mapa.
8. Jaké výhody má Heap oproti tříděným polím?
Časová efektivita využití haldy přes tříděná pole je klíčovou výhodou. Zatímco operace haldy jsou rychlejší, řazení pole vyžaduje spoustu času. Hromada může objevit nejmenší prvek podstatně rychleji, než lze třídit pole.
Daná sbírka čísel může být uspořádána jedním ze dvou způsobů pomocí Sorted Arrays. Na druhou stranu pro danou kolekci čísel může existovat více než jedna potenciální hromada.
9. Můžeme definovat velikost pole jako zápornou?
Ne, nemůžeme definovat záporné celé číslo jako velikost pole. Pokud deklarujeme, nedojde k chybě při kompilaci. Za běhu se však setkáme s výjimkou NegativeArraySizeException.
10. Jak najdete chybějící celé číslo v poli o 1 až 100 prvcích?
Součet řady lze vypočítat použitím následující funkce: n (n + 1) / 2
Tato funkce bude fungovat pouze v případě, že pole nemá žádné duplikáty nebo v něm chybí více než jedno celé číslo. Ať už pole obsahuje duplicitní prvky, můžete pole seřadit a zjistit, zda existují nějaké ekvivalentní prvky.
11. Jak zjistíte index prvku v poli?
Index prvku lze zjistit pomocí lineárního nebo binárního vyhledávání. Dokud nenajde shodu požadovaného prvku, funkce lineárního vyhledávání prochází smyčkou nad každým prvkem v poli. Jakmile najde odpovídající prvek, vrátí index. V důsledku toho je časová složitost lineárního vyhledávání O. (n). Jak seřazené, tak nesetříděné pole může používat lineární vyhledávání.
Pomocí binárního vyhledávání, které neustále rozděluje pole na polovinu, dokud medián intervalu neodpovídá požadovanému prvku a poskytuje index, můžete získat index prvku, pokud je pole seřazeno. V důsledku toho je časová složitost binárního vyhledávání O. (log n).
12. Jak se můžete zbavit konkrétního prvku z pole?
Vzhledem k tomu, že nemůžete jednoduše odstranit prvky z původního pole, protože se jedná o pevné sady s definovanou velikostí, tazatel vás hledá, abyste navrhli jiný přístup a vypořádali se s problémem, který otázka vyvolává. Nejlepším postupem je vytvořit nové pole za účelem odstranění prvku. Můžete duplikovat prvky z prvního pole v tomto poli a zahrnout pouze prvek, který chcete odstranit.
Další strategie zahrnuje nalezení cílového prvku v poli a následné obrácení pořadí všech položek, které jsou napravo od cílového prvku.
13. Jak lze ověřit rovnost dvou polí?
Nejprve musíte ověřit délky dvou poskytnutých polí. Shodné položky obou polí se porovnávají, když jsou jejich délky stejné. Tato dvě pole budou považována za rovnocenná. pokud je každá dvojice složek v každé korespondenci stejná. Tento přístup se nedoporučuje kontrolovat rovnost dvou polí, pokud jsou pole velká, protože to zabere spoustu času. Můžete také použít metodu equals() obsaženou ve třídě Arrays, ale pokud vás tazatel požádá o porovnání dvou polí bez použití vestavěných metod, bude tento způsob užitečný.
14. Když mluvíme o polích, co myslíte frázemi „Dimension“ a „Subscript“?
„Dimenze“ pole je počet indexů nebo indexů potřebných k identifikaci každého jednotlivého člena. Dolní indexy a rozměry mohou být nejasné. Dimenze je popis rozsahu povolených klíčů, zatímco dolní index je číslo. Pro každou dimenzi pole je vyžadován pouze jeden dolní index.
Například pole arr[10][5] má dva rozměry. Velikost 10 na jedné a 5 na druhé. K adresování jeho součástí potřebujete dva indexy. Oba jsou mezi 0 a 4; jedna mezi 0 a 9 včetně.
Otázky k pohovoru o kódování
15. Najděte pár v poli, který má zadaný součet
Například,
Vstup:
- nums = [8, 7, 2, 5, 3, 1]
- cíl = 10
Výstup:
- Pár nalezen (8, 2)
- Or
- Pár nalezen (7, 3)
Vstup:
- nums = [5, 2, 6, 8, 1, 9]
- cíl = 12
Výstup:
- Pár nenalezen
16. Třídění binárních polí s lineárním časem
Seřaďte binární pole v lineárním čase a v pevné oblasti. Výstup by měl nejprve zobrazovat všechny nuly, poté všechny jedničky.
Například,
- Vstup: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Výstup: { 0, 0, 0, 0, 1, 1, 1, 1 }
Přímým přístupem by bylo vypočítat celkový počet nul v poli, řekněme k, a poté vyplnit prvních k indexů v poli nulami a zbývajících indexů 0. Alternativně bychom mohli vypočítat, kolik 0 je celkem v poli. pole k, vyplňte posledních k indexů v poli 1 a zbytek indexů nechte vyplněný 1.
Daný přístup má časovou složitost O(n) a nepoužívá žádné další úložiště, kde n je velikost vstupu.
17. Najděte největší dvouintový součin v poli.
Najděte největší součin dvou čísel v celočíselném poli.
Představte si pole 10 3 5 6 2 jako příklad. Dvojice (-10, -3) nebo (5, 6) je nejvyšší součin.
Přemýšlet o každé kombinaci prvků a vymýšlet jejich produkt je pošetilý přístup. Pokud je součin aktuálního páru větší než dosud získaný maximální součin, aktualizujte maximální součin. Jako poslední vytiskněte součásti konečného produktu.
Výše uvedené řešení, kde n je množství vstupu, má časovou složitost O(n2) a nezabírá více místa.
18. Jak posunout všechny nuly pole na konec
Přesuňte všechny nuly v celočíselném poli na konec. Odpověď by se měla vyhnout použití konstantního prostoru a zachovat relativní pořadí komponent pole.
Vstup: {1,2,3,0,8,0,4,7}
Výstup bude {1,2,3,8,4,7,0,0}
Umístěte prvek na následující dostupnou pozici v poli, pokud aktuální prvek není nula. Jakmile budou všechny položky pole zpracovány, vyplňte všechny zbývající indexy 0.
Předchozí řešení má časovou složitost O(n), kde n je velikost vstupu.
19. Jak seřadit pole se dvěma položkami, které se přepínají v jedné operaci.
Seřaďte pole v lineárním čase podle dvou prohozených položek a pole se všemi jeho prvky uspořádanými vzestupně. Předstírejte, že pole neobsahuje žádné duplikáty.
Vstup:= [1,9,3,4,7,2] nebo [9,3,7,2,1,4] nebo [2,4,1,7,3,9]
Výstup: = [1,2,3,4,7,9]
Počínaje druhým prvkem v poli je cílem porovnat každý prvek s jeho předchůdcem. Pozice sporu je uložena pomocí dvou ukazatelů, x a y.
Aktualizujte x na index předchozího prvku a y na index aktuálního prvku, pokud je první větší než druhý. Aktualizujte y na index aktuálního prvku, pokud se ukáže, že předchozí prvek je větší než aktuální prvek.
Nakonec přepněte prvky na indexech x a y, jakmile dokončíme zpracování každé sousední dvojice prvků.
Vzhledem k tomu, že výše uvedená metoda provádí pouze jeden sken vstupního pole velikosti n, je její časová složitost O(n). Pro řešení není potřeba žádný další prostor.
20. Jak spojit dvě setříděná pole na místě.
Sloučit položky polí X[] a Y[] – každé dvě seřazená pole o velikosti m a n – zachováním setříděného pořadí, tj. vyplněním X[] prvními m nejmenšími prvky a vyplněním Y[] zbývající prvky.
Pokud je prvek v poli X[] již na správné pozici (tj. ten, který je nejmenší ze zbývajících prvků), ignorujte jej; jinak jej nahraďte nejmenším prvkem, který je také náhodou prvním členem Y[]. Chcete-li zachovat seřazené pořadí po výměně, přeneste prvek (nyní na Y[0]) na správné místo v Y[].
Velikost prvního pole je m a velikost druhého pole je n a časová složitost je O(mn).
21. Jak změnit pořadí položek ve střídavě vysokých a nízkých pozicích?
Uspořádejte celočíselné pole tak, aby každý následující člen byl větší než předchozí a následující prvky. Předpokládejme, že pole neobsahuje žádné duplicitní prvky.
Třídění pole nebo využití dalšího prostoru není pro efektivní přístup nutné. Plán je, pro začátek, druhý člen pole a jít nahoru o dva pro každou iteraci smyčky.
Vyměňte součásti, pokud poslední prvek přesahuje první. V podobném duchu přepněte obě položky, pokud je následující prvek větší než aktuální prvek. Na konci cyklu získáme požadované pole, které vyhovuje zadaným omezením.
22. Jak nahradit každý prvek pole bez použití operátoru dělení součinem každého prvku v poli?
Bez použití operátoru dělení nahraďte každý prvek v poli celých čísel součinem všech ostatních prvků.
V lineárním čase a konstantním prostoru můžeme k řešení tohoto problému využít rekurzi. Podstatou je rekurzivní výpočet součinů každého prvku v pravém dílčím poli a předání součinu levého dílčího pole jako funkční parametry.
Časová složitost je O(n).
23. Najděte nejpodivnější prvek v poli v logaritmickém čase
Vzhledem k celočíselnému poli, ve kterém mají všechny členy kromě jednoho sudý počet výskytů, je problém určit, kolikrát se tento jeden prvek objeví. Najděte lichý prvek v logaritmickém čase a konstantním prostoru, pokud se stejné prvky vyskytují v párech v poli a nikdy nemohou být více než dva výskyty daného prvku v řadě.
Operace XOR nám umožňuje vyřešit tento problém v lineárním čase. Cílem je XOR každý prvek v poli. Poté, co se sudé prvky navzájem vyruší, zůstanou pouze liché se vyskytující prvky.
Tento problém lze dokonce vyřešit v čase O(log(n)).
24. Jak získat následný větší prvek pro každý prvek v kruhovém poli?
Měl by být umístěn další větší prvek pro každý prvek v kruhovém celočíselném poli. První větší celé číslo po prvku x v poli je následný větší prvek tohoto prvku.
Zprava doleva můžeme pracovat s položkami pole. Cílem je opakovat každý prvek x, dokud není zásobník prázdný, nebo nad ním nemáme vyšší prvek. Nastavte další větší prvek x, aby se objevil na vrcholu zásobníku, když se tak stane.
25. Najděte počet inverzí pole?
Najděte celkový počet inverzí pole. Dvojice Ij) se označuje jako inverze pole A, pokud Ij) a (A[i] > A[j]). Musíme spočítat každý pár těchto v poli.
Počítání všech členů pole, kterých je méně než vpravo od něj, a přidání výsledku k výstupu je přímočarý přístup.
Toto řešení má složitost O(n2), kde n je velikost vstupu.
26. Jaký je problém zachycování dešťové vody?
Nalezení největšího množství vody, které může být zachyceno v dané sadě tyčí o šířce jedné jednotky, je známé jako problém „zachycování dešťových srážek“.
Cílem je určit nejvyšší pruh, který může být umístěn vlevo a vpravo od každého pruhu. Minimum vodicích pruhů vlevo a vpravo, mínus výška aktuálního pruhu, je množství vody, které je uloženo na vrcholu každého pruhu.
Proč investovat do čističky vzduchu?
Ve srovnání s jinými tématy datových struktur jsou pole jednodušší. Abyste mohli odpovědět na otázky na pohovorech s polem, musíte mít základní znalosti polí.
Měli byste si důkladně prostudovat základy polí, včetně operací s poli (od deklarace/vytvoření pole po přístup/úpravu položek pole), stejně jako programovací koncepty, jako jsou smyčky, rekurze a základní operátory, abyste mohli úspěšně odpovědět na otázky pohovoru s poli. Zcela rozpoznat problém.
Pokud máte nějaké dotazy, měli byste požádat o vysvětlení. Přemýšlejte o rozdělení problému na lépe zvládnutelné části. Než začnete programovat, ujistěte se, že máte algoritmus na paměti; zapište si to nebo si to vizualizujte ve vývojovém diagramu. pak začněte psát kód.
Napsat komentář