These problem-solving patterns will help you ace your next coding interview

Coding interviews might be daunting for many applicants. Especially those, where you have to code live without accessing external resources. It is a completely different environment setup from a classical workflow, where you are working on a feature and you can access Google and Stack Overflow. It is a craft on its own and it can be mastered by hours of practice.

Today, I will share several patterns that can help you tackle down certain classical problems and help you build a mental framework, that will make your life easier.

All examples of code are written in JavaScript but can be applied to other languages as well.

Objects are your friends

A lot of interviewing questions are tricky. They test if we can really think about code as they tease us to choose a brute force decision.

Write a function that takes two arrays as arguments and returns true if those arrays have at least one element in common. Otherwise, it should return false. You can expect that the arrays are not empty and elements in them can repeat.

As we see the problem this obvious solution can come to mind: Create a nested loop and check all elements against each other, if two elements are equal we can return true.

 arr1 = ["a", "b", "c", "c"]
 arr2 = ["d", "e", "f"]
 arr3 = ["g", "h", "b"]
// yourFunc(arr1, arr2) -> false
// yourFunc(arr1, arr3) -> true (both contain "b")

function containsSameElement(arr1, arr2) {

  for (let i = 0; i < arr1.length; i++) {
    const curr = arr1[i]
    for (let j = 0; j < arr2.length; j++) {
      if (curr === arr2[j])  {
        return true
      }  
    }
  }

  return false
}

containsSameElement(arr1, arr3) // true
containsSameElement(arr1, arr2) // false

Well, the "obvious" solution gets the job done. But is it the best solution? Its complexity is O(n*m), therefore not very efficient for large inputs.

A better solution, that shows we can think about a problem in terms of its efficiency, is the following.

 arr1 = ["a", "b", "c", "c"]
 arr2 = ["d", "e", "f"]
 arr3 = ["g", "h", "b"]
// yourFunc(arr1, arr2) -> false
// yourFunc(arr1, arr3) -> true (both contain "b")

function containsSameElement(arr1, arr2) {
  const obj = {}
  for (let el of arr1) {
   obj[el] = true
  }

 for (let el of arr2) {
   if(obj[el]) {
     return true
   }
 }

  return false
}

containsSameElement(arr1, arr3) // true
containsSameElement(arr1, arr2) // false

As we can see, there are no nested loops, so its complexity is "only" O(n+m), therefore linear.

This pattern can also be applied to frequency problems such as anagrams.

Write a function that is gonna take two strings as arguments and returns true if they are anagrams (Wikipedia: An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once). Otherwise, the function should return false. The inputs are not empty and are lowercased

 str1 = "cinema"
 str2 = "iceman"
 str3 = "icemen"
// yourFunc(str1, str2) -> true
// yourFunc(str1, str3) -> false 

function isAnagram(str1, str2) {
  const obj = {}

  for (let l of str1) {
    obj[l] = obj[l] ? obj[l] + 1 : 1 
  }

  for (let l of str2) {
    // number <= 0 is falsy
    if(!obj[l]) {
      return false
    } else {
      obj[l] = obj[l] - 1
    }
  }


  return true
}

isAnagram(str1, str2) // true
isAnagram(str1, str3) // false

Again, we managed to avoid nested loops and found a quite elegant solution. Knowing this pattern we should always think twice before reaching for a nested loop.

Multiple pointers

This pattern is helpful when working with sorted arrays and we are required to find a pair of elements that fulfill a certain condition.

Write a function that accepts a number and a sorted array. Find a pair of elements whose average equals the number that was passed as the argument. The function should return them as an array. If there is no such number return null. The passed array contains at least two sorted elements. If you find several solutions, return just one

const arr = [-2, 3, 7, 8, 9]
// yourFunc(arr, 5) // [3,7]
// yourFunc(arr, 2) // null


function avgPair(arr, num) {
  let left = 0;
  let right = arr.length - 1

  while (left < right) {
    let avg = (arr[left] + arr[right]) / 2
    if(avg === num) {
      return [left, right]
    } else if (avg < num) {
      left++
    } else {
      right--
    }
  }
  return null
}

avgPair(arr, 5) // [3,7]
avgPair(arr, 2) // null

Write a function that accepts a sorted array of length 1 or more and returns the number of unique values in that array. You can modify the passed array

Our algorithm will consist of having two pointers which we will compare. Then, we will be modifying our passed array to have all the unique elements at the start, and at the end, we will return a value of one of the pointers as it's gonna be pointing to the last unique elements of that sorted "subarray".

const arr = [-2, -1, -1, 0, 3, 6, 6, 7, 8, 8]
// yourFunc(arr) // 7


function uniqNumbersCount(arr) {
  let i = 0
  for(j = 1; j < arr.length; j++) {
    if(arr[i] !== arr[j]) {
      i++
      arr[i] = arr[j]
    }
  }
  // i is pointing to the index, but we want the length
  return i + 1
}

uniqNumbersCount(arr) // 7
console.log(arr) // [ -2, -1, 0, 3, 6, 7, 8, 7, 8, 8 ]


// Alternative one-liner
const uniqNumbersCount2 = (arr) => new Set(arr).size

Sliding

Whenever we see the word "sub" in the problem we are about to solve. The sliding pattern might be a good approach.

The idea of the sliding pattern is basically moving over the array or string as a laser scanner of a certain length.

Write a function that accepts a number (n) and an array and returns the maximum sum of the consecutive n elements. The number n will always be equal to or smaller than the length of the array

const arr = [7,8,2,6,8,1,12,5,13,8,2]
// your func(arr, 3) // 30 (12,5,13)


function maxSum(arr, num) {
  let max = -Infinity
  let maxLength = arr.length - num + 1

  for(let i = 0; i < maxLength; i++) {
    let tempSum = 0;
    // Sliding
    for(let j = 0; j < num; j++) {
      tempSum += arr[i + j]
    }
    if(tempSum > max) {
      max = tempSum
    }
  }

  return max
}

maxSum(arr, 3)

Divide and Conquer

A classical approach that is used in the more efficient sorting algorithms. You can read my article on sorting if you wanna dive deeper into this concept.

The idea behind divide and conquer is basically splitting our sorted data into smaller chunks and then working with a smaller portion of data during each iteration. We can reach a complexity of O(log(n)).

A classical algorithm that illustrates this approach is Binary Search.

*Write a function that takes a sorted array and a number (n) and returns true if the array contains n, otherwise the function should return false. The array is not empty. *

const arr = [1,3,7,9,15,23,85,101,250]
// yourFunc(arr, 23) // true
// yourFunc(arr, 11) // false


function searchEl(arr, num) {
  let start = 0
  let end = arr.length - 1

  while(start <= end) {
    let middle = Math.floor(((start + end) / 2)) 
    if(arr[middle] === num) {
      return true
    } else if (arr[middle] < num) {
      start = middle + 1
    } else {
      end = middle - 1
    }
  }
  return false
}


searchEl(arr, 23) // true
searchEl(arr, 11) // false

The reason the complexity of the searchEl function reaches "only" O(log(n)) is, that if we double the array we only have to make one more step as we eliminate half during each iteration. Logarithmic functions are the inverses of exponential ones.