Transform array such that each element contains the greatest element on its right side

Problem statement

In this article we will be discussing how to solve an easy problem that has been asked at Amazon coding interviews. This is a must do problem for your coding interview preparation. The problem statement goes as follows:

You are given an array A of size N. You have to modify A in place s.t. A[i] = M where M is the maximum value among all elements A[j], j > i. If such element does not exists set A[i] = -1.

Example

Input :  A = {15, 22, 12, 13, 12, 19, 0, 2}
Output : A = {22, 19, 19, 19, 19, 2, 2, -1}

Input :  A = {2, 3, 1, 9}
Output : A = {9, 9, 9, -1}


Solution

Since this is a quite easy problem, we need to focus on making a good impression on the interviewer by showing a clean reasoning and elegant code implementation of the solution.

Let's start by outlining our solution:

1. The rightmost element of A will always be -1 There is no element at the right of the rightmost location.
2. When processing the element at index i all we need to do is substituting it with the maximum element found so far.
3. We need to make sure that at each iteration we keep track of what is the maximum element so far.

C++ Code

The ideas above can be coded as follows:

void solve(std::vector<int>&amp; V)
{
if(V.size() <=0 )
return;
//max so far
int M = -1;
int i = V.size()-1;
do{
const int m = max(M,V[i]);
V[i] = M;
M = m;
i--;
}while(i >= 0);
}


Another alternative and cleaner implementation is given below:

void solve(std::vector<int>&amp; V)
{
if(V.size() > 0 )
{
V.back() = -1;
for(int i = V.size()-2, M = V.back(); i >=0; i--){
const int m = max(M,V[i]);
V[i] = M;
M = m;
}
}
}


The time and space complexity of the code above is linear in the length of A.

If you liked this article and you want to read more about coding interview preparation, take a look at the previous article of the series.

Return the Maximum absolute difference of values and indices

The problem statement goes as follows:

Problem statement

Given an array A determine the maximum possible value of the following expression:
$f(i,j) =| A[i]-A[j] | +|i-j|$

Example

Input : A = {1, 3, -1}
Output : 5
because the maximum value obtainable is:
=> f(1,2) = |3 - (-1)| + |1-2| = 5

Input : A={3, -2, 5, -4}
Output : 10
=> f(1, 4) = f(4, 1) = |3 - (-4)| + |1 - 4| = 10
Note that in this case we can also obtain 10 from
=> f(3, 4) = f(4, 3) = |5 - (-4)| + |3 - 4| = 10


Sort an array of size N made of numbers from 0 to K

Problem statement

In this article we will be discussing another (see the previous article) very popular programming interview question. This time we are asked to sort an array of size N whose elements are in the range [0,K).

Problem statement

Given an array $A=[a_1,a_2,…a_n],\: 1 \leq a_i \leq K$
modify A s.t. it is sorted.

As usual you should ask your interviewer some clarifying questions. For example a sensible question to ask could be:

• What is the maximum value of $K$ and of $N$? Let's assume that $N \leq 10^7$ and $K\leq 10^3$

Example

Input : A={1,8,9,66,2,1,45,12}
Output : A={1,1,2,8,9,12,45,66}


Solution

First start noticing that the question seems rather simple at first. After all all you are asked to do is to sort an array. This is an easy peasy task that can be accomplished in a one-liner in C++.

Simple sort solution

bool sort_range_K(vector<int>&amp; A)
{
sort(begin(A), end(A));
}


But at this point you should also notice that you are not using the information about the range of the elements, and this should make your eyebrows raise and make you think a bit harder. This means that there is a better way of solving this problem.
The complexity of the above code is of $O(n \times log_2(n))$

Linear time Solution

You might not be aware of this (and if you are not I highly encourage you to get familiar with the topic) that it is possible to achieve better asymptotic complexity for sorting than $O(n \times log_2(n))$.
If you know the range of the elements you are dealing with, sorting can be done in linear time using Counting sort.

The idea behind is really simple. For each number in the range [0,K) you count how many times it appears in the original array in an array F of size K.
W.r.t. to the example above for instance:

A={1,8,9,66,2,1,45,12}
F ={0,2,1,0,0,0,0,0,1,1,....}

• F[0] = 0 because 0 appears 0 times in A
• F[1] = 2 because 1 appears 2 times in A
• $…$
• F[9] = 2 because 9 appears 1 times in A

With that information we can easily produce the output array by putting all the zeros first, then the ones, and so on.

C++ code

The idea above can be coded as follows:

