Clár na nÁbhar[Folaigh][Taispeáin]
- 1. Conas a shainíonn tú Eagar?
- 2. Arrays Dinimiciúla: Cad iad? Cad a chuireann amach iad ó Bhun-Eagar?
- 3. Conas a athraíonn eagar agus foclóir óna chéile?
- 4. Liostaigh cuid de na buntáistí agus na míbhuntáistí a bhaineann le eagair.
- 5. Cad dó a dtagraíonn “Sparse Eagar”?
- 6. Cathain a roghnófá liosta nasctha thar eagar?
- 7. Cad a dhéanann idirdhealú idir eagar innéacsaithe agus eagar comhthiomsaitheach?
- 8. Cad iad na buntáistí a bhaineann le Heap thar eagair sórtáilte?
- 9. An féidir linn méid an eagair a shainiú mar dhiúltach?
- 10. Conas a aimsíonn tú an tslánuimhir atá ar iarraidh in eagar 1 go 100 eilimint?
- 11. Conas a aimsíonn tú innéacs dúil in eagar?
- 12. Conas is féidir leat fáil réidh le gné ar leith ó eagar?
- 13. Conas is féidir comhionannas dhá eagar a fhíorú?
- 14. Agus eagair á bplé againn, cad atá i gceist agat leis na frásaí “Toise” agus “Síntiús”?
- Ceisteanna Agallaimh a Chódú
- 15. Lorg péire in eagar a bhfuil an tsuim shonraithe aige
- 16. Sórtáil eagar dénártha le ham líneach
- 17. Faigh an táirge dhá-uimhir is mó in eagar.
- 18. Conas nialais an eagair go léir a aistriú go dtí an deireadh
- 19. Conas eagar a shórtáil le dhá iontráil a lasctar in oibríocht amháin.
- 20. Conas dhá eagar sórtáilte a chur le chéile i bhfeidhm.
- 21. Conas raon míreanna a athordú i suíomhanna ard agus ísle ailtéarnacha?
- 22. Conas gach eilimint d'eagar a chur in ionad gan oibreoir deighilte a úsáid le táirge gach dúil san eagar?
- 23. Faigh an dúil is corr in eagar in am logartamach
- 24. Conas an eilimint níos mó ina dhiaidh sin a fháil do gach eilimint in eagar ciorclach?
- 25. Faigh comhaireamh inbhéartaithe eagair?
- 26. Cad í an Fhadhb um Ghaisteoireacht Uisce Báistí?
- Conclúid
Tá sraith ceisteanna DSA in agallaimh códaithe. Ba cheart duit a bheith oilte ar eagair má tá tú ag ullmhú don agallamh teicniúil atá le teacht le FAANG nó le gnólacht teicneolaíochta Sraith-1 eile.
I bhformhór na n-agallamh códaithe, tagann sé sa dara háit do Strings. Is éard is eagar ann ná grúpáil d’eilimintí sonraí gaolmhara a choinnítear i ngaireacht dá chéile i gcuimhne.
Toisc go bhfuil siad ceangailte le gach teanga ríomhchlárúcháin, mar C, C ++, Java, Python, Perl, agus Ruby, tá siad i ngach áit. Lean ort ag léamh le haghaidh roinnt dúshlán códaithe cleachtais agus ceisteanna agallaimh agus freagraí bunaithe ar eagair.
Bainfear úsáid as Python sa phost seo chun dul i ngleic leis na saincheisteanna códaithe toisc go bhfuil sé simplí a úsáid, a thuiscint, agus ní mór dúinn a bheith eolach ar an gcuid is mó againn.
Let's start.
1. Conas a shainíonn tú Eagar?
- Is sraith é grúpa de chineálacha sonraí gaolmhara.
- Arrays socraithe i gcónaí.
- Stóráiltear an cineál céanna athróg in áiteanna éagsúla trí réada eagair.
- Tá cineálacha primitive agus tagairtí réad araon ag luí leis.
2. Arrays Dinimiciúla: Cad iad? Cad a chuireann amach iad ó Bhun-Eagar?
Is buntáiste suntasach é an scálaiú uathoibríoch a sholáthraíonn eagair dhinimiciúla (dá ngairtear eagair infhásta, eagair in-athraithe, eagair inathraithe, nó ArrayLists i Java).
Ní mór go mbeadh a fhios agat i gcónaí cé mhéad eilimint a stórálfar san eagar roimh ré ós rud é go bhfuil méid seasta ag eagair. Fásann eagar dinimiciúil, ar an láimh eile, de réir mar a chuireann tú baill bhreise leis, mar sin ní gá go mbeadh a fhios agat roimh ré faoina mhéid cruinn.
3. Conas a athraíonn eagar agus foclóir óna chéile?
Seo sraith de cheisteanna agallaimh bunúsacha-bhunaithe a chuirtear go rialta. Seo a leanas na príomh-idirdhealuithe idir eagar agus foclóirí:
- Is éard is eagar ann ná liosta ordaithe de mhíreanna comhchosúla. Ar an láimh eile, tá péirí eochairluacha ag foclóir.
- Is féidir le méideanna eagair athrú go dinimiciúil. Ní bhíonn a leithéid de smaointe dinimiciúla sna foclóirí.
- Sula n-úsáidtear eagar, ní mór a mhéid a shonrú. Ní gá méideanna foclóir a shaincheapadh.
- Úsáid an ráiteas Redim más mian leat méid an eagair a leathnú. I bhfoclóirí, is féidir eilimint a chur leis gan dearbhú.
4. Liostaigh cuid de na buntáistí agus na míbhuntáistí a bhaineann le eagair.
Buntáistí:
- Is féidir le eagair roinnt gnéithe a shórtáil go comhuaineach.
- Eile struchtúir sonraí, cosúil le stoic, scuainí, liostaí nasctha, crainn, graif, etc., a chur i bhfeidhm in eagar.
- Is féidir innéacs a úsáid chun eilimint d’eagair a bhaint amach.
Míbhuntáistí:
- Ní mór méid eagair a dhearbhú roimh ré. Ag tráth an dearbhaithe eagair, b'fhéidir nach mbeadh a fhios againn, áfach, an méid atá uainn.
- Tá struchtúr an eagar statach. Tugann sé le tuiscint go mbíonn méid an eagar socraithe i gcónaí agus nach féidir leithdháileadh cuimhne a mhéadú nó a laghdú.
5. Cad dó a dtagraíonn “Sparse Eagar”?
Is éard is eagar gann ann ná eagar sonraí a bhfuil go leor iontrálacha acu le luachanna nialais. I gcodarsnacht leis sin, tá an chuid is mó de na míreanna le luachanna neamh-nialasacha in eagar dlúth. D’fhéadfadh bearnaí a bheith sna hinnéacsanna d’eagar gann, a athraíonn uimhreacha go réada. I gcomparáid le HashMap, tá siad níos éifeachtaí ó thaobh cuimhne.
6. Cathain a roghnófá liosta nasctha thar eagar?
Agus liostaí nasctha á n-úsáid in ionad eagair, smaoinigh ar:
- Ní theastaíonn aon eilimint uait chun rochtain randamach a bheith agat.
- Sa chás go bhfuil intuarthacht ama riachtanach, beidh ort cuir isteach am seasta agus baint ón liosta.
- Chun scuaine tosaíochta a chruthú, seans go mbeidh ort míreanna a chur i lár an liosta.
- Níl aon smaoineamh agat cé chomh fada agus a bheidh an liosta. Má ardaíonn méid an eagar, ní mór duit cuimhne a athdhearbhú agus a dhúbailt, díreach mar a dhéantar le eagair shimplí.
7. Cad a dhéanann idirdhealú idir eagar innéacsaithe agus eagar comhthiomsaitheach?
Tá na príomh-idirdhealuithe idir eagair chomhthiomsaitheach agus eagair innéacsaithe liostaithe sa tábla seo a leanas.
- Úsáidtear péire eochairluacha i bhformáid téacs nó uimhriúil chun eagar comhthiomsaitheach a shórtáil. Tá eochracha an eagar innéacsaithe go léir uimhriúil, agus tá gach eochair ceangailte le luach ar leith.
- In eagar comhthiomsaitheach, b'fhéidir gur teaghrán an eochair. Eagar innéacsaithe le heochracha slánuimhir ag tosú ag 0.
- Déanann tábla dhá cholún aithris ar iompar eagar comhthiomsaitheach. Cosúil le tábla aon-cholún tá eagair innéacsaithe.
- Is cineál eagair chomhthiomsaitheach iad léarscáileanna. Ní léarscáil é eagar innéacs.
8. Cad iad na buntáistí a bhaineann le Heap thar eagair sórtáilte?
Is é an buntáiste is mó a bhaineann leis an éifeachtúlacht ama a bhaineann le Heap over Sorted Arrays a úsáid. Cé go mbíonn oibríochtaí carn níos tapúla, bíonn go leor ama ag teastáil chun eagar a shórtáil. Is féidir le carn an eilimint is lú a aimsiú i bhfad níos tapúla ná mar is féidir eagar a chur in eagar.
Is féidir cnuasach uimhreacha tugtha a shocrú ar cheann amháin de dhá bhealach ag baint úsáide as Eagar Sórtáilte. Ar an taobh eile, d’fhéadfadh go mbeadh níos mó ná carn féideartha amháin ann do bhailiúchán áirithe uimhreacha.
9. An féidir linn méid an eagair a shainiú mar dhiúltach?
Ní féidir, ní féidir linn slánuimhir dhiúltach a shainiú mar mhéid eagair. Ní bheidh earráid ama tiomsaithe ann má dhearbhaímid. Ag am rite, tiocfaimid ar NegativeArraySizeException, áfach.
10. Conas a aimsíonn tú an tslánuimhir atá ar iarraidh in eagar 1 go 100 eilimint?
Is féidir iomlán na sraithe a ríomh tríd an bhfeidhm seo a leanas a chur i bhfeidhm: n (n + 1) / 2
Ní oibreoidh an fheidhm seo ach amháin mura bhfuil aon dúblaigh san eagar nó go bhfuil níos mó ná slánuimhir amháin in easnamh. Cibé an bhfuil eilimintí dúblacha ag eagar, is féidir leat an t-eagar a shórtáil féachaint an bhfuil aon eilimintí comhionann.
11. Conas a aimsíonn tú innéacs dúil in eagar?
Is féidir innéacs eiliminte a aimsiú trí chuardach líneach nó dénártha. Go dtí go n-aimsíonn sé meaitseáil na heiliminte riachtanacha, lúbann feidhm chuardaigh líneach thar gach eilimint in eagar. Filleann sé an t-innéacs nuair a aimsíonn sé an eilimint mheaitseála. Mar thoradh air sin, is é O. (n) castacht ama an chuardaigh líneach. Is féidir cuardach líneach a úsáid as eagar sórtáilte agus neamhshórtáilte.
Trí úsáid a bhaint as cuardach dénártha, a roinneann an t-eagar ina dhá leath go leanúnach go dtí go dtagann airmheán an eatraimh leis an eilimint riachtanach agus go soláthraíonn sé an t-innéacs, is féidir leat innéacs na heiliminte a fháil má tá an t-eagar curtha in eagar. Dá bhrí sin, is é O. (log n) castacht ama an chuardaigh dhénártha.
12. Conas is féidir leat fáil réidh le gné ar leith ó eagar?
Ós rud é nach féidir leat míreanna a scriosadh as an eagar bunaidh toisc gur tacair seasta iad le méid sainithe, tá an t-agallóir ag iarraidh ort cur chuige difriúil a mholadh agus déileáil leis an bhfadhb a ardaíonn an cheist. Is é an beart is fearr ná eagar nua a dhéanamh chun eilimint a scriosadh. Is féidir leat na heilimintí ón gcéad eagar san eagar seo a dhúbailt agus gan ach an eilimint is mian leat a scriosadh a áireamh.
Is éard atá i gceist le straitéis eile ná an sprioceilimint a aimsiú san eagar agus ansin ord na míreanna go léir atá ar thaobh na láimhe deise den sprioceilimint a aisiompú.
13. Conas is féidir comhionannas dhá eagar a fhíorú?
Caithfidh tú faid an dá eagar a chuirtear ar fáil a fhíorú ar dtús. Déantar comparáid idir míreanna meaitseála an dá eagar nuair a bhíonn a gcuid faid cothrom. Measfar an dá eagar a bheith comhionann. más ionann gach péire comhpháirt i ngach comhfhreagras. Ní mholtar an cur chuige seo comhionannas dhá eagair a sheiceáil má tá na eagair mór i méid ós rud é go dtógfaidh sé go leor ama. Is féidir leat an modh comhionann() atá sa rang Arrays a úsáid freisin, ach má iarrann an t-agallóir ort dhá eagar a chur i gcomparáid gan úsáid a bhaint as modhanna ionsuite, beidh sé seo úsáideach.
14. Agus eagair á bplé againn, cad atá i gceist agat leis na frásaí “Toise” agus “Síntiús”?
Is ionann “Toise” eagar agus líon na n-innéacsanna, nó na bhfoscríbhinní, a theastaíonn chun gach ball aonair a shainaithint. D’fhéadfadh go mbeadh síntiúis agus toisí doiléir. Is éard is toise ann ná cur síos ar raon na n-eochracha ceadaithe, ach is uimhir é síntiús. Níl ach síntiús amháin ag teastáil le haghaidh gach toise eagair.
Mar shampla, tá dhá thoise ag an eagar eagair[10][5]. Méideanna 10 ar cheann amháin agus 5 ar an taobh eile. Chun aghaidh a thabhairt ar a chomhpháirteanna, teastaíonn dhá shíntiús uait. Tá an dá cheann idir 0 agus 4; ceann idir 0 agus 9, san áireamh.
Ceisteanna Agallaimh a Chódú
15. Lorg péire in eagar a bhfuil an tsuim shonraithe aige
Mar shampla,
Ionchur:
- uimhreacha = [8, 7, 2, 5, 3, 1]
- sprioc = 10
aschur:
- Aimsíodh péire (8, 2)
- Or
- Aimsíodh péire (7, 3)
Ionchur:
- uimhreacha = [5, 2, 6, 8, 1, 9]
- sprioc = 12
aschur:
- Péire gan aimsiú
16. Sórtáil eagar dénártha le ham líneach
Sórtáil eagar dénártha in am líneach agus i limistéar seasta. Ba chóir go dtaispeánfadh an t-aschur gach nialais ar dtús, ansin gach nialais.
Mar shampla,
- Ionchur: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Aschur: { 0, 0, 0, 0, 1, 1, 1, 1 }
Cur chuige simplí a bheadh ann líon iomlán 0s an eagar a ríomh, abair k, agus ansin na chéad innéacsanna k san eagar a líonadh le 0s agus na hinnéacsanna atá fágtha le 1. Mar mhalairt air sin, d’fhéadfaimis a ríomh cé mhéad 1 atá san iomlán sa eagar k, líon na hinnéacsanna deiridh k san eagar le 1, agus fág an chuid eile de na hinnéacsanna líonta le 0.
Tá castacht ama O(n) ag an gcur chuige a thugtar agus ní úsáideann sé aon stóras breise, nuair is é n méid an ionchuir.
17. Faigh an táirge dhá-uimhir is mó in eagar.
Faigh an táirge is mó de dhá uimhir in eagar slánuimhreacha.
Smaoinigh ar an eagar 10 3 5 6 2 mar shampla. Is é an péire (-10, -3) nó (5, 6) an táirge is airde.
Is cur chuige amaideach é smaoineamh ar gach teaglaim eilimint agus a dtáirge a dhéanamh amach. Má tá táirge an phéire reatha níos mó ná an t-uastáirgeacht a fuarthas go dtí seo, nuashonraigh an t-uastáirge. Priontáil comhpháirteanna an táirge deiridh go deireanach.
Is é O(n2) castacht ama an réiteach thuas, áit arb é n méid an ionchuir, agus ní thógann sé a thuilleadh spáis.
18. Conas nialais an eagair go léir a aistriú go dtí an deireadh
Bog na nialais go léir in eagar slánuimhir go dtí an deireadh. Ba cheart go seachnódh an freagra spás tairiseach a úsáid agus ord coibhneasta comhpháirteanna an eagair a chaomhnú.
Ionchur: {1,2,3,0,8,0,4,7}
Is é an t-aschur ná {1,2,3,8,4,7,0,0}
Cuir an eilimint ag an suíomh seo a leanas atá ar fáil san eagar mura bhfuil an eilimint reatha náid. Líon na hinnéacsanna go léir atá fágtha le 0 nuair a bheidh na míreanna ar fad próiseáilte.
Tá castacht ama O(n) ag an réiteach roimhe seo, áit arb é n méid an ionchuir.
19. Conas eagar a shórtáil le dhá iontráil a lasctar in oibríocht amháin.
Sórtáil eagar san am líneach a thugtar dhá mhír mhalartaithe agus eagar a bhfuil a chuid gnéithe uile eagraithe in ord ardaitheach. Lig ort nach bhfuil aon dúblaigh san eagar.
Ionchur:= [1,9,3,4,7,2] nó [9,3,7,2,1,4] nó [2,4,1,7,3,9]
Aschur: = [1,2,3,4,7,9]
Ag tosú leis an dara eilimint san eagar, is é an cuspóir gach eilimint a chur i gcomparáid lena réamhtheachtaí. Stóráiltear suíomh na díospóide trí dhá phointe a ghlacadh, x, agus y.
Nuashonraigh x go hinnéacs na heiliminte roimhe seo agus y chuig innéacs na heiliminte reatha má tá an chéad eilimint níos mó ná an dara ceann. Nuashonraigh y chuig innéacs na heiliminte reatha má tharlaíonn sé go bhfuil an eilimint roimhe sin níos mó ná an eilimint reatha.
Ar deireadh, aistrigh na heilimintí ag innéacsanna x agus y nuair a bheidh gach péire dúil in aice láimhe críochnaithe againn.
Toisc nach ndéanann an modh thuasluaite ach scanadh amháin ar an eagar ionchuir de mhéid n, is é O(n) a chastacht ama. Níl aon seomra breise riachtanach don réiteach.
20. Conas dhá eagar sórtáilte a chur le chéile i bhfeidhm.
Cumaisc na míreanna eagair X[] agus Y[]—dhá eagar sórtáilte ar méid iad m agus n an ceann—tríd an t-ord sórtáilte a choinneáil, is é sin, trí X[] a líonadh leis na chéad m eilimintí is lú agus líonadh Y[] leis an eilimintí fágtha.
Má tá dúil san eagar X[] ag an suíomh ceart cheana féin (.i. an ceann is lú i measc na n-eilimintí atá fágtha), déan neamhaird de; ar shlí eile, cuir an eilimint is lú ina ionad, a tharlaíonn gurb é an chéad bhall de Y[] é freisin. Chun an t-ordú sórtáilte a choinneáil tar éis babhtála, aistrigh an eilimint (anois ag Y[0]) chuig a suíomh ceart in Y[].
Is é m méid an chéad eagar agus is é n méid an dara eagar, agus is é O(mn) an chastacht ama.
21. Conas raon míreanna a athordú i suíomhanna ard agus ísle ailtéarnacha?
Déan eagar slánuimhir ionas go mbeidh gach ball ina dhiaidh sin níos mó ná na heilimintí roimhe seo agus na heilimintí seo a leanas. Glac leis nach bhfuil aon eilimintí dúblacha san eagar.
Ní gá an t-eagar a shórtáil nó spás breise a úsáid le haghaidh cur chuige éifeachtach. Is é an plean, ar dtús, an dara ball den eagar agus dul suas faoi dhó le haghaidh gach atriall lúibe.
Babhtáil na comhpháirteanna má sháraíonn an eilimint dheireanach an chéad cheann. Ar an mbealach céanna, athraigh an dá mhír má tá an eilimint seo a leanas níos mó ná an eilimint reatha. Gheobhaidh muid an t-eagar atá ag teastáil a chomhlíonann na srianta sonraithe ag deireadh an lúb.
22. Conas gach eilimint d'eagar a chur in ionad gan oibreoir deighilte a úsáid le táirge gach dúil san eagar?
Gan an t-oibreoir rannáin a úsáid, cuir táirge na n-eilimintí eile go léir in ionad gach eilimint in eagar slánuimhir.
In am líneach agus i spás tairiseach, is féidir linn úsáid a bhaint as atarlú chun aghaidh a thabhairt ar an gceist seo. Is é an smaoineamh táirgí gach eilimint a ríomh go hathchúrsach sa fho-aráiteas ceart agus an táirge fo-arátha clé a rith mar pharaiméadair feidhme.
Is í an chastacht ama ná O(n).
23. Faigh an dúil is corr in eagar in am logartamach
I bhfianaise eagar slánuimhreacha ina bhfuil líon cothrom teagmhas ag gach ball seachas ball amháin, is í an fhadhb atá ann a chinneadh cé mhéad uair a thagann an ghné amháin seo chun solais. Faigh an corrdhúil a tharlaíonn in am logartamach agus sa spás tairiseach má tharlaíonn na dúile céanna i mbeirteanna san eagar agus nach féidir níos mó ná dhá chás d’eilimint tugtha a bheith ann i ndiaidh a chéile.
Cuireann oibríocht XOR ar ár gcumas an cheist seo a réiteach in am líneach. Is é an sprioc XOR gach eilimint san eagar. Ní fhanann ach corr-eilimintí a tharlaíonn tar éis do na gnéithe cothroma a chéile a chealú.
Is féidir an fhadhb seo a réiteach fiú in am O(log(n)).
24. Conas an eilimint níos mó ina dhiaidh sin a fháil do gach eilimint in eagar ciorclach?
Ba cheart an chéad eilimint eile níos mó do gach eilimint in eagar slánuimhir ciorclach a shuíomh. Is í an chéad slánuimhir níos mó tar éis dúil x san eagar an eilimint is mó ina dhiaidh sin den eilimint sin.
Ó dheis go clé, féadfaimid oibriú ar mhíreanna eagair. Is é an sprioc ná lúb a dhéanamh do gach eilimint x go dtí go mbeidh an chairn folamh nó go bhfuil eilimint níos airde againn ar a bharr. Socraigh an chéad eilimint eile níos mó de x le feiceáil ar bharr an chruach nuair a dhéanfaidh sé.
25. Faigh comhaireamh inbhéartaithe eagair?
Faigh líon iomlán na n-aisiompuithe ar eagar. Tagraítear do phéire I j) mar inbhéartú ar eagar A más I j) agus (A[i] > A[j]). Ní mór dúinn gach péire díobh seo a chomhaireamh san eagar.
Is cur chuige simplí é gach ball eagair atá níos lú ná é a chomhaireamh agus an toradh a chur leis an aschur.
Tá castacht O(n2) ag an réiteach seo, áit arb é n méid an ionchuir.
26. Cad í an Fhadhb um Ghaisteoireacht Uisce Báistí?
Is saincheist “báisteach gafa” a thugtar ar an tsaincheist is mó uisce is féidir a ghabháil i sraith barraí ar leithead aonad amháin an ceann a fháil.
Is é an sprioc ná an barra is airde a fhéadfar a chur ar chlé agus ar dheis gach barra a chinneadh. Is é íosmhéid na mbarraí tosaigh ar chlé agus ar dheis, lúide airde an bharra reatha, an méid uisce a stóráiltear ar bharr gach barra.
Conclúid
I gcomparáid le topaicí struchtúir sonraí eile, tá eagair níos simplí. Chun ceisteanna agallaimh a réiteach, ní mór tuiscint bhunúsach a bheith agat ar eagair.
Ba cheart duit athbhreithniú cuimsitheach a dhéanamh ar bhunús na n-eagair, lena n-áirítear oibríochtaí eagair (ó dhearbhú/a chruthú eagar go rochtain/mionathrú a dhéanamh ar mhíreanna eagair), chomh maith le coincheapa ríomhchláraithe amhail lúba, atarlú, agus oibreoirí bunúsacha chun ceisteanna agallaimh eagair a fhreagairt go rathúil. An cheist a aithint go hiomlán.
Ba cheart duit soiléiriú a lorg má tá aon cheist agat. Smaoinigh ar an tsaincheist a roinnt ina gcodanna níos soláimhsithe. Déan cinnte go bhfuil an algartam i gcuimhne agat sula dtosaíonn tú ar an ríomhchlárú; scríobh síos é nó léirshamhlú i sreabhchairt é. ansin tosú ag scríobh cód.
Leave a Reply