# Top 20 Array Coding Questions for Online Assessment

Hey everyone! Today we’re going to discuss the top 20 array coding questions which are most frequently asked in online assessments (and interviews) by top product-based companies primarily for the role of Software Developer Engineer. We are not going to see those standard array problems which you see on other websites. We are majorly going to focus on those coding questions which are mostly asked in the online coding rounds and not in interviews.

Questions asked in interviews are far easier than the questions asked in online assessments. In an interview, they’ll ask you to sort the array. What do you think they’ll ask the same thing in the online coding round? No, right! If you have any experience you might be aware of this thing. Everyone is talking about top DSA questions to crack any FAANG interview but interviews are generally the second round. But what about the first round? What about the online assessments? How to crack those? Moreover, which type of questions we should practice for cracking the OA of top product-based companies? Let’s start with Array! The dearest topic of product-based companies!

## Array Coding Problems List

1. Napolean Cake (Codeforces)
2. Max Chunks To Make Sorted (Leetcode Medium)
3. Possible Options to book the room
4. Maximum of minimum of all subarrays of size k
5. Maximum sum circular subarray

## Array Coding Problem #1

Problem Name: Napolean Cake

Problem Statement (In simple words):

Rahul decided to bake the Napoleon cake. He baked n dry layers first, and then put them on each other in one stack(see image), adding some cream. Rahul started with an empty plate, and performed the following steps n times:

• place a new dry layer of cake on the top of the stack;
• after the i-th layer is placed, pour ai units of cream on top of the stack.

When x units of cream are poured on the top of the stack, the top x layers of the cake get wet in the cream. If there are fewer than x layers, all layers get wet. If x=0, no layer gets wet.

Help Rahul determine which layers of the cake eventually get wet when the process is over, and which don’t.

Input: Each test case contains n integers arr[0], arr[1], … arr[n-1] — where arr[i] is the amount of cream poured on the cake after adding ith layer.

Output: Print array of n integers. The i-th of the integers should be equal to 1 if the i-th layer is wet, and 0 otherwise. Let’s see an example.

Example Test Case:

Input: n = 6 arr[6] = 0 3 0 0 1 3

Ouput: 1 1 0 1 1 1

### Explanation of Napolean Cake Problem

After putting 1st layer(i=0) of cake, he pour 0 amounts of cream so no layer gets wet. Then he put the 2nd(i=1) layer of cake and pour 3 units of cream due to which layers from i = 1 to i = -1(top 3 layers) gets wet. Then he put 3rd, 4th layer, and 5th layer. On the 5th layer(i=4) he pour 1 unit of cream and i = 4 layer gets wet. He adds the 6th(i=5) layer and pours 3 units of cream due to this layers from i=5 to i=3 all get wet. Now THINK about how you will solve this array coding problem?

Think more! 🙂

### Naive Approach for Napolean Cake

Firstly, Make an answer array of size n. Initialize it with 0. Then, traverse the given array from left to right. For any current index, you just need to make entries from i=current index to i=current_index – arr[current_index] + 1 layers wet in the answer array. Here we are going backward to make layers wet but can we do better? of course, we can!

```vector<int> solve(vector<int> arr, int n)
{
vector<int> ans(n,0);
for(int i = 0; i < n; i++)
{
for(int j = i; j >= 0 && j >= i - arr[i]+1; j--)
ans[j] = 1;
}
return ans;
}```

I hope you’ve thought of this approach.

Time Complexity: O(n*n)

Space complexity: O(n).

But this will give you TLE (most irritating I know). So what we can do now? How to optimize this?

### Efficient Solution for Napolean Cake

Hint1: Let’s traverse the given array from right to left!

Hint 2: Additionally, Maintain a minele, initialized with INT_MAX; Traverse the array from i = n-1 to i = 0 and maintain minimum of minele , i – arr[i] + 1. (Note: i – arr[i] + 1 represents that index until which arr[i] can make layers wet.)

