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.
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 that encapsulates an algorithm, like the reverse string, and call the function when needed instead of rewriting the algorithm code every time. Some algorithms can be very lengthy and difficult to understand so placing it in a well-named function call can abstract some of the complexities that are not necessarily needed to understand the code.
Basically any method can be written using an algorithm. Some common 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, which will be covered later.
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 thinking about every subproblem. A developer just needs to focus on the existing cases and the solution of the simplest subproblem, all other complexity will be handled by the algorithm automatically. Recursion simply means that a method calls 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 multiplied 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. This algorithm starts with one possible option and tries to solve the problem. If unsuccessful it 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); this is the worst case scenario. If chosen correctly the randomized algorithm can have an ideal complexity of O(nlogn).
Conclusion
This has only been an introduction to the topic of algorithms, there is a lot more that was not covered here. Knowing how to write and use algorithms will be very beneficial when the time comes for a technical interview. Lastly, understanding the basic logic of algorithms and how to pseudocode that logic is a great place to start! If nerves get the better of you during the interview, then at the very least you can write out the logic of what the algorithm is supposed to do and often times this is enough to prove that you have the basic understanding of algorithms and how they function.
Top comments (0)