One of the biggest trouble people face when preparing for interviews is not solving problems despite knowing the core concepts.
How many times has it happened with you that you knew a particular data structure/concept and understood it thoroughly but could not solve its problems?
Believer it or not, this is a widespread issue that people face when preparing for interviews and trying to solve problems on a website like Leetcode.
In this post, we will be discussing ways in which we can improve problem-solving skills and learn to solve more problems for the same concept.
Start With Brute Force
This is one of the most underestimated steps when solving problems. If we face difficulty solving any problem, we should always start with a brute force solution (unless we figure out the optimized solution directly).
This will provide two benefits :
- Reduce brain fog: If we start with brute force solution, we get into thinking mode and progress while solving the problem. This is important because it gets us thinking and reduces the lack of thoughts (brain fog) we face while solving problems.
- Provides Insight: Once we go through the brute force solution, we can usually see some pattern or get some insight into which the optimized solution builds upon. We can then use this insight to optimize our solution further.
Learn Through Patterns
When you go through the brute force solution, try to identify the brute force solution’s inefficiency and how it was made efficient in the optimized solution.
Once you have identified the difference between brute force and optimized solution, then try to remember this method.
To understand this in more detail, let us understand with a simple example :
Write a program to check if two strings are anagrams of each other.
For example, if we compare two strings, “binary” and “brainy”, they both are anagrams of each other because both of them have the same letters with the same frequency (essentially, they are just rearranged versions of the same letters).
Brute Force Approach
If we try to solve the problem using the brute force approach, we can solve the problem by doing two things :
- Compare the strings’ length: If the length of both the strings is not the same, then obviously they can’t be anagrams.
- Map each character of the first string with each character of the second string: What this means is that try to match each of the first string characters with the characters of the second string. Doing this will involve two for loops, and the time complexity will quickly jump up to O(N^2)
If we identify the inefficiency in the above solution, then the inefficiency would be that after picking up each character in the first string, we search for that character in the 2nd string. Since searching once involves one traversal (N comparisons), if we search for N characters => we are searching N times => Total comparisons would be (N*N = N^2) => Time complexity becomes N^2.
Can we get rid of the above inefficiency?
Can we use some data structure to reduce the search time?
Yes, we can use a hash table! In that hash table, we will store the frequency of each character present in the 2nd string. Now while searching, we will not be searching in the 2nd string. Instead, we will search in the hash table. Since searching in a hash table is O(1) Amortized, our solution also becomes optimized!
If you solve the problem in this manner, you can remember that we used a hash table to improve the search. Next time you see that the brute force solution is unoptimized because of the search, you can use a hash table to optimize it.
Do Medium Problems
If you want to improve your problem-solving skills, always try to do problems that are just slightly above your current level. This would make problem-solving fun and interesting.
If you do too many easy problems, you will become bored very easily.
If you do too hard problems, you will become bored as that would be too difficult to crack.
Therefore, try to do medium level problems. For most of the people who have just started with problem-solving and DSA preparation, they will provide the right level of challenge and fun.