A running list of algorithm questions and answers that commonly appear in programming interviews.
Since the goal of this exercise is to practice logical skills necessary for a coding interview, I will avoid using most built-in JS methods, and will rely on for/while and for-in loops to iterate through data structures.
Also, for simplicity, I will assume that expected inputs will be correct so I don’t have to waste space doing error checking or validation. So if an array is the expected parameter, the input will not be an object, and so on.
Arrays
One of the most common data structures in programming. These questions are those involving arrays.
- Find the missing number in a given integer array of 1 to 100
Return: integer — the missing number in the array
My approach to this solution was to realize that the numbers are in consecutive order. Since the array is sorted, we can solve this in one pass by looking ahead using arr[i] + 1 and comparing that to arr[i + 1]. If arr[i + 1] is not equal to arr[i] + 1, it means that arr[i] + 1 is the missing number.
let arr = [1,2,3,4,5,6,7,8,10];const findMissingNum = (arr) => {
for(var i = 0; i < arr.length - 1; i++) {
if(arr[i] + 1 != arr[i+1] ) {
return arr[i] + 1;
}
}
return false;
}console.log(findMissingNum(arr)); // Returns 9, the missing number
For the sake of simplicity, 1 or 100 will be included in the array for sure. If not, a simple check if arr[0] === 1 and arr[arr.length — 1] === 100 could return the answer without looping through the array at all.
2. Find a duplicate number in an array of integers
Return: integer — the duplicate number
Assumptions: if no duplicate is found, return false;
This problem can be easily solved using a hash. As we go through the array, we use the hash to keep track of which numbers we have seen before. If we encounter a number we have seen before, we return the number.
const arr = [1,2,3,4,5,6,7,7,8,6,10];const findDupes = (arr) => {
const observed = {}; for(let i = 0; i < arr.length; i++) {
if(observed[arr[i]]) {
return arr[i]
} else {
observed[arr[i]] = arr[i];
}
}
return false;
}console.log(findDupes(arr)); // Returns 7
The reason this works, is that by setting observed[arr[i]] = arr[i], we can do a simple hash look-up with observed[arr[i]], which will return true or false if the key-value pair exists or not.
Note: you can also do this by using a new Set() (See MDN: Set — Javascript)
const nums = new Set();nums.add(1);
nums.has(1); // true
3. Find the largest and smallest number in an unsorted array of integers
Return: object — containing value of min and max
This can be solved by creating a min and max reference variable initialized to equal the value of the first item in the array — arr[0]. We then loop through the array and compare the values of min/max to arr[i] . If it is more or less, we update the value. Finally, I return an object with the values of min and max.
const arr = [1, 2, 3, 4, 100];const findMaxMin = (arr) => {
let max = arr[0];
let min = arr[0];
for(let i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
} else if (arr[i] < min) {
min = arr[i];
}
}
return {
"max": max,
"min": min
};
}console.log(findMaxMin(arr)); // Returns object { "max": 100, "min": 1 }
4. Return an array showing the cumulative sum at each index of an array of integers
Return: array — integers showing the cumulative sum at each index
First we set a new array which will be initialized to contain the value at index 0 of list. This is because we need a starting reference value to begin our calculations. Then we loop through the list starting at index 1 (since we already have the value at list[0]. For each item in the array, we add the current value to the previous value and push it to the result array.
let arr = [1,3,5,7];const cumulativeSum = list => {
let result = [list[0]];
for(let i = 1; i < list.length; i++) {
result.push(list[i] + result[i-1]);
}
return result;
}console.log(cumulativeSum(arr)); // Returns [1, 4, 9, 16]
5. Find all duplicate numbers in an array with multiple duplicates
Return: array — containing all duplicates found or empty array if none are found
Like question 2, I would use an hash map, but instead of setting the value of observed[arr[i]] = arr[i], we will increment a count. Depending on what we want to return, we can either return the object with the repeated values or we could push the duplicate numbers to a new array and return the new array. Since it is cleaner, and we can do it in one pass, I will do the latter.
const arr = [1,1,2,3,4,5,6,7,8,6,6,7,7,7,10,10];const returnMultipleDupesArray = (arr) => {
let observed = {};
let dupesArray = [];
for(let i = 0; i < arr.length; i++) {
if(observed[arr[i]]) {
if(observed[arr[i]] === 1) {
dupesArray.push(arr[i]);
}
observed[arr[i]] = observed[arr[i]] + 1;
} else {
observed[arr[i]] = 1;
}
}
return dupesArray;
}console.log(returnMultipleDupesArray(arr)); // prints [1, 6, 7, 10]
If no duplicates are found in the array, then the function returns an empty array
6. Remove all duplicates from an array of integers
Return: array — without any duplicates
For this next solution, I got the idea from this blogpost which shows how to do this in Java. The concept is to do the opposite of what I did in solution 1 (looking 1 ahead), to keeping track of the one behind. By keeping track of the previous item encountered, we know whether or not we have encountered the number and whether or not to push to the result array.
Note: in order for this solution to work, we need a sorted array. In the Java example, they performed a .sort() method on the array before looping through it. For me, I will just assume that we are getting a sorted array as an input.
const arr = [1, 1, 1, 1, 1, 1, 1];const removeDupes = (arr) => {
let result = [];
let previous = arr[0];
result[0] = previous;
for(let i = 0; i < arr.length; i++) {
if (arr[i] != previous) {
result.push(arr[i]);
}
previous = arr[i];
}
return result;
}console.log(removeDupes(arr)); // prints [1]
If we can’t sort, we could use a look-up hash like in previous solutions.
7. Find all pairs in an array of integers whose sum is equal to a given number
Return: array — matching pairs or empty arrays.
To simplify, the input array will not have duplicates. However, there will be negative and positive numbers. For the solution, like before, I will use a lookup hash. As you can see, knowing how to use a lookup hash, which has constant lookup time, can be very useful.
let arr = [1,5,6,1,0,1];const findSumPairs = (arr, value) => {
let sumsLookup = {};
let output = [];
for(let i = 0; i < arr.length; i++) {
let targetVal = value - arr[i];
if(sumsLookup[targetVal]) {
output.push([arr[i], targetVal]);
}
sumsLookup[arr[i]] = true;
}
return output;
}console.log(findSumPairs(arr, 6));
Conclusion
The above solutions show how you can use simple concepts to solve many common array problems with one pass, linear solutions. There must be other solutions that can do better than linear complexity, but I will leave it to you to think about it and propose some ideas!
If you are just starting out, hopefully this shows you how you can move away from the nested for-loop solutions that usually first come to mind.
I myself am still studying these concepts and tricks to master the technical interview, and I am happy to share these ideas with other people.
If you enjoyed this article and want to know more, please check out:
