Algorithmic Problem solving is one of the biggest asset of a Software engineer.
It is the skill set which interviewers focus on the most during interviews.
If you demonstrate the good problem solving skills then it leaves an impression that the candidate has good thinking capability.
Thinking ability ensures the interviewers that the candidate will be able to pick any technology, programming language etc. very quickly and excel at it and solve any problems related to it.
In order to get the most out of this post, once you are done with reading this article chart down all the key pointers which are present in the right hand side index. Keep it safe for quick reference and refer it whenever you are approaching an Algorithmic Problem Solving.
If you are very new to programming then you should definitely check out the article Think Programming. It helps you in understanding why a concept in programming exists.
What is an Algorithm?
Algorithm : In the simplest of form, an Algorithm is a series of steps towards problem solving. That’s all should cross your mind when someone refers to the word Algorithm.
Real question here is, what are the series of steps towards problem solving?
Steps Towards Problem Solving:
Following the below mentioned steps can helps you in designing your algorithm for a problem with all the information you need and also helps you in avoiding a lot of rework.
Understand the Problem
The very first step of designing the algorithm is to understand the problem at hand completely.
Read the Description Carefully
Don’t rush into a solution. Taking out time to understand the problem at hand makes you appreciate the problem. Read over it carefully multiple times.
Once you are able to understand the problem and appreciate it, you would want to cover every aspect of the problem and will come up with a fitting solution.
Be it an interview, or taking the requirements from your clients/stake holders, do not hold back from asking the questions whose answers are not visible through the problem statement.
The questions can be as simple as does it take input of only integers or it can take the floating point numbers as well?
When you ask appropriate questions, it gives an impression about your thinking process and how do you approach a problem.
Try Out with Small Examples
The problem at hand may be very big but it can always be broken down into a smaller problem. Design the solution for the smaller problem and work your way upwards towards bigger problem.
To find the largest of 100 numbers. It would be better if you try your solution on just 5 numbers and then take it from there. It works as a mechanism of fast feedback.
Think About Special Cases
Every problem have their own special cases where your solution wouldn’t work. You need to think of as many possibilities as possible where your solution can go wrong.
For example : If you are designing a solution for an automated door system, what would happen if the power goes off. And How your system will behave in that case?
So you need to think on all the external as well as internal dependencies of your solution. What happens to your system if they go out of order!
Ask Questions Again if Needed
If any point in time during designing a solution there is lack of clarity on what needs to be done, then ask the questions again. Do not assume things and develop a solution. It would be like digging yourself into a hole.
The step of Understanding the problem is very important. Do not skip it. You can save a lot of unnecessary rework.
Decide on Data Structures, Design Techniques
Deciding on Data Structures
Data structure remains crucially important for both design and analysis of algorithm.
Data Structure is important because your entire solution to the problem is based on the data which you are dealing with.
For example, the questions like whether you should be using a stack or a queue , priority queue etc. or should you build a custom Data structure for your solution.
Using the correct data structure helps you in designing the efficient solution.
Deciding on Algorithm Design Techniques
After understanding the problem, all the questions asked and deciding on the data structure; how do you design an algorithm to solve a given problem?
Algorithm Design Technique is a general strategy and approach to solving the problems algorithmically that is applicable to variety of problems.
There are various design techniques available for solving a problem, to name a few :
- Brute Force
- Divide and Conquer
- Decrease and Conquer
- Transform and Conquer
- Greedy Technique
So based on your problem, you should follow one of these(and many more) general techniques to get to a solution.
For getting a grip on design techniques I recommend Introduction to Design and Analysis of Algorithms by Anany Levitin.
Specifying an Algorithm
Once an algorithm is designed, you need to specify an algorithm such that it can be read and understood by others.
There are two ways of doing it:
Pseudocode is a mixture of natural language and programming language like constructs like if, for, and while.
It looks like as shown below, an algorithm for computing greatest common divisor:
//Compute GCD(m, n)
//Input : Two non-negative integers m, n.
//Output : Greatest common divisor of m and n.
while n != 0 do
r <- m mod n
m <- n
n <- r
Flowchart is a collection of connected geometric shapes containing the descriptions of the algorithm’s steps.
The main image shows the flowchart of algorithm to solve a problem. That’s how a flowchart looks like.
Proving an Algorithm’s Correctness
Once an algorithm is in place, you have to prove its correctness. You have to prove that the algorithm yields a required result.
Pick some sample inputs for your algorithm and run those input against the algorithm. Your algorithm should return the desired output.
Try to break your algorithm by using invalid inputs. This makes your algorithm better and helps you in covering all possible special cases.
Analysing the Algorithm
An algorithm should have various attributes for it to be called a good Algorithm. After correctness, the most important attribute is efficiency.
Apart from efficiency, the 2 other attributes of a good algorithm is Simplicity and Generality.
Let’s discuss them briefly:
Time efficiency indicates that how much time an algorithm runs for solving a problem.
Space Efficiency indicates how much extra memory the algorithm needs to solve a problem.
Simplicity indicates how simple it is to understand the algorithm. Like efficiency, it is hard to measure the simplicity of an algorithm as it may vary from person to person.
Generality indicates the breadth of a problem types that a particular algorithm solves.
Since it is difficult to measure the Simplicity and Generality attributes of an algorithm, the focus always remains on the Time and Space efficiency of an algorithm.
Coding The Algorithm
Once you have your algorithm is designed and tested manually for correctness with some sample inputs, it’s time for you to implement the algorithm with the language of your choice.
When your algorithm is implemented, it turns into a program. And the validity of a program can only be asserted by thorough testing.
There are many stages where you can test your program – Unit tests, integration tests, at REST API layer, at UI layer.
But i truly believe that unit tests are the most important type of testing there can be. To read more about Unit Testing refer the article Introduction to unit tests and its importance.
Designing an algorithm before you start implementing your program can save you from various pitfalls because when you understand and design an algorithm, you take many aspects into consideration. Which otherwise in a rushed implementation would require a lot of rework.
Also, during interviews, the way you approach and think about designing an algorithm also helps interviewers in understanding you, which boosts your chances of selection.
Stay connected for the post on Analysing the efficiency of an Algorithm.
Leave comments for your feedback.