Змест[Схаваць][Паказаць]
- 1. Як вы вызначаеце масіў?
- 2. Дынамічныя масівы: што гэта? Што адрознівае іх ад асноўных масіваў?
- 3. Чым адрозніваюцца адзін ад аднаго масіў і слоўнік?
- 4. Пералічыце некаторыя перавагі і недахопы масіваў.
- 5. Што азначае «Разрэджаны масіў»?
- 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 або іншым тэхналагічным бізнесам першага ўзроўню.
У большасці інтэрв'ю па кадзіраванню ён займае другое месца пасля Strings. Масіў - гэта група звязаных элементаў даных, якія захоўваюцца ў памяці ў непасрэднай блізкасці адзін ад аднаго.
Паколькі яны звязаны з усімі мовамі праграмавання, такімі як C, C++, Java, Python, Perl і Ruby, яны паўсюль. Працягвайце чытаць некаторыя задачы па практыцы кадавання і пытанні і адказы на інтэрв'ю на аснове масіваў.
Python будзе выкарыстоўвацца ў гэтай публікацыі для вырашэння праблем кадавання, таму што ён просты ў выкарыстанні, зразумелы і павінен быць знаёмы большасці з нас.
Давайце пачнем.
1. Як вы вызначаеце масіў?
- Група звязаных тыпаў даных - гэта масіў.
- Масівы заўсёды фіксаваныя.
- Аднатыпная зменная захоўваецца ў некалькіх месцах аб'ектамі масіва.
- Прымітыўныя тыпы і спасылкі на аб'екты сумяшчальныя з ім.
2. Дынамічныя масівы: што гэта? Што адрознівае іх ад асноўных масіваў?
Аўтаматычнае маштабаванне, якое забяспечваюць дынамічныя масівы (якія таксама называюць масівамі з магчымасцю павелічэння, масівамі з магчымасцю змены памеру, масівамі з магчымасцю змены або ArrayLists у Java), з'яўляецца значнай перавагай.
Вы заўсёды павінны загадзя ведаць, колькі элементаў будзе захоўваць ваш масіў, паколькі масівы маюць фіксаваны памер. З іншага боку, дынамічны масіў павялічваецца па меры дадання дадатковых членаў, таму вам не трэба загадзя ведаць яго дакладны памер.
3. Чым адрозніваюцца адзін ад аднаго масіў і слоўнік?
Гэта заснаваны на асновах набор пытанняў для інтэрв'ю, якія рэгулярна задаюць. Ніжэй прыведзены асноўныя адрозненні паміж масівамі і слоўнікамі:
- Масіў - гэта ўпарадкаваны спіс падобных элементаў. З іншага боку, у слоўніку ёсць пары ключ-значэнне.
- Памеры масіва могуць змяняцца дынамічна. Такіх дынамічных уяўленняў няма ў слоўніках.
- Перш чым выкарыстоўваць масіў, неабходна вызначыць яго памер. Памеры слоўніка не трэба наладжваць.
- Выкарыстоўвайце аператар Redim, калі хочаце павялічыць памер масіва. У слоўніках элемент можа быць дададзены без дэкларацыі.
4. Пералічыце некаторыя перавагі і недахопы масіваў.
Перавагі:
- Масівы могуць сартаваць некалькі элементаў адначасова.
- іншае структуры дадзеных, як стэкі, чэргі, звязаныя спісы, дрэвы, графы і г.д., могуць быць рэалізаваны ў масіве.
- Для дасягнення элемента масіва можна выкарыстоўваць індэкс.
Недахопы:
- Памер масіва павінен быць заяўлены загадзя. Аднак у момант дэкларацыі масіва мы можам не ведаць, які памер нам патрабуецца.
- Структура масіва статычная. Гэта азначае, што памер масіва заўсёды фіксаваны і што размеркаванне памяці не можа быць павялічана або паменшана.
5. Што азначае «Разрэджаны масіў»?
Разрэджаны масіў - гэта масіў даных, які змяшчае шмат запісаў з нулявымі значэннямі. Наадварот, шчыльны масіў змяшчае большасць сваіх элементаў з ненулявымі значэннямі. Індэксы разрэджанага масіва, які пераўтворыць лікі ў аб'екты, могуць утрымліваць прабелы. У параўнанні з 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 }
Простым падыходам было б вылічыць агульную колькасць нулёў у масіве, скажам, k, а затым запоўніць першыя k індэксаў у масіве нулямі, а астатнія індэксы - 0. У якасці альтэрнатывы мы можам падлічыць, колькі адзінак усяго ў масіве масіў k, запоўніце апошнія k індэксаў у масіве 0, а астатнія індэксы пакіньце запоўненымі 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, пакуль альбо стэк не стане пустым, альбо мы не атрымаем вышэйшы элемент на яго вяршыні. Усталюйце, каб наступны большы элемент x з'яўляўся на вяршыні стэка, калі ён з'яўляецца.
25. Знайсці колькасць інверсій масіва?
Знайдзіце агульную колькасць інверсій масіва. Пара I j) называецца інверсіяй масіва A, калі I j) і (A[i] > A[j]). Мы павінны падлічыць кожную пару з іх у масіве.
Падлік усіх членаў масіва, якія знаходзяцца менш за яго справа, і даданне выніку да вываду - просты падыход.
Гэтае рашэнне мае складанасць O(n2), дзе n - памер уваходных дадзеных.
26. Што такое праблема ўлоўлівання дажджавой вады?
Пошук найбольшай колькасці вады, якая можа быць захоплена ў дадзеным наборы палос шырынёй у адну адзінку кожная, вядома як праблема «захопу ападкаў».
Мэта складаецца ў тым, каб вызначыць самую высокую планку, якая можа быць размешчана злева і справа ад кожнай паласы. Мінімальная колькасць вядучых слупкоў злева і справа, за вылікам вышыні бягучага слупка, - гэта колькасць вады, якая захоўваецца ў верхняй частцы кожнага слупка.
заключэнне
У параўнанні з іншымі тэмамі структуры даных, масівы больш простыя. Для таго, каб адказваць на пытанні інтэрв'ю з масівам, вам трэба мець фундаментальнае разуменне масіваў.
Вы павінны падрабязна разгледзець асновы масіваў, у тым ліку аперацыі з масівам (ад аб'яўлення/стварэння масіва да доступу/змянення элементаў масіва), а таксама паняцці праграмавання, такія як цыклы, рэкурсія і асноўныя аператары, каб паспяхова адказаць на пытанні інтэрв'ю з масівам. Прызнайце праблему цалкам.
Калі ў вас ёсць якія-небудзь пытанні, вам варта звярнуцца па тлумачэнні. Падумайце аб падзеле праблемы на больш кіраваныя часткі. Упэўніцеся, што ў вас ёсць алгарытм перад тым, як пачаць праграмаванне; запішыце або візуалізуйце гэта ў блок-схеме. затым пачніце пісаць код.
Пакінуць каментар