Table of Contents[Kache][Montre]
- 1. Ki jan ou defini yon etalaj?
- 2. ranje dinamik: ki sa yo ye? Ki sa ki fè yo apa de Array debaz yo?
- 3. Ki jan yon etalaj ak yon diksyonè diferan youn ak lòt?
- 4. Lis kèk nan benefis ak dezavantaj etalaj yo.
- 5. Ki sa "Sparse Array" refere a?
- 6. Kilè ou ta chwazi yon lis lye sou yon etalaj?
- 7. Ki sa ki fè distenksyon ant yon etalaj endis ak yon etalaj asosyativ?
- 8. Ki avantaj Heap genyen sou etalaj ki klase?
- 9. Èske nou ka defini gwosè a nan etalaj la yo dwe negatif?
- 10. Ki jan ou jwenn nonb antye ki manke a nan yon etalaj 1 a 100 eleman?
- 11. Ki jan ou jwenn endèks yon eleman nan yon etalaj?
- 12. Ki jan ou ka debarase m de yon eleman espesifik nan yon etalaj?
- 13. Ki jan yo ka verifye egalite de etalaj?
- 14. Lè nou diskite sou etalaj, kisa ou vle di ak fraz "Dimansyon" ak "Subscript"?
- Kesyon Entèvyou Kodaj
- 15. Chèche yon pè nan yon etalaj ki gen sòm espesifye a
- 16. Triyay etalaj binè ak tan lineyè
- 17. Jwenn pi gwo pwodwi de-int nan yon etalaj.
- 18. Ki jan yo chanje tout zewo etalaj la nan fen an
- 19. Ki jan yo sòt yon etalaj ak de antre ki chanje nan yon operasyon.
- 20. Ki jan yo konbine de etalaj Ranje an plas.
- 21. Ki jan yo rekòmande yon etalaj de atik nan altène pozisyon wo ak ba?
- 22. Ki jan yo ranplase chak eleman nan yon etalaj san yo pa itilize yon operatè divizyon ak pwodwi a nan chak eleman nan etalaj la?
- 23. Jwenn eleman ki pi etranj nan yon etalaj nan tan logaritmik
- 24. Ki jan yo jwenn eleman ki vin apre a pi gwo pou chak eleman nan yon etalaj sikilè?
- 25. Jwenn konte envèsyon yon etalaj?
- 26. Ki Pwoblèm Pyèj Dlo Lapli a?
- konklizyon
Entèvyou kodaj yo genyen yon seri kesyon DSA. Ou ta dwe gen konpetans ak etalaj si w ap prepare pou entèvyou teknoloji k ap vini ak FAANG oswa yon lòt biznis teknoloji Tier-1.
Nan pifò entèvyou kodaj, li vini an dezyèm plas nan Strings. Yon etalaj se yon gwoupman nan eleman done ki gen rapò kenbe nan pwoksimite youn ak lòt nan memwa.
Kòm yo konekte ak tout langaj pwogramasyon, tankou C, C++, Java, Python, Perl, ak Ruby, yo toupatou. Kontinye lekti pou kèk pratik kodaj defi ak kesyon entèvyou ak repons ki baze sou etalaj.
Python pral itilize nan pòs sa a pou atake pwoblèm kodaj yo paske li senp pou itilize, konprann, epi li dwe abitye ak pifò nan nou.
Ann kòmanse.
1. Ki jan ou defini yon etalaj?
- Yon gwoup kalite done ki gen rapò se yon etalaj.
- Etalaj yo toujou fiks.
- Se menm kalite varyab ki estoke nan plizyè kote pa objè etalaj.
- Kalite primitif ak referans objè yo tou de konpatib ak li.
2. ranje dinamik: ki sa yo ye? Ki sa ki fè yo apa de Array debaz yo?
Echèl otomatik ke etalaj dinamik (ki refere tou kòm etalaj ki kapab grandi, etalaj redimensionnable, etalaj ki chanje, oswa ArrayLists nan Java) bay se yon avantaj enpòtan.
Ou dwe toujou konnen konbyen eleman etalaj ou a pral estoke davans depi etalaj yo gen yon gwosè fiks. Yon etalaj dinamik, nan lòt men an, ap grandi pandan w ap ajoute manm adisyonèl nan li, kidonk, ou pa bezwen konnen gwosè egzak li davans.
3. Ki jan yon etalaj ak yon diksyonè diferan youn ak lòt?
Sa a se yon seri kesyon entèvyou ki baze sou fondamantal yo ke yo poze regilyèman. Sa ki annapre yo se distenksyon kle ant etalaj ak diksyonè:
- Yon etalaj se yon lis òdone atik ki sanble. Diksyonè, nan lòt men an, gen pè kle-valè.
- Gwosè etalaj ka chanje dinamik. Lide dinamik sa yo pa egziste nan diksyonè.
- Anvan w itilize yon etalaj, yo dwe espesifye gwosè li. Gwosè diksyonè pa bezwen Customized.
- Sèvi ak deklarasyon Redim la si ou vle elaji gwosè etalaj la. Nan diksyonè, yo ka ajoute yon eleman san yon deklarasyon.
4. Lis kèk nan benefis ak dezavantaj etalaj yo.
Avantaj:
- Etalaj ka sòt yon kantite eleman ansanm.
- Lòt bagay estrikti done, tankou pil, ke moun kap kriye, lis lye, pye bwa, graf, elatriye, ka aplike nan yon etalaj.
- Yon endèks ka itilize pou rive nan yon eleman nan yon etalaj.
Dezavantaj:
- Gwosè yon etalaj dwe deklare davans. Nan moman deklarasyon etalaj la, nou ta ka pa, sepandan, dwe okouran de gwosè nou bezwen an.
- Estrikti etalaj la se estatik. Li implique ke gwosè etalaj toujou fiks epi ke alokasyon memwa pa ka ogmante oswa diminye.
5. Ki sa "Sparse Array" refere a?
Yon etalaj sparse se yon etalaj done ki gen yon anpil nan antre ak valè zewo. Nan kontras, yon etalaj dans gen majorite nan atik li yo ak valè ki pa zewo. Endis yo nan yon etalaj rar, ki konvèti nimewo nan objè, ka gen ladan twou vid ki genyen. Konpare ak yon HashMap, yo gen plis memwa efikas.
6. Kilè ou ta chwazi yon lis lye sou yon etalaj?
Lè w ap itilize lis ki lye olye de etalaj, konsidere:
- Ou pa bezwen okenn eleman pou gen aksè o aza.
- Kote previzibilite tanporèl esansyèl, ou bezwen ensèsyon ak retire yon tan konstan nan lis la.
- Yo nan lòd yo kreye yon keu priyorite, ou ta ka bezwen mete atik nan sant la nan lis la.
- Ou pa gen okenn lide konbyen tan lis la pral. Si gwosè etalaj la ogmante, ou dwe re-deklare epi kopi memwa, menm jan ak etalaj senp.
7. Ki sa ki fè distenksyon ant yon etalaj endis ak yon etalaj asosyativ?
Yo bay distenksyon prensipal ant etalaj asosyatif ak endis yo nan tablo ki anba la a.
- Yo itilize yon pè kle-valè nan fòma tèks oswa nimerik pou klase yon etalaj asosyativ. Kle etalaj endis la yo tout nimerik, epi chak kle konekte ak yon valè diferan.
- Nan yon etalaj asosyasyon, kle a ta ka yon fisèl. Etalaj endèks ak kle nonb antye ki kòmanse nan 0.
- Yon tablo de kolòn imite konpòtman yon etalaj asosyativ. Menm jan ak yon tab yon sèl kolòn yo endis ranje.
- Kat yo se yon kalite etalaj asosyasyon. Yon etalaj endèks se pa yon kat.
8. Ki avantaj Heap genyen sou etalaj ki klase?
Efikasite tan nan itilize Heap over Sorted Arrays se benefis prensipal la. Pandan ke operasyon pil yo pi rapid, klasman yon etalaj mande anpil tan. Yon pil ka dekouvri eleman ki pi piti a konsiderableman pi vit pase yon etalaj ka klase.
Yon koleksyon nimewo yo ka ranje nan youn nan de fason lè l sèvi avèk Sorted Arrays. Nan lòt men an, pou yon koleksyon nimewo yo bay, ka gen plis pase yon pil potansyèl.
9. Èske nou ka defini gwosè a nan etalaj la yo dwe negatif?
Non, nou pa ka defini yon nonb antye relatif negatif yo dwe gwosè a nan yon etalaj. Pa pral gen yon erè konpile-tan si nou deklare. Nan ègzekutabl, nou pral, sepandan, rankontre yon NegativeArraySizeException.
10. Ki jan ou jwenn nonb antye ki manke a nan yon etalaj 1 a 100 eleman?
Yo ka kalkile total seri a lè w aplike fonksyon sa a: n (n + 1) / 2
Sèlman si etalaj la pa gen okenn kopi oswa gen plis pase yon nonb antye ki manke fonksyon sa a ap fonksyone. Kit yon etalaj gen eleman kopi, ou ka klase etalaj la pou wè si gen nenpòt eleman ki ekivalan.
11. Ki jan ou jwenn endèks yon eleman nan yon etalaj?
Endèks yon eleman ka dekouvri atravè yon rechèch lineyè oswa binè. Jiskaske li lokalize matche ak eleman obligatwa a, yon fonksyon rechèch lineyè bouk sou chak eleman nan yon etalaj. Li retounen endèks la yon fwa li lokalize eleman matche a. An konsekans, konpleksite tanporèl rechèch lineyè a se O. (n). Tou de yon etalaj ki klase ak yon etalaj ki pa klase ka itilize rechèch lineyè.
Sèvi ak yon rechèch binè, ki toujou divize etalaj la an mwatye jiskaske medyàn entèval la matche ak eleman obligatwa a epi li bay endèks la, ou ka jwenn endèks eleman an si etalaj la klase. An konsekans, konpleksite tanporèl rechèch binè a se O. (log n).
12. Ki jan ou ka debarase m de yon eleman espesifik nan yon etalaj?
Depi ou pa ka senpleman efase eleman nan etalaj orijinal la depi yo fikse ansanm ak yon gwosè defini, entèvyou a ap chèche pou ou sijere yon apwòch diferan epi fè fas ak pwoblèm nan ke kesyon an soulve. Kou a pi bon nan aksyon se fè yon nouvo etalaj yo nan lòd yo efase yon eleman. Ou ka kopi eleman ki soti nan premye etalaj la nan etalaj sa a epi sèlman enkli eleman ou vle efase a.
Yon lòt estrateji enplike jwenn eleman sib la nan etalaj la ak Lè sa a, ranvèse lòd la nan tout atik yo ki sou bò dwat la nan eleman sib la.
13. Ki jan yo ka verifye egalite de etalaj?
Ou dwe premye verifye longè de etalaj yo bay yo. Atik ki matche tou de etalaj yo konpare lè longè yo egal. De etalaj yo pral konsidere kòm egal. si chak pè konpozan nan chak korespondans egal. Apwòch sa a pa konseye pou tcheke egalite de etalaj si etalaj yo gwo nan gwosè paske li pral pran anpil tan. Ou ka itilize tou metòd equals() ki enkli nan klas Arrays la, sepandan, si entèvyou a mande w konpare de etalaj san w pa itilize metòd entegre, fason sa a ap itil.
14. Lè nou diskite sou etalaj, kisa ou vle di ak fraz "Dimansyon" ak "Subscript"?
"Dimansyon" yon etalaj se kantite endis, oswa enskripsyon, ki nesesè pou idantifye chak manm endividyèl elèv yo. Enskripsyon ak dimansyon yo ta ka pa klè. Yon dimansyon se yon deskripsyon seri kle ki pèmèt yo, tandiske yon enskri se yon nimewo. Gen yon sèl abònman obligatwa pou chak dimansyon etalaj.
Pa egzanp, etalaj arr[10][5] gen de dimansyon. Gwosè 10 sou youn ak 5 sou lòt la. Pou adrese konpozan li yo, ou bezwen de enskripsyon. Tou de se ant 0 ak 4; youn ant 0 ak 9, enklizif.
Kesyon Entèvyou Kodaj
15. Chèche yon pè nan yon etalaj ki gen sòm espesifye a
Pou egzanp,
Antre:
- chif = [8, 7, 2, 5, 3, 1]
- sib = 10
Sòti:
- Pè yo te jwenn (8, 2)
- Or
- Pè yo te jwenn (7, 3)
Antre:
- chif = [5, 2, 6, 8, 1, 9]
- sib = 12
Sòti:
- Pè pa jwenn
16. Triyay etalaj binè ak tan lineyè
Triye yon etalaj binè nan tan lineyè ak nan yon zòn fiks. Pwodiksyon an ta dwe montre tout zewo an premye, Lè sa a, tout sa yo.
Pou egzanp,
- Antre: {1, 0, 1, 0, 1, 0, 0, 1}
- Sòti: {0, 0, 0, 0, 1, 1, 1, 1}
Yon apwòch senp ta dwe kalkile kantite total etalaj la nan 0, di k, ak Lè sa a, ranpli premye k endis yo nan etalaj la ak 0s ak endis ki rete yo ak 1. Kòm yon altènatif, nou ta ka kalkile konbyen 1 yo total nan etalaj la. etalaj k, ranpli dènye k endis yo nan etalaj la ak 1, epi kite rès endis yo ranpli ak 0.
Apwòch yo bay la gen yon konpleksite tan O(n) epi li pa sèvi ak okenn depo adisyonèl, kote n se gwosè opinyon an.
17. Jwenn pi gwo pwodwi de-int nan yon etalaj.
Jwenn pi gwo pwodwi de nonb nan yon etalaj nonb antye relatif.
Panse sou etalaj la 10 3 5 6 2 kòm yon egzanp. Pè (-10, -3) oswa (5, 6) se pwodwi ki pi wo a.
Reflechi sou chak konbinezon eleman ak konnen pwodwi yo se yon apwòch san konprann. Si pwodwi pè aktyèl la pi gwo pase maksimòm pwodwi a jwenn jiska prezan, mete ajou pwodwi maksimòm lan. Enprime eleman yo nan pwodwi final la dènye.
Solisyon ki pi wo a, kote n se kantite lajan an nan opinyon an, gen yon konpleksite tan nan O(n2) epi li pa pran plis espas.
18. Ki jan yo chanje tout zewo etalaj la nan fen an
Deplase tout zewo yo nan yon etalaj nonb antye relatif nan fen an. Repons lan ta dwe evite itilize espas konstan epi prezève lòd relatif konpozan etalaj la.
Antre: {1,2,3,0,8,0,4,7}
Sòti a pral {1,2,3,8,4,7,0,0}
Mete eleman an nan pozisyon sa a ki disponib nan etalaj la si eleman aktyèl la pa zewo. Ranpli tout endis ki rete yo ak 0 yon fwa atik etalaj la yo tout te trete.
Solisyon anvan an gen yon konpleksite tan O(n), kote n se gwosè opinyon an.
19. Ki jan yo sòt yon etalaj ak de antre ki chanje nan yon operasyon.
Ranje yon etalaj nan tan lineyè a bay de atik echanj ak yon etalaj ak tout eleman li yo ranje nan lòd monte. Fè kòmsi etalaj la pa gen kopi.
Antre:= [1,9,3,4,7,2] oswa [9,3,7,2,1,4] oswa [2,4,1,7,3,9]
Sòti: = [1,2,3,4,7,9]
Kòmanse ak dezyèm eleman nan etalaj la, objektif la se konpare chak eleman ak predesesè li yo. Pozisyon diskisyon an estoke lè w pran de endikasyon, x, ak y.
Mete ajou x nan endèks eleman anvan an ak y nan endèks eleman aktyèl la si ansyen an pi gwo pase dènye a. Mete ajou y nan endèks eleman aktyèl la si li sanble ke eleman anvan an pi gran pase eleman aktyèl la.
Finalman, chanje eleman yo nan endèks x ak y yon fwa nou te fini trete chak pè eleman adjasan.
Akòz lefèt ke metòd la susmansyone sèlman fè yon eskanè sèl nan etalaj la opinyon nan gwosè n, konpleksite tan li yo se O (n). Pa gen okenn chanm adisyonèl ki nesesè pou solisyon an.
20. Ki jan yo konbine de etalaj Ranje an plas.
Fizyone atik yo nan etalaj X[] ak Y[]—de etalaj klase ki gen gwosè m ak n chak—nan kenbe lòd klasman an, se sa ki, lè w ranpli X[] ak premye m pi piti eleman yo epi ranpli Y[] ak la. eleman ki rete yo.
Si yon eleman nan etalaj X[] deja nan bon pozisyon (sa vle di, youn nan ki pi piti a nan mitan eleman ki rete yo), neglije li; otreman, ranplase li ak eleman ki pi piti a, ki tou rive premye manm Y[]. Pou kenbe lòd klasman an apre echanj, transfere eleman an (kounye a nan Y[0]) nan bon kote li nan Y[].
Gwosè premye etalaj la se m ak gwosè dezyèm etalaj la se n, ak konpleksite tan an se O(mn).
21. Ki jan yo rekòmande yon etalaj de atik nan altène pozisyon wo ak ba?
Ranje yon lòt etalaj nonb antye relatif pou chak manm ki vin apre yo pi gwo pase eleman anvan ak eleman sa yo. Sipoze etalaj la pa genyen okenn eleman kopi.
Klase etalaj la oswa itilize espas adisyonèl pa nesesè pou yon apwòch efikas. Plan an se, pou kòmanse, dezyèm manm nan etalaj la epi ale moute pa de pou chak iterasyon bouk.
Boukante eleman yo si dènye eleman an depase premye a. Nan yon sans menm jan an, chanje tou de atik si eleman sa a pi gwo pase eleman aktyèl la. Nou pral jwenn etalaj la vle ki konfòm ak restriksyon yo espesifye nan konklizyon an nan bouk la.
22. Ki jan yo ranplase chak eleman nan yon etalaj san yo pa itilize yon operatè divizyon ak pwodwi a nan chak eleman nan etalaj la?
San yo pa itilize operatè divizyon an, ranplase chak eleman nan yon etalaj nonb antye relatif ak pwodwi a nan tout lòt eleman.
Nan tan lineyè ak espas konstan, nou ka itilize repetisyon pou rezoud pwoblèm sa a. Recursively kalkile pwodwi yo nan chak eleman nan subbarray dwat la ak pase pwodwi soubarray gòch la kòm paramèt fonksyon se nosyon an.
Konpleksite tan an se O(n).
23. Jwenn eleman ki pi etranj nan yon etalaj nan tan logaritmik
Bay yon etalaj nonb antye relatif kote tout manm men yon sèl gen menm kantite ensidan, pwoblèm nan se detèmine konbyen fwa yon sèl eleman sa a parèt. Jwenn eleman enpè ki rive nan tan logaritmik ak espas konstan si menm eleman yo parèt an pè nan etalaj la epi pa janm ka gen plis pase de ka yon eleman bay nan yon ranje.
Operasyon XOR la pèmèt nou rezoud pwoblèm sa a nan tan lineyè. Objektif la se XOR chak eleman nan etalaj la. Se sèlman eleman ki rive enpè ki rete apre eleman ki rive menm anile youn ak lòt.
Pwoblèm sa a ka menm rezoud nan tan O(log(n)).
24. Ki jan yo jwenn eleman ki vin apre a pi gwo pou chak eleman nan yon etalaj sikilè?
Pwochen pi gwo eleman pou chak eleman nan yon etalaj sikilè antye ta dwe lokalize. Premye pi gwo nonb antye apre yon eleman x nan etalaj la se pi gwo eleman ki vin apre nan eleman sa a.
De dwat a goch, nou ka opere sou atik etalaj. Objektif la se bouk pou chak eleman x jiskaske swa pile a vid oswa nou gen yon eleman ki pi wo sou li. Mete pwochen pi gwo eleman x pou parèt sou tèt pil la lè li fè sa.
25. Jwenn konte envèsyon yon etalaj?
Jwenn kantite total envèrsyon yon etalaj. Yon pè I j) refere yo kòm yon envèsyon nan yon etalaj A si I j) ak (A[i] > A [j]). Nou dwe konte chak pè sa yo nan etalaj la.
Konte tout manm etalaj ki gen mwens pase li sou bò dwat li epi ajoute rezilta a nan pwodiksyon an se yon apwòch ki senp.
Solisyon sa a gen yon konpleksite O(n2), kote n se gwosè opinyon an.
26. Ki Pwoblèm Pyèj Dlo Lapli a?
Jwenn pi plis dlo ki ka bloke nan yon seri ba ak yon lajè yon inite chak ke yo rekonèt kòm pwoblèm nan "pèchman lapli".
Objektif la se detèmine ba ki pi wo a ki ka mete sou bò gòch ak dwa chak ba. Minimòm ba ki mennen nan goch ak dwa, mwens wotè ba aktyèl la, se kantite dlo ki estoke sou chak ba.
konklizyon
Konpare ak lòt sijè estrikti done, etalaj yo pi senp. Yo nan lòd yo ace etalaj kesyon entèvyou, ou bezwen gen yon konpreyansyon fondamantal nan etalaj.
Ou ta dwe byen revize fondasyon etalaj yo, ki gen ladan operasyon etalaj (soti nan deklare/kreye yon etalaj rive jwenn aksè/modifye atik etalaj), osi byen ke konsèp pwogramasyon tankou bouk, rekursion, ak operatè debaz yo nan lòd yo reponn ak siksè kesyon entèvyou etalaj. Rekonèt pwoblèm nan nèt.
Ou ta dwe chèche klarifikasyon si ou gen nenpòt kesyon. Reflechi sou divize pwoblèm nan an pati ki pi jere. Asire w ke ou gen algorithm nan tèt ou anvan ou kòmanse pwogramasyon; ekri li oswa vizyalize li nan yon organigram. Lè sa a, kòmanse ekri kòd.
Kite yon Reply