Often encountered during a coding interview is being challenged to a very tricky coding question which you try to give the best approach you know in delivering the solution in record time! You impressed of your performance and you become happy when your coding interviewer tells you that your algorithm will work but stumped when he asks you for a more efficient way of providing the solution. Now is when the real challenge starts, you probably have given the best you know in solving the problem and you possibly can’t think of any better approach to solving the problem. Well, you don’t have to feel specially embarrassed because this is commonly encountered among many at various times, and the bright side to it is that you don’t need to be stuck on an approach anymore, because there are some other common and easily applicable approaches to improve the efficiency of your algorithms. Therefore, when next you find yourself in a similar circumstance, try exploiting one of the three approaches given below.
- Hash maps
Hash maps, also known as associative arrays or dictionaries based on different programming languages are effective ways to reduce the run time of algorithms. A good example of how this can come in handy is when you are asked to find the most repeated number in an array, instead of looping through the array of numbers and count the number of time the numbers occur in two nested loops.
We can even make this whole process a whole lot better by storing our count in a hash map (mapping numbers to their count) which makes the problem solved in a simple step. This method is faster!
- Bit Manipulation
Knowing this will make you shine among many, especially when you appropriately apply when the need demands it. Imagine you are looking for a way to find a single non-repeated number in an array of numbers, this is a perfect way to go about doing that. Bit manipulation is a way to XOR numbers with themselves which allows them to cancel each other out leaving one unrepeated number which doesn’t cancel out.
- Go Bottom-up
For questions which yield to recursion, it is easy to go from say n to 1 recursively, however, this system is not time or space efficient. A better way to go about this is to go bottom-up which enables us to skip the recursion:
Now, you are ready to render more efficient solution when an interviewer asks you. Good luck!