Most of the interview questions that I have come across involve some kind of array manipulations. Here are a few common interview questions based on arrays:
1. Given an array consisting of 0s and 1s sort it in one-pass
This problem is similar to the partition step of Quicksort, where elements less than or equal to the pivot are on the left side of the eventual location of the pivot and the elements greater than the pivot are to its right. Similarly, in this case we partition such that all 0s appear before all 1s. The code is as below.
void ColorSort2(vector<int> &arr)
{
int sz = arr.size();
int i=0, j=0;
while(j<sz)
{
while(j<sz && arr[j] == 1)
{
j++;
}
if(j<sz)
swap(arr[i++], arr[j]);
}
}
2. Given an array consisting of 0s,1s,2s sort it in one-pass [Dutch national flag algorithm]
The problem is similar to the previous problem. This is because, it can be mapped to a different partition approach of Quicksort, where we divide the entire array into three parts. The left part consists of the elements lesser than the pivot, the center corresponds to the elements equal to the pivot and the right part consists of elements greater than the pivot. The code is as below.
void ColorSort3(vector<int> &arr)
{
int sz = arr.size();
int i=0, j=0, k = sz-1;
while(j<=k)
{
while(j <= k && arr[j] == 1)
j++;
if(j>k)
break;
if(arr[j] == 0)
swap(arr[j++], arr[i++]);
else if(arr[j] == 2)
swap(arr[j], arr[k--]);
}
}
3. Given an array consisting of equal number of positive and negative numbers, rearrange them so that negative numbers are in even positions and positive numbers are in odd position.
The problem is similar to the previous 2 problems which are modified versions of the Quicksort partitioning scheme. In this problem, we use a similar scheme where we partition elements in even and odd positions instead of partitioning left and right of the pivot as is the case in the standard Quicksort partitioning scheme.
void alternate_positive_negative(int arr[], int n)//Where n is the size of the array
{
int i=0, j = 1;
while(i<n && j<n)
{
while(i<n && a[i]<0){i+=2;} //If a negative element is in the even position move to the next even position
while(j<n && a[j]>0){j+=2;}//If a positive element is in the odd position move to the next odd position
if(i< n && j<n)
{
swap(a[i], a[j]);//If we find an (i,j) such that a positive element is in even position and a negative element is in the even position - swap the two elements.
i+=2;
j+=2;
}
}
}
4. An array A[] consists of positive and negative numbers such that the sum of all elements is 0. Now if you start with an index 'k' in each array and do the following summation, SUMMATION (Ak), where Ak is the value at index k of array A, where 'k' increments and wraps back all the way to k-1, the final sum value will be zero. Question: Find a suitable 'k' such that during any point in the summation, SUMMATION(Ak) is always non negative. Find such a 'k' in O(n) time.
For eg. consider an array A[0] = {a,b,c,d}. If k=1, the summations start with 1 and are a[1] followed by a[1]+a[2], a[1]+a[2]+a[3] and wrapping around a[1]+a[2]+a[3]+a[0].
Now, k is valid if
a[1]>=0,
a[1]+a[2] >=0,
a[1]+a[2]+a[3]>=0 and
a[1]+a[2]+a[3]+a[4]>=0.
Find such a valid k in O(N).
int FindIndex(int arr[], int nums)
{
int start = 0, end;
while(arr[start]<0)start++; //Start with some k = start, such that arr[start]>=0
int sum = arr[start];
end = start+1; //End indicates that all elements from [start, end) have been scanned. The interval wraps around the left as well as the right end
while(start!=end)
{
sum = sum+arr[end]; //Increment end, as long as sum>=0
end = (end+1)%nums;
while(sum<0) //If sum < 0
{
start--;
if(start<0)
start = nums-1;
sum = sum+arr[start]; //Decrement start till sum >=0. If sum >=0, all SUMMATIONS from [start, end) are positive. Please note that, the interval wraps around the left and right endpoints as seen previously.
}
}
return start;
}
5. Given 123, 1+2 = 3;
Given 123410, 1+2+3+4 = 10; Thus, given a number can an equation be formed. Only +/= can be used.
Here, we divide the work into 2 functions. In the driver function we generate all possible values that can appear on the right hand side. Thus, in the above example (123410) the values that can appear on the right hand side are: 0, 10, 410, 3410, 23410. The 2nd function checks if an equivalent value can be obtained as a sum of some combination of the remaining digits and ‘+’ signs. The code is as below. Maintain a state variable for better performance.
bool CanFormN(char *string, int end, int n)
{
if(n == 0 && end == -1)
return true;
if(end == -1)
return false;
char temp = string[end+1];
string[end+1] = 0;
for(int i = end;i>=0;i--)
{
int num = atof(string+i);
if(num>n)
break;
if(CanFormN(string, i-1, n-num)
{
string[end+1] = temp;
return true;
}
}
string[end+1] = temp;
return false;
}
bool CanEquationBeFormed(char *string)
{
int num = strlen(string);
for(int i = num-1;i>0;i--)
{
int n = atoi(string+i);
if(CanFormN(string, i-1, n))
return true;
}
}
