Содржина[Крие][Прикажи]
- 1. Како дефинирате низа?
- 2. Динамички низи: што се тие? Што ги издвојува од основните низи?
- 3. Како се разликуваат низата и речникот еден од друг?
- 4. Наведете некои од придобивките и недостатоците на низите.
- 5. На што се однесува „Sparse Array“?
- 6. Кога би избрале поврзан список преку низа?
- 7. Што разликува индексирана низа од асоцијативна низа?
- 8. Какви предности има Heap во однос на подредените низи?
- 9. Можеме ли да ја дефинираме големината на низата да биде негативна?
- 10. Како да го лоцирате цел број што недостасува во низа од 1 до 100 елементи?
- 11. Како се наоѓа индексот на елемент во низа?
- 12. Како можете да се ослободите од одреден елемент од низата?
- 13. Како може да се потврди еднаквоста на две низи?
- 14. Кога разговараме за низи, што мислите со фразите „Димензија“ и „Подлог“?
- Кодирање прашања за интервју
- 15. Побарајте пар во низа што ја има одредената сума
- 16. Сортирање на бинарни низи со линеарно време
- 17. Најдете го најголемиот двоинтен производ во низа.
- 18. Како да се префрлат сите нули на низата до крај
- 19. Како да се сортира низа со два записи кои се префрлуваат во една операција.
- 20. Како да се комбинираат две подредени низи на место.
- 21. Како да се преуреди низа ставки на наизменични високи и ниски позиции?
- 22. Како да се замени секој елемент од низата без да се користи оператор за делење со производот на секој елемент во низата?
- 23. Најдете го најчудниот елемент во низата во логаритамско време
- 24. Како да се добие следниот поголем елемент за секој елемент во кружна низа?
- 25. Најдете го бројот на инверзија на низа?
- 26. Што е проблемот со заробување на дождовната вода?
- Заклучок
Интервјуата за кодирање содржат серија прашања за DSA. Треба да бидете вешти со низи ако се подготвувате за претстојното технолошко интервју со FAANG или друг технолошки бизнис од Tier-1.
Во повеќето интервјуа за кодирање, таа е на второ место по Стрингс. Низата е групација на поврзани податочни елементи кои се чуваат во непосредна близина еден до друг во меморијата.
Бидејќи се поврзани со сите програмски јазици, како што се C, C++, Java, Python, Perl и Ruby, тие се насекаде. Продолжете со читање за некои практикувачки предизвици за кодирање и прашања и одговори на интервју врз основа на низи.
Python ќе се користи во оваа објава за да се справи со проблемите со кодирањето бидејќи е едноставен за користење, разбирање и мора да биде познат на повеќето од нас.
Да почнеме.
1. Како дефинирате низа?
- Група поврзани типови на податоци е низа.
- Низите се секогаш фиксни.
- Истиот вид на променлива е зачуван на неколку места со објекти од низа.
- Примитивните типови и референци на објекти се компатибилни со него.
2. Динамички низи: што се тие? Што ги издвојува од основните низи?
Автоматското скалирање што го обезбедуваат динамичките низи (исто така познат како растечки низи, низи со промена на големината, променливи низи или ArrayLists во Java) е значајна предност.
Секогаш мора да знаете колку елементи вашата низа ќе складира однапред бидејќи низите имаат фиксна големина. Динамична низа, од друга страна, расте како што додавате дополнителни членови на неа, така што не треба претходно да ја знаете нејзината точна големина.
3. Како се разликуваат низата и речникот еден од друг?
Ова е низа прашања за интервјуа базирани на основи кои редовно се поставуваат. Следниве се клучните разлики помеѓу низите и речниците:
- Низа е подредена листа на слични ставки. Речник, од друга страна, има парови клуч-вредност.
- Големините на низите може динамички да се менуваат. Вакви динамични идеи не постојат во речниците.
- Пред да се користи низа, мора да се наведе нејзината големина. Големините на речник не треба да се приспособуваат.
- Користете ја изјавата Redim ако сакате да ја проширите големината на низата. Во речниците, елемент може да се додаде без декларација.
4. Наведете некои од придобивките и недостатоците на низите.
предности:
- Низите можат да подредат повеќе елементи истовремено.
- други структури на податоци, како стекови, редици, поврзани списоци, дрвја, графикони итн., може да се имплементираат во низа.
- Индексот може да се користи за да се достигне елемент од низата.
Недостатоци:
- Големината на низата мора однапред да се декларира. Меѓутоа, во моментот на декларирање на низата, можеби не сме свесни за големината што ја бараме.
- Структурата на низата е статична. Тоа имплицира дека големината на низата е секогаш фиксна и дека распределбата на меморијата не може да се зголеми или намали.
5. На што се однесува „Sparse Array“?
Ретка низа е податочна низа која има многу записи со нула вредности. Спротивно на тоа, густата низа содржи поголемиот дел од нејзините ставки со не-нула вредности. Индексите на ретка низа, која ги претвора броевите во објекти, може да вклучуваат празнини. Во споредба со HashMap, тие се поефикасни за меморија.
6. Кога би избрале поврзан список преку низа?
Кога користите поврзани списоци наместо низи, земете во предвид:
- Не ви се потребни никакви елементи за да имате случаен пристап.
- Онаму каде што временската предвидливост е од суштинско значење, потребни ви се вметнувања и бришења со постојано време од списокот.
- За да креирате приоритетна редица, можеби ќе треба да поставите ставки во центарот на листата.
- Немате идеја колку долга ќе биде листата. Ако големината на низата се зголеми, мора повторно да ја декларирате и дуплирате меморијата, исто како со едноставните низи.
7. Што разликува индексирана низа од асоцијативна низа?
Примарните разлики помеѓу асоцијативните и индексираните низи се наведени во следната табела.
- Пар клуч-вредност во текст или нумерички формат се користи за сортирање на асоцијативна низа. Копчињата на индексираната низа се сите нумерички и секое копче е поврзано со посебна вредност.
- Во асоцијативна низа, клучот може да биде низа. Индексирана низа со целобројни клучеви кои почнуваат од 0.
- Табела со две колони го имитира однесувањето на асоцијативна низа. Слично на табела со една колона се индексирани низи.
- Мапите се тип на асоцијативна низа. Индексната низа не е мапа.
8. Какви предности има Heap во однос на подредените низи?
Временската ефикасност на користењето на куп преку сортирани низи е клучната придобивка. Додека операциите на купот се побрзи, сортирањето низа бара многу време. Купот може да го открие најмалиот елемент значително побрзо отколку што може да се подреди низата.
Дадена збирка броеви може да се подреди на еден од двата начини со помош на подредени низи. Од друга страна, за дадена збирка на броеви, може да има повеќе од еден потенцијален куп.
9. Можеме ли да ја дефинираме големината на низата да биде негативна?
Не, не можеме да дефинираме негативен цел број да биде со големина на низа. Нема да има грешка во времето на компајлирање ако изјавиме. За време на извршувањето, сепак, ќе наидеме на NegativeArraySizeException.
10. Како да го лоцирате цел број што недостасува во низа од 1 до 100 елементи?
Вкупниот број на сериите може да се пресмета со примена на следнава функција: n (n + 1) / 2
Само ако низата нема дупликати или недостасува повеќе од еден цел број, оваа функција ќе работи. Без разлика дали низата има дупликати елементи, можете да ја сортирате низата за да видите дали има елементи што се еквивалентни.
11. Како се наоѓа индексот на елемент во низа?
Индексот на елементот може да се открие преку линеарно или бинарно пребарување. Сè додека не го лоцира совпаѓањето со потребниот елемент, линеарна функција за пребарување се врти над секој елемент во низата. Го враќа индексот откако ќе го лоцира соодветниот елемент. Следствено, временската сложеност на линеарното пребарување е O. (n). И сортирана и несортирана низа може да користат линеарно пребарување.
Користејќи бинарно пребарување, кое постојано ја дели низата на половина додека медијаната на интервалот не се совпадне со бараниот елемент и го обезбеди индексот, можете да го добиете индексот на елементот ако низата е подредена. Следствено, временската сложеност на бинарното пребарување е O. (log n).
12. Како можете да се ослободите од одреден елемент од низата?
Бидејќи не можете едноставно да ги избришете елементите од оригиналната низа бидејќи тие се фиксни множества со дефинирана големина, интервјуерот бара од вас да предложите поинаков пристап и да се справите со проблемот што го поставува прашањето. Најдобар начин на дејствување е да се направи нова низа за да се избрише елемент. Можете да ги дуплирате елементите од првата низа во оваа низа и да го вклучите само елементот што сакате да го избришете.
Друга стратегија вклучува наоѓање на целниот елемент во низата и потоа менување на редоследот на сите ставки кои се десно од целниот елемент.
13. Како може да се потврди еднаквоста на две низи?
Прво мора да ги потврдите должините на двете обезбедени низи. Соодветните ставки на двете низи се споредуваат кога нивните должини се еднакви. Двете низи ќе се сметаат за еднакви. ако секој пар компоненти во секоја кореспонденција е еднаков. Овој пристап не се препорачува да се провери еднаквоста на две низи ако низите се големи по големина бидејќи ќе одземе многу време. Може да го користите и методот equals() вклучен во класата Arrays, меѓутоа, ако интервјуерот побара од вас да споредите две низи без да користите вградени методи, овој начин ќе биде корисен.
14. Кога разговараме за низи, што мислите со фразите „Димензија“ и „Подлог“?
„Димензијата“ на низата е бројот на индекси, или претплати, потребни за да се идентификува секој поединечен член. Претплатите и димензиите можеби се нејасни. Димензијата е опис на опсегот на дозволени клучеви, додека претплата е број. Потребен е само еден подлог за секоја димензија на низата.
На пример, низата arr[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, да речеме k, а потоа да се пополнат првите k индекси во низата со 0, а останатите индекси со 1. Како алтернатива, можеме да пресметаме колку 1 се вкупно во низата k, пополнете ги последните k индекси во низата со 1, а останатите индекси оставете ги пополнети со 0.
Дадениот пристап има O(n) временска сложеност и не користи дополнително складирање, каде што n е големината на влезот.
17. Најдете го најголемиот двоинтен производ во низа.
Најдете го најголемиот производ од два броја во цела низа.
Размислете за низата 10 3 5 6 2 како пример. Парот (-10, -3) или (5, 6) е највисокиот производ.
Да се размислува за секоја комбинација на елементи и да се открие нивниот производ е глупав пристап. Ако производот на тековниот пар е поголем од максималниот производ добиен досега, ажурирајте го максималниот производ. Последно испечатете ги компонентите на финалниот производ.
Горенаведеното решение, каде што n е количината на влезот, има временска сложеност од O(n2) и не зазема повеќе простор.
18. Како да се префрлат сите нули на низата до крај
Поместете ги сите нули во цела низа до крај. Одговорот треба да избегне користење на постојан простор и да го зачува релативниот редослед на компонентите на низата.
Влез: {1,2,3,0,8,0,4,7}
Излезот ќе биде {1,2,3,8,4,7,0,0}
Ставете го елементот на следната достапна позиција во низата ако моменталниот елемент не е нула. Пополнете ги сите преостанати индекси со 0 откако сите ставки од низата ќе бидат обработени.
Претходното решение има O(n) временска сложеност, каде што n е големината на влезот.
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]
Почнувајќи со вториот елемент во низата, целта е да се спореди секој елемент со неговиот претходник. Позицијата на спорот се зачувува со земање два покажувачи, x и y.
Ажурирајте го x на индексот на претходниот елемент и y на индексот на тековниот елемент ако првиот е поголем од вториот. Ажурирајте го y на индексот на тековниот елемент ако се покаже дека претходниот елемент е поголем од тековниот елемент.
Конечно, префрлете ги елементите на индексите x и y откако ќе завршиме со обработката на секој соседен пар елементи.
Поради фактот што гореспоменатиот метод врши само едно скенирање на влезната низа со големина n, неговата временска сложеност е O(n). Не е потребна дополнителна просторија за решението.
20. Како да се комбинираат две подредени низи на место.
Спојте ги ставките од низите X[] и Y[] - две подредени низи со големина m и n секоја - со задржување на подредениот редослед, односно со пополнување на X[] со првите m најмали елементи и пополнување Y[] со преостанатите елементи.
Ако елементот во низата X[] е веќе на вистинската позиција (т.е. оној што е најмал меѓу преостанатите елементи), игнорирајте го; во спротивно, заменете го со најмалиот елемент, кој исто така е првиот член на Y[]. За да го задржите подредениот редослед по замената, префрлете го елементот (сега на Y[0]) на неговата соодветна локација во Y[].
Големината на првата низа е m и големината на втората низа е n, а временската сложеност е O(mn).
21. Како да се преуреди низа ставки на наизменични високи и ниски позиции?
Преуредете ја цела низа така што секој следен член да биде поголем од претходните и следните елементи. Да претпоставиме дека низата не вклучува никакви дупликати елементи.
Сортирањето на низата или користењето дополнителен простор не е неопходно за ефективен пристап. Планот е, за почеток, вториот член на низата и да се зголемува за два за секое повторување на јамката.
Заменете ги компонентите ако последниот елемент го надминува првиот. На сличен начин, префрлете ги двете ставки ако следниот елемент е поголем од тековниот елемент. Ќе ја добиеме саканата низа што е во согласност со наведените ограничувања на крајот на циклусот.
22. Како да се замени секој елемент од низата без да се користи оператор за делење со производот на секој елемент во низата?
Без користење на операторот за поделба, заменете го секој елемент во цела низа со производот на сите други елементи.
Во линеарно време и константен простор, можеме да користиме рекурзија за да го решиме ова прашање. Рекурзивно пресметување на производите на секој елемент во десната подниза и пренесување на производ од левата подниза како параметри на функцијата е поимот.
Временската сложеност е O(n).
23. Најдете го најчудниот елемент во низата во логаритамско време
Со оглед на цела низа во која сите до еден член имаат парен број на појави, проблемот е да се одреди колку пати овој елемент се појавува. Најдете го непарниот елемент во логаритамско време и константен простор ако истите елементи се појавуваат во парови во низата и никогаш не може да има повеќе од два примери на даден елемент по ред.
Операцијата XOR ни овозможува да го решиме ова прашање во линеарно време. Целта е да се XOR секој елемент во низата. Само непарните елементи остануваат откако парните елементи се поништуваат едни со други.
Овој проблем може да се реши дури и во O(log(n)) време.
24. Како да се добие следниот поголем елемент за секој елемент во кружна низа?
Треба да се лоцира следниот поголем елемент за секој елемент во кружна цела низа. Првиот поголем цел број по елементот x во низата е последователниот поголем елемент на тој елемент.
Од десно кон лево, може да работиме на ставки од низа. Целта е да се направи јамка за секој елемент x додека оџакот не се испразни или немаме повисок елемент над него. Поставете го следниот поголем елемент од x да се појавува на врвот на оџакот кога ќе се појави.
25. Најдете го бројот на инверзија на низа?
Најдете го вкупниот број на инверзии на низа. Пар I j) се нарекува инверзија на низа A ако јас j) и (A[i] > A[j]). Мора да го броиме секој пар од нив во низата.
Броењето на сите членови на низата кои се помалку од него десно и додавањето на резултатот на излезот е директен пристап.
Ова решение има O(n2) сложеност, каде што n е големината на влезот.
26. Што е проблемот со заробување на дождовната вода?
Наоѓањето на најмногу вода што може да се зароби во даден сет на шипки со ширина од по една единица е познато како прашање на „заробување на врнежите“.
Целта е да се одреди највисоката лента што може да се постави лево и десно од секоја лента. Минимумот од водечките шипки лево и десно, помалку од висината на тековната лента, е количината на вода што се складира на врвот на секоја шипка.
Заклучок
Во споредба со другите теми за структурата на податоците, низите се поедноставни. За да одговорите на прашањата за интервју со низа, треба да имате фундаментално разбирање за низите.
Треба опширно да ги прегледате основите на низите, вклучително и операциите на низи (од декларирање/создавање низа до пристап/измена на ставки од низа), како и концепти за програмирање како циклуси, рекурзија и основни оператори со цел успешно да одговорите на прашања за интервју со низа. Препознајте го проблемот целосно.
Треба да побарате појаснување ако имате какви било прашања. Размислете да го поделите проблемот на повеќе податливи делови. Проверете дали го имате на ум алгоритмот пред да започнете со програмирање; запишете го или визуелизирајте го во дијаграм на текови. потоа започнете со пишување код.
Оставете Одговор