Преглед садржаја[Сакрити][Прикажи]
- 1. Како дефинишете низ?
- 2. Динамички низови: шта су они? Шта их разликује од основних низова?
- 3. Како се низ и речник разликују један од другог?
- 4. Наведите неке од предности и мана низова.
- 5. На шта се односи „Спарсе Арраи“?
- 6. Када бисте изабрали повезану листу уместо низа?
- 7. Шта разликује индексирани низ од асоцијативног низа?
- 8. Које предности има Хеап у односу на сортиране низове?
- 9. Можемо ли дефинисати величину низа као негативну?
- 10. Како лоцирате цео број који недостаје у низу од 1 до 100 елемената?
- 11. Како пронаћи индекс елемента у низу?
- 12. Како можете да се решите одређеног елемента из низа?
- 13. Како се може проверити једнакост два низа?
- 14. Када говоримо о низовима, шта подразумевате под фразама „Димензија“ и „Субсцрипт“?
- Кодирање питања за интервју
- 15. Потражите пар у низу који има наведени збир
- 16. Бинарно сортирање низа са линеарним временом
- 17. Пронађите највећи производ са два целина у низу.
- 18. Како померити све нуле низа до краја
- 19. Како сортирати низ са два уноса који се мењају у једној операцији.
- 20. Како комбиновати два сортирана низа на месту.
- 21. Како преуредити низ ставки у наизменичним високим и ниским позицијама?
- 22. Како сваки елемент низа без употребе оператора дељења заменити производом сваког елемента у низу?
- 23. Пронађите најчуднији елемент у низу у логаритамском времену
- 24. Како добити следећи већи елемент за сваки елемент у кружном низу?
- 25. Наћи број инверзија низа?
- 26. Шта је проблем задржавања кишнице?
- Zakljucak
Интервјуи за кодирање садрже низ ДСА питања. Требало би да будете вешти са низовима ако се спремате за предстојећи технички интервју са ФААНГ-ом или неким другим технолошким бизнисом Тиер-1.
У већини интервјуа за кодирање, налази се на другом месту после Стринга. Низ је груписање повезаних елемената података који се држе у непосредној близини један другом у меморији.
Пошто су повезани са свим програмским језицима, као што су Ц, Ц++, Јава, Питхон, Перл и Руби, они су свуда. Наставите да читате за неке изазове кодирања у пракси и интервјуишите питања и одговоре на основу низова.
Питхон ће се користити у овом посту за рјешавање проблема кодирања јер је једноставан за кориштење, разумијевање и мора бити познат већини нас.
Почнимо.
1. Како дефинишете низ?
- Група повезаних типова података је низ.
- Низови су увек фиксни.
- Иста врста променљиве се чува на неколико места од стране објеката низа.
- Примитивни типови и референце објеката су компатибилни са њим.
2. Динамички низови: шта су они? Шта их разликује од основних низова?
Аутоматско скалирање које динамички низови (који се такође називају низови који се могу увећати, низови променљиве величине, променљиви низови или АрраиЛистс у Јави) пружају је значајна предност.
Увек морате знати колико елемената ће ваш низ сачувати унапред пошто низови имају фиксну величину. С друге стране, динамички низ расте како му додајете додатне чланове, тако да не морате унапред да знате његову тачну величину.
3. Како се низ и речник разликују један од другог?
Ово је низ питања за интервју који се редовно постављају заснован на основама. Следе кључне разлике између низова и речника:
- Низ је уређена листа сличних ставки. Речник, с друге стране, има парове кључ-вредност.
- Величине низа могу се динамички мењати. Овакве динамичне идеје не постоје у речницима.
- Пре употребе низа, његова величина мора бити специфицирана. Величине речника не морају да се прилагођавају.
- Користите наредбу Редим ако желите да проширите величину низа. У речницима, елемент се може додати без декларације.
4. Наведите неке од предности и мана низова.
Предности:
- Низови могу сортирати више елемената истовремено.
- други структуре података, као што су стекови, редови, повезане листе, стабла, графикони, итд., могу се имплементирати у низ.
- Индекс се може користити за достизање елемента низа.
Мане:
- Величина низа мора бити декларисана унапред. У тренутку декларације низа, можда нећемо бити свесни величине која нам је потребна.
- Структура низа је статична. То подразумева да је величина низа увек фиксна и да се алокација меморије не може повећати или смањити.
5. На шта се односи „Спарсе Арраи“?
Ретки низ је низ података који има много уноса са нултим вредностима. Насупрот томе, густи низ садржи већину својих ставки са вредностима које нису нула. Индекси разређеног низа, који претвара бројеве у објекте, могу укључивати празнине. У поређењу са ХасхМап-ом, они су ефикаснији за меморију.
6. Када бисте изабрали повезану листу уместо низа?
Када користите повезане листе уместо низова, узмите у обзир:
- Не требају вам никакви елементи да бисте имали случајни приступ.
- Тамо где је временска предвидљивост неопходна, потребна су вам уметања и уклањања са листе у сталном времену.
- Да бисте креирали приоритетни ред, можда ћете морати да поставите ставке у центар листе.
- Немате појма колико ће листа бити дуга. Ако се величина низа повећа, морате поново декларисати и дуплирати меморију, баш као и код једноставних низова.
7. Шта разликује индексирани низ од асоцијативног низа?
Примарне разлике између асоцијативних и индексираних низова су наведене у следећој табели.
- Пар кључ-вредност у текстуалном или нумеричком формату се користи за сортирање асоцијативног низа. Сви кључеви индексираног низа су нумерички, а сваки кључ је повезан са различитом вредношћу.
- У асоцијативном низу, кључ може бити стринг. Индексирани низ са целобројним кључевима који почињу од 0.
- Табела са две колоне имитира понашање асоцијативног низа. Слично табели са једном колоном су индексирани низови.
- Мапе су асоцијативни тип низа. Индексни низ није мапа.
8. Које предности има Хеап у односу на сортиране низове?
Временска ефикасност коришћења гомиле преко сортираних низова је кључна предност. Док су операције гомиле брже, сортирање низа захтева много времена. Хрпа може открити најмањи елемент знатно брже него што се низ може сортирати.
Дата колекција бројева може се уредити на један од два начина помоћу сортираних низова. С друге стране, за дату колекцију бројева може постојати више од једне потенцијалне гомиле.
9. Можемо ли дефинисати величину низа као негативну?
Не, не можемо дефинисати негативан цео број као величину низа. Неће бити грешке у времену компајлирања ако прогласимо. Међутим, током извршавања наићи ћемо на изузетак НегативеАрраиСизеЕкцептион.
10. Како лоцирате цео број који недостаје у низу од 1 до 100 елемената?
Укупан број серије се може израчунати применом следеће функције: н (н + 1) / 2
Ова функција ће радити само ако низ нема дупликата или ако недостаје више од једног целог броја. Без обзира да ли низ има дупликате елемената, можете сортирати низ да бисте видели да ли постоје елементи који су еквивалентни.
11. Како пронаћи индекс елемента у низу?
Индекс елемента се може открити путем линеарне или бинарне претраге. Док не лоцира подударност траженог елемента, функција линеарне претраге се креће преко сваког елемента у низу. Враћа индекс када лоцира одговарајући елемент. Према томе, временска сложеност линеарне претраге је О. (н). И сортирани и несортирани низ могу користити линеарну претрагу.
Користећи бинарну претрагу, која непрекидно дели низ на пола док се медијана интервала не поклопи са траженим елементом и обезбеди индекс, можете добити индекс елемента ако је низ сортиран. Сходно томе, временска сложеност бинарне претраге је О. (лог н).
12. Како можете да се решите одређеног елемента из низа?
Пошто не можете једноставно да избришете елементе из оригиналног низа пошто су то фиксни скупови са дефинисаном величином, анкетар тражи од вас да предложите другачији приступ и решите проблем који поставља питање. Најбоља акција је да направите нови низ да бисте избрисали елемент. Можете дуплирати елементе из првог низа у овом низу и укључити само елемент који желите да избришете.
Друга стратегија укључује проналажење циљног елемента у низу, а затим обрнути редослед свих ставки које се налазе десно од циљног елемента.
13. Како се може проверити једнакост два низа?
Прво морате да проверите дужине два наведена низа. Подударне ставке оба низа се упоређују када су њихове дужине једнаке. Два низа ће се сматрати једнакима. ако је сваки пар компоненти у свакој кореспонденцији једнак. Овај приступ се не препоручује да се проверава једнакост два низа ако су низови велике величине, јер ће за то требати доста времена. Такође можете да користите метод екуалс() који је укључен у класу Арраис, међутим, ако вас анкетар затражи да упоредите два низа без коришћења уграђених метода, овај начин ће бити користан.
14. Када говоримо о низовима, шта подразумевате под фразама „Димензија“ и „Субсцрипт“?
„Димензија“ низа је број индекса, или индекса, потребних за идентификацију сваког појединачног члана. Индекси и димензије могу бити нејасни. Димензија је опис опсега дозвољених кључева, док је индекс број. За сваку димензију низа потребан је само један индекс.
На пример, низ арр[10][5] има две димензије. Величине 10 на једној и 5 на другој. Да бисте адресирали његове компоненте, потребна су вам два индекса. Оба су између 0 и 4; један између 0 и 9, укључујући.
Кодирање питања за интервју
15. Потражите пар у низу који има наведени збир
На пример,
Улаз:
- бројеви = [8, 7, 2, 5, 3, 1]
- циљ = 10
Излаз:
- Пронађен пар (8, 2)
- Or
- Пронађен пар (7, 3)
Улаз:
- бројеви = [5, 2, 6, 8, 1, 9]
- циљ = 12
Излаз:
- Пар није пронађен
16. Бинарно сортирање низа са линеарним временом
Сортирајте бинарни низ у линеарном времену и у фиксној области. Излаз би прво требало да прикаже све нуле, а затим све јединице.
На пример,
- Улаз: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Излаз: { 0, 0, 0, 0, 1, 1, 1, 1 }
Једноставан приступ би био да се израчуна укупан број низа од 0, рецимо к, а затим попуни првих к индекса у низу са 0, а преосталих индекса са 1. Као алтернативу, могли бисмо израчунати колико је 1 укупно у низу. низ к, попуните последњих к индекса у низу са 1, а оставите остатак индекса попуњеним са 0.
Дати приступ има О(н) временску сложеност и не користи додатну меморију, где је н величина улаза.
17. Пронађите највећи производ са два целина у низу.
Пронађите највећи производ два броја у низу целих бројева.
Размислите о низу 10 3 5 6 2 као примеру. Пар (-10, -3) или (5, 6) је највећи производ.
Размишљати о свакој комбинацији елемената и схватити њихов производ је глуп приступ. Ако је производ тренутног пара већи од максималног производа добијеног до сада, ажурирајте максимални производ. Одштампајте компоненте коначног производа последње.
Горње решење, где је н количина инпута, има временску сложеност од О(н2) и не заузима више простора.
18. Како померити све нуле низа до краја
Померите све нуле у низу целог броја до краја. Одговор треба да избегава коришћење константног простора и да сачува релативни редослед компоненти низа.
Улаз: {1,2,3,0,8,0,4,7}
Излаз ће бити {1,2,3,8,4,7,0,0}
Ставите елемент на следећу доступну позицију у низу ако тренутни елемент није нула. Попуните све преостале индексе са 0 када се све ставке низа обрађују.
Претходно решење има О(н) временску сложеност, где је н величина улаза.
19. Како сортирати низ са два уноса који се мењају у једној операцији.
Сортирајте низ у линеарном времену дате две замењене ставке и низ са свим његовим елементима распоређеним у растућем редоследу. Претварајте се да низ не садржи дупликате.
Улаз:= [1,9,3,4,7,2] или [9,3,7,2,1,4] или [2,4,1,7,3,9]
Излаз: = [1,2,3,4,7,9]
Почевши од другог елемента у низу, циљ је да се сваки елемент упореди са његовим претходником. Позиција спора се чува узимањем два показивача, к и и.
Ажурирајте к на индекс претходног елемента и и на индекс тренутног елемента ако је први већи од другог. Ажурирајте и на индекс тренутног елемента ако се испостави да је претходни елемент већи од тренутног елемента.
Коначно, промените елементе са индексима к и и када завршимо са обрадом сваког суседног пара елемената.
Због чињенице да поменути метод обавља само једно скенирање улазног низа величине н, његова временска сложеност је О(н). За решење није потребна додатна просторија.
20. Како комбиновати два сортирана низа на месту.
Спојите ставке низова Кс[] и И[] — два сортирана низа величине м и н сваки — задржавањем сортираног редоследа, односно попуњавањем Кс[] са првих м најмањих елемената и попуњавањем И[] са преостали елементи.
Ако је елемент у низу Кс[] већ на правој позицији (тј. онај који је најмањи међу преосталим елементима), занемарите га; у супротном, замените га најмањим елементом, који је такође први члан И[]. Да бисте задржали сортирани редослед након замене, пренесите елемент (сада на И[0]) на његову одговарајућу локацију у И[].
Величина првог низа је м, а величина другог низа је н, а временска сложеност је О(мн).
21. Како преуредити низ ставки у наизменичним високим и ниским позицијама?
Преуредите низ целих бројева тако да сваки следећи члан буде већи од претходног и следећег елемента. Претпоставимо да низ не садржи дупле елементе.
Сортирање низа или коришћење додатног простора није неопходно за ефикасан приступ. План је, за почетак, други члан низа и повећање за два за сваку итерацију петље.
Замените компоненте ако је последњи елемент већи од првог. На сличан начин, промените обе ставке ако је следећи елемент већи од тренутног. Добићемо жељени низ који је у складу са наведеним ограничењима на крају петље.
22. Како сваки елемент низа без употребе оператора дељења заменити производом сваког елемента у низу?
Без коришћења оператора дељења, замените сваки елемент у целобројном низу производом свих осталих елемената.
У линеарном времену и константном простору, можемо користити рекурзију за решавање овог проблема. Рекурзивно израчунавање производа сваког елемента у десном поднизу и преношење производа левог подниза као параметара функције је појам.
Временска сложеност је О(н).
23. Пронађите најчуднији елемент у низу у логаритамском времену
С обзиром на целобројни низ у којем сви осим једног члана имају паран број појављивања, проблем је одредити колико пута се овај елемент појављује. Пронађите непарни елемент који се појављује у логаритамском времену и константном простору ако се исти елементи јављају у паровима у низу и никада не може бити више од две инстанце датог елемента у низу.
Операција КСОР нам омогућава да решимо овај проблем у линеарном времену. Циљ је КСОР сваки елемент у низу. Само непарни елементи остају након што се парни елементи међусобно поништавају.
Овај проблем се чак може решити за О(лог(н)) времена.
24. Како добити следећи већи елемент за сваки елемент у кружном низу?
Следећи већи елемент за сваки елемент у кружном низу целих бројева треба да буде лоциран. Први већи цео број после елемента к у низу је следећи већи елемент тог елемента.
С десна на лево, можемо да радимо на ставкама низа. Циљ је направити петљу за сваки елемент к све док се стек не испразни или док не будемо имали виши елемент на њему. Поставите следећи већи елемент од к да се појави на врху стека када се појави.
25. Наћи број инверзија низа?
Пронађите укупан број инверзија низа. Пар И ј) се назива инверзијом низа А ако је И ј) и (А[и] > А[ј]). Морамо пребројати сваки пар ових у низу.
Бројање свих чланова низа који су мањи од њега десно и додавање резултата излазу је једноставан приступ.
Ово решење има О(н2) сложеност, где је н величина улаза.
26. Шта је проблем задржавања кишнице?
Проналажење највеће количине воде која се може заробити у датом низу шипки ширине од једне јединице познато је као проблем „заробљавања падавина“.
Циљ је одредити највишу траку која се може поставити лево и десно од сваке шипке. Минимум водећих шипки лево и десно, умањен за висину тренутне траке, је количина воде која је ускладиштена на врху сваке шипке.
Zakljucak
У поређењу са другим темама о структури података, низови су једноставнији. Да бисте одговорили на питања за интервју са низом, морате имати темељно разумевање низова.
Требало би да детаљно прегледате основе низова, укључујући операције низа (од декларисања/креирања низа до приступања/модификовања ставки низа), као и концепте програмирања као што су петље, рекурзија и основни оператори да бисте успешно одговорили на питања у интервјуу за низ. Препознајте проблем у потпуности.
Требало би да тражите појашњење ако имате било каквих питања. Размислите о подели проблема на делове којима је лакше управљати. Уверите се да имате алгоритам на уму пре него што почнете са програмирањем; запишите или визуализујте у дијаграму тока. затим почните да пишете код.
Ostavite komentar