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
- Napolean Cake (Codeforces)
- Max Chunks To Make Sorted (Leetcode Medium)
- Possible Options to book the room
- Maximum of minimum of all subarrays of size k
- 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:
- Initialize a variable *res* as 0.
- Run a loop for i equals 0 to (n – k).
- Run a nested loop for j = i to (i + k)(not included), this loop represents a sub-array of size k.
- Traverse this sub-array and find the minimum elements.
- Then find max(res, min).
Now, res contains your result.
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:
- Initialize a variable res = INT_MIN.
- Declare a vector to store minimum element of all subarrays of size k, and a deque.
- Take two variables i=0 and j=0 as we do in standard sliding window technique.
- Run a loop while(j<n)
- 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.
- Now push back this current element.
- 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.
- 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.
- Slide the window by doing i++ and j++.
- 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
Normal Kadanesum(arr) = 15
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 kadane(int arr[], int n)
{
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 reverseKadane(int arr[], int n)
{
int total_sum = 0;
//Calculating sum and flipping sign
for(int i=0; i<n; i++)
{
total_sum += arr[i];
arr[i] = -arr[i];
}
//Apply Kadanes' over modified array
int k = kadane(arr, n);
// Handling all negative elements case
if(total_sum != -k){
total_sum += k;
}
return total_sum;
}
int main()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
int normal_maxsum = kadane(arr, n);
int circular_maxsum = reverseKadane(arr, n);
cout << max(normal_maxsum, circular_maxsum) << endl;
return 0;
}
Java Code
import java.util.Scanner;
class MaxSumSubarray {
public static int kadane(int[] nums){
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;
}
public static int reverseKadane(int[] nums){
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];
}
//Apply Kadanes' over modified array
int k = kadane(nums);
// Handling all negative elements case
if(total_sum != -k){
total_sum += k;
}
return total_sum;
}
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();
}
System.out.println(Math.max(kadane(nums), reverseKadane(nums)));
}
}
If you want us to add more array coding questions kindly tell us in the comments. Don’t forget to share it with your friends. Thanks 🙂
Please wait for the next 45 Array Coding Questions for Online Assessment, till then enjoy coding.
Thank you guys for visiting our website, hope you enjoyed the article and found it useful, if you have any queries regarding the article or the website i.e. if you found something mistakes in the article or website, then you can reach out to us at admin@violet-cat-415996.hostingersite.com.
Also read:
- Download 1000+ Projects, All B.Tech & Programming Notes, Job, Resume & Interview Guide, and More – Get Your Ultimate Programming Bundle!
- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope
