Interview Killer: Arrays
Oct 5th 2020Technical interviewers love arrays. They can run your unprepared mind to the ground with various logical questions about them. With little to no prior knowledge,it can be really tough to figure out some of these questions on the spot. I'll ask you this: which is faster, main RAM of a computer, or its cache memory? Of course, its cache memory. When the interviewer looks at you and asks a hard question, you should be able to get the answer from your mind's cache memory, and kill the interview. On this first installment of Interview Killer, I will go through some of the more common interview tasks regarding arrays, and provide solutions to them, however, I strongly recommend you try to solve the problem yourself before looking at the provided solutions. You can use any language that you're comfortable with, but I will be using Javascript from this point on.
1. FINDING MISSING ELEMENTS IN A GIVEN INTEGER ARRAY
Say, you're given an array containing sorted elements from 1 to 10. One of the elements is missing and your task is to instruct the computer to find such an element and return it. What you can do is simply calculate the default sum for any sorted array using a Summation formula. Sum of an array from 1 to n, using this formula would be n(n+1)/2*. In pseudocode, what we need to do is:
 Write a function that takes an array as a parameter.

Declare
n
variable and equate it to the value of the last element in the array. The sum would be n(n+1)/2 if the array was not missing an element.
 Use Summation formula to calculate the default sum and store the result in
totalSum
variable.  Iterate through the array, calculate the sum, and store the result in a different variable, say,
sum
.  When you subtract
sum
fromtotalSum
, what you get is the value of the missing element.
const MissingElement = (array) => {
let n = array[array.length  1]
let totalSum = n * (n + 1) / 2; // Summation formula
let sum = 0;
// Iterating through the array and adding its elements
// Onto each other on each iteration
for (let i = 0; i < array.length; i++){
sum += array[i];
}
console.log(`Sum if there was no missing element: ${totalSum}`)
console.log(`Sum excluding the missing element: ${sum}`)
return totalSum  sum; // what we need
}
// Driver code
let fuctionValue = MissingElement([1, 2, 3, 4, 6, 7, 8, 9, 10]);
console.log(`Missing element: ${fuctionValue}`);
Time Complexity of the above code is O(n), only one iteration cycle needed. Let's looks at the output of this code:
Sum if there was no missing element: 55
Sum excluding the missing element: 50
Missing element: 5
2. FINDING DUPLICATES IN A GIVEN INTEGER ARRAY
You are given an array of integers in which you have to find duplicate numbers. The array might have negative numbers or it might not, it also may be sorted or not. Who knows, but down below you'll find a solution for each usecase respectively.
2.1 Simplified solution
The simplest and most straightforward way of checking for duplicates in an integer array is to iterate through its elements and compare each of them to their next neighbor. Naturally, this first solution requires the array to be sorted.
const duplicateKiller = (array) => {
if (array.length <= 1) { // How will it have duplicates with only just 1 element?
console.log("Invalid situation for this case")
return 1
}
array.sort() // If we don't sort the array, this solution won't be correct
let duplicateArray = [] // Here we store duplicated numbers, one by one
for (let i = 0; i < array.length; i++){
if (array[i] == array[i + 1]) { // Comparing an element to its next neighbor
duplicateArray.push(array[i])
}
}
return duplicateArray; // Returning an array filled with only duplicated numbers
}
let sampleArray = [1, 2, 3, 4, 5, 6, 6, 8, 7, 8];
const answer = duplicateKiller(sampleArray);
console.log(answer)
The above solution's Time Complexity value is O(nlog(n)) because we needed to sort the array. This solution, as you can see, also works with negative numbers.
2.2 Counting with an additional data structure
The second solution to this problem is to have an additional data structure count each element's occurrence. I'll use a separate array to store such information.
const duplicateKiller2 = (array) => {
let duplicateArray = []
if (array.length <= 1) {
console.log("Invalid situation for this case")
return 1
}
// Here I initialize an array filled with 0s, since, by default
// All iterations are on 0, later to be incremented.
let count = new Array(array.length  1).fill(0);
// Alternatively, you could use a for loop to do the
// Exact same thing as the above line.
// for (let i = 0; i < array.length  1; i++){
// count[i] = 0;
// }
for (let i = 0; i < array.length; i++){
// n variable takes in the value of the ith element...
let n = array[i];
// And uses it as index. If this index is revisited
// And thus incremented, it means that a duplicate has been spotted
count[n]++;
// If the index has been incremented more than once,
// Its value is going to be more than 1, for sure
if (count[n] > 1){
duplicateArray.push(array[i]);
}
}
// The returned array will contain all duplicates.
return duplicateArray;
}
let sampleArray2 = [3, 2, 2, 6, 6, 1, 1, 3, 7];
const answer2 = duplicateKiller2(sampleArray2);
console.log(answer2)
The 2.2 solution offers Time complexity of O(n), and since we're relying on array indexes to help us in counting, we're unable to use negative numbers, as there are no negative indexes to be visited in an array.
3. FINDING BOTH LARGEST & SMALLEST NUMBER IN AN UNSORTED INTEGER ARRAY
You're lucky if you get his task because it is fairly easy. But there's a catch  you have to traverse the array only once and therefore achieve time complexity of O(n). To complete this task efficiently, you should keep track of both min
and max
variables in a single function. All that you can do by setting their values to that of the given array's 0th element. From this point, once we write out the for
loop, there are two possibilities to look out for  the ith element either is greater than the max
variable's value or it is not. If it is, we should pass the ith element's value to max
, and if it is not, we should pass the ith element's value down to min
. Once the for
loop is over, what we'll be left with are min
and max
variables with correct values.
const MinMax = (array) => {
min = array[0];
max = array[0];
// Kills two birds with one stone ↓↓↓
for (let i = 0; i < array.length; i++){
if (array[i] > max) {
max = array[i];
}
else {
min = array[i];
}
}
// Tip: you can return multiple values by using arrays
return [min, max];
}
let sampleArray3 = [1, 2, 4, 5, 8, 10, 11, 12, 15];
// That'll be [12, 15] in this case
const answer3 = MinMax(sampleArray3);
console.log(answer3);
4. COUNT PAIRS WITH GIVEN SUM
Already sounds tricky, doesn't it? You're given an arbitrary array in which you have to find and count pairs with a predefined sum. If you're given a sum of, say, 15, you should look for pairs like [11, 4], [9, 6], [5, 10] and so on. In this case we can ignore the order, in other words, it doesn't matter whether the numbers in the pair are in a row or not.
4.1 Double traversal method
The simplest way of solving this problem is traversing the array twice, the first for
loop stops at each element and looks for possible other elements to add to give correct sum, by engaging the second, nested for
loop. If current iterations of both loops sum up to the given value, the count
variable should be incremented once.
const CountPairs1 = (array, sum) => {
let count = 0;
// Outer loop
for (let i = 0; i < array.length; i++){
// Inner loop
for (let k = i + 1; k < array.length; k++){
// If current iterations sum up to what we want,
// The count goes up
if (array[i] + array[k] == sum){
count++;
}
}
}
return count;
}
The above solution is far from perfect. In fact, it is really slow because it offers Time Complexity of O(n²) due to us running two for
loops, effectively making n amount of steps on each iteration, the number of which is also n, thus  n². Let's write something faster.
4.2 Single traversal method using a hash map/table data structure
This solution is one power of n faster than the previous one. This time we will be taking advantage of what's called Dynamic Programming, meaning that we will be saving computed values for later usage to find the solution. By saying hash map/table data structure up in the subtitle, I mean any given structure that lets you store keyvalue pairs. Such can be, for example, dict
in Python. In Javascript, a simple object would suffice. So, in pseudocode, the plan is:
 Write out a function that accepts an array and a number as two of its parameters.
 Declare variables for our hash map, pairs array and count.

