Have you ever thought "how does netflix work" or "how google search works" . The answer is Algorithm. In the real world we use algorithm for problem solving techniques . The importance of algorithm can not be undermined. Algorithm is solely responsible for driving technical revolution in the past decade . Algorithm depends upon the time and space complexity . Good algorithms take less time and memory to perform a task . In case you need to create your own algorithm , you can use these five problem solving techniques.
1. Examplify : Create the example of the algorithm
Before thinking about the logic of algorithm,We should understand the question clearly. Write atleast two examples , indicating input and output. This two minute initial work will remove the uncertainity of misunderstanding the question and thinking in wrong direction.
For example ,
Question is to find first non repeated character in the string
Then, before writing algorithm follow this steps
Example 1 :
Input : AliveIsAwesome
Output : l (small L)
Example 2 :
Input : LoveYourself
Output : v
This is one of the mostly used problem solving techniques for algorithms.
Read Also : How to become a Good Programmer : What it takes to stand out from rest
2. Pattern Matching
We have to consider what problems the algorithm is similar to , we need to figure out if we can modify the solution to develop an algorithm for the given problem .
For example :
Question :A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2 . How would we find the minimum element.
Similar Problems:
1.Find the minimum element in an array.
2.Find a particular element in an array (eg. binary search).
Finding the minimum element in an array is unlikely to be useful here.As it does not use the information information provided (that the array is sorted).
Binary search could be very useful. We know that the array is sorted, but rotated. So, it must proceed in an increasing order, then reset and increase again. The minimum element is the “reset” point.
Comparing the first and middle element (3 and 6), we know that the range is still increasing. It indicates that the reset point must be after the 6 (or, 3 is the minimum element and the array was never rotated). We can continue to apply the lessons from binary search to pinpoint this reset point, by looking for ranges where LEFT > RIGHT. That is, for a particular point, if LEFT < RIGHT, then the range does not contain the reset. If LEFT > RIGHT, then it does.
We often do practice for writitng algorithms. If we write algorithm , then we can not have algorithm
3. Simplify and Generalize
Changing constraint (e.g size,length,data type) to simplify the problem.For example changing the data type from double to int , make the problem smaller. Write algorithm for int data type and then generalize for double .
For example ,
Question is to trim the whitespaces in the password string or squeeze the string
Solve like this
1. left trim (remove whitespaces from the extreme left)
2. right trim (remove whitespaces from the extreme right)
3. remove whitespaces in between the string
4. Base case and Build
This approach is most widely used in the recursive algorithm .
Solve the algorithm first for a base case (e.g., just one element). Then, try to solve it for elements one and two, assuming that we have the answer for element one. Then, try to solve it for elements one, two and three, assuming that we have the answer to elements one and two.
For Example ,
Question is to find all possible permuations of a string , assuming all the characters in the string is unique.
Input string : "abcdef"
Solving procedure :
Take one character at a time from the input string
Base Case
a(first element of the input string) : a( possible permutation )
Build
ab : ab,ba
abc : abc,acb,bac,bca,cba,cab
abcd...
abcde...
abcdef...
5. Data Structure Brainstorm
This is tiresome method and based on hit and trial method . Simply , run through a list of data structures and try to apply each one.
For Example ,
Question : Numbers are randomly generated and stored into an (expanding) array. How would we keep track of the median(odd number of elements : the middle number but if even number of elements then the average of the middle two elements)?
Data Structure Brainstorm:
1. Linked list : Linked lists do not perform very well with accessing and sorting numbers. Hence it is better to avoid it .
2. Array : Not sure, as we already have an array.It could be expensive to keep elements sorted in array . We will keep this option on hold and return to it if it’s needed.
3. Binary tree : It can be a viable option, since binary trees do fairly well with ordering. As we know the top of the perfectly balanced binary search tree is median if there’s an odd number of elements present in the binary search tree. But if there’s an even number of elements, the median is actually the average of the middle two elements. The middle two elements can’t both be at the top. This is probably we need to look at, lets hold off to it.
4. Heap : A heap is really good at basic ordering and keeping track of max and mins. Suppose we had two heaps, we could keep track of the biggest half and the smallest half of the elements. The biggest half is kept in a min heap, such that the smallest element in the biggest half is at the root. The smallest half is kept in a max heap, such that the biggest element of the smallest half is at the root. Now, with these data structures, we have the potential median elements at the roots. If the heaps are no longer the same size, we can quickly “rebalance” the heaps by popping an element off the one heap and pushing it onto the other.
Note that the more problems you do, the better instinct you will develop about which data structure to apply.
1. Examplify : Create the example of the algorithm
Before thinking about the logic of algorithm,We should understand the question clearly. Write atleast two examples , indicating input and output. This two minute initial work will remove the uncertainity of misunderstanding the question and thinking in wrong direction.
For example ,
Question is to find first non repeated character in the string
Then, before writing algorithm follow this steps
Example 1 :
Input : AliveIsAwesome
Output : l (small L)
Example 2 :
Input : LoveYourself
Output : v
This is one of the mostly used problem solving techniques for algorithms.
Read Also : How to become a Good Programmer : What it takes to stand out from rest
2. Pattern Matching
We have to consider what problems the algorithm is similar to , we need to figure out if we can modify the solution to develop an algorithm for the given problem .
For example :
Question :A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2 . How would we find the minimum element.
Similar Problems:
1.Find the minimum element in an array.
2.Find a particular element in an array (eg. binary search).
Binary search could be very useful. We know that the array is sorted, but rotated. So, it must proceed in an increasing order, then reset and increase again. The minimum element is the “reset” point.
Comparing the first and middle element (3 and 6), we know that the range is still increasing. It indicates that the reset point must be after the 6 (or, 3 is the minimum element and the array was never rotated). We can continue to apply the lessons from binary search to pinpoint this reset point, by looking for ranges where LEFT > RIGHT. That is, for a particular point, if LEFT < RIGHT, then the range does not contain the reset. If LEFT > RIGHT, then it does.
We often do practice for writitng algorithms. If we write algorithm , then we can not have algorithm
3. Simplify and Generalize
Changing constraint (e.g size,length,data type) to simplify the problem.For example changing the data type from double to int , make the problem smaller. Write algorithm for int data type and then generalize for double .
For example ,
Question is to trim the whitespaces in the password string or squeeze the string
Solve like this
1. left trim (remove whitespaces from the extreme left)
2. right trim (remove whitespaces from the extreme right)
3. remove whitespaces in between the string
4. Base case and Build
This approach is most widely used in the recursive algorithm .
Solve the algorithm first for a base case (e.g., just one element). Then, try to solve it for elements one and two, assuming that we have the answer for element one. Then, try to solve it for elements one, two and three, assuming that we have the answer to elements one and two.
For Example ,
Question is to find all possible permuations of a string , assuming all the characters in the string is unique.
Input string : "abcdef"
Solving procedure :
Take one character at a time from the input string
Base Case
a(first element of the input string) : a( possible permutation )
Build
ab : ab,ba
abc : abc,acb,bac,bca,cba,cab
abcd...
abcde...
abcdef...
5. Data Structure Brainstorm
This is tiresome method and based on hit and trial method . Simply , run through a list of data structures and try to apply each one.
For Example ,
Question : Numbers are randomly generated and stored into an (expanding) array. How would we keep track of the median(odd number of elements : the middle number but if even number of elements then the average of the middle two elements)?
Data Structure Brainstorm:
1. Linked list : Linked lists do not perform very well with accessing and sorting numbers. Hence it is better to avoid it .
2. Array : Not sure, as we already have an array.It could be expensive to keep elements sorted in array . We will keep this option on hold and return to it if it’s needed.
3. Binary tree : It can be a viable option, since binary trees do fairly well with ordering. As we know the top of the perfectly balanced binary search tree is median if there’s an odd number of elements present in the binary search tree. But if there’s an even number of elements, the median is actually the average of the middle two elements. The middle two elements can’t both be at the top. This is probably we need to look at, lets hold off to it.
4. Heap : A heap is really good at basic ordering and keeping track of max and mins. Suppose we had two heaps, we could keep track of the biggest half and the smallest half of the elements. The biggest half is kept in a min heap, such that the smallest element in the biggest half is at the root. The smallest half is kept in a max heap, such that the biggest element of the smallest half is at the root. Now, with these data structures, we have the potential median elements at the roots. If the heaps are no longer the same size, we can quickly “rebalance” the heaps by popping an element off the one heap and pushing it onto the other.
Note that the more problems you do, the better instinct you will develop about which data structure to apply.
Mention in the comments what problem solving techniques you use in your work .