Algorithm puzzles are an unfortunately common way to weed out candidates in the application process. However, when you aren't stressing over the job search, they're actually a lot of fun, like crossword puzzles for coders.
Solving them presents unique challenges that you won't encounter when spinning up Yet Another Crud App and exposes you to concepts that you might not already be familiar with. Practicing algorithm challenges will improve your broader problem solving abilities, as well as cement a problem solving process that is more generically useful.
Much like other types of puzzles, there are strategies that give you an early foothold into the problem and a way to break it down into smaller, more approachable chunks. With an actual puzzle, you might sort the pieces into coherent groups of similar colors or features, find look for obvious matches and grow outwards. With minesweeper, you might start with a random click, and then move around the exposed edges, marking off obvious mines and exposes obvious clear areas, only clicking randomly once more when you've exhausted all possibilities.
While there are strategies for approaching similar kinds of algorithms, I would recommend that you start with a broader problem solving strategy that you embrace as a general habit, and not just when you're grinding LeetCode as interview prep.
Be Strategic, Think First
Rather than diving in, approach the problem in stages:
Think:
- Analyze the problem
- Restate the problem
- Write out examples of input and output
- Break the problem into its component parts
- Outline a solution in psuedo-code
- Step through your example data with your psuedo-code
Execute
- Code it up
- Test your solution against your examples
- Refactor
(If you're familiar with this approach, skip down to Algorithm Patterns)
Analyze the Problem
You may have had a flash of insight when you first saw the problem. This is typically your mind connecting to some prior experience. Hold on to that insight! However, you should still spend some time looking at the problem, particularly for ways that your insight differs from the actual question.
Any well written puzzle has the components needed to answer the problem contained in a sentence or two. However just because you read the problem doesn't mean you understand the problem. And if you don't understand the problem, you will stumble about aimlessly, or solve what you assumed the problem was.
Look for key words which determine the shape of the challenge.
Identify the input.
Identify the desired output.
Identify critical keywords and phrases.
For example, LeetCode #26
Given a [sorted] [array] nums, [remove the duplicates] [in-place] such that each element appear only once and [return the new length].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with [O(1) extra memory].
Input:
- an array. So we know we're probably going to do some kind of iteration.
- an array of numbers. That's more implied rather than specifically stated and doesn't really matter as much as we can use the same set of conditionals.
Return:
- length of altered array
- side effect: a modified array
Critical Words and Phrases:
- sorted: repeated elements will be next to each other
- remove...duplicates
- in-place: the array itself must be destructively modified. This constraint dictates what array methods we may use.
- O(1) extra memory: we are limited to O(1) space complexity, allowing us to define variables, but not create a copy of the array.
Restate the Problem
Now, in our own words, rephrase this so it is meaningful to ourselves. If you are in an interviewing situation, you may restate it back to the interviewer, both to set it in your own mind, and to make sure that you heard and understood them correctly.
Restated:
Given a sorted array of numbers, passed by reference, destructively modify the original array in-place by removing duplicate, so that each value only appears once. Return the length of the modified array.
Write out Example Inputs and Expected Outputs
All we are doing is mapping inputs to outputs. The challenge is figuring out how to get from A to B, however first we need to establish what A and B are. Even if you are given test cases, write your own. Looking at something doesn't create nearly as much understanding as doing it for yourself.
This is also a great time to explore your understanding of the problem and look for quirks that might trip up a naive solution. That includes edge cases like empty inputs, an array filled with duplicates of the same value, a massive data set, etc. We don't need to worry about anything outside of the constraints of the problem
Write out at least 3 examples:
[] -> [], return 0
[1] -> [1], return 1
[1, 1, 2, 3, 4, 4, 4, 5] -> [1, 2, 3, 4, 5], return 5
[1, 1, 1, 1, 1] -> [1], return 1
Given the inputs, do you have enough information to map to the result? If you don't, take a step back and continue examining the problem before continuing. If you are interviewing, feel free to ask for clarification.
Look for a simple and consistent process that you can apply regardless of the value to reach the outcome. If you end up with a convoluted series of steps and exceptions, you've likely gone too far and passed over a simpler solution.
Break the Problem into Small Parts
Starting with the simplest possible example, simply the problem down to an essential puzzle and build upon that. In this case, that is an array of three elements, two duplicated, e.g. [1, 1, 2]. Reducing the problem to such a small case makes it more approachable and clarifies the the first step you need to take. Your task from there is to develop a procedure which solves that simple case and holds true for all other cases in the problem set.
So we know we need to do a couple things:
- Iterate through an array
- Keep track of where in the array we are
- Check adjacent values for equality
- Destructively remove any duplicate values after the first occurrence
- Get the final array length and return it
This is a relatively simple example problem, however there is a gotcha lurking in it: lots of iteration methods don't play nicely with removing elements from the array while you're iterating through the array, because the index values change. You may end up skipping a duplicate because the pointer incremented over it.
This gotcha indicates that we'll want to use an approach that gives us explicit control of iteration.
In a more involved problem, we might consider some or all of these components into helper functions, allowing us to write a clear and succinct solution, as well as test the validity of each of our sub-parts separately.
Psuedocode the Solution
If we've clearly grasped the problem, identified the core tasks and hopefully spotted the flaws in our own assumptions and any gotchas, we write out a human-legible description of what our approach will be. Hopefully once we've done that we can cleanly transform it into working code.
How you write pseudocode is up to you. Your notation doesn't need to be perfectly spelled and grammatically correct. It can be a gestural combination of code and words meant to convey meaning. Your pseudocode will provide a meaningful roadmap that you can refer back to if you find yourself lost deep in the particulars of implementation, so make sure that you record enough to be useful later.
If you're interviewing, this is a great opportunity to walk the interviewer through your intent. And if you're running out of time, you will at least have something on the board that demonstrates your problem solving approach.
Recommendations:
- start with a function signature: removeDuplicates :: (Array) -> number
- if whiteboarding, leave plenty of space to write your actual code
- if using an IDE, write comments and keep them separate from your code so you can reference back later on.
- write it as a series of steps and use bullet points
Since we're looking for duplicates, that means we need to perform a comparison. We can look ahead of our current position in the array, or we can look behind.
// removeDuplicates :: (Array) -> number
// if array is empty or has 1 element, return array length and exit
// iterate through array
// compare each element to the next element
//
// repeat until false:
// if the next element is the same as the current element
// remove the next element
//
// move on to the next element in the array
// stop once the second to last element has been reached
// return array length
We start by exiting if our array is only 0 or 1 elements in size, partly because these cases satisfy the conditions of the problem: there are no duplicates possible, and partly because they'll break our code if we try and compare the first value with a second that doesn't exist.
We also establish our iteration exit condition, and because we'll be using a look-ahead, we make sure to stop before we reach the last element.
Because we don't move our pointer position until after we've dealt with any duplicates, we should be clear of the shifting indices issue.
Step Through the Sample Data
Take a moment and mentally run some of the sample data through our pseudocode:
[] -> [], return 0
[1] -> [1], return 1
[1, 1, 2, 3, 4, 4, 4, 5] -> [1, 2, 3, 4, 5], return 5
[1, 1, 1, 1, 1] -> [1], return 1
Are we missing anything?
There may be an issue with the last example: [1, 1, 1, 1, 1]. What happens if we remove all of the duplicates, and then try and move on to the next element in our array without checking to see if there are any?
We'll want to make sure that our end condition catches any changes in the array length.
Code It
Time for rubber to meet the road. This is where you have all of the assumptions you didn't even know you made come back to haunt you. The better you were able to plan, the fewer there will be.
function removeDuplicates(arr) {
if (arr.length < 2) return arr.length
return arr.length
}
Personally I like to put in my return values first. That way I'm clear on what my goal is, and I've also captured the first case of empty or single element arrays.
function removeDuplicates(arr) {
if (arr.length < 2) return arr.length
for(let i = 0; i < arr.length; arr++) {}
return arr.length
}
Yup, we're going with a standard for-loop. I prefer not to use them if there's more appropriate or cleaner syntax, but for this particular problem, we need the ability to control our iteration.
function removeDuplicates(arr) {
if (arr.length < 2) return arr.length
for(let i = 0; i < arr.length; i++) {
while (arr[i + 1] && arr[i] === arr[i + 1]) arr.splice(i + 1, 1)
}
return arr.length
}
And that works out of the box, except for:
removeDuplicates([0,0,1,1,1,2,2,3,3,4]) //> 6, should be 5
Turns out the existence check I snuck in the while loop resolves to falsy if the array value is 0. Thanks JavaScript! So let's just rework that real quick and do a look behind instead of look ahead, which actually cleans the code up a tad as well:
function removeDuplicates(arr) {
if (arr.length < 2) return arr.length
for(let i = 0; i < arr.length; i++) {
while (arr[i] === arr[i - 1]) arr.splice(i, 1)
}
return arr.length
}
And that passes. It's a memory efficient solution, we've only defined 1 variable besides the array reference. And it is of average speed, which we could improve upon.
But mostly it was a simple example of a process:
- Analyze
- Restate
- Write examples
- Break into small problems
- Outline in pseudocode
- Step through pseudocode with examples
- Code
- Test
- Refactor
Algorithm Patterns
Aside from specific data structures and algorithms which have known and fairly standardized approaches, algorithm challenges tend to fall into categories that suggest similar solution approaches. Learning these approaches gives you a foothold into the problem.
Multiple Pointers
When we first learn to iterate through a collection, typically an array, we do so with a single pointer with an index going from the lowest value to the highest. This works for some operations and is simple to consider and code. However for problems involving comparing multiple elements, particularly ones where their position in the collection is important, finding corresponding value with a single pointer requires iterating through the array at least once for each value, an O(n2) operation.
If instead we use multiple multiple points we can potentially reduce the computation down to an O(n) operation.
There are two common strategies: Two Pointer and Sliding Window
Two Pointer
Why not start at both ends and work your way in? Or start at a value or pair of values and expand outwards. This is a great approach for finding the largest sequence in a collection.
Because you are handling two points, you will need to define a rule to ensure that they do not cross over each other.
// Time complexity O(n)
// Space complexity O(1)
function sumZero(arr) {
let left = 0;
let right = array.length - 1;
while (left < right) {
let sum = arr[left] + arr[right];
if (sum === 0) return [arr[left], arr[right]];
else if (sum > 0) right--;
else left++;
}
}
Sliding Window
Instead of placing two points at the outer bounds, we can march through our array sequentially moving two pointers in parallel. The width of our window may grow or shrink according to the problem set, but it continues to progress across the collection, capturing a snapshot of whatever sequence best fits the desired outcome.
function maxSubarraySum(array, n) {
if (array.length < n) n = array.length;
let sum = 0;
for (let i = 0; i < n; i++) {
sum = sum + array[i];
}
let maxSum = sum;
// shift window across array
for (let i = n; i < array.length; i++) {
sum = sum + array[i] - array[i - n];
if (sum > maxSum) maxSum = sum;
}
return maxSum;
}
Divide and Conquer
Divide and Conquer often involves a recursive approach: applying the same rule to divide a collection until you've broken it down into the smallest components and identify the answer.
Binary Search and Merge Sort are both excellent examples of recursive subdivision leading to a solution.
O(1) Lookup: Object/Dictionary/Hash
Hashed Key:Value stores, called Objects, Dictionaries or Hashes depending upon your coding language, are incredibly useful tools for storing information when counting frequency, checking for duplicates or the complement of an answer. As there
You may store the value, or you may store the value that you are looking for instead. For example, when looking for zero-sum pairs in an array, we can save the complement rather than the value itself.
Resources:
Fundamentals of Algorithmic Problem Solving (video)
Algorithmic Problem Solving for Programmers
Top 10 Algorithms in Interview Questions
Improving your Algorithms and Data Structure Skills