Introduction
Array questions are among the most common types of problems that coding interviewers throw at candidates, often testing a variety of concepts like loops, sorting, searching, and data manipulation. Let’s dive into some popular array-based interview questions with detailed explanations and examples:
Question 1: Find the Duplicate Number
Problem: Given an array containing n + 1 integers where each integer is between 1 and n (inclusive), prove there must be a duplicate number and find one of them.
Solution: This problem can be solved by applying Floyd’s Tortoise and Hare algorithm, which detects cycles in linked lists. We interpret the array as pointers into an array that represents a linked
list where each element points to another index:
def findDuplicate(nums):
tortoise = hare = nums[0]
# Phase 1: Detecting cycle
while True:
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare:
break
# Phase 2: Finding the entry point of the loop
tortoise = nums[0]
while tortoise != hare:
tortoise = nums[tortoise]
hare = nums[hare]
return tortoise
nums = [3,1,3,4,2]
print(findDuplicate(nums)) # Output: 3Question 2: Two Sum Problem
Problem: Given an array nums and a target value, return the indices of the two numbers such that they add up to the target.
Solution: Use a hash map (dictionary in Python) to store each number along with its index during iteration. For every element, check if target - nums[i] exists in the dictionary:
def twoSum(nums, target):
dict = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in dict:
return [dict[complement], i]
else:
dict[nums[i]] = i
nums, target = [2, 7, 11, 15], 9
print(twoSum(nums, target)) # Output: [0, 1]Question 3: Search Insert Position
Problem: Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
Solution: Implement binary search to find the target or its insertion point:
“`python
def searchInsert(nums, target):
left, right = 0, len(nums) – 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return leftnums, target = [1, 3, 5, 6], 7
print(searchInsert(nums, target)) # Output: 4
Question 4: Maximum Subarray
Problem Statement: Given an array of integers, find the contiguous subarray within the array which has the largest sum.
Example 1:
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (The maximum subarray is [4,-1,2,1], and their sum is 6.)Solution
One of the most efficient ways to solve this problem is using Kadane’s algorithm.
Python Code:
def max_sub_array(nums):
if not nums:
return 0
current_sum = max_sum = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sumQuestion 5: Rotate Array
Problem Statement: Given an array and a number of positions k, rotate the array to the right by k steps.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: Rotates the array to become `[5,6,7,1,2,3,4]`Solution
To rotate an array k times in a clockwise direction:
Python Code:
def rotate(nums, k):
n = len(nums)
# Ensure k is within the bounds of the list length
k %= n
def reverse(start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
rotate([1,2,3,4,5,6,7], 3)Question 6: Find Pivot Index
Problem Statement: Given an array of integers where every element appears twice except for one. Find the single number.
Example 1:
Input: nums = [1,2,3,4,1,3]
Output: The pivot index is 3 since nums[3] (which is 4) does not appear in its range.Solution
Use a hash map to count the occurrences of each number:
Python Code:
def find_pivot(nums):
counts = {}
for num in nums:
if num in counts:
counts[num] += 1
else:
counts[num] = 1
pivot = None
for i, num in enumerate(nums):
if counts.get(num) == 1:
pivot = i
break
return pivot
find_pivot([1,2,3,4,1,3])Question 7: Search in Rotated Sorted Array
Problem Statement: Given a sorted array nums rotated at some pivot unknown to you beforehand and an element target, find the index of target if it is present in the array. If it’s not found, return
-1.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4 (The pivot was at position 3, so we search in `nums[3:]` and find that the index of target is actually 4.)Solution
Use a modified binary search algorithm:
Python Code:
def search(nums, target):
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Check which part of the array is sorted and search accordingly
if nums[left] <= nums[mid]: # Left part is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # Right part is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
search([4,5,6,7,0,1,2], 0)Question 8 : Valid Parentheses
Problem Statement: Determine if the input string of parentheses is valid. Only three types of parentheses: (, ), {, }, [, ] are considered.
Example 1:
Input: s = "({[]})"
Output: True (The given string has all open and closed parentheses in the correct sequence.)Solution
Use a stack to keep track of opening parentheses:
Python Code:
“`python
def is_valid(s):
stack, mapping = [], {‘)’: ‘(‘, ‘}’: ‘{‘, ‘]’: ‘[‘}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stackis_valid(“({[]})”)
Conclusion
Mastering these challenges requires practice and understanding of underlying data structures like arrays, linked lists (in a conceptual sense), and maps. By breaking down problems step-by-step and
implementing solutions efficiently, you can significantly improve your performance during coding interviews. Always remember to think logically about the problem space, optimize your algorithms for time complexity, and use appropriate data structures to manage information effectively.