Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
This is the list of Interview Questions based on Array Data Structure. You must practice these Multiple Choice Questions. This will help you master Array Coding Questions for Interviews at companies like Google and Microsoft.
Go through this article to learn more about arrays and practice different coding problems before you attempt the questions:
Question 1
What is the minimum number of comparisons required to find the largest element in an array of N elements?
N-1
N
N/2
logN
The minimum number of comparisons required to find the largest element in an array of N elements is N-1 comparisons. To learn more about this, go through this article on largest element and this article on smallest element.
Question 2
What is the minimum number of comparisons to find the 2nd largest element provided you have found the largest element?
logN - 1
N-1
N
N + logN - 2
The minimum number of comparisons required to find the 2nd largest element is N + logN - 2. Of this, N-1 comparisons are required to find the largest element. So, only logN - 1 extra comparisons are needed to find the 2nd largest element. To learn more about this, go through this article.
Question 3
In Array Data Structure, what is the biggest limitation?
Pre-defined array size
Slow access time
Slow deletion operation
No random access
The biggest limitation of array is that we need to define the size of array beforehand. This is possible only if the maximum size of array is known beforehand and may lead to memory wastage. The solution is to use Dynamic Array or Linked List.
Question 4
In Dynamic Array, what is the worst case Time Complexity of inserting an new element?
O(N)
O(1)
O(logN)
O(N^2)
The worst case Time Complexity of inserting an new element in a Dynamic Array is O(N). On average, it is O(1). This is because if the array is full and we want to insert a new element, a new array with size 2N is allocated and all N elements are copied before inserting the new element. This makes the worst case O(N).
Question 5
If we have N elements, what is the maximum size of the Dynamic Array?
(N left shift 1) AND (NOT N)
2N
N
N left shift 1
If we have N elements, the maximum size of Dynamic Array is the power of 2 (2^M) which is just greater or equal to N. This is because size of Dynamic Array is always a power of 2 and it increases by doubling.
Question 6
What is the average case Time Complexity to delete a specific element in an array?
O(N)
O(1)
O(logN)
O(loglogN)
The average case Time Complexity to delete a specific element in an array is O(N). This is because on deleting an element, all elements after it are shifted to the left by one position. This allows all elements in the array to stay together and makes the deletion operation O(N).
Question 7
How is an N-dimensional array stored in memory?
1D array
2D array
N-D array
Linked List
A N-dimensional array is stored as a 1-D array in memory with ordering of row-major or column-major.
Question 8
To move all negative numbers to the front of array, how many traversals are needed?
1
2
N
logN
We can move all negative numbers to the front of the array in just one traversal. To learn the algorithm required to solve this problem, check This article.
Question 9
Array was improved by Dynamic Array. Dynamic Array is improved by?
Hashed Array Tree
Suffix Array
Prefix Sum Array
Bit Array
Hashed Array Tree is an improvement to Dynamic Array in the case where there is a large amount of unused memory. To learn more about this, go through this article on Hashed Array Tree
Question 10
What is the Time Complexity to create Suffix Array?
O(N logN logN)
O(N^2 logN)
O(N^2)
O(N)
The Time Complexity to create Suffix Array is O(N logN logN). To learn more about suffix array, go through this article.
Question 11
Using Rolling Hash technique in array, the time complexity to find the hash of a sub-array is?
O(1)
O(N)
O(logN)
O(N logN)
Using Rolling Hash technique in array, the time complexity to find the hash of a sub-array is O(1) with a pre-processing of O(N). To learn more about Rolling Hash, go through this article.
Question 12
Which data structure is used to find the least frequent element in an array?
Hash Map
Sorting
Brute force
Linked List
Using Hash Map, you can find the least frequent element in an array takes O(N) time and O(N) space. Other approaches are not optimal in terms of time complexity. To learn more, go this algorithm.
Question 13
Which Algorithm is used to find the largest sub-array sum in optimal time O(N)?
Kadane's algorithm
Slow Fast pointer
Boyer Moore algorithm
option4
Kadane's Algorithm is used to find the largest sub-array sum in optimal time O(N). To learn more about Kadane's Algorithm, go through this article.
Question 14
Boyer Moore voting algorithm is used to find the majority element among the given sequence of elements in an array which occurs more than N/2 times. What is the Time Complexity provided space complexity is O(1)?
O(N)
O(N logN)
O(N^2)
O(N loglogN)
Boyer Moore voting algorithm is used to find the majority element among the given sequence of elements in an array which occurs more than N/2 times in linear time O(N) with space complexity O(1). To learn more about Boyer Moore Algorithm, go through this article.
Question 15
If there are 1024 elements and we have found the largest element, how many comparisons are needed to find the 2nd largest element?
9
1023
1022
10
If there are 1024 elements and we have found the largest element, we need only 9 comparisons to find the 2nd largest element. 9 = log(1024) - 1. The minimum number of comparisons required to find the 2nd largest element is N + logN - 2. Of this, N-1 comparisons are required to find the largest element. So, only logN - 1 extra comparisons are needed to find the 2nd largest element. To learn more about this, go through this article.
With these questions (with answers) at OpenGenus, you must have a strong idea of Array and good practice of Coding Interview Porblems. Best of luck for your Coding Interview.
