Мазмуну[Жашыруу][Көрсөтүү]
- 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. Жамгыр суусун кармоо маселеси эмнеде?
- жыйынтыктоо
Коддоо интервьюлары DSA суроолорунун бир катар камтыйт. Эгер сиз FAANG же башка Tier-1 технологиялык бизнеси менен алдыдагы технологиялык интервьюңузга даярданып жатсаңыз, массивдер боюнча чебер болушуңуз керек.
Көпчүлүк коддоо интервьюларында ал Strings экинчи орунда турат. Массив - эстутумда бири-бирине жакын сакталган тиешелүү маалымат элементтеринин топтому.
Алар C, C++, Java, Python, Perl жана Ruby сыяктуу бардык программалоо тилдерине туташтырылгандыктан, алар бардык жерде. Кээ бир практикалык коддоо көйгөйлөрүн окууну улантыңыз жана массивдерге негизделген интервью суроолору жана жооптору.
Python бул постто коддоо маселелерин чечүү үчүн колдонулат, анткени аны колдонуу оңой, түшүнүү жана көпчүлүгүбүзгө тааныш болушу керек.
Кудайдын баштайлы.
1. Массивди кантип аныктайсыз?
- Байланышкан маалымат түрлөрүнүн тобу массив болуп саналат.
- Массивдер ар дайым бекитилет.
- Бир эле түрдөгү өзгөрмө массив объекттери тарабынан бир нече жерде сакталат.
- Примитивдик типтер жана объекттик шилтемелер аны менен шайкеш келет.
2. Динамикалык массивдер: Алар эмне? Аларды негизги массивдерден эмнеси менен айырмалап турат?
Динамикалык массивдер (ошондой эле өстүрүлүүчү массивдер, өлчөмү өзгөрүлүүчү массивдер, өзгөрүлүүчү массивдер же Javaдагы ArrayLists деп аталат) автоматтык түрдө масштабдоо маанилүү артыкчылык болуп саналат.
Сиз ар дайым массивиңиз канча элементти сактай турганын алдын ала билишиңиз керек, анткени массивдердин белгиленген өлчөмү бар. Динамикалык массив, тескерисинче, ага кошумча мүчөлөрдү кошкон сайын өсөт, андыктан анын так өлчөмүн алдын ала билүүнүн кереги жок.
3. Массив менен сөздүк бири-биринен кандайча айырмаланат?
Бул үзгүлтүксүз берилүүчү интервью суроолорунун негиздерине негизделген массив. Төмөндө массивдер менен сөздүктөрдүн ортосундагы негизги айырмачылыктар бар:
- Массив - бул окшош нерселердин иреттелген тизмеси. Сөздүк, экинчи жагынан, ачкыч-маани жуптары бар.
- Массивдин өлчөмдөрү динамикалык түрдө өзгөрүшү мүмкүн. Мындай динамикалуу идеялар сөздүктөрдө жок.
- Массивди колдонуудан мурун анын өлчөмү көрсөтүлүшү керек. Сөздүк өлчөмдөрүн ыңгайлаштыруунун кереги жок.
- Эгер массивдин өлчөмүн кеңейтүүнү кааласаңыз, Redim операторун колдонуңуз. Сөздүктөрдө элементти декларациясыз кошууга болот.
4. Массивдердин кээ бир артыкчылыктарын жана кемчиликтерин тизмектеңиз.
артыкчылыктары:
- Массивдер бир эле учурда бир нече элементтерди иреттей алат.
- башка маалымат структуралары, мисалы, стектер, кезектер, байланышкан тизмелер, дарактар, графиктер ж.б., массивде ишке ашырылышы мүмкүн.
- Индекс массивдин элементине жетүү үчүн колдонулушу мүмкүн.
кемчиликтери:
- Массивдин өлчөмү алдын ала жарыяланышы керек. Массивди жарыялоо учурунда, биз талап кылган өлчөмдөрдү биле албашыбыз мүмкүн.
- Массивдин структурасы статикалык. Бул массивдин өлчөмү ар дайым туруктуу экендигин жана эстутум бөлүштүрүүнү көбөйтүү же азайтуу мүмкүн эмес экенин билдирет.
5. «Сейрек массив» эмнени билдирет?
Сейрек массив – бул нөл маанилери бар көптөгөн жазууларды камтыган маалымат массиви. Ал эми, жыш массив нөл эмес маанилери бар анын элементтеринин көпчүлүгүн камтыйт. Сандарды объекттерге айландыруучу сейрек массивдин индекстери боштуктарды камтышы мүмкүн. HashMap менен салыштырганда, алар эстутумду үнөмдүү.
6. Качан массивдин ордуна шилтемеленген тизмени тандайт элеңиз?
Массивдердин ордуна шилтемеленген тизмелерди колдонууда төмөнкүлөрдү эске алыңыз:
- Кокус жетүү үчүн эч кандай элементтердин кереги жок.
- Убактылуу алдын ала билүү маанилүү болгон учурда, тизмеден туруктуу убакыт киргизүү жана алып салуу керек.
- Приоритеттүү кезекти түзүү үчүн, сиз элементтерди тизменин ортосуна коюшуңуз керек болушу мүмкүн.
- Сиз тизме канчага созулаарын билбейсиз. Массивдин өлчөмү чоңойсо, жөнөкөй массивдердегидей эле эстутумду кайра жарыялоо жана кайталоо керек.
7. Индекстелген массив ассоциативдик массивден эмнеси менен айырмаланат?
Ассоциативдик жана индекстелген массивдердин ортосундагы негизги айырмачылыктар төмөнкү таблицада келтирилген.
- Ассоциативдик массивди иреттөө үчүн тексттик же сандык форматтагы ачкыч-маани жуптары колдонулат. Индекстелген массивдин ачкычтарынын баары сандык жана ар бир ачкыч өзүнчө бир мааниге туташтырылган.
- Ассоциативдик массивде ачкыч сап болушу мүмкүн. 0дөн башталган бүтүн сан баскычтары менен индекстелген массив.
- Эки тилкелүү таблица ассоциативдик массивдин жүрүм-турумун туурайт. Бир мамычалуу таблицага окшош индекстелген массивдер.
- Карталар ассоциативдик массивдин түрү. Индекс массив карта эмес.
8. Хептин сорттолгон массивдерден кандай артыкчылыктары бар?
Сортталган массивдердин үймөгүн колдонуунун убакыттын натыйжалуулугу негизги артыкчылык болуп саналат. Үймөк операциялары тезирээк болгону менен массивди сорттоо көп убакытты талап кылат. Үймөк эң кичинекей элементти массивди иреттегенге караганда тезирээк ача алат.
Берилген сандар жыйнагы Сортталган массивдерди колдонуу менен эки жолдун биринде жайгаштырылышы мүмкүн. Башка жагынан алганда, берилген сандардын жыйнагы үчүн бирден ашык потенциалдуу үймөк болушу мүмкүн.
9. Массивдин өлчөмүн терс деп аныктай алабызбы?
Жок, биз терс бүтүн санды массивдин өлчөмү катары аныктай албайбыз. Эгер биз жарыяласак, компиляция учурунда ката болбойт. Аткаруу убагында биз NegativeArraySizeException менен жолугабыз.
10. 1 ден 100 элементке чейинки массивде жетишпеген бүтүн санды кантип табасыз?
Сериянын жалпы санын төмөнкү функцияны колдонуу менен эсептөөгө болот: n (n + 1) / 2
Массивде эч кандай дубликаттар болбосо же бирден ашык бүтүн сандар жок болсо гана бул функция иштейт. Массивде кайталануучу элементтер барбы, сиз массивдин эквиваленттүү элементтери бар-жоктугун текшерүү үчүн иреттей аласыз.
11. Массивдеги элементтин индексин кантип табасыз?
Элементтин индексин сызыктуу же бинардык издөө аркылуу табууга болот. Керектүү элементтин дал келүүсүн тапканга чейин, сызыктуу издөө функциясы массивдеги ар бир элементтин үстүнөн айланып өтөт. Ал дал келген элементти тапкандан кийин индексти кайтарат. Демек, сызыктуу издөөнүн убактылуу татаалдыгы O. (n). Сорттолгон жана сорттолбогон массив сызыктуу издөөнү колдоно алат.
Интервалдын медианасы талап кылынган элементке дал келгенге чейин массивди тынымсыз экиге бөлүүчү жана индексти камсыз кылган бинардык издөөнү колдонуп, массив иреттелген болсо, элементтин индексин ала аласыз. Демек, бинардык издөөнүн убактылуу татаалдыгы O. (log n).
12. Массивден белгилүү бир элементти кантип алып салууга болот?
Түпнуска массивден элементтерди жөн эле жок кыла албайсыз, анткени алар белгиленген өлчөмдөрү менен белгиленген топтомдор болгондуктан, интервью берүүчү сизден башка ыкманы сунуштап, суроо жараткан көйгөйдү чечүү үчүн издеп жатат. Эң жакшы иш - бул элементти жок кылуу үчүн жаңы массив түзүү. Сиз бул массивдеги биринчи массивдин элементтерин кайталай аласыз жана сиз жок кылгыңыз келген элементти гана кошо аласыз.
Дагы бир стратегия массивден максаттуу элементти таап, андан кийин максаттуу элементтин оң жагында жайгашкан бардык элементтердин тартибин өзгөртүүнү камтыйт.
13. Эки массивдин теңдигин кантип текшерүүгө болот?
Адегенде эки берилген массивдин узундугун текшеришиңиз керек. Эки массивдин дал келген элементтери алардын узундугу бирдей болгондо салыштырылат. Эки массив бирдей деп эсептелинет. эгерде ар бир корреспонденциядагы ар бир жуп компоненттер бирдей болсо. Массивдердин көлөмү чоң болсо, бул ыкма эки массивдин теңдигин текшерүү сунушталбайт, анткени ал көп убакытты талап кылат. Сиз ошондой эле Arrays классына кирген equals() ыкмасын колдонсоңуз болот, бирок интервью алуучу сизден эки массивди орнотулган методдорду колдонбостон салыштырууну суранса, бул ыкма пайдалуу болот.
14. Массивдерди талкуулаганыбызда, “Өлчөм” жана “Бөлчөм” деген сөз айкаштары менен эмнени түшүнөсүз?
Массивдин “Өлчөмү” – бул ар бир мүчөнү идентификациялоо үчүн талап кылынган индекстердин же субскрипттердин саны. Жазуулар жана өлчөмдөр түшүнүксүз болушу мүмкүн. Өлчөм – бул уруксат берилген баскычтардын диапазонунун сүрөттөлүшү, ал эми субскрипт – сан. Ар бир массивдин өлчөмү үчүн бир гана субскрипт талап кылынат.
Мисалы, arr[10][5] массивинин эки өлчөмү бар. Биринде 10, экинчисинде 5 өлчөмү. Анын компоненттерин чечүү үчүн сизге эки жазылуу керек. Экөө тең 0 жана 4 ортосунда; 0 жана 9 ортосундагы бири, анын ичинде.
Интервью суроолорун коддоо
15. Белгиленген суммага ээ болгон массивден жупту издеңиз
Мисалы,
киргизүү:
- сандар = [8, 7, 2, 5, 3, 1]
- максат = 10
Output:
- Жуп табылган (8, 2)
- Or
- Жуп табылган (7, 3)
киргизүү:
- сандар = [5, 2, 6, 8, 1, 9]
- максат = 12
Output:
- Жуп табылган жок
16. Сызыктуу убакыт менен бинардык массивди сорттоо
Бинардык массивди сызыктуу убакытта жана белгиленген аймакта сорттоо. Чыгуу адегенде бардык нөлдөрдү, андан кийин бардыгын көрсөтүүсү керек.
Мисалы,
- Киргизүү: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Чыгуу: { 0, 0, 0, 0, 1, 1, 1, 1 }
Жөнөкөй ыкма массивдин жалпы 0 санын, айталы, k деп эсептеп, андан кийин массивдеги биринчи k индексти 0 менен, ал эми калган индекстерди 1 менен толтуруу болот. k массивинде, массивдеги акыркы k индекстерин 1 менен толтуруңуз, калган индекстерди 1 менен толтуруңуз.
Берилген ыкманын 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 элементин стектин үстүндө пайда болушу үчүн коюңуз.
25. Массивдин инверсия санын табыңыз?
Массивдин инверсияларынын жалпы санын табыңыз. Эгерде I j) жана (A[i] > A[j]) I j) жуптары А массивинин инверсиясы деп аталат. Биз массивдеги булардын ар бир түгөйүн санашыбыз керек.
Андан азыраак болгон массивдин бардык мүчөлөрүн анын оң жагына эсептөө жана натыйжаны чыгарууга кошуу - бул жөнөкөй ыкма.
Бул чечимдин O(n2) татаалдыгы бар, мында n - киргизүүнүн өлчөмү.
26. Жамгыр суусун кармоо маселеси эмнеде?
Ар биринин туурасы бир бирдик болгон тилкелердин берилген топтомунда камалып калышы мүмкүн болгон эң көп сууну табуу “жаан-чачынды кармоо” маселеси деп аталат.
Максат - ар бир тилкенин сол жана оң жагына жайгаштырылышы мүмкүн болгон эң бийик тилкени аныктоо. Сол жана оң тараптагы алдыңкы тилкелердин эң азы, учурдагы тилкенин бийиктиги азыраак, ар бир тилкенин үстүндө сакталган суунун саны.
жыйынтыктоо
Берилиштер структурасынын башка темаларына салыштырмалуу массивдер жөнөкөй. Массивдин интервью суроолоруна жооп берүү үчүн сиз массивдер жөнүндө негизги түшүнүккө ээ болушуңуз керек.
Массивдин негиздерин, анын ичинде массив операцияларын (массивди жарыялоодон/түзүүдөн массив элементтерине жетүү/өзгөртүүгө чейин), ошондой эле массивдин интервью суроолоруна ийгиликтүү жооп берүү үчүн циклдер, рекурсия жана негизги операторлор сыяктуу программалоо түшүнүктөрүн кеңири карап чыгышыңыз керек. Маселени толугу менен таануу.
Суроолоруңуз болсо, түшүндүрмө алышыңыз керек. Маселени башкара турган бөлүктөргө бөлүү жөнүндө ойлонуңуз. Программалоону баштоодон мурун алгоритмди эске алыңыз; аны жазыңыз же блок-схемада элестетиңиз. анан код жазууну баштаңыз.
Таштап Жооп