O(n)
Additional space:
O(n)
This is usually faster than comparing every pair, which can take O(n²).
🔹 8. What is the Two Sum problem?
Answer:
You are given an array and a target value. Find two elements whose sum equals the target.
Example:
Array: [2, 7, 11, 15]
Target: 9
The answer is:
2 + 7 = 9
A HashMap can solve this efficiently.
arr = [2, 7, 11, 15]
target = 9
seen = {}
for i, num in enumerate(arr):
complement = target - num
if complement in seen:
print(seen[complement], i)
break
seen[num] = i
Output:
0 1
Average time complexity:
O(n)
Space complexity:
O(n)
This is one of the most important patterns to recognize in array interviews.
🔹 9. How do you move all zeroes to the end?
Example:
Input:
[0, 1, 0, 3, 12]
Output:
[1, 3, 12, 0, 0]
A Two Pointer approach can solve this in-place.
arr = [0, 1, 0, 3, 12]
position = 0
for i in range(len(arr)):
if arr[i] != 0:
arr[position], arr[i] = arr[i], arr[position]
position += 1
print(arr)
Output:
[1, 3, 12, 0, 0]
Time complexity:
O(n)
Space complexity:
O(1)
🔹 10. How do you find the missing number?
Suppose the array contains numbers from "0" to "n", but one number is missing.
Example:
[3, 0, 1]
The missing number is:
2
One efficient approach uses the expected sum:
arr = [3, 0, 1]
n = len(arr)
expected_sum = n * (n + 1) // 2
actual_sum = sum(arr)
missing = expected_sum - actual_sum
print(missing)
Output:
2
Time complexity:
O(n)
Space complexity:
O(1)
🔹 11. What is the difference between Linear Search and Binary Search?
Answer:
Linear Search checks elements one by one.
Time: O(n)
It can work on unsorted data.
Binary Search repeatedly divides the search space approximately in half.
Time: O(log n)
It requires suitable sorted data.
For example:
Linear Search:
10 → 20 → 30 → 40 → 50
Binary Search:
30
/ \
10 40...
The key interview point is not simply memorizing the complexities. You should understand when Binary Search can actually be applied.
🔹 12. What is an in-place algorithm?
Answer:
An in-place algorithm modifies the input data structure while using only a small amount of additional memory.
For example, reversing an array using two pointers:
arr = [1, 2, 3, 4]
left = 0
right = len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
No second array is created.
Therefore, the extra space used is:
O(1)
🔹 13. What is the Maximum Subarray problem?
Answer:
You are given an array of integers and need to find the contiguous subarray with the maximum sum.
Example:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
The maximum-sum contiguous subarray is:
[4, -1, 2, 1]
Its sum is:
6
A famous solution uses Kadane's Algorithm.
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
current = arr[0]
maximum = arr[0]
for i in range(1, len(arr)):
current = max(arr[i], current + arr[i])
maximum = max(maximum, current)
print(maximum)
Output:
6