Complete C++ Solution

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n;
// for multiple test cases
cin >> t;
while(t--)
{
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];

// Initialising answer array with 0
int ans[n] = {0};
int mn = INT_MAX; // To maintain minimum
for(int i = n-1; i >= 0; i--)
{
mn = min(mn, i - arr[i] + 1);

if(i >= mn) ans[i] = 1;
}

for(int i = 0; i <n; i++)
cout << ans[i] << " ";
cout << endl;
}
return 0;
}```

Never solve a question by thinking that it might come in your test. Because that will not going to happen. Instead, just look at the approach. What was the approach here?

Take Away: If in the brute force approach, you are traversing an array from left to right and then going backward for every element then chances are if you traverse the array from right to left you will solve it in an efficient manner. Remember this while solving any array coding problem!

## Array Coding Problem #2

Problem Name: Max Chunks To Make Sorted

Problem Statement: You are given an integer array `arr` of length `n` that represents a permutation of the integers in the range `[0, n - 1]`. We split `arr` into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

Example Test Case:

Input: arr = [1,0,2,3,4]

Output: 4

Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. If we sort each chunk and concatenate them we will get a sorted array. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

### How to Approach this leetcode problem?

There are multiple ways to do this question. One way is to iterate through the array, each time all elements to the left are smaller (or equal) to all elements to the right, there is a new chunk. Use two auxiliary arrays to store the left max and right min to achieve O(n) time complexity. Space complexity is O(n) too.

### Naive C++ Solution

```int maxChunksToSorted(vector<int>& arr) {

int n = arr.size();
int maxOfLeft[n];
int minOfRight[n];
maxOfLeft[0] = arr[0];
for (int i = 1; i < n; i++) {
maxOfLeft[i] = max(maxOfLeft[i-1], arr[i]);
}
minOfRight[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
minOfRight[i] = min(minOfRight[i + 1], arr[i]);
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
if (maxOfLeft[i] <= minOfRight[i + 1])
ans++;
}
return ans + 1;
}```

### Efficient Solution for Max Chunks To Sort

How we can improve this solution? Do we really need to check the max element in the left and the minimum element in right?

Hint 1: array elements are in the range of 0 to n-1.

Hint 2: What happens when the sum of array elements from 0 to i , is equal to the sum of indexes from 0 to i?

You got a new chunk! So here you just need to maintain two sum variables. One for summing the array elements and the other for summing the indexes as you traverse the array from left to right. If array_sum is equal to index_sum increment the count of the chunk.

### Efficient C++ Solution

```int maxChunksToSorted(vector<int>& arr) {

int n = arr.size();
int array_sum = 0, index_sum = 0;
int count_chunk = 0;

for(int i = 0; i < n; i++)
{
array_sum = array_sum + arr[i];
index_sum = index_sum + i;

if(index_sum == array_sum)
count_chunk++;
}

return count_chunk;
}```

Follow-Up Question: Max Chunks To Make Sorted – II (LeetCode Hard)

Hey, If you’re liking this blog so far do comment “Nice!” and tell us whether you want more such posts or not. Feedback is really important for us! Thanks 🙂

## Array Coding Problem #3

Problem Name: Possible options to book the rooms (Asked recently in OA)

Problem Statement: Virat is looking to book hotel rooms for an incoming delegation of engineers. He is Allowed to spend anywhere between BRupees and C Rupees (Both Inclusive). He needs to book rooms consecutively as delegates would prefer to stay as close as possible.

Virat has been given the pricing of the rooms in the form of an array (A). You need to help Virat to find the total no of options available to book like this in the given range.

Note- There is no restriction on no of rooms he can book. ( Min 1 or Max Size of the array)

Input Format

• First Line contains 3 Integers N,B,C where N is the Size of the array. (1<= N, B, C <= 106)
• Second Line contains N integers denoting the price of t=each rooms available.
• Notes: price[] array, and range B to C (both inclusive)

Output Format

• Total No of possible option available for to book the rooms.

Example Test Cases

Sample Input 0

N=5 B=6 C=8

Price Array= 10 5 1 0 2

Sample Output 0

3

Sample Input 1

N=10 B=5 C=9

Price Array= 1 2 3 4 5 6 7 8 9 10

Sample Output 1

10

### Explanation

Virat can book consecutive rooms within the price range of 6 to 8. [5,1],[5,1,0],[5,1,0,2] are only 3 consecutive options available within the price sum range. That’s why the output is 3.

### Naive Solution

As we are given with price array and range, one simple solution is to check for all possible subarrays. First, find all possible subarrays then find the sum of the individual subarray. If this sum lies within the range, increment the answer count.

Time Complexity: O(N2)

### Java Code

```import java.util.Scanner;
//Naive Solution
class HotelBookingNS {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();

int price[] = new int[n];

for(int i=0;i<n;i++){
price[i] = sc.nextInt();
}

int sum=0;

// counter for number of required subarrays.
int count=0;

for(int i = 0; i < n; i++){
sum=0;
for(int j=i;j<n;j++){
sum += price[j];

//Checking our range constraints
if(sum >= B && sum <= C)
count++;

//Sum must not greater than required range
if(sum > C)
break;
}
}

System.out.println(count);
}
}
//Time Complexity: O(N^2)
//Space Complexity: O(1)```

