Hey Folks,
Welcome back to LetsAlgo.
Today I will be talking about the top 5 array problems that are most frequently asked in interviews. I am saying with my personal experience as well.
Array is considered as the most basic data structure, which is probably used in every application. Hence it’s become quite necessary to have a good grab on it.
Interviewers asked questions related to arrays to check how you handle indexes and values to derive an optimized solution.
So below are the 5 handpicked problems which are asked most frequently in interviews.
Without wasting much time, let’s get started.
1) Move all 0s to the end.
This is simple yet a bit tricky for those who have just started preparing the data structure for the interview.
Problem Statement:
You are given an array of integers, your task is to move all 0s to the end.
Code:
void moveZeroToEnd(int arr[], int n)
{
int left = 0;
int right = 0;
while(left < n) {
if (arr[left] == 0) {
left++;
} else {
swap(arr[left],arr[right]);
left++;
right++;
}
}
}
Brief:
So to solve this problem optimally, we just use two pointers, left and right.
Left looks for the non-zero element and right hold the index of zero elements.
Every time we find the non-zero element, we just swap the element at right with the element at left.
For a detailed article about this problem, please click here.
2) Sort array of 0s,1s, and 2s.
This is another most frequently asked array data structure problem and it has been asked in interviews of multiple reputed organization.
Problem statement:
You are given an array of 0s, 1s, and 2s, your task is to sort the input array without using any sorting algorithm.
Code:
void sort012(int arr[], int n)
{
int left = 0;
int middle = 0;
int right = n-1;
while(middle <= right ) {
if (a[middle] == 0) {
swap(a[middle], a[left]);
left++;
middle++;
}else if (a[middle] == 1) {
middle++;
}
else {
swap(a[middle], a[right]);
right–;
}
}
}
Brief:
To Solve this, we use three-pointer name left, middle and right, first two has initial values 0s and the last one has an initial value equal to the length of array-1.
We swap elements at the left and middle pointer, whenever we find 0 in the array.
When we find 1, then we just increase the middle pointer.
When we find 2, we swap elements at middle and right and decrease right.
For a detailed article about this problem, please click here.
3) Rotate array by K
Yet another, frequently asked interview problem. You just can not afford to skip this one.
Problem Statement:
You are given an array of size n and an integer value k. Your task is to rotate the input array towards the left by k times.
Code:
void reverse(int arr[], int start, int end)
{
while(start < end) {
swap(arr[start++],arr[end–]);
}
}
void rotate(int arr[], int n, int k)
{
reverse(arr,0,k-1);
reverse(arr,k,n-1);
reverse(arr,0,n-1);
}
Brief:
To rotate the array by K time, we just divide the array into two parts, one from 0 to K-1 and another from k to n-1.
We then rotate both parts of the array.
At last, we rotate the entire array and which gives us our output.
For a detailed article about this problem, please click here.
4) Maximum and minimum element.
This is one of the plainest and simple problems of array data structure yet it is asked multiple times.
With this problem, the interviewer sees, how well you can handle base cases and reduce the iterations and no. of comparison.
Problem statement:
Your task is to find maximum and minimum elements in the input array with a minimum comparison as possible.
Code:
void getMinMax(int arr[], int n)
{
if (n == 1) {
cout<<“maximum “<<arr[o]<<endl;
cout<“minimum”<<arr[o]<<endl;
return ;
}
int minimum;
int maximum;
if (arr[0] > arr[1]) {
minimum = arr[1];
maximum = arr[0];
} else {
minimum = arr[0];
maximum = arr[1];
}
for(int i = 0; i < n; i++)
{
if (arr[i] > maximum)
maximum = arr[i];
else if (arr[i] < minimum)
minimum = arr[i];
}
cout<<“maximum “<<maximum<<endl;
cout<“minimum”<<minimum<<endl;
}
Brief:
So as said earlier, this problem is very much about base cases.
As our first base case, we checked if the length of the array is 1. If that is true then our maximum and minimum element would be that element only.
If the above condition is false, then we compared the first two elements and initialized maximum and minimum.
Then we ran a loop from 2 to the length of the array and on every iteration, we checked for minimum and maximum elements.
For a detailed article about this problem, please click here.
5) Pair of sum
This is the most common problem asked in interviews and the reason for the same is, this is a moderate problem, and it’s sufficiently good to check interviewee analytics skills.
Problem statement:
You are given an array of length n and a K integer value. Your task is to find numbers of pairs of elements in the array whose sum is equal to K.
Code:
int getPairsCount(int arr[], int n, int sum)
{
unordered_map<int, int> map;
for (int i = 0; i < n; i++)
map[arr[i]]++;
int count = 0;
for (int i = 0; i < n; i++) {
count += map[sum — arr[i]];
if (sum — arr[i] == arr[i])
count–;
}
return count / 2;
}
Brief:
So to solve this problem we use an unordered map, which is a key-value pair dictionary.
In key, we store the unique element and in the value, we store the occurrence of that element in the input array.
Then we run for loop and in every iteration, we look for a paired element for the current element in our map.
For a detailed article, please click here.
