Understanding These Concepts will Help you Solve Algorithms!
Solving algorithms is fun, challenging, and strengthens your conceptual understanding of computer science. Every engineer is expected to pass a coding challenge prior to getting hired, so it is a necessity that engineers consistently work on algorithms when job hunting. Being good at algorithms is all about recognizing the type of problem you have and figuring out the thought process of how to go about solving it. When hiring developers, most companies are looking for this skill. Here are some concepts that, when understood, will help you recognize the type of problem you are looking at:
Recursion
Recursion is the process in which a function calls itself directly or indirectly. The function that is called again is called a recursive function. An example of this can be seen with the Fibonacci sequence function:
function fibo(n){if(n==0){ return 0};
if(n==1){return 1};return fibo(n-1) + fibo(n-2);}
For those unfamiliar with Fibonacci sequence, you can read more about it here. In this case, ’n’ is the index number you are trying to add up to. The value at index 8 is equal to the value at index 7 plus the value at index 6. This simplifies down to:
n = (n-1) + (n-2)As you can see, we called the function ‘fibo’ within itself, but altered the parameters passed. This function will continuously run until ’n’ reaches 1 or 0. The function then adds up to the original inputted index number and the output is the value at that index.
Recursion is useful in solving algorithms that can be broken down into smaller problems. The Climbing Stairs problem is a great example of recursion. Give it a try!
Iteration
Iteration is a single execution of a set of instructions that are repeated until it has been applied to all items within the set. It is typically seen in the form of a loop. Let’s take an array of numbers and multiply them by 2 using iteration:
function doubleUp(n){let array = new Array;for(let i = 0; i < n.length; i++){array.push(n[i] * 2); }return array; }
Line 3 is what we call a “for-loop.” This sets up a condition that will add 1 to ‘i’ up until ‘i’ is 1 less than the length of ‘n.’ We do this because indexes start at 0, and ‘i’ will be serving as our index number. Line 4 is the repeated condition we apply every single time ‘i’ is increased by 1. We are taking the value at ‘n[i],’ multiplying it by 2, and pushing it into our new array. This will occur until all the values in ’n’ are multiplied by 2 and pushed into the new array. Finally, we return that new array.
Iteration is very useful when solving algorithms. If you see a problem that requires you to apply a set of conditions to a collection of some type, iteration is an easy way to get the problem done. Try using iteration to solve the Plus One problem!
Binary Search
Binary search is an algorithm used to find certain things within an array. This is an important concept when solving algorithms because it helps you easily find things within an array and apply whatever conditions you need to solve the problem.
As the algorithm runs, it is narrowing down on the target until it finally reaches what you are looking for. It cuts the data set in half every single run, which is useful if you are working with millions of items within a dataset. You’d be able to quickly find one item in a set of billions within 20 runs. Here is how it looks in code:
function binarySearch(array, target){
let start = 0;
let end = array.length - 1;
while(start <= end) {
let middle = Math.floor((start + end) / 2);
if(target === array[middle]) {
return console.log("Target was found at index ${middle}");} if(target > array[middle]) {
console.log("Searching the right side of Array")
start = middle + 1;
} if(target < array[middle]) {
console.log("Searching the left side of array")
end = middle - 1;
} else {
console.log("Not Found this loop iteration. Looping another iteration")
}
}
console.log("Target value not found in array");
}This sets the start, end, and middle values based on the length of the array. The goal is to get the middle value to be at the index of the array where the value equals the target. If the target is more than the value, everything to the left of the target gets negated and the search continues on the right side. If the target is less than the value, the opposite occurs. This continues until the algorithm finds the correct index value. Try using this method to solve the Binary Search problem!
Sources:
https://www.digitalocean.com/community/tutorials/js-linear-vs-binary-search
https://medium.com/@jeffrey.allen.lewis/javascript-algorithms-explained-binary-search-25064b896470
