Tartalomjegyzék[Elrejt][Előadás]
- 1. Hogyan definiálunk egy tömböt?
- 2. Dinamikus tömbök: Mik ezek? Mi különbözteti meg őket az alapvető tömböktől?
- 3. Hogyan különbözik egymástól egy tömb és egy szótár?
- 4. Sorolja fel a tömbök előnyeit és hátrányait!
- 5. Mire utal a „Sparse Array”?
- 6. Mikor választana linkelt listát egy tömb helyett?
- 7. Mi különbözteti meg az indexelt tömböt az asszociatív tömbtől?
- 8. Milyen előnyei vannak a Heap-nek a rendezett tömbökhöz képest?
- 9. Meghatározhatjuk-e a tömb méretét negatívnak?
- 10. Hogyan lehet megtalálni a hiányzó egész számot egy 1-100 elemű tömbben?
- 11. Hogyan találja meg egy elem indexét egy tömbben?
- 12. Hogyan lehet megszabadulni egy adott elemtől egy tömbből?
- 13. Hogyan ellenőrizhető két tömb egyenlősége?
- 14. Amikor a tömbökről beszélünk, mit értesz a „Dimenzió” és „Aláindex” kifejezéseken?
- Kódolási interjúkérdések
- 15. Keressen egy párt egy tömbben, amely a megadott összeggel rendelkezik
- 16. Bináris tömb rendezés lineáris idővel
- 17. Keresse meg egy tömbben a legnagyobb két int szorzatot!
- 18. Hogyan tolható el a tömb összes nullája a végére
- 19. Hogyan rendezzünk egy tömböt két bejegyzéssel, amelyeket egy művelettel váltanak.
- 20. Hogyan kombináljunk két rendezett tömböt a helyükön.
- 21. Hogyan lehet átrendezni a tételek tömbjét váltakozó magas és alacsony pozíciókban?
- 22. Hogyan lehet egy tömb minden elemét osztásoperátor használata nélkül helyettesíteni a tömb minden elemének szorzatával?
- 23. Keresse meg egy tömb legpáratlanabb elemét logaritmikus időben!
- 24. Hogyan kapjuk meg a következő nagyobb elemet egy körtömb minden eleméhez?
- 25. Keresse meg egy tömb inverziószámát?
- 26. Mi az esővíz megkötési probléma?
- Következtetés
A kódoló interjúk DSA-kérdések sorozatát tartalmazzák. A tömbök kezelésében jártasnak kell lennie, ha a közelgő műszaki interjúra készül a FAANG-gal vagy egy másik Tier-1 technológiai vállalkozással.
A legtöbb kódoló interjúban a második helyen áll a Strings után. A tömb összetartozó adatelemek csoportja, amelyek egymás közelében vannak a memóriában.
Mivel minden programozási nyelvhez csatlakoznak, mint például a C, C++, Java, Python, Perl és Ruby, mindenhol megtalálhatók. Olvasson tovább néhány gyakorlati kódolási kihívásért, valamint interjúkérdésekért és válaszokért tömbök alapján.
Ebben a bejegyzésben a Python-t fogjuk használni a kódolási problémák megoldására, mivel egyszerűen használható, érthető, és a legtöbbünk számára ismerősnek kell lennie.
Kezdjük.
1. Hogyan definiálunk egy tömböt?
- A kapcsolódó adattípusok egy csoportja egy tömb.
- A tömbök mindig rögzítettek.
- Ugyanazt a változót több helyen tárolják a tömbobjektumok.
- A primitív típusok és az objektumhivatkozások egyaránt kompatibilisek vele.
2. Dinamikus tömbök: Mik ezek? Mi különbözteti meg őket az alapvető tömböktől?
A dinamikus tömbök (Java nyelven bővíthető tömböknek, átméretezhető tömböknek, módosítható tömböknek vagy ArrayLists-eknek is nevezik) által biztosított automatikus méretezés jelentős előnyt jelent.
Mindig tudnia kell, hogy a tömb hány elemet fog tárolni előre, mivel a tömbök fix méretűek. Egy dinamikus tömb viszont növekszik, ha további tagokat ad hozzá, így nem kell előre tudni a pontos méretét.
3. Hogyan különbözik egymástól egy tömb és egy szótár?
Ez a rendszeresen feltett interjúkérdések alapismereteken alapuló tömbje. A tömbök és szótárak közötti fő különbségek a következők:
- A tömb hasonló elemek rendezett listája. A szótárnak viszont vannak kulcs-érték párjai.
- A tömb mérete dinamikusan változhat. Ilyen dinamikus ötletek nem léteznek a szótárakban.
- Egy tömb használata előtt meg kell adni a méretét. A szótár méretét nem kell testre szabni.
- Használja a Redim utasítást, ha bővíteni szeretné a tömb méretét. A szótárakban egy elem deklaráció nélkül is hozzáadható.
4. Sorolja fel a tömbök előnyeit és hátrányait!
Előnyök:
- A tömbök egyszerre több elemet is rendezhetnek.
- Más adatszerkezetek, mint például veremek, sorok, csatolt listák, fák, grafikonok stb., megvalósíthatók tömbben.
- Egy index használható egy tömb elemének eléréséhez.
Hátrányok:
- A tömb méretét előre meg kell adni. A tömbdeklaráció pillanatában azonban előfordulhat, hogy nem vagyunk tisztában a szükséges mérettel.
- A tömb szerkezete statikus. Ez azt jelenti, hogy a tömb mérete mindig rögzített, és a memóriafoglalás nem növelhető vagy csökkenthető.
5. Mire utal a „Sparse Array”?
A ritka tömb olyan adattömb, amely sok nulla értékű bejegyzést tartalmaz. Ezzel szemben egy sűrű tömb elemeinek többségét nem nulla értékekkel tartalmazza. A számokat objektummá konvertáló ritka tömb indexei hézagokat tartalmazhatnak. A HashMap-hez képest memóriahatékonyabbak.
6. Mikor választana linkelt listát egy tömb helyett?
Ha linkelt listákat használ tömbök helyett, vegye figyelembe:
- Nincs szükség semmilyen elemre a véletlenszerű hozzáféréshez.
- Ahol az időbeli kiszámíthatóság elengedhetetlen, állandó idejű beszúrásokra és eltávolításokra van szükség a listából.
- Előfordulhat, hogy prioritási sor létrehozásához elemeket kell elhelyeznie a lista közepén.
- Fogalmad sincs, milyen hosszú lesz a lista. Ha a tömb mérete növekszik, akkor újra deklarálnia és megkettőznie kell a memóriát, mint az egyszerű tömböknél.
7. Mi különbözteti meg az indexelt tömböt az asszociatív tömbtől?
Az asszociatív és indexelt tömbök közötti elsődleges különbségeket a következő táblázat sorolja fel.
- A szöveges vagy numerikus formátumú kulcs-érték pár az asszociatív tömb rendezésére szolgál. Az indexelt tömb kulcsai mind numerikusak, és mindegyik kulcs külön értékhez kapcsolódik.
- Egy asszociatív tömbben a kulcs egy karakterlánc lehet. Indexelt tömb 0-tól kezdődő egész kulcsokkal.
- A kétoszlopos táblázat egy asszociatív tömb viselkedését utánozza. Az egyoszlopos táblákhoz hasonlóan az indexelt tömbök is.
- A térképek asszociatív tömbtípusok. Az indextömb nem térkép.
8. Milyen előnyei vannak a Heap-nek a rendezett tömbökhöz képest?
A Heap over Sorted Arrays használatának időhatékonysága a legfontosabb előny. Míg a kupac műveletek gyorsabbak, egy tömb rendezése sok időt vesz igénybe. Egy kupac sokkal gyorsabban képes felfedezni a legkisebb elemet, mint egy tömb rendezni.
Egy adott számgyűjtemény a rendezett tömbök segítségével kétféleképpen rendezhető el. Másrészt egy adott számgyűjteményhez több potenciális kupac is lehet.
9. Meghatározhatjuk-e a tömb méretét negatívnak?
Nem, nem definiálhatunk negatív egész számot egy tömb méretének. Nem lesz fordítási hiba, ha kijelentjük. Futás közben azonban találkozni fogunk egy NegativeArraySizeException-vel.
10. Hogyan lehet megtalálni a hiányzó egész számot egy 1-100 elemű tömbben?
A sorozatok összege a következő függvény alkalmazásával számítható ki: n (n + 1) / 2
Ez a függvény csak akkor működik, ha a tömbnek nincsenek ismétlődései, vagy egynél több egész szám hiányzik. Függetlenül attól, hogy egy tömbben vannak-e ismétlődő elemek, rendezheti a tömböt, hogy megnézze, vannak-e egyenértékű elemek.
11. Hogyan találja meg egy elem indexét egy tömbben?
Egy elem indexe lineáris vagy bináris kereséssel fedezhető fel. Amíg meg nem találja a kívánt elem egyezését, egy lineáris keresőfüggvény a tömb minden egyes eleme felett köröz. Visszaadja az indexet, miután megtalálta a megfelelő elemet. Következésképpen a lineáris keresés időbeli összetettsége O. (n). A rendezett és a rendezetlen tömb is használhat lineáris keresést.
Egy bináris kereséssel, amely folyamatosan felosztja a tömböt, amíg az intervallum mediánja meg nem egyezik a kívánt elemmel, és megadja az indexet, megkaphatja az elem indexét, ha a tömb rendezve van. Következésképpen a bináris keresés időbeli összetettsége O. (log n).
12. Hogyan lehet megszabadulni egy adott elemtől egy tömbből?
Mivel az elemeket nem lehet egyszerűen törölni az eredeti tömbből, mivel ezek meghatározott méretű rögzített halmazok, a kérdező arra kér, hogy javasoljon egy másik megközelítést, és kezelje a kérdés által felvetett problémát. A legjobb megoldás egy új tömb létrehozása egy elem törléséhez. Az első tömb elemeit megkettőzheti ebben a tömbben, és csak a törölni kívánt elemet tartalmazza.
Egy másik stratégia magában foglalja a célelem megtalálását a tömbben, majd megfordítja a célelemtől jobbra lévő elemek sorrendjét.
13. Hogyan ellenőrizhető két tömb egyenlősége?
Először ellenőriznie kell a két megadott tömb hosszát. Mindkét tömb egyező elemeit összehasonlítjuk, ha a hosszúságuk egyenlő. A két tömb egyenlőnek minősül. ha minden megfeleltetésben minden komponenspár egyenlő. Ezzel a megközelítéssel nem tanácsos ellenőrizni két tömb egyenlőségét, ha a tömbök nagy méretűek, mivel ez sok időt vesz igénybe. Használhatja az Arrays osztályban található equals() metódust is, de ha a kérdező két tömb összehasonlítását kéri a beépített metódusok használata nélkül, akkor ez hasznos lesz.
14. Amikor a tömbökről beszélünk, mit értesz a „Dimenzió” és „Aláindex” kifejezéseken?
Egy tömb „dimenziója” az egyes tagok azonosításához szükséges indexek vagy alsó indexek száma. Előfordulhat, hogy az alsó indexek és a méretek nem egyértelműek. A dimenzió az engedélyezett kulcsok tartományának leírása, míg az alsó index egy szám. Minden tömbdimenzióhoz csak egy alsó index szükséges.
Például az arr[10][5] tömbnek két dimenziója van. Az egyiken 10-es, a másikon 5-ös méret. Összetevőinek kezeléséhez két alsó indexre van szükség. Mindkettő 0 és 4 között van; egy 0 és 9 között, beleértve.
Kódolási interjúkérdések
15. Keressen egy párt egy tömbben, amely a megadott összeggel rendelkezik
Például,
Bemenet:
- számok = [8, 7, 2, 5, 3, 1]
- cél = 10
output:
- Pár található (8, 2)
- Or
- Pár található (7, 3)
Bemenet:
- számok = [5, 2, 6, 8, 1, 9]
- cél = 12
output:
- A pár nem található
16. Bináris tömb rendezés lineáris idővel
Bináris tömb rendezése lineáris időben és rögzített területen. A kimenetnek először az összes nullát, majd az egyeseket kell megjelenítenie.
Például,
- Bemenet: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Kimenet: { 0, 0, 0, 0, 1, 1, 1, 1 }
Egy egyszerű megközelítés az lenne, ha kiszámítjuk a tömb 0-inak teljes számát, mondjuk k-t, majd a tömb első k indexét 0-val, a többi indexet pedig 1-gyel kitöltjük. Alternatív megoldásként kiszámíthatjuk, hogy hány 1-es van összesen k tömb, töltse ki a tömb utolsó k indexét 1-gyel, a többi indexet pedig hagyja kitöltve 0-val.
Az adott megközelítés O(n) idejű bonyolultságú, és nem használ további tárhelyet, ahol n a bemenet mérete.
17. Keresse meg egy tömbben a legnagyobb két int szorzatot!
Keresse meg két szám legnagyobb szorzatát egy egész tömbben.
Példaként gondoljon a 10 3 5 6 2 tömbre. A (-10, -3) vagy (5, 6) pár a legmagasabb szorzat.
Minden elemkombinációt végiggondolni és a terméküket kitalálni ostoba megközelítés. Ha az aktuális pár szorzata nagyobb, mint az eddig elért maximális szorzat, frissítse a maximális szorzatot. Utoljára nyomtassa ki a végtermék összetevőit.
A fenti megoldás, ahol n a bemenet mennyisége, O(n2) időbonyolultságú, és nem foglal több helyet.
18. Hogyan tolható el a tömb összes nullája a végére
Mozgassa az összes nullát egy egész tömbben a végére. A válasz kerülje az állandó szóköz használatát, és őrizze meg a tömb összetevőinek relatív sorrendjét.
Bevitel: {1,2,3,0,8,0,4,7}
A kimenet a következő lesz: 1,2,3,8,4,7,0,0}
Ha az aktuális elem nem nulla, helyezze az elemet a következő elérhető helyre a tömbben. Töltse ki az összes fennmaradó indexet 0-val, miután a tömb elemeit feldolgozta.
Az előző megoldás O(n) időbonyolultságú, ahol n a bemenet mérete.
19. Hogyan rendezzünk egy tömböt két bejegyzéssel, amelyeket egy művelettel váltanak.
Rendezzen egy tömböt a lineáris időben két felcserélt elem alapján, és egy tömböt, amelynek minden eleme növekvő sorrendben van elrendezve. Tegyük fel, hogy a tömb nem tartalmaz ismétlődéseket.
Bemenet:= [1,9,3,4,7,2] vagy [9,3,7,2,1,4] vagy [2,4,1,7,3,9]
Kimenet: = [1,2,3,4,7,9]
A tömb második elemétől kezdve a cél az, hogy minden elemet összehasonlítsunk elődjével. A vita helyzetét két mutató, x és y felvételével tároljuk.
Frissítse x-et az előző elem indexére, és y-t az aktuális elem indexére, ha az előbbi nagyobb, mint az utóbbi. Frissítse az y-t az aktuális elem indexére, ha kiderül, hogy az előző elem nagyobb, mint az aktuális elem.
Végül váltsa fel az x és y indexű elemeket, miután befejeztük az egyes szomszédos elempárok feldolgozását.
Tekintettel arra, hogy a fent említett módszer csak egyszeri pásztázást hajt végre az n méretű bemeneti tömbön, az időbonyolultsága O(n). A megoldáshoz nincs szükség további helyiségre.
20. Hogyan kombináljunk két rendezett tömböt a helyükön.
Egyesítse az X[] és Y[] tömb elemeit – két-két rendezett, m és n méretű tömböt – úgy, hogy megtartja a rendezett sorrendet, azaz töltse ki X[] elemet az első m legkisebb elemmel és Y[] elemet fennmaradó elemek.
Ha az X[] tömb egy eleme már a megfelelő pozícióban van (azaz azon, amelyik a legkisebb a fennmaradó elemek közül), hagyja figyelmen kívül; ellenkező esetben cserélje ki a legkisebb elemre, amely történetesen az Y[] első tagja. A rendezett sorrend cseréje utáni megőrzéséhez helyezze át az elemet (jelenleg Y[0]-ban) a megfelelő helyre az Y[]-ben.
Az első tömb mérete m, a másodiké n, az időbonyolultság pedig O(mn).
21. Hogyan lehet átrendezni a tételek tömbjét váltakozó magas és alacsony pozíciókban?
Rendezzünk át egy egész tömböt úgy, hogy minden következő tag nagyobb legyen, mint az előző és a következő elemek. Tegyük fel, hogy a tömb nem tartalmaz ismétlődő elemeket.
A hatékony megközelítéshez nem szükséges a tömb rendezése vagy további hely kihasználása. A terv először is a tömb második tagja, és minden ciklusiterációnál kettővel feljebb kerül.
Cserélje ki az összetevőket, ha az utolsó elem meghaladja az elsőt. Hasonló módon váltson mindkét elemet, ha a következő elem nagyobb, mint az aktuális elem. A ciklus végén megkapjuk a kívánt tömböt, amely megfelel a megadott korlátozásoknak.
22. Hogyan lehet egy tömb minden elemét osztásoperátor használata nélkül helyettesíteni a tömb minden elemének szorzatával?
Az osztás operátor használata nélkül cserélje ki az egész tömb minden elemét az összes többi elem szorzatára.
Lineáris időben és állandó térben a rekurziót használhatjuk a probléma megoldására. A jobb oldali altömb egyes elemeinek szorzatának rekurzív kiszámítása és a bal oldali alrendszer szorzatának függvényparaméterekként való átadása az elképzelés.
Az időbonyolultság O(n).
23. Keresse meg egy tömb legpáratlanabb elemét logaritmikus időben!
Adott egy egész tömb, amelyben egy kivételével minden tagnak páros számú előfordulása van, a probléma annak meghatározása, hogy ez az egy elem hányszor jelenik meg. Keresse meg a páratlan előforduló elemet logaritmikus időben és állandó térben, ha ugyanazok az elemek párban fordulnak elő a tömbben, és egy adott elemnek soha nem lehet kettőnél több példánya egy sorban.
Az XOR művelet lehetővé teszi, hogy ezt a problémát lineáris időben megoldjuk. A cél a tömb minden elemének XOR-ja. Csak a páratlan előforduló elemek maradnak meg, miután a páros előforduló elemek kioltják egymást.
Ez a probléma akár O(log(n)) idő alatt is megoldható.
24. Hogyan kapjuk meg a következő nagyobb elemet egy körtömb minden eleméhez?
A kör alakú egész tömb minden eleméhez a következő nagyobb elemet kell elhelyezni. A tömbben egy x elem utáni első nagyobb egész szám az adott elem következő nagyobb eleme.
Jobbról balra tömbelemekkel dolgozhatunk. A cél az, hogy minden x elemre hurkoljunk addig, amíg vagy a verem ki nem ürül, vagy egy magasabb elem lesz a tetején. Állítsa be az x következő nagyobb elemét, hogy megjelenjen a verem tetején, amikor megjelenik.
25. Keresse meg egy tömb inverziószámát?
Határozza meg egy tömb inverzióinak teljes számát. Az I j) pár az A tömb inverziója, ha I j) és (A[i] > A[j]). Ezeknek minden párját meg kell számolnunk a tömbben.
Az összes tömbtag megszámlálása, amelyik kisebb, mint a tőle jobbra lévő tömb, és az eredményt hozzáadni a kimenethez, egyszerű megközelítés.
Ennek a megoldásnak O(n2) komplexitása van, ahol n a bemenet mérete.
26. Mi az esővíz megkötési probléma?
Az egy egység szélességű rúdkészletben megfogható legtöbb víz megtalálása a „csapadék befogása” probléma.
A cél az, hogy meghatározzuk a legmagasabb sávot, amely az egyes sávok bal és jobb oldalán helyezhető el. A bal és jobb oldali bevezető rudak minimuma, az aktuális sáv magasságával csökkentve az egyes rudak tetején tárolt víz mennyisége.
Következtetés
A többi adatszerkezeti témakörhöz képest a tömbök egyszerűbbek. Az ász tömb interjúkérdéseinek megválaszolásához alapvető ismeretekkel kell rendelkeznie a tömbökről.
Alaposan át kell tekintenie a tömbök alapjait, beleértve a tömbműveleteket (a tömb deklarálásától/létrehozásától a tömbelemek eléréséig/módosításáig), valamint olyan programozási fogalmakat, mint a hurkok, a rekurzió és az alapvető operátorok, hogy sikeresen válaszolhasson a tömbinterjú kérdéseire. Ismerje fel teljesen a problémát.
Ha bármilyen kérdése van, kérjen felvilágosítást. Gondoljon arra, hogy a problémát jobban kezelhető részekre ossza fel. Mielőtt elkezdené a programozást, győződjön meg arról, hogy az algoritmust szem előtt tartja; írja le vagy jelenítse meg egy folyamatábrában. majd kezdje el írni a kódot.
Hagy egy Válaszol