### Efficient Solution

Hint 1: Sliding Window Technique

I hope you have an idea of the sliding window technique. If not just watch this playlist and you will never face any difficulty in this technique. The main idea of the sliding window is to scan the given array only once and while scanning calculate the sum. First, find all the subarrays having a sum less than or equal to C. Then find all subarrays having a sum less than B. Now, subtract the first result with the second.

Result = numOfSubArraysLessThan(pricearray, C) – numOfSubArraysLessThan(pricearray, B – 1);

Time Complexity: O(N)

Space Complexity: O(1)

### Java Code

```import java.util.Scanner;

class HotelBooking
{

// Function to find number of subarrays having sum less than or equal to x.
static int countSubArray(int price[], int k)
{

int n = price.length;

// Starting index of sliding window.
int st = 0;

// Sum of elements in sliding window.
int sum = 0;

// counter for number of required subarrays.
int count = 0;

for(int i = 0; i < n; i++)
{
// Update sum adding new element each time.
sum += price[i];

while (st <= i && sum > k)
{
sum -= price[st++];
}

// Update count of number of subarrays.
count += (i - st + 1);
}

return count;
}

// Function to find number of options available to book in given range
static int totalAvailableOptions(int price[], int B, int C)
{
int n = price.length;

int R = countSubArray(price, C);

int L = countSubArray(price, B - 1);

return R - L;
}

public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();

int price[] = new int[n];
for(int i = 0; i < n; i++){
price[i] = sc.nextInt();
}

System.out.println(totalAvailableOptions(price, B, C));
}
}
//Time Complexity: O(N)
//Space Complexity: O(1)```

## Array Coding Problem #4

Problem Name: Maximum of minimum elements of all subarrays of size k.

Problem Statement: Given an array, arr[] of size N and an integer K. Find the minimum element for each and every contiguous subarray of size K and then return the maximum among all those minimum elements.

Input Format

First Line contains 2 Integers N (Size of the array) and K(size of subarray).

The second Line contains N integers of an array.

Output format

Maximum among all minimum

Constraints

1 <= K < N <= 10^6

-109 < arr[i] < 109

Sample Input 0

10 3

10 5 -1 0 2 -5 1 4 6 -6

Sample Output 0

1

Explanation

All subarrays of size 3:

{10, 5, -1} =>min(10, 5, -1) = -1

{5, -1, 0}  =>min(5, -1, 0) = -1

{-1, 0, 2}  =>min(-1, 0, 2) = -1