template<class T>
void sort_range_K(vector<T>&amp; A, const int K)
{
vector<int> F(K,0);
for(const auto&amp;x : A)
F[x]++;

int p = 0;
for(int i = 0 ; i < K ; i++)
for(int j = 0 ; j < F[i] ; j++)
A[p++] = i;

}


The complexity of the code above is linear the length of $\Theta(A)$.
The space complexity is $\Theta(K)$
You can try the above code online on Wandbox.

Conclusions

In this article we discussed a common coding interview question asked by many tech companies. The takeaways from this exercise are:

• If an information is provided in the problem statement, it needs to be used
• If you know the range of the element you want to sort, you can sort them in linear time. The space complexity is linear in the biggest possible value an element of the array can take.

If you like this article check the previous article of the series (determine if a number is an Armstrong number).

Coding interview question: Determine if number is an Armstrong number

Problem statement

In this article we will be discussing another (see the previous article counting triples with a given sum) of the most common coding interview questions. The problem statement is really simple and goes as follows:

Given an positive integer N determine if it is an Armstrong number?
A number $x_1x_2…x_n$ (1 \leq x_i \leq 9 $is a digit ) of length$n$is an Armstrong number if the following is true:$x_nx_{n-1}…x_2x_1 = pow(x_1,n) + pow(x_2,n) + … pow(x_n,n)$In other words if raising all digits to power$n$and sum all them up you obtain the original number, then$N\$ is an Armstrong number.

The problem statement goes as follows: Given an vector<T> A of elements of type T of length Nand a vector<size_t> P where Pis a permutation of numbers from [0-N-1]you need to apply the permutation Pto the vector A. You are not allowed to use more than O(1) additional space.

For example suppose A=['a','b','c','d'] and P=['2','0','4','1']. After applying P to A, the latter becomes: ['c','a','d','b']. P[i] basically tell you which element of A should go in position i in the final arrangement of A.

Solving this problem can be very easy if you are allowed to use additional O(n) memory. All you need to do is to construct a new array, taking the elements as specified in P. The following code shows how this approach can be implemented in C++

template<typename T>
void apply_permutation(vector<T>&amp; A, const vector<int>&amp; P)
{
vector<T> A1;
A1.reserve(A.size());
for(size_t i = 0 ; i < A.size() ; i++)
A1.push_back(std::move(A[P[i]]));

A = move(A1);
}


Note how we use move which will avoid the copy if possible) of potentially heavy objects. Once the additional array A1 has been constructed, we modify A by moving A1 into it. That is pretty easy stuff.

In order to solve the hardest version we need to work a bit more.

The approach that will lead to the correct solution goes as follows: for each element that it is not yet in the correct location, then move it to its correct location. Sounds easy, and in-fact it it. Let's use the following concrete problem instance example as a guide:

• A = [a,b,c,d,e,f]
• P = [3,1,0,2,5,4]

For i = 0 we notice that P[i] != 0, meaning that in A[i] we should moveA[3]. In order to achieve so we swap(A[i], A[3]) which results in A=[d, b, c, a, e, f]. Now the first position of the answer is correct. Well done.

But we moved element originally at positioni=0to position 3which is clearly not its correct position ( because according to P, a should be placed in position 2). What do we do? We swap the correct element ( A[P[3]]) with A[3]=a . In other words we substitute the awith the element that should really go in that position i.e. c. After swap(A[3], A[2]), A=[d,b,a,c,e,f]. a is now not at location 2 and P[2] says that the element that should go here is a. good, we found the correct spot for the element originally in position i=0. In the process we also placed many other elements in the correct position.

Ideally now we should process another element that is not in its correct location. But how do we know which one is in the correct location? Since we cannot use any additional memory, we need to be clever and use P instead. What if we set P[i] = iwhenever we do a swap? If we do that then we do not really do nothing for that element because when P[i]= ithere is no work to do, as the element is already in its final location.

If we apply this line of reasoning to all elements of A then the final result will be what we really expected. Basically for an element i not yet in its correct location we keep swapping it until it reaches its final location. If we do it for all elements, then by definition we have solved the problem.

I am sure the idea above will be much more clear once we look at the code: curr and next are respectively the indices of the elements we are considering for a swap.

template<typename T>
void apply_permutation_in_place(vector<T>&amp; A, vector<int>&amp; P)
{
for(size_t i = 0 ; i < A.size() ; i++){
size_t curr = i;
size_t next = P[curr];
while(next != i)
{
swap(A[curr], A[next]);
P[curr] = curr;
curr = next;
next = P[next];
}
P[curr] = curr;
}
}


You can try the above code online on wandbox ( https://wandbox.org/permlink/NevnhZFq2G0cgL7O ).