Breaking Down and Rebuilding Interview Questions

There’s a common coding phrase that we learned about at Flatiron School. This phrase, which is commonly attributed to Kent Beck, goes something like this, “Make it work, make it right, make it fast”. That’s a list of instructions, a life philosophy, and the title for Fast & Furious 17, probably. Anyways, it breaks down to three separate categories; the first priority is to get the code working, second priority is to clean up and make the code work for all conditions, and the final priority is to refactor and make the code more efficient. It is a good mantra to have while writing code in both the short-term and long-term.

I’m used to writing code at my own pace, where I can apply these rules in order since each instruction is more difficult and complicated than the last. In an interview, time is crunched and all three objectives happen simultaneously. It is interesting to work under a time constraint, the added duress definitely puts a spin on things. To successfully complete an interview question, I’ve got to be thinking about space and time complexity from the beginning. I’ve been going on to codefights, to help prepare for algorithm questions. Even though there is a time limit, I can work at a pace where I can still deconstruct the coded into these three separate categories.

Below is an interview question on codefights. I believe this is one of the questions that they’ve taken from an actual interview. I have pasted a bulk of the question.

Given an array of integers nums and an integer k, determine whether there are two distinct indices i and j in the array where nums[i] = nums[j] and the absolute difference between i and j is less than or equal to k.

Example

• For nums = [0, 1, 2, 3, 5, 2] and k = 3, the output should be
  containsCloseNums(nums, k) = true.
• There are two 2s in nums, and the absolute difference between their positions is exactly 3.
• For nums = [0, 1, 2, 3, 5, 2] and k = 2, the output should be
• containsCloseNums(nums, k) = false.
• The absolute difference between the positions of the two 2s is 3, which is more than k.

I have broken down the code into my first solution, which passed most of the basic tests, and then my second solution, which had the proper space and time complexity needed to pass all the tests, and finally, someone else’s solution that is the most optimized. I bring up Kent Beck’s mantra because making it work wasn’t sufficient to pass the test, it needed to be right and fast as well.

function containsCloseNums(nums, k) {
    let arr = []
    let ind = []
    for (let i = 0; i < nums.length; i++) {
        nums[i] = Math.abs(nums[i])
        if (arr[nums[i]]) {
            arr[nums[i]] += 1
        } else {
            arr[nums[i]] = 1
        }
    }
    let check = arr.filter(k => k >= 2)
    if (check.length < 1) {
        return false
    } else {
        nums.forEach( (k,i) => 
            {if (k === arr.indexOf(check[0]))
                 {ind.push(i)}
            }
        )
        if ((ind[1] - ind[0] <= k) || (ind[2] - ind[1] <= k) ) {
            return true
        } else {
            return false
        }
    }
}

This was my first pass at the problem. Though it passed most of the basic tests, it was too slow to complete all of the required tests. To solve this problem, my first instinct was to set up an array that accounts for duplicates. This is what arr represents, the indices are the values of the original array, and the values are the count. Now that it worked, I had to identify the parts of the code that were wasting the most time. I put these lines in bold, the filter and forEach commands meant that I was running through the array two more times than necessary. If I was gunning for O(n), I was writing O(3n) with this code. I had to find ways to remove the filter and forEach functions. I solved those issues with the code below.

function containsCloseNums(nums, k) {
    let arr = []
    let ind = []
    for (let i = 0; i < nums.length; i++) {
        nums[i] = Math.abs(nums[i])
        if (arr[nums[i]]) {
            ind = [...arr[nums[i]], i]
            arr[nums[i]].push(i)
        } else {
            arr[nums[i]] = [i]
        }
    }
    if (ind.length <= 1) {
        return false
    } else {
        if ((ind[1] - ind[0] <= k) || (ind[2] - ind[1] <= k) ) {
            return true
        } else {
            return false
        }
    }
}

The filter and forEach functions have the same kind of quality to them, they require an array to be built beforehand, and then they search and parse through the code. Instead of relying on array being built beforehand, why not create those arrays simultaneously. The duplicate array, arr, will not be responsible for count anymore, but be responsible for holding the indices of the value. Take an example array of [1, 4, 2, 4]. Instead of “4” having a count of 2, it will be an array that holds the two indices “4”: [1, 3]. Since we now know that “4” is going to have multiple indices, we can directly place them into an array, ind, as well. The way we handle arr and ind now do not require the filter and forEach functions. We are back down closer to O(n).

function containsCloseNums(nums, k) {
    var indexes={}
    
    for(i=0; i<nums.length; i++){
        if(i-indexes[nums[i]]<=k) return true
        indexes[nums[i]]=i
    }
    
    return false
}

This is the complete, optimized solution. It is right and it is fast. It occupies less than half the lines that my best attempt did. Though I guess the time complexity is still considered O(n), this code has the potential to end before running through the entire array. The most time it will take is O(n), I’m not sure how to refer to is but the average time complexity could probably be considered to be more like O(.7n). I like this solution because it relies on a trick I have never tried before, it relies on a conditional statement

i-indexes[nums[i]]<=k

This statement will fail most of the time as this

Integer — undefined <= Integer

This is a false statement, which conceptually makes sense, but I was worried would cause an error exception. It is good to know that I can create conditionals with undefined terms interacting with real values. This is another way to speed up my code.

I hope this was a useful foray into my thought process for an interview question. It was good to extrapolate the problem into separate parts like Kent Beck’s mantra, because I will have to keep all three in mind while trying to solve a question on a real interview.