Flipkart SDE-II: Common Interview Question

Here is a sub-array sum concept asked in interviews for the SDE 2 (Software Development Engineer 2) role at Flipkart, a leading e-commerce company in India.

Let’s see how to solve it.

Given an array arr[] of size n containing integers. The problem is to find the length of the longest sub-array having a sum equal to the given value k.

Examples:

Input: arr[] = { 10, 5, 2, 7, 1, 9 }, k = 15

Output: 4

Explanation: The sub-array is {5, 2, 7, 1}.

Input: arr[] = {-5, 8, -14, 2, 4, 12}, k = -5

Output: 5

Solution

1. Initialize a variable to keep track of the maximum sub-array length found so far.
2. Use a hashmap to store the cumulative sum up to all the indices along with the index.
3. Iterate through the array, calculating the cumulative sum.
4. For each cumulative sum, check if (cumulative sum - k) exists in the hashmap.
5. If it does, update the maximum sub-array length if the current sub-array length is greater.
6. If the cumulative sum is not in the hashmap, add it along with the current index.
7. After iterating through the array, return the maximum sub-array length found.

Let's implement this approach in Python:

def max_sub_array_length(arr, k):

# Map to store the cumulative sum which has appeared already.

sum_map = {}

# Variable to store the maximum length of subarray.

max_len = 0

# Variable to keep track of current cumulative sum.

curr_sum = 0

for i in range(len(arr)):

# Update the cumulative sum.

curr_sum += arr[i]

# Check if the current sum is equal to desired k.

if curr_sum == k:

max_len = i + 1

# Check if there are any subarrays previously having sum = (curr_sum - k).

if (curr_sum - k) in sum_map:

# Update max_len if required.

max_len = max(max_len, i - sum_map[curr_sum - k])

# If current sum is not present in map then add it.

if curr_sum not in sum_map:

sum_map[curr_sum] = i

return max_len

# Example usage:

arr1 = [10, 5, 2, 7, 1, 9]

k1 = 15

print(max_sub_array_length(arr1, k1)) # Output: 4

arr2 = [-5, 8, -14, 2, 4, 12]

k2 = -5

print(max_sub_array_length(arr2, k2)) # Output: 5

This function max_sub_array_length will return the length of the longest sub-array with a sum equal to k.