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.
Article No Longer Available
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.
Discussion (8)
Why so much code?
Or, if you want to go small and don't mind polluting global namespace:
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:
For the custom code:
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.
Well, you cant do that in other languages. I wanted a solution that people can "replicate" using a language of their choice ;)
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
Here is the same technique in Python (array join not necessary as we can do array equality):
And in PHP (again, no join needed):
And in Ruby:
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
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?