# A Coding Test I Took

Nov 20, 2020 · 4 min read

I appeared in the Nasdaq Intern Hiring Challenge 2020.
The challenge included two coding questions and 10 MCQs.
The MCQs were easy. They were based on basic Math, understanding of pie charts, bar graphs etc.

Out of the two coding questions, I was able to solve one correctly.

This question was called, ‘Arrays and Pizzas’.

Here are the screenshots I took:

In lesser words, the question says:

We’re given an array of integers (the size of which is always a multiple of 4).
We are supposed to divide this array into sets having 4 elements each.
From each set, the second minimum element out of the four elements, will be added to a variable ‘gain’ (which is initialized to 0).
The task is to maximize the value of gain.

You might want to stop reading and think about the problem (and the possible solution) for a few minutes.

The second minimum element of each set is added to the variable ‘gain’ and we want to maximize ‘gain’. So, we would greedily want the second minimum element of each set to be as large as possible.
But, at the same time, this element must be smaller than two other elements of the set.

Consider this example:

Array: 1,3,4,10,11,12,5,6,7,8,9,2

The largest element in this array is ‘12’. Can we make a set of four elements, such that ‘12’ is the second minimum?
No.
To make ‘12’ the second minimum element, we need two more elements greater than ‘12’. But ‘12’ itself is the largest element.
So, we look for the largest element in the array, such that there are only two elements greater than itself.
‘12’ is the largest. ‘11’ is the second largest. Then comes ‘10’. ‘10’ is the largest element of the given array, such that there are only two more elements in the array greater than itself.
‘10’ is hence the largest element we can add to ‘gain’.
The set becomes, {10,11,12}.
But we are supposed to form sets of four elements each. We need one more element to complete this set.

{x,10,11,12}

Can we choose the next largest element ‘9’ ?
We can. But if we choose ‘9’, we’d be wasting away a large valued element which otherwise could have been used in forming another set and maximizing ‘gain’.
So, we use the smallest element of the array to complete this set, i.e. ‘1’.
The set becomes {1,10,11,12}.
We add the second minimum element of this set to ‘gain’.

‘gain’ = 0+10 = 10

Let us sort the array so that it is easier to find the largest and the smallest elements.
After sorting we get:

Array: 1,2,3,4,5,6,7,8,9,10,11,12

If we observe this sorted array, we see that every third element from the end can be added to ‘gain’ to maximize it.

Example:

We made the first set as: {1,10,11,12}

The array becomes: 2,3,4,5,6,7,8,9

Now the largest element with only two elements greater than itself is ‘7’ (the third element from the end).
So, we form a set : {7,8,9}
As explained above, we insert the smallest element from this array to the set to complete it.
{2,7,8,9}
We add the second minimum of this set to ‘gain’.

‘gain’ = 0 + 12 + 7

The pattern is evident.

Every third element from the end of the sorted original array is added to the variable ‘gain’. One element from the beginning of the array (where the smallest elements are present) is removed each time ‘gain’ is updated.

This problem can be solved using two pointers, ‘i’ and ‘j’. ‘i’ pointing to the start of the array and ‘j’ to the third largest element.
We run a loop, adding array[j] to the gain on each iteration, then decrementing ‘j’ by 3 and incrementing ‘i’ by 1.
The loop runs as long as ‘i’ is smaller than ‘j’.

The entire array is traversed only once, so the complexity is O(N), where ’N’ is the number of elements in the array.

Note that we are required to sort the input array and the inbuilt sort() function in C++ implements Quick Sort under the hood, which has a complexity of O(NlogN).

Written by

Written by