Съдържание[Крия][Покажи]
- 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 или друг технологичен бизнес от ниво 1.
В повечето интервюта за програмиране той е на второ място след Strings. Масивът е групиране на свързани елементи от данни, съхранявани в непосредствена близост един до друг в паметта.
Тъй като са свързани с всички езици за програмиране, като C, C++, Java, Python, Perl и Ruby, те са навсякъде. Продължете да четете за някои практически предизвикателства при кодиране и въпроси и отговори на интервю, базирани на масиви.
Python ще бъде използван в тази публикация за справяне с проблемите с кодирането, защото е лесен за използване, разбираем и трябва да е познат на повечето от нас.
Нека да започнем.
1. Как се дефинира масив?
- Група от свързани типове данни е масив.
- Масивите винаги са фиксирани.
- Същият вид променлива се съхранява на няколко места от масивни обекти.
- Примитивните типове и препратките към обекти са съвместими с него.
2. Динамични масиви: какво представляват те? Какво ги отличава от основните масиви?
Автоматичното мащабиране, което предоставят динамичните масиви (наричани също нарастващи масиви, масиви с възможност за промяна на размера, променливи масиви или ArrayLists в Java), е значително предимство.
Винаги трябва да знаете колко елемента вашият масив ще съхранява предварително, тъй като масивите имат фиксиран размер. Динамичният масив, от друга страна, расте, когато добавяте допълнителни членове към него, така че не е необходимо да знаете точния му размер предварително.
3. Как се различават един от друг масив и речник?
Това е базиран на основи набор от въпроси за интервю, които се задават редовно. Следните са основните разлики между масиви и речници:
- Масивът е подреден списък от подобни елементи. Речникът, от друга страна, има двойки ключ-стойност.
- Размерите на масивите могат да се променят динамично. Такива динамични идеи не съществуват в речниците.
- Преди да използвате масив, неговият размер трябва да бъде уточнен. Размерите на речника не е необходимо да се персонализират.
- Използвайте командата Redim, ако искате да разширите размера на масива. В речниците елемент може да се добави без декларация.
4. Избройте някои от предимствата и недостатъците на масивите.
Предимства:
- Масивите могат да сортират няколко елемента едновременно.
- Други структури от данни, като стекове, опашки, свързани списъци, дървета, графики и т.н., могат да бъдат внедрени в масив.
- Индекс може да се използва за достигане до елемент от масив.
Недостатъци:
- Размерът на масива трябва да бъде деклариран предварително. В момента на деклариране на масива обаче може да не сме наясно с размера, който изискваме.
- Структурата на масива е статична. Това означава, че размерът на масива винаги е фиксиран и че разпределението на паметта не може да се увеличава или намалява.
5. За какво се отнася „Sparse Array“?
Разреденият масив е масив от данни, който има много записи с нулеви стойности. За разлика от това, плътният масив съдържа по-голямата част от своите елементи с ненулеви стойности. Индексите на разреден масив, който преобразува числата в обекти, може да включват пропуски. В сравнение с HashMap, те са по-ефективни откъм памет.
6. Кога бихте избрали свързан списък пред масив?
Когато използвате свързани списъци вместо масиви, помислете за:
- Не са ви необходими елементи, за да имате произволен достъп.
- Когато времевата предсказуемост е от съществено значение, вие се нуждаете от постоянно време вмъквания и премахвания от списъка.
- За да създадете приоритетна опашка, може да се наложи да поставите елементи в центъра на списъка.
- Нямате представа колко дълъг ще бъде списъкът. Ако размерът на масива се увеличи, трябва да декларирате отново и да дублирате паметта, точно както при обикновените масиви.
7. Какво отличава индексирания масив от асоциативния масив?
Основните разлики между асоциативни и индексирани масиви са изброени в следващата таблица.
- Двойка ключ-стойност в текстов или цифров формат се използва за сортиране на асоциативен масив. Всички ключове на индексирания масив са числови и всеки ключ е свързан с отделна стойност.
- В асоциативен масив ключът може да бъде низ. Индексиран масив с целочислени ключове, започващи от 0.
- Таблица с две колони имитира поведението на асоциативен масив. Подобно на таблица с една колона са индексираните масиви.
- Картите са тип асоциативен масив. Индексният масив не е карта.
8. Какви предимства има Heap пред сортираните масиви?
Ефективността на времето от използването на 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, ако I j) и (A[i] > A[j]). Трябва да преброим всяка двойка от тях в масива.
Преброяването на всички членове на масива, които са по-малко от него вдясно, и добавянето на резултата към изхода е лесен подход.
Това решение има O(n2) сложност, където n е размерът на входа.
26. Какъв е проблемът с улавянето на дъждовната вода?
Намирането на най-много вода, която може да бъде уловена в даден набор от ленти с ширина от една единица всяка, е известно като проблем с „улавянето на валежите“.
Целта е да се определи най-високата лента, която може да бъде поставена отляво и отдясно на всяка лента. Минимумът на водещите ленти отляво и отдясно, минус височината на текущата лента, е количеството вода, което се съхранява в горната част на всяка лента.
Заключение
В сравнение с други теми за структура на данни, масивите са по-прости. За да отговаряте на въпроси за интервю за масиви, трябва да имате фундаментално разбиране за масивите.
Трябва да прегледате задълбочено основите на масивите, включително операциите с масиви (от деклариране/създаване на масив до достъп до/модифициране на елементи от масив), както и концепции за програмиране като цикли, рекурсия и основни оператори, за да отговорите успешно на въпроси за интервю за масиви. Признайте напълно проблема.
Трябва да потърсите разяснение, ако имате някакви въпроси. Помислете за разделянето на проблема на по-управляеми части. Уверете се, че имате предвид алгоритъма, преди да започнете да програмирате; запишете го или го визуализирайте в блок-схема. след това започнете да пишете код.
Оставете коментар