{0, 2, -5}  =>min(0, 2, -5) = -5

{2, -5, 1}  =>min(2, -5, 1) = -5

{-5, 1, 4}  =>min(-5, 1, 4) = -5

{1, 4, 6}   =>min(1, 4, 6) = 1

{4, 6, -6}  =>min(4, 6, -6) = -6

Now we will take maximum of all these minimum elements.

Maximum(-1, -1, -1, -5, -5, -5, 1, -6) = 1 (Final Result)

### Naive Solution

Here first we need to generate all the possible subarrays, then we need to find the minimum element in each subarray and after that we can simply find the maximum among all of them. Naive solution is pretty straightforward. Here are the steps of naive solution:

1. Initialize a variable *res* as 0.
2. Run a loop for i equals 0 to (n – k).
3. Run a nested loop for j = i to (i + k)(not included), this loop represents a sub-array of size k.
4. Traverse this sub-array and find the minimum elements.
5. Then find max(res, min).

Time Complexity: O(N*K)

Space Complexity: O(1)

### C++ Code

```#include <bits/stdc++.h>
using namespace std;
int solve(int arr[], int n, int k)
{
int res = INT_MIN;
// Traverse all the subarray of size k one by one
for (int i = 0; i <= n - k; i++)
{
int minele = INT_MAX;
// traverse the current subarray
for (int j = i; j < i + k; j++)
minele = min(minele, arr[j]);

res = max(res, minele);
}

return res;
}
int main() {

int n, k;
cin >> n >> k;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];

cout << solve(arr, n, k) << endl;
return 0;
}```

### Java Code

```import java.util.Scanner;
class MaxElementNS{
private static int maxAmongMin(int[] arr, int k) {
int n = arr.length;

int res = 0;

// Traverse all the subarray of size k one by one
for (int i = 0; i <= n - k; i++) {
int min = Integer.MAX_VALUE;

// traverse the current subarray
for (int j = i; j < i + k; j++) {
min = Math.min(min, arr[j]);
}

res = Math.max(res, min);
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();

int arr[] = new int[n];
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
System.out.println(maxAmongMin(arr, k));
}
}```

### Efficient Solution

Hint 1: Sliding Window Technique

Hint 2: Deque Data Structure

Whenever you see any specific size (here k) is mentioned for a subarray that’s a clear indication that you can improve your solution using the sliding window technique. Here what we need to do is we have to maintain a deque in such a way that its front will always contain the minimum element of k sized subarray. We will maintain elements in increasing order in the deque. If at any instance we find the current element is smaller than the greatest element in the deque we will pop that greatest element from the deque and put this current element because this might become the smallest for some subarray. Here are the steps:

1. Initialize a variable res = INT_MIN.
2. Declare a vector to store minimum element of all subarrays of size k, and a deque.
3. Take two variables i=0 and j=0 as we do in standard sliding window technique.
4. Run a loop while(j<n)
5. Now check if deque is non empty and current element is smaller than the greatest element which will be at dq.back( ) then delete that greatest element.
6. Now push back this current element.
7. Check if window size is reached or not. If not increase the size by doing j++. If yes, just push back the dq.front in minimum element vector.
8. Now we need to slide the window by 1. But before that we need to check whether arr[i] was the smallest element that we just pushed into the vector or not. If yes delete that from deque.
9. Slide the window by doing i++ and j++.
10. Lastly, find the maximum in mineleofsubarray vector.

Time Complexity: O(N*K)

Space Complexity: O(K)

### C++ Efficient Solution

