Data Structures Question Bank Part 1: Arrays (with Answers)
MCQs Conceptual Coding (Python) Step-by-step PDF series
This PDF is part of a step-by-step series covering the full Data Structures syllabus.
Topic in this part: Arrays.
Contents
1) Multiple Choice Questions (with answers & explanations)
2) Conceptual / Short Answer (with solutions)
3) Coding Exercises (with sample Python solutions)
Prepared on: September 01, 2025
Data Structures Question Bank Arrays
Arrays MCQs
MCQs Arrays (Answers & Explanations)
Q1. What is the time complexity to access the i-th element in a static array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: A
Explanation: Arrays are contiguous in memory, so computing the address of a[i] is constant-
time.
Q2. Inserting an element at the beginning of an array of size n (without extra space) takes:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C
Explanation: All existing elements must be shifted right by one position, costing linear
time.
Q3. Deleting an element at index k (0-based) from an array of size n (without extra space)
takes:
A) O(1)
B) O(k)
C) O(n - k)
D) O(n) amortized
Answer: C
Explanation: Elements after index k must be shifted left, costing O(n - k), which is O(n) in
the worst case.
Q4. Which expression is equivalent to a[i] in C/C++?
A) *(a+i)
B) *(i+a)
C) i[a]
D) All of the above
Answer: D
Explanation: Pointer arithmetic makes a[i], *(a+i), *(i+a), and i[a] equivalent.
Q5. If an array starts at address base and each element takes w bytes, what is the address of
a[i]?
A) base + i
B) base + i*w
C) base + (i+1)*w
D) base + i + w
Answer: B
Explanation: Address is base + i * w.
Q6. Best data structure to implement a fixed-size circular buffer is:
Arrays MCQs
Arrays MCQs
A) Array
B) Singly linked list
C) Binary tree
D) Hash table
Answer: A
Explanation: Circular buffers map naturally to arrays with modular arithmetic.
Q7. Which technique efficiently finds the maximum sum subarray in O(n)?
A) Divide and Conquer
B) Kadane s algorithm
C) Greedy with sorting
D) Dynamic programming on subsets
Answer: B
Explanation: Kadane s algorithm keeps a running best ending at each index in O(n).
Q8. Which is TRUE for a dynamic array (e.g., Python list, C++ vector)?
A) Push at end is always O(1) worst-case
B) Random access is O(n)
C) Occasional resizing leads to amortized O(1) append
D) It cannot shrink
Answer: C
Explanation: Dynamic arrays resize geometrically, giving amortized O(1) append.
Q9. What is a sparse array?
A) Array where most elements are zero or empty
B) Array of pointers
C) Array with small size
D) Array with variable element sizes
Answer: A
Explanation: Sparse arrays save space by storing non-zero entries compactly (e.g., as
(index,value) pairs).
Q10. Which algorithm is most suitable to find the second largest element in one pass?
A) Sort the array then pick a[n-2]
B) Maintain two variables: max and secondMax
C) Binary search
D) Hash map of counts
Answer: B
Explanation: Track the largest and second largest in a single linear scan.
Q11. Which technique is commonly used to compute range sums quickly after O(n) preprocessing?
A) Two pointers
B) Prefix sums
C) Binary search
D) Bitmask DP
Answer: B
Explanation: Prefix sums allow O(1) range-sum queries after O(n) preprocessing.
Arrays MCQs
Arrays MCQs
Q12. The space complexity of in-place reversal of an array is:
A) O(n)
B) O(log n)
C) O(1)
D) Depends on input
Answer: C
Explanation: Swapping pairs from ends requires constant extra space.
Q13. Rotating an array right by k positions using the reversal algorithm takes:
A) O(k)
B) O(n)
C) O(n log n)
D) O(1)
Answer: B
Explanation: Three reversals each take linear time.
Q14. Merging two sorted arrays of sizes m and n into one sorted array takes:
A) O(m+n)
B) O(m log n)
C) O(n log m)
D) O(mn)
Answer: A
Explanation: Use two pointers; each element is processed once.
Q15. In an array-based binary heap stored 1-indexed, left child of i is at:
A) 2*i - 1
B) 2*i
C) 2*i + 1
D) i/2
Answer: B
Explanation: Left child at 2*i, right child at 2*i+1, parent at i/2.
Q16. Given a sorted array, the best time complexity to search for an element is:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B
Explanation: Binary search on sorted arrays is O(log n).
Q17. What is the advantage of using two-pointer technique on arrays?
A) Works only on unsorted arrays
B) Reduces space to O(n)
C) Solves many linear-time window problems
D) Guarantees exact k elements in window
Answer: C
Explanation: Two pointers help solve many O(n) problems like 2-sum (sorted), windows, etc.
Arrays MCQs
Arrays MCQs
Q18. Which operation is NOT efficient on arrays compared to linked lists?
A) Random access
B) Insert/delete in the middle
C) Traversal
D) Binary search on sorted data
Answer: B
Explanation: Middle insert/delete is costly due to shifts.
Q19. Which of the following is TRUE about static arrays?
A) Size can be changed at runtime
B) Contiguous memory allocation
C) Elements are not indexable
D) Store heterogeneous types by default
Answer: B
Explanation: Static arrays are contiguous and have fixed size.
Q20. For a k-size sliding window maximum using a deque, the time complexity over n elements is:
A) O(nk)
B) O(n log k)
C) O(n)
D) O(k log n)
Answer: C
Explanation: Each element is pushed/popped at most once across the whole pass.
Q21. To find if any duplicate exists in an array of n integers in O(n) expected time and O(n)
space:
A) Sort and scan
B) Use a hash set
C) Use two pointers
D) Use prefix sums
Answer: B
Explanation: Hash set detects repeats in expected O(1) per element.
Q22. Which is TRUE about array-of-structures (AoS) vs structure-of-arrays (SoA)?
A) AoS improves SIMD-friendliness
B) SoA groups fields to improve cache locality per field
C) Neither affects cache
D) Both are identical
Answer: B
Explanation: SoA can provide better cache/SIMD for field-wise processing.
Q23. Finding majority element (> n/2) in an array in O(n) and O(1) space uses:
A) Counting sort
B) Boyer Moore voting
C) Binary search
D) Heap
Answer: B
Explanation: Boyer Moore maintains a candidate and a counter.
Arrays MCQs
Arrays MCQs
Q24. In-place partition step of Quickselect/Quicksort on arrays takes:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C
Explanation: Partition scans the array once, so it s linear.
Q25. Which statement about cache locality in arrays is TRUE?
A) Arrays hurt spatial locality
B) Linked lists are often better for caches
C) Arrays benefit from contiguous memory
D) Caches don t matter for performance
Answer: C
Explanation: Arrays exploit spatial locality better than pointer-chasing lists.
Arrays MCQs
Arrays Conceptual / Short Answer
Conceptual / Short Answer Arrays
C1. Differentiate row-major and column-major order.
Solution: Row-major (e.g., C) stores rows contiguously; column-major (e.g., Fortran, MATLAB)
stores columns contiguously. This affects address calculation and cache locality when
iterating.
C2. What is the difference between static and dynamic arrays?
Solution: Static arrays have fixed size determined at allocation; dynamic arrays can resize
(typically doubling strategy), providing amortized O(1) append.
C3. Array vs Linked List: key differences?
Solution: Arrays: contiguous, O(1) random access, costly middle insert/delete. Linked lists:
non-contiguous nodes with pointers, O(1) insert/delete with pointer, O(n) random access.
C4. When would you prefer an array over a linked list?
Solution: When random access, cache locality, and memory overhead are important, and
frequent middle insertions/deletions are NOT required.
C5. Define prefix sums and a use-case.
Solution: Prefix sums p[i]=a[0]+...+a[i] allow O(1) range sum queries: sum(l,r)=p[r]-p[l-1].
Used in frequency ranges, difference arrays, cumulative counts.
C6. Explain the sliding window technique.
Solution: Maintain a window [l,r] and move pointers based on constraints (e.g., sum K).
Useful in subarray sums, longest substrings, and streaming problems in O(n).
C7. Describe Kadane s algorithm.
Solution: Track bestEndingHere = max(a[i], bestEndingHere + a[i]); bestSoFar =
max(bestSoFar, bestEndingHere). Finds maximum subarray sum in O(n).
C8. How does the reversal algorithm rotate an array by k?
Solution: Reverse entire array, reverse first k elements, reverse remaining n-k elements (or
adjust for left/right rotation).
C9. What is a sparse array representation?
Solution: Store only non-zero entries as (index, value) pairs or maps to save memory while
enabling access via lookup.
C10. What is two-pointer technique for sorted 2-sum?
Solution: Set i=0, j=n-1; if a[i]+a[j] < target, i++; if > target, j--; else found. Runs in
O(n).
C11. Why is merging two sorted arrays linear?
Solution: Each element is examined and moved at most once using two pointers.
C12. How do dynamic arrays grow?
Solution: Typically double capacity when full; copy old elements to new buffer. This yields
Arrays Conceptual
Arrays Conceptual / Short Answer
amortized O(1) append but O(n) on resize steps.
C13. What is a difference array and why use it?
Solution: Diff arr d where d[l]+=x, d[r+1]-=x allows range updates in O(1) per update;
prefix the diff to get final array.
C14. What is stable vs unstable algorithm in array context?
Solution: Stability preserves the relative order of equal keys (e.g., Merge Sort stable,
Quick Sort not by default). Matters for compound keys.
C15. How does cache affect array algorithms?
Solution: Contiguity leverages spatial locality; sequential scans are cache-friendly.
Algorithms with linear scans often outperform pointer-heavy traversals.
Arrays Conceptual
Arrays Coding Exercises (Python)
Coding Exercises Arrays (Python Solutions)
P1. Reverse an array in place.
Solution:
Python:
def reverse_in_place(a):
i, j = 0, len(a)-1
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
# Example: a=[1,2,3] -> [3,2,1]
P2. Rotate array right by k using reversal algorithm.
Solution:
Python:
def rotate_right(a, k):
n = len(a)
k %= n
def rev(l, r):
while l < r:
a[l], a[r] = a[r], a[l]
l += 1; r -= 1
rev(0, n-1); rev(0, k-1); rev(k, n-1)
P3. Merge two sorted arrays into one sorted array.
Solution:
Python:
def merge_sorted(a, b):
i=j=0; out=[]
while i < len(a) and j < len(b):
if a[i] <= b[j]:
[Link](a[i]); i += 1
else:
[Link](b[j]); j += 1
[Link](a[i:]); [Link](b[j:])
return out
P4. Remove duplicates from a sorted array (return new length).
Solution:
Python:
def dedup_sorted(a):
if not a: return 0
w = 1
for r in range(1, len(a)):
if a[r] != a[w-1]:
a[w] = a[r]; w += 1
return w # first w elements are unique
Arrays Coding
Arrays Coding Exercises (Python)
P5. Maximum subarray sum (Kadane).
Solution:
Python:
def max_subarray(a):
best = cur = a[0]
for x in a[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best
P6. Find majority element (> n/2) using Boyer Moore.
Solution:
Python:
def majority_element(a):
cand = None; cnt = 0
for x in a:
if cnt == 0: cand, cnt = x, 1
elif x == cand: cnt += 1
else: cnt -= 1
# Optional: verify cand is indeed > n/2
return cand
P7. Two-sum in a sorted array in O(n).
Solution:
Python:
def two_sum_sorted(a, target):
i, j = 0, len(a)-1
while i < j:
s = a[i] + a[j]
if s == target: return (i, j)
if s < target: i += 1
else: j -= 1
return None
P8. Find the missing number from 0..n given n numbers.
Solution:
Python:
def missing_number(a):
n = len(a)
expected = n*(n+1)//2
return expected - sum(a)
P9. Search in rotated sorted array (no duplicates).
Solution:
Python:
def search_rotated(a, target):
l, r = 0, len(a)-1
Arrays Coding
Arrays Coding Exercises (Python)
while l <= r:
m = (l+r)//2
if a[m] == target: return m
if a[l] <= a[m]: # left sorted
if a[l] <= target < a[m]: r = m-1
else: l = m+1
else: # right sorted
if a[m] < target <= a[r]: l = m+1
else: r = m-1
return -1
P10. Product of array except self (no division).
Solution:
Python:
def product_except_self(a):
n = len(a)
left = [1]*n; right = [1]*n
for i in range(1, n): left[i] = left[i-1]*a[i-1]
for i in range(n-2, -1, -1): right[i] = right[i+1]*a[i+1]
return [left[i]*right[i] for i in range(n)]
Arrays Coding
