DEV Community

loading...
Cover image for These problem-solving patterns will help you ace your next coding interview

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

albert_hadacek profile image Albert Hadacek ・5 min read

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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.

Discussion (8)

pic
Editor guide
Collapse
jonrandy profile image
Jon Randy • Edited

Why so much code?

const isAnagram = ([...str1], [...str2]) => str1.sort().join() == str2.sort().join()
Enter fullscreen mode Exit fullscreen mode

Or, if you want to go small and don't mind polluting global namespace:

const isAnagram=([...a],[...b])=>(x=s=>s.sort().join(),x(a)==x(b))
Enter fullscreen mode Exit fullscreen mode
Collapse
roberocity profile image
Rob Sutherland

Jon,

I like terse code. And for most scenarios, the terse code will work perfectly. However, the terse code will start to show performance issues with sufficientlly large strings (or arrays).

I often forget to consider the algorithmic time complexity of native methods when I'm writing code. I don't really think about what goes in to array.sort(), I just know it works.

If we dive into the gritty details of the custom algorithm vs the terse code, we can start to see they have different asymtotic runtimes.

For the terse code using native methods:

  • array.sort() is O(n log n) when n > 10 and O(n^2) when n <= 10.
  • array.join() is O(n)
  • array == array is O(n + m)

For the custom code:

  • iteration is O(n)
  • dictionary lookup and set are constant O(1)

So we'll end up with the custom code's asymtotic runtime of O(n + m) and the terse code's runtime of O(n log n + m log m). That is a relatively minor considering the log(1,000,000) is 6. But it could make a difference if performance was key.

Oh, and yes, i realize the idoicy of a 1,000,000 character anagram. However, it is important to consider the runtime and go native when you can and custom when you really need to get every bit of performance.

Collapse
albert_hadacek profile image
Albert Hadacek Author

Well, you cant do that in other languages. I wanted a solution that people can "replicate" using a language of their choice ;)

Collapse
jonrandy profile image
Jon Randy • Edited

Yes, you almost certainly can. I think plenty, if not most other languages have the ability to split strings, sort arrays, and join arrays. These are fairly common operations. The syntax would be different, sure - but the logic is easily repeatable

Thread Thread
jonrandy profile image
Jon Randy • Edited

Here is the same technique in Python (array join not necessary as we can do array equality):

def is_anagram(str1, str2):
  return sorted(list(str1)) == sorted(list(str2))
Enter fullscreen mode Exit fullscreen mode
Thread Thread
jonrandy profile image
Jon Randy

And in PHP (again, no join needed):

function isAnagram($str1, $str2) {
   $s1 = str_split($str1);
   $s2 = str_split($str2);
   sort($s1);
   sort($s2);
   return $s1 == $s2;
}
Enter fullscreen mode Exit fullscreen mode
Thread Thread
jonrandy profile image
Jon Randy

And in Ruby:

def is_anagram(str1, str2)
  str1.split('').sort() == str2.split('').sort()
end
Enter fullscreen mode Exit fullscreen mode
Collapse
darthbob88 profile image
Raymond Price

I'd also add in a discussion of graph search, because that's the one that always gets me on technical screens.

Graph Search

The basic algorithm of graph search is

  1. Keep a list of nodes to search, initialized with a starter node. Optionally, keep a list of nodes you have visited.
  2. For each node in that list, search that node.
    1. If you've found the target, return.
    2. Otherwise, mark that node as visited and add that node's neighbors to the list to search.
  3. If you have run out of nodes to search, return an error.

Given a starting point (xStart, yStart) on a chessboard of size N * N, and an ending point (xEnd, yEnd), what is the minimum number of moves for a chess knight to get from the start to the end?

function minKnightMoves(n, xStart, yStart, xEnd, yEnd) {
    // Initialize chessboard. The value of each entry represents the number of moves to get there, as well as indicating whether we've visited that node.
    const chessboard = []
    for (let ii = 0; ii < n; ii++) {
      chessboard[ii] = [];
      for (let jj = 0; jj < n; jj++) {
        chessboard[ii][jj] = 0;
      }
    }

    // List of nodes to search. Using array with [x, y] to represent points.
    // We want to do breadth-first search, so we're using a FIFO queue.
    // Depth-first search would require a LIFO stack. 
    const nodeList = [ [xStart, yStart] ];

    // Search through each node.
    while (nodeList.length > 0) {
        const currNode = nodeList.pop();
        const currX = currNode[0];
        const currY = currNode[1];

        // If we've found the target, return the result
        if (currX == xEnd && currY == yEnd) {
            return chessboard[currX][currY];
        }

        // Search this node's neighbors
        if ((currX + 2 < n && currX + 2 >= 0) && (currY + 1 >= 0 && currY + 1 < n) && (chessboard[currX + 2][currY+1] == 0)) {
            chessboard[currX + 2][currY+1] = chessboard[currX][currY] + 1;

            if (currX + 2 == xEnd &&  currY + 1 == yEnd) {
                return chessboard[currX + 2][currY+1];
            } else {
                nodeList.push([currX + 2, currY + 1]);
            }
        }
        // Repeat the above for all 8 possible knight's moves from this node.

    }

    // We've searched every possible node and haven't found it. 
    return -1;
}
Enter fullscreen mode Exit fullscreen mode