```#include <bits/stdc++.h>
using namespace std;
int solve(int arr[], int n, int k)
{
int res = INT_MIN;
vector<int> mineleofsubarrays;
deque<int> dq;

int i = 0, j = 0;
while(j < n)
{
// if current element is smaller than greatest element in deque
while(!dq.empty() && arr[j] < dq.back())
dq.pop_back();

dq.push_back(arr[j]);

// window size is < k
if(j - i + 1 < k)
j++;
else
{
mineleofsubarrays.push_back(dq.front());
if(dq.front() == arr[i])
dq.pop_front();

// Sliding the window
i++;
j++;
}
}

for(int i = 0; i <= n-k; i++)
{
res = max(res, mineleofsubarrays[i]);
}

return res;
}
int main() {

int n, k;
cin >> n >> k;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];

cout << solve(arr, n, k) << endl;
return 0;
}```

## Array Coding Problem #5

Problem Name: Maximum sum circular subarray

Problem Statement: Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums. Here, a circular array means the end of the array connects to the beginning of the array.

Input Format

First Line contains Integers N (Size of the array).

Second Line contains N integers of the array.

Output format

Maximum Sum Subarray

Sample Input

7

8, -8, 9, -9, 10, -11, 12

Sample Output

22

Explanation

(12 + 8 – 8 + 9 – 9 + 10) = 22

### Maximum Sum Circular Subarray Solution

Now to solve this problem, firstly, we have to analyze two cases here:

Case 1: We find maximum sum subarray, considering no wrapping.

Case 2: In the second case, we’ll check the max sum subarray considering wrapping ends as below. We can see in the below figure that if we subtract minsum subarray from the total array sum then we can get the max sum subarray. Try to think over that and you’ll get it.

Now, we can get our answer as max(case 1, case 2).

For case 1, that is for finding the maximum sum subarray we can simply use Kadane’s Algorithm.

Now for case 2, that is for finding the minimum sum subarray we will use the Reverse Kadane algorithm. Umm, Now what is this? Don’t worry, there is nothing new about it. To find the minimum sum subarray, we’ll flip the sign of each element of the array and apply Kadanes’ on it. Now, we subtract this result with the total sum of the original array. But remember, we flipped the sign of array for the operation, so logically we will add the result to the total sum.(total + reverseKadane(arr))

Now, whichever is the maximum between case 1 and case 2, is our answer.

#### Lets take an example to understand the case 2:

arr[] = {2, 5, 8, -5, -2, -6, 7, 3}

Totalsum = 12

Array after flipping sign

arr[] = {-2, -5, -8, 5, 2, 6, -7, -3}

Apply Kadanes Algorithm, you will get (5 + 2 + 6) = 13

Case 2: Result = Totalsum + 13 = 25

Case 1 : Result = 15

Final Answer -> max(15, 25) = 25

Note: There is an edge, where the above will not work, i.e., when the array contains all negative elements. Think over that, and try to debug it by yourself. I handled this in the code below.

Time Complexity: O(N)

Space Complexity: O(1)

### C++ Code

```#include <bits/stdc++.h>
using namespace std;
{
int maxsum = arr[0];
int res = 0;
for(int i = 0; i < n; i++)
{
res = max(arr[i], res + arr[i]);
maxsum = max(maxsum, res);
}

return maxsum;
}

{
int total_sum = 0;

//Calculating sum and flipping sign
for(int i=0; i<n; i++)
{
total_sum += arr[i];
arr[i] = -arr[i];
}

// Handling all negative elements case
if(total_sum != -k){
total_sum += k;
}

}

int main()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];

cout << max(normal_maxsum, circular_maxsum) << endl;
return 0;
}```

### Java Code

```import java.util.Scanner;
class MaxSumSubarray {
int max = nums[0];
int res = 0;
for(int i = 0; i < nums.length; i++){
res = Math.max(nums[i], res + nums[i]);
max= Math.max(max, res);
}
return max;
}

int n = nums.length;
int total_sum = 0;

//Calculating sum and flipping sign
for(int i=0;i<n;i++){
total_sum += nums[i];
nums[i] = -nums[i];
}

// Handling all negative elements case
if(total_sum != -k){
total_sum += k;
}

}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

int nums[] = new int[n];
for(int i = 0; i < n; i++){
nums[i] = sc.nextInt();
}