DIY Optimisation

If most people ask them to find an element in an ordered array - they are quite likely to implement a O(N) algorithm that will basically search for each element in the array iteratively, until it finds it and returns it.

Now, if a person asks you to find a student's exam in a pile of tests that are arranged alphabetically, quite likely by intuition they would apply a binary search algorithm O(Log N) in which you will start looking more or less for the medium, and will continue to pivot to the left or right of that medium - and will continue to split that half into another half until it eventually reaches the exam it needs.

For this reason it is very important to consider our intuition when designing an algorithm. Above all it is important to draw several examples on paper and try to solve it in this way, rather than trying to solve it in code. Think that in most scenarios, a process that is slow for a person will surely also be slow for a computer.

Try it with this example:

If we give you 2 Strings, the first shorter than the second. Design an algorithm that finds any permutation of String (A) within the second String (B) - which is longer.

String a = “abbc”;
String b = “cbabadcbbabbcbabaabccbabc”;

Try to think for a moment how would you solve it? Most programmers would try to solve it in code first. If you are like the majority of programmers I know, you would try to generate all the permutations of String A, which takes a very bad time of O(A!), And then you would compare linearly with the pieces of String B. To give you a sense - if the String A has 14 characters - this would entail an amount greater than 87 billion permutations. If you add one more character that would be multiplied by 15.

Look at this example that teaches all the permutations of A within B.

When you see it drawn it is much more obvious there are easier ways to find these permutations. You need 4 characters - 1 a, 2 b, 1 c. If you start from left to right you will notice that if you find one of these characters while traversing the String - you can see both sides to see if you also have the necessary amount of others to form a permutation.

Try this form of optimization when solving problems. Remember to use a large example and then manually solve it. If you have already solved the problem in code - try comparing it with your “manual” answer.