Мазмұны[Жасыру][Көрсету]
- 1. Массивті қалай анықтауға болады?
- 2. Динамикалық массивтер: олар қандай? Олардың негізгі массивтерден айырмашылығы неде?
- 3. Массив пен сөздік бір-бірінен қалай ерекшеленеді?
- 4. Массивтердің кейбір артықшылықтары мен кемшіліктерін көрсетіңіз.
- 5. «Сирек массив» нені білдіреді?
- 6. Жиым орнына байланыстырылған тізімді қашан таңдар едіңіз?
- 7. Индекстелген массивтің ассоциативті массивтен айырмашылығы неде?
- 8. Үйменің сұрыпталған массивтерден қандай артықшылығы бар?
- 9. Массив өлшемін теріс деп анықтай аламыз ба?
- 10. 1 ден 100 элементке дейінгі массивте жетіспейтін бүтін санды қалай табуға болады?
- 11. Массивтегі элементтің индексін қалай табуға болады?
- 12. Массивтен белгілі бір элементті қалай алып тастауға болады?
- 13. Екі массивтің теңдігін қалай тексеруге болады?
- 14. Массивтерді талқылағанда, «Өлшем» және «Жіберу» тіркестерін қалай түсінесіз?
- Сұхбат сұрақтарын кодтау
- 15. Көрсетілген қосындысы бар массивтен жұпты іздеңіз
- 16. Сызықтық уақыт бойынша екілік массивтерді сұрыптау
- 17. Жиымдағы ең үлкен екі int көбейтіндісін табыңыз.
- 18. Массивтің барлық нөлдерін соңына дейін қалай ауыстыруға болады
- 19. Бір операцияда ауыстырылатын екі жазбасы бар массив қалай сұрыпталады.
- 20. Екі сұрыпталған массивтерді орнында қалай біріктіруге болады.
- 21. Ауыспалы жоғары және төмен позициялардағы элементтер массивінің ретін қалай өзгертуге болады?
- 22. Бөлу операторын қолданбай, массивтің әрбір элементін массивтің әрбір элементінің көбейтіндісіне қалай ауыстыруға болады?
- 23. Логарифмдік уақыт бойынша массивтің ең тақ элементін табыңыз
- 24. Дөңгелек массивтің әрбір элементі үшін келесі үлкен элементті қалай алуға болады?
- 25. Массивтің инверсия санын табыңыз?
- 26. Жаңбыр суын ұстау мәселесі қандай?
- қорытынды
Кодтау сұхбатында DSA сұрақтары бар. Егер сіз FAANG немесе басқа деңгейдегі 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. Екі массивтің теңдігін қалай тексеруге болады?
Алдымен берілген екі массивтің ұзындығын тексеру керек. Екі массивтің сәйкес элементтері олардың ұзындығы тең болғанда салыстырылады. Екі массив тең деп есептеледі. егер әрбір сәйкестіктегі компоненттердің әрбір жұбы тең болса. Массивтердің өлшемі үлкен болса, бұл тәсіл екі массивтің теңдігін тексеру ұсынылмайды, себебі бұл көп уақытты алады. Сіз сондай-ақ Массивтер сыныбына енгізілген equals() әдісін пайдалана аласыз, бірақ сұхбат алушы кірістірілген әдістерді қолданбай екі массивді салыстыруды сұраса, бұл әдіс пайдалы болады.
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. Жиымдағы ең үлкен екі int көбейтіндісін табыңыз.
Бүтін массивтегі екі санның ең үлкен көбейтіндісін табыңыз.
Мысал ретінде 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[i] > A[j]), егер I j) жұбы А массивінің инверсиясы деп аталады. Біз массивтегі бұлардың әрбір жұбын санауымыз керек.
Оң жағындағы барлық массив мүшелерін санау және нәтижені нәтижеге қосу - қарапайым тәсіл.
Бұл шешімнің O(n2) күрделілігі бар, мұндағы n – кіріс өлшемі.
26. Жаңбыр суын ұстау мәселесі қандай?
Әрқайсысының ені бір бірлік болатын жолақтардың берілген жинағында ұстауға болатын ең көп суды табу «жауын-шашынды ұстау» мәселесі ретінде белгілі.
Мақсат - әр жолақтың сол және оң жағында орналасуы мүмкін ең жоғары жолақты анықтау. Сол және оң жақтағы жетекші жолақтардың ең азы, ағымдағы жолақтың биіктігін азайтқанда, әрбір жолақтың үстінде сақталатын судың мөлшері.
қорытынды
Басқа деректер құрылымы тақырыптарымен салыстырғанда массивтер қарапайым. Массив бойынша сұхбат сұрақтарын шешу үшін сіз массивтер туралы іргелі түсінікке ие болуыңыз керек.
Жиым сұхбатының сұрақтарына сәтті жауап беру үшін сіз массивтердің негіздерін, соның ішінде массив операцияларын (массивті жариялау/жасаудан массив элементтеріне қатынасуға/өзгертуге дейін), сонымен қатар циклдар, рекурсия және негізгі операторлар сияқты бағдарламалау тұжырымдамаларын жан-жақты қарап шығуыңыз керек. Мәселені толығымен мойындаңыз.
Қандай да бір сұрақтарыңыз болса, түсініктеме алуыңыз керек. Мәселені басқарылатын бөліктерге бөлу туралы ойланыңыз. Бағдарламалауды бастамас бұрын алгоритмді есте сақтаңыз; оны жазыңыз немесе блок-схемада визуализациялаңыз. содан кейін кодты жазуды бастаңыз.
пікір қалдыру