Содержание[Скрывать][Показывать]
- 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 или другой технологической компанией уровня 1.
В большинстве интервью по программированию он стоит на втором месте после строк. Массив представляет собой группу связанных элементов данных, хранящихся в непосредственной близости друг от друга в памяти.
Поскольку они связаны со всеми языками программирования, такими как C, C++, Java, Python, Perl и Ruby, они повсюду. Продолжайте читать, чтобы узнать о некоторых практических задачах по программированию, а также о вопросах и ответах на собеседованиях, основанных на массивах.
Python будет использоваться в этом посте для решения проблем кодирования, потому что он прост в использовании, понятен и должен быть знаком большинству из нас.
Давай начнем.
1. Как вы определяете массив?
- Группа связанных типов данных представляет собой массив.
- Массивы всегда фиксированы.
- Одинаковые переменные хранятся в нескольких местах объектами массива.
- Примитивные типы и ссылки на объекты совместимы с ним.
2. Динамические массивы: что это такое? Что отличает их от базовых массивов?
Автоматическое масштабирование, которое обеспечивают динамические массивы (также называемые расширяемыми массивами, массивами с изменяемым размером, изменяемыми массивами или ArrayList в Java), является значительным преимуществом.
Вы всегда должны заранее знать, сколько элементов будет храниться в вашем массиве, поскольку массивы имеют фиксированный размер. С другой стороны, динамический массив растет по мере добавления в него дополнительных элементов, поэтому вам не нужно заранее знать его точный размер.
3. Чем массив и словарь отличаются друг от друга?
Это базовый набор вопросов для интервью, которые регулярно задают. Ниже приведены основные различия между массивами и словарями:
- Массив представляет собой упорядоченный список похожих элементов. Dictionary, с другой стороны, имеет пары ключ-значение.
- Размеры массивов могут изменяться динамически. Таких динамических идей нет в словарях.
- Перед использованием массива необходимо указать его размер. Размеры словарей не нужно настраивать.
- Используйте оператор Redim, если вы хотите увеличить размер массива. В словари элемент можно добавить без объявления.
4. Перечислите некоторые преимущества и недостатки массивов.
Преимущества:
- Массивы могут одновременно сортировать несколько элементов.
- Другое структуры данных, такие как стеки, очереди, связанные списки, деревья, графы и т. д., могут быть реализованы в виде массива.
- Индекс можно использовать для доступа к элементу массива.
Минусы:
- Размер массива должен быть объявлен заранее. Однако в момент объявления массива мы можем не знать, какой размер нам нужен.
- Структура массива статична. Это означает, что размер массива всегда фиксирован и выделение памяти не может быть увеличено или уменьшено.
5. Что означает «разреженный массив»?
Разреженный массив — это массив данных, содержащий множество элементов с нулевыми значениями. Напротив, плотный массив содержит большинство элементов с ненулевыми значениями. Индексы разреженного массива, преобразующего числа в объекты, могут содержать пробелы. По сравнению с HashMap они более эффективно используют память.
6. Когда бы вы предпочли связный список массиву?
При использовании связанных списков вместо массивов учитывайте:
- Вам не нужны никакие элементы для произвольного доступа.
- Там, где важна временная предсказуемость, вам нужны вставки и удаления из списка за постоянное время.
- Чтобы создать очередь с приоритетом, вам может потребоваться поместить элементы в центр списка.
- Вы не представляете, насколько длинным будет этот список. Если размер массива увеличивается, вы должны повторно объявить и дублировать память, как и в случае с простыми массивами.
7. Что отличает индексированный массив от ассоциативного массива?
Основные различия между ассоциативными и индексированными массивами перечислены в следующей таблице.
- Пара ключ-значение в текстовом или числовом формате используется для сортировки ассоциативного массива. Все ключи индексированного массива являются числовыми, и каждый ключ связан с отдельным значением.
- В ассоциативном массиве ключ может быть строкой. Индексированный массив с целочисленными ключами, начинающимися с 0.
- Таблица с двумя столбцами имитирует поведение ассоциативного массива. Подобно таблице с одним столбцом индексированные массивы.
- Карты представляют собой тип ассоциативного массива. Массив индексов не является картой.
8. Какие преимущества у кучи перед отсортированными массивами?
Ключевым преимуществом использования Heap вместо Sorted Arrays является экономия времени. Хотя операции с кучей выполняются быстрее, сортировка массива требует много времени. Куча может обнаружить наименьший элемент значительно быстрее, чем массив может быть отсортирован.
Данную коллекцию чисел можно упорядочить одним из двух способов с помощью отсортированных массивов. С другой стороны, для данного набора чисел может быть более одной потенциальной кучи.
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 индексов в массиве нулями, а остальные индексы — единицей. В качестве альтернативы мы могли бы вычислить, сколько единиц всего в массиве массив k, заполните последние k индексов в массиве 0 и оставьте остальные индексы заполненными 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. В чем проблема улавливания дождевой воды?
Поиск максимального количества воды, которое может быть захвачено заданным набором стержней шириной в одну единицу каждый, известен как проблема «улавливания осадков».
Цель состоит в том, чтобы определить самую высокую полосу, которую можно разместить слева и справа от каждой полосы. Минимум ведущих столбцов слева и справа за вычетом высоты текущего столбца представляет собой количество воды, хранящейся наверху каждого столбца.
Заключение
По сравнению с другими темами структуры данных, массивы проще. Чтобы получить ответы на вопросы интервью с массивами, вам необходимо иметь фундаментальное представление о массивах.
Вы должны тщательно изучить основы массивов, включая операции с массивами (от объявления/создания массива до доступа/изменения элементов массива), а также концепции программирования, такие как циклы, рекурсия и основные операторы, чтобы успешно отвечать на вопросы интервью с массивами. Полностью осознайте проблему.
Вам следует обратиться за разъяснениями, если у вас есть какие-либо вопросы. Подумайте о разделении проблемы на более управляемые части. Убедитесь, что у вас есть алгоритм, прежде чем вы начнете программировать; запишите его или визуализируйте в блок-схеме. затем начните писать код.
Оставьте комментарий