Interview Killer: Arrays

Technical 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:

1. Write a function that takes an array as a parameter.

2. 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.
3. Use Summation formula to calculate the default sum and store the result in totalSum variable.
4. Iterate through the array, calculate the sum, and store the result in a different variable, say, sum.
5. When you subtract sum from totalSum, 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 pre-defined 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 sub-title, I mean any given structure that lets you store key-value 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.