Traverse the array and check if there is an element with key in the hash map, that corresponds to the current iteration's value.
 If there is such an element, we need its key and value.
 If there is no such element, save what'd the current iteration value need to complete the sum, as the key, and the current iteration's value, as the value.
 So, if the remembered (key) number ever comes up in the array, the above
if
statement will catch it and pair its value up with the current iteration's value.
 Return hash map, array and count.
const CountPairs2 = (array, sum) => {
// Could be dict in Python, or HashMap in Java,
// or Dictionary in C#...
let hashMap = {};
let pairs = [];
let count = 0;
for (let i = 0; i < array.length; i++){
// If there exists an element with this key
// Take its value, pair it up with the current iteration
// And append to the pairs array
if (hashMap[array[i]]){
pairs.push([hashMap[array[i]], array[i]]);
count++;
}
// If there is not, save the computed value for potential later usage
else {
hashMap[sum  array[i]] = array[i];
}
}
// Return as array, you can be more creative than that, though
return [hashMap, pairs, count];
}
let sampleArray4 = [1, 2, 5, 4, 6, 7, 9, 4, 8, 2];
const answer5 = CountPairs2(sampleArray4, 10);
console.log(answer5);
To make sure that you understand this latest example, let's go through it once again, but with a microscope.

Iteration 0
i
is 0. In our array, 0th element is 1.
 Is there an element in the hash map that has '1' as key?
 No.
 Then, create an element with key of
sum  array[i]
(aka 10  1 in our case, which is 9) and set its value to the current iteration's value (aka 1).
...Some iterations later

Iteration 6
i
is 6. In our array, 6th element is 9.
 Is there an element in the hash map that has '9' as key?
 Yes.
 Visiting key '9', we see its value is 1.
 Combine it with the current iteration's value (aka 9), we get a valid pair.
 Append.
Take a look at the output of the last bit of code:
[
{ '3': 7, '5': 5, '6': 4, '8': 2, '9': 1 },
[ [ 4, 6 ], [ 1, 9 ], [ 2, 8 ] ],
3
]
Some pairs in the hash map are not valid. The system encountered 7 in the array, saved 3 as the key, 7 as the value, but that 3 was never encountered in the array.
TO BE CONTINUED...
That's it for today's Interview Killer. Stay tuned for further installments of this rubric on Darkroom. Visit the Shop or Projects tab in the meantime, if you'd like.