The Importance of Algorithms and Data Structures
When interviewing for a job in the tech field, a common practice for employers is to have the applicant solve a problem using algorithms. Instead of using already built out methods. An algorithm is a list of instructions, used to solve problems or perform tasks, based on the understanding of available alternatives.
An example would be something like reversing a string without using the reverse method. Say you have a string that says “Hi!” , or “Hello World!”. The reverse method would do this very easily for us, but how would you complete this without using a prewritten method? As with most things in life, there is more than one way to solve this. One way would be to iterate over the string and place the following letter in front of the previous letter. The code would look something like this.
def reverse_string(str)
reversed_string = “”
str.chars.each do |char|
reversed_string = char + reversed_str
end
reversed_str
end
puts “Expecting: “!iH”
puts reverse_string(“Hi!)
puts “Expecting: “!dlroW olleH”
puts reverse_string(“Hello World!”)
Algorithms are what is happening under the hood of these functions. Someone wrote these functions to make writing code easier to read, understand, and be less repetitive. It is easier to write a function like the reverse string, and call the function when needed instead of rewriting the code every time.
Basically any method written can be written using an algorithm. The types of algorithms are:
- Brute Force algorithm
- Greedy algorithm
- Recursive algorithm
- Backtracking algorithm
- Divide & Conquer algorithm
- Dynamic programming algorithm
- Randomized algorithm
Brute Force Algorithm
This is the simplest of all the algorithms that can be devised to solve a problem. Every problem can be solved using the brute force approach, but generally not with the appreciable space and time complexity. Space and time complexity is the time taken by the algorithm to complete each set of instructions
//Searching for an element in a sorted array of elements
Int main() {
//sorted array
Int arr[] = { 1, 2, 3, 4, 6 };
//searching for 5
Int search = 5;
bool flag = false;
// for loop to iterate over array until i = 5
// time complexity 0(n)
for (int i=0; 1<5; i++)
{
If (arr[i] == search)
Flag = true;
}
if (flag == true)
Count << “found”;
else
Count << “not found”;
return 0;
}
Greedy algorithm
For this algorithm, a decision is made that sounds good at the time without considering the future. This algorithm doesn’t always work, but when it does, it works like a charm.
Greedily choosing the best option
Optimal substructure property: if an optimal solution can be found by retrieving the optimal solution to its subproblems.
This algorithm is easy to device and most of the time is the simplest one. Making locally best decisions doesn’t always work as it sounds. It is usually replaced by a reliable solution called Dynamic Programming.
An example could be a scheduling problem. Consider a situation where you have starting and end times of events. How could we optimize the number of events that can be organized where no two events overlap. A brute force solution would be to sort the events by starting times.
The events with starting and ending times.
The events sorted by start time
With this approach, the only non overlapping events are A, F. Can we get a better outcome? What about the Greedy method? With this algorithm we would sort based on end times.
The events sorted by end time
With this approach we now have B, E, C that don’t overlap. Hence in such cases, the Greedy algorithm gives the best solution to this particular problem.
Recursive algorithm
Probably one of the simplest algorithms to devise, because it does not require us to think about every subproblem. Just need to focus on the existing cases and the solution of the simplest subproblem, all other complexity will be handled by it automatically. Recursion simply means calling itself to solve its subproblems.
//Factorial of a number
Int Fact (x) {
//Base case is 0 the return is 1
If(x == 0)
return 1;
//returns the factorial of x-1 multioplied by x
Return x*Fact(x-1);
}
Remember to give the base case or else the loop will be infinite and give a memory error.
Backtracking algorithm
An improvement on the brute force approach. With this algo we will start with one possible option and try to solve the problem. If unsuccessful we will backtrack and try a different approach. This is a form of recursion.
Divide and conquer algorithm
One of the most used in programming. This approach will divide the problems into subproblems, solve for each and then combine them to form the solution to the given problem. It is not possible to solve all problems using this algorithm.
This problem is split into two parts of n/a and n/b size. They are computed separately and recursively to get back the result and combine them to get the solution.
Dynamic algorithm
This is the most efficient way to solve a problem. It simply means remembering the past and applying it to future corresponding results.
This approach has two properties:
- Optimal Substructure
- Overlapping subproblems
There are also two versions:
- Bottom-up approach: start with the last possible subproblem and use the results of those to solve the above subproblems.
- Top-down approach: start with solving the first problem to arrive at the required subproblem, and solve it using the previously solved subproblems.
Randomized algorithm
This approach uses random numbers to decide what to do next anywhere in its logic. An example would be Randomized quick sort. We use a random number to pick the next pivot, or shuffle the array randomly. Normally this randomness is used to reduce the time or space complexity in the algorithm. In terms of quick sort, if we fail to choose the correct element, the complexity could end up being O(n^2). The worst case scenario. Although if chosen correctly it can have an ideal complexity of O(nlogn).
Conclusion
There is a lot more out there about algorithms, this has been an introduction to the topic. Knowing how to use algorithms will be very beneficial when the time comes to have a technical interview.
Leave a Reply