Algorithm Journal #2
Four-Step Guide for Solving Algorithms
Problem Solving Tips for both Technical and Non-Technical Problems
Overview:
Introduction
In the previous story, I walked step by step through an algorithm. Since that was an introduction, I didn’t go into too many specifics and directly showed an algorithm example. Now we’ll go into greater detail, so let’s hang ten and jump right in! We will go over a non-technical example first, and then look at an algorithm that stumped me because I didn’t understand it at first.
Step 1: Understand the Problem
Say we have this problem to solve:
Make a sandwhich with the following ingredients: Bread, Mustard, Mayonaise(or literally anything else), Cheese, Ham, Tomato, and Lettuce.
Our very first step before doing anything is to make sure we can understand specifically what problem we are solving. So let’s ask some questions and make observations about the problem to guide our understanding.
Say the problem out loud in your own words, write it down.
Make a yummy snack that is comprised of bread and other snadwhich making ingredients.
Alrighty, best not to overthink it past that. If interviewing, we may even get a reaction from an interviewer that serves up hints based on how we restate the problem. This shows that we can pick out the essential language and think about it in terms that make sense to us.
What are the input(s) that go into the problem & what are the Expected Output(s)?
What data or items are we starting with and where are we trying to go? This one is pretty simple for this problem. For inputs, we have a list of sandwich ingredients: Bread, Mustard, Mayonnaise(yuck), Cheese, Ham, Tomato, and Lettuce.
For output, we have a single constructed sandwich.
Do we have enough information about the problem?
Is what we know about the inputs, constraints, and details about the problem enough to make a deterministic solution? This means that we can arrive at the output as long as the proper inputs are present and the conditions required are met.
If we are interviewing, this is where we ask questions like, “Can I assume X?”, “What are the upper and lower limits (or constraints) of Y?”, “Do I have Z tool available to me?”
We can imagine asking about what exactly constitutes a sandwich, and if the order of ingredients matters, so let's add two assumptions in our restatement: A sandwich must consist of two slices of bread and the ingredients have a recommended order of layering. Our new statement reads:
Make a yummy snack that is comprised of two slices of bread and has several ingredients layered in a recommended order(list).
(No, there is no such thing as an open-faced sandwich. There’s only one piece of bread, sometimes require utensils, and don’t actually sandwich anything. Fight me if you disagree 😛 👨🏾🍳)
Identify the important pieces of data
Personally, I like to label the important pieces with some combination of bolding, CAPITAL LETTERS, side notes, and diagrams for visualization. For example, I recently solved a problem involving data structures to represent a grid. It would have been very tough to solve the problem without drawing a diagram first. Finally, does the above information help us determine what is important?
Step 2: Create Test Examples
Create examples to model the specific cases your solution needs to handle. Doing so helps us both understand the problem better and catch any errors we may have overlooked when we initially wrote out a problem. Here’s an example:
Implement a function called areThereDuplicates which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in.areThereDuplicates(1, 2, 3, 4, 4); //=> true
areThereDuplicates("a", "b", "c", "d", "d"); //=> true
areThereDuplicates(1, 2, 3); //=> false
areThereDuplicates("a", "b", "c", "d"); //=> false
areThereDuplicates(); //=> null
Here, we write our test cases by building magic functions that describe the specific expected outputs for specific inputs. Doing so gives us a roadmap of cases for our solution to address, which deepens our understanding of the problem. Other ways we can write examples include user stories and unit tests.
Step 3: Break it down first, then solve
At this point, we can begin our first steps towards solving the problem. Let’s continue with the problem from before.
Write an outline of steps needed to take
function areThereDuplicates(){// handle variable number of arguments
// handle no arguments passed
// handle only one argument passed// Make a counter object to track frequency of argument occurence// iterate over all arguments, for each argument:
// if the argument doesn't exist as a key in the counter, create
// that argument's key at set it's value to 0 OR increment it by 1// iterate over the counter object, for each key:
// if the key's value is greater than 1
// return true//otherwise:
//return false}
Above, we’ve now extended our problem-solving roadmap to include the specific steps that we will take to implement our solution. This problem is about counting beans and the beans are the arguments passed in. We can use a frequency counter in order to count if there are duplicate arguments.
When I first encountered this problem, I realized it was the first time I had to consider that I wouldn’t always know what or how many arguments are passed to the function. How do I work with this then? A quick Google search led me to this on MDN:
argumentsis an Array-like object accessible inside functions that contains the values of the arguments passed to that function.
Perfect, with this information and our outline we can now write actual code!
Make the function by replacing the outline with actual code
Pro-tip: if we get to a part we don’t know how to implement, we can reuse our “magic functions” idea here too!
Say we didn't know how to count each argument, me may choose to write: function areThereDuplicates(){//edge cases
if (arguments.length === 0) {
return null;
}
if (arguments.length === 1) {
return false;
}// Make a counter object to track frequency of argument occurence
let counter = {}// iterate over all arguments, for each argument:
// if the argument doesn't exist as a key in the counter, create
// that argument's key at set it's value to 0 OR increment it by 1// logic that sets the matching value of an argument's counter key // to 0 or adds 1 to the count
// counter = {"a": 1, "b": 1, "c": 1}// iterate over the counter object, for each key:
// if the key's value is greater than 1
// return truelet keys = Object.keys(counter)
for (let i = 0; i < keys.length; i++){
if (counter[keys[i]] > 1) {
return true;
}
}//otherwise:
//return falsereturn false
}
The idea being that we can move on assuming that we have implemented that part of the functions, which can save us a lot of time and demonstrate that we have a clear idea of where we are going, if not how we will get there.
Solve!
function areThereDuplicates(){//edge cases
if (arguments.length === 0) {
return null;
}
if (arguments.length === 1) {
return false;
}// Make a counter object to track frequency of argument occurence
let counter = {}// iterate over all arguments, for each argument:
// if the argument doesn't exist as a key in the counter, create
// that argument's key at set it's value to 0 OR increment it by 1for (let i = 0; i < arguments.length; i++){
if (counter[arguments[i]] === undefined){
counter[arguments[i]] = 0
} else {
counter[arguments[i]]] + 1
}
}// iterate over the counter object, for each key:
// if the key's value is greater than 1
// return truelet keys = Object.keys(counter)
for (let i = 0; i < keys.length; i++){
if (counter[keys[i]] > 1) {
return true;
}
}//otherwise:
//return falsereturn false
}
Above represents my first solution. This doesn’t mean we are done yet, but hooray, problem solved!
Step 4: Analyze & Refactor!
In the previous step, we have arrived at a solution. Now we can look back and ask which ways we can make it better. Normally, we would first analyze the time and space complexity of the algorithm, but I won’t do that here because it right deserves it’s own story. However, there are other questions we can ask like:
Can I check the results?
Can I derive the result differently?
Now that I have solved the problem, what other things could I have done?
Can I understand it at a glance?
How legible is it?
Can I use the result or method for other problems?
What similarities does my solution have to other problems?
Can I improve the performance of my solution?
- Time and Space Complexity, finding bottlenecks
Can I think of other ways to refactor?
- Style guides, spacing consistent, etc.
How have others solved this solution?
Can find ideas or different approaches in other people’s work/other languages?
Here are two refactors to this problem:
Refactor 1: Clean up loops and use more modern JavaScript Syntaxfunction areThereDuplicates() { //edge cases
if (arguments.length === 0) {
return null;
} if (arguments.length === 1) {
return false;
} let frequencyCounter = {}; for (let index in arguments) {
frequencyCounter[arguments[index]] =
(frequencyCounter[arguments[index]] || 0) + 1;
} for (let key in frequencyCounter) {
if (frequencyCounter[key] > 1) {
return true;
}
}return false;}
Above we use for...in loops to clean up our looping logic and we use a Ternary statement and the logical OR || operator for setting the initial value or adding 1 to it if it exists.
Refactor 2: One Liner using JavaScript Setfunction areThereDuplicates() {
return new Set(arguments).size !== arguments.length;
}
On MDN, it reads:
Setobjects are collections of values. You can iterate through the elements of a set in insertion order. A value in theSetmay only occur once; it is unique in theSet's collection.
So the logic going on here is to create a Setwith the function’s passed in arguments and compare the size of new Set to the length of the original arguments object. Since the Setchecks for uniqueness, if they are unequal we know that there are duplicates in the original arguments object.
Conclusion
Following the steps to make sure we understand what problem we are trying to solve, have examples that we can test against, breaking it down before solving, and then analyzing before refactoring is a tried a true method of approach solve algorithms, general coding problems, and with not so much mental leg-work, life’s problems too!
I hope this is useful to you. Studying it and writing about it sure has been for me. Enjoy!
Sources:
- Colt Steele’s JavaScript Data Structures and Algorithms Masterclass on Udemy.
- MDN — JavaScript
argumentsobject. - MDN — JavaScript
Set
What did you think about this post? See something inaccurate? We’d love to hear from you! Leave a comment about your tips and approach to algorithm solving, or just about anything else! Looking to find out more about Joshua? Read this story and follow him on social media!
Interested in contributing to this publication? Start a conversation with me at dance.syntax@gmail.com, I promise I don’t bite. 😁
