Data Structures and Algorithms (DSA) questions on Arrays 2024

Data Structures and Algorithms (DSA) questions on Arrays

We are listing some important  “Array” based Data Structures and Algorithms (DSA) questions frequently asked in technical interviews of multiple companies, categorized by topic:

Arrays:

Q1) Find the maximum subarray sum (Kadane’s Algorithm).
Kadane’s Algorithm is an efficient way to find the maximum sum of a contiguous subarray in an array of integers. It runs in O(n) time complexity.

Kadane’s Algorithm is an efficient way to find the maximum sum of a contiguous subarray in an array of integers. It runs in O(n) time complexity.

Algorithm Steps :

• First of all, Initialize Variables:

i)max_current to 0 (or the first element if considering non-empty subarrays only).
ii) max_global to the smallest possible integer value (or the first element).

• Iterate Through the Array:
  For each element in the array:
  i)Update max_current as the maximum of the current element and the sum of max_current and the current element.
  ii)Update max_global as the maximum of max_global and max_current.
  iii)Return max_global as the result.

Our Code Implementation in Python (Data Structures and Algorithms (DSA) questions on Arrays): 

def max_subarray_sum(nums):
if not nums:
return 0 # Handle the edge case of an empty array

max_current = nums[0]
max_global = nums[0]

for i in range(1, len(nums)):
max_current = max(nums[i], max_current + nums[i])
max_global = max(max_global, max_current)

return max_global

# Example Usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(nums)
print(“Maximum Subarray Sum:”, result)

Q2) Merge two sorted arrays without extra space.

A: Merging two sorted arrays without extra space involves rearranging the elements in place, using the properties of sorting to maintain the order. Below is a step-by-step explanation and Python implementation.

Approach: Gap Algorithm (Optimized Approach)

The Gap Algorithm efficiently merges two sorted arrays without using extra space. It works by progressively reducing the gap between compared elements and swapping them if necessary.

Steps

1. Initialization:
   • Consider the combined length of the two arrays as n = m + n (sizes of the two arrays).
   • Start with a gap equal to (n + 1) // 2.
2. Compare and Swap:
   • For each gap, compare elements within the first array, between the arrays, and in the second array. Swap if the order is incorrect.
3. Reduce the Gap:
   • Update gap = (gap + 1) // 2 and repeat the process until gap == 1.
4. End:
   • After the process, both arrays will be merged in sorted order.

Code Implementation :

def merge_sorted_arrays(arr1, arr2):
n, m = len(arr1), len(arr2)
gap = (n + m + 1) // 2 # Initial gap size

while gap > 0:
i, j = 0, gap # Two pointers

# Compare and swap elements in arr1
while j < n:
if arr1[i] > arr1[j]:
arr1[i], arr1[j] = arr1[j], arr1[i]
i += 1
j += 1

# Compare and swap elements between arr1 and arr2
j -= n # Move j to the start of arr2
while i < n and j < m:
if arr1[i] > arr2[j]:
arr1[i], arr2[j] = arr2[j], arr1[i]
i += 1
j += 1

# Compare and swap elements in arr2
i, j = 0, max(0, gap – n) # Reset pointers for arr2
while j < m:
if arr2[i] > arr2[j]:
arr2[i], arr2[j] = arr2[j], arr2[i]
i += 1
j += 1

# Reduce the gap
gap = (gap + 1) // 2

return arr1, arr2

# Example Usage
arr1 = [1, 4, 7, 8, 10]
arr2 = [2, 3, 9]
merged_arr1, merged_arr2 = merge_sorted_arrays(arr1, arr2)
print(“Merged Array 1:”, merged_arr1)
print(“Merged Array 2:”, merged_arr2)

Time Complexity

• Each gap iteration performs O(n + m) comparisons and swaps.
• The gap reduces approximately as a geometric series, so the overall complexity is O((n + m) log(n + m)).

Space Complexity

• O(1): No additional space is used.

Q3)  Find the duplicate number in an array containing n+1 integers where numbers are in the range [1, n].

A:

Finding the duplicate number in an array where integers are in the range $[1,n]$ and the array contains $n+1$ elements can be done efficiently without modifying the array or using extra space. Here’s a solution using Floyd’s Tortoise and Hare Algorithm.

Approach: Floyd’s Tortoise and Hare (Cycle Detection)

This approach is based on the idea of treating the array as a linked list where:

• Each index is a node.
• Each value at an index points to the next node.

In such a setup, there is a cycle because one value appears twice. The goal is to find this cycle and determine the duplicate.

Q7) Trapping Rain Water problem.

A:

Approach : Brute Force

For each bar, calculate the water it can trap by finding the maximum height on its left and right, then take the minimum of these heights minus the height of the bar itself.

Steps

1. For each bar i:
   • Find the maximum height to its left (max_left).
   • Find the maximum height to its right (max_right).
   • Calculate water trapped on this bar as min(max_left, max_right) - height[i].
2. Sum up the trapped water for all bars.

Code:

def trap_brute_force(height):
n = len(height)
if n == 0:
return 0

water = 0
for i in range(n):
max_left = max(height[:i+1])
max_right = max(height[i:])
water += max(0, min(max_left, max_right) – height[i])
return water

# Example Usage
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(“Trapped Water:”, trap_brute_force(height))

Time Complexity: O(n2)O(n^2)O(n2)

Space Complexity: $O(1)$

Q8)Sort an array of 0s, 1s, and 2s (Dutch National Flag Problem).

A:

Algorithm Steps

1. Initialize Pointers:
   • low = 0, mid = 0, high = n - 1 (where $n$ is the size of the array).
2. Iterate Until mid > high:
   • If arr[mid] == 0:
     • Swap arr[low] and arr[mid].
     • Increment low and mid.
   • If arr[mid] == 1:
     • Increment mid.
   • If arr[mid] == 2:
     • Swap arr[mid] and arr[high].
     • Decrement high.

This ensures:

• All 0s are placed before low.
• All 2s are placed after high.
• All 1s remain in between.

Code: 

def sort_012(arr):
low, mid, high = 0, 0, len(arr) – 1

while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
else: # arr[mid] == 2
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1

# Example Usage
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(“Sorted Array:”, arr)

Complexity Analysis

1. Time Complexity: $O(n)$
   • Each element is processed at most once.
2. Space Complexity: $O(1)$
   • No extra space is used; sorting is done in-place.

Q9) Longest Consecutive Sequence.

A:

Approach: Using HashSet

We can solve this problem in O(n) time using a HashSet. The key idea is to use a set to store the elements and check if consecutive elements exist.

Steps:

1. Insert all elements into a set. The set allows for $O(1)$ average time complexity for lookup.
2. Iterate over each element in the array:
   • If the current element is the start of a sequence (i.e., num - 1 is not in the set), find the length of the sequence starting from this element.
   • The sequence continues as long as the next consecutive number (num + 1) is in the set.
3. Keep track of the longest sequence found during the iteration.

Code :

def longestConsecutive(nums):
if not nums:
return 0

num_set = set(nums) # Insert all elements into a set
longest = 0

for num in num_set:
# Check if ‘num’ is the start of a sequence
if num – 1 not in num_set:
current_num = num
current_streak = 1

# Count the length of the sequence starting from ‘num’
while current_num + 1 in num_set:
current_num += 1
current_streak += 1

# Update the longest streak
longest = max(longest, current_streak)

return longest

# Example Usage
nums = [100, 4, 200, 1, 3, 2]
print(“Longest Consecutive Sequence Length:”, longestConsecutive(nums))

Time Complexity

• Time Complexity: $O(n)$, where $n$ is the number of elements in the input array. We make a constant time lookup for each element in the set, and we only visit each element once.
• Space Complexity: $O(n)$, as we are storing all the elements in a set.

Q10) Subarray with a given sum (sliding window or hash map).

A;

Sliding Window (For Non-negative Integers)

The sliding window technique is most efficient when the array contains only non-negative integers. It allows us to maintain a window of elements that sum to a target value.

Steps:

1. Initialize two pointers, start and end, both at the beginning of the array.
2. Expand the window by moving end to the right and adding the current element to the window sum.
3. If the window sum exceeds the target sum, increment start to shrink the window until the sum is less than or equal to the target.
4. If the window sum matches the target, return the subarray or indices.

Code:

def subarray_sum_sliding_window(arr, target):
start = 0
current_sum = 0

for end in range(len(arr)):
current_sum += arr[end]

# Shrink the window if sum exceeds target
while current_sum > target and start <= end:
current_sum -= arr[start]
start += 1

# Check if we found a valid subarray
if current_sum == target:
return arr[start:end + 1] # Return the subarray

return None # No subarray found

# Example Usage
arr = [1, 2, 3, 7, 5]
target = 12
print(“Subarray with given sum:”, subarray_sum_sliding_window(arr, target))

Time Complexity: $O(n)$

• Both start and end pointers only move forward once.

Space Complexity: $O(1)$

More Visit : https://taazakhobor.in/

More You read :

Class 11 physics chapter 1 important questions with answers for Jee and Neet

Class 11 Chemistry Chapter 1 Important Questions For Neet and Jee.

PRP treatment for hair and face in 2024: The best treatment for your hair and face. Know the side effects and its cost.

Offline vs Online Education. Which one is best for your children to score 91+%?

Neet scam 2024-The greatest educational scam in the history of India!!

What are Mutual Funds? Are Mutual Funds safe to invest in 2024?