Here I want to share tips on how to approach solving algorithmic tasks and common pitfalls, which I gathered from my experience by solving more than 350 tasks on LeetCode, InterviewBit, Code Forces & Co.
To begin with, I really recommend the G. Polya’s book “How to solve it” – it covers lots of approaches and strategies for mathematical problems, which is also applicable to algorithmic ones. I will mention some of them in this post.
Understanding the Problem
Read the problem carefully. Write down key data and introduce an appropriate notation. Draw a picture/figure. Be sure you got a mental picture of the problem (in my case it means that I can “visualize” it in my head). If not – reread the problem and try to picture the conditions first on the paper, then in your imagination. Remember, solving tasks is a creative process.
If you will solve the task on the interview, ask if the input fits into the memory, ask about corner cases and clarify how the problem must behave given different inputs.
Finding and Planning Solution
To a great extent, solving a problem is the asking of the right questions. Great teachers know how to direct the learning process by asking just the right questions so that a student can come up with the solution on its own. With time, a student learns to ask this questions thyself.
Think about whether the problem is similar to something you have met before. If the problem is designed to be simple and you have no clue on how to approach it, it means you did not learn to solve this type of questions (so just jump to the understanding of the answer). In more complex tasks it is very common that they are built using multiple levels of easier problems. Oftentimes if you cannot solve a more complex task, it may mean you miss some of the bricks.
A quick note on what it means that you cannot solve it: for easy questions I will not spend more than an hour on thinking. For more complex – max the next day. In this way, you ensure steady progress in your ability to think while enriching your algorithmic toolbox.
If you do not see the solution immediately, twist and turn the task. Drop some constraints. Good [level:hard]exercise for changing constraints. Think of more general task to solve. Think if you can solve some special case of this problem and then try to generalize it to the initial problem. Could you restate the problem? Could you first solve some related problem?
Think how can you convert the input data, what are the invariants.
Example Solving a Problem from the End
Sometimes it helps to look at the problem from the end: look on what you want to get and shift your focus from how to get there from what you got towards answering the question: is there a way I can unfold backward from the result to the primary condition. A good illustration of such an approach is in the following problem:
[level: hard] Given a coordinate plane and a random set of dots of it with the integer X and Y coordinates, find out how many dots will remain after crossing them out. You can cross out 2 dots if they have the same X or the same Y coordinate.
Pause and think a while on this problem. Think as described in the previous sections.
If you go forwards and start crossing out the dots, sooner or later you will find that it is a pretty complicated and daunting procedure and it is not clear on how to code it. If you go backward and think, ok, I have these dots. Which of them will remain in the end? In the end, from each “cluster” of interconnected dots will remain only one dot, because since they are connected, we can cross them one by one from outer boundaries and move to the one last dot. What does that cluster mean? Think in terms of graphs, where vertices are dots and to dots are connected by an edge if they have the same X or Y coordinate. So the cluster is a connected component. So our problem boils down to finding the number of connected components in a graph and belongs to that “bricks” I have mentioned (it is a standard problem one should learn to be able to apply it later to other problems).
After you come up with a solution, analyze its time complexity and the amount of space you need in terms of big O notation.
Before jumping into implementing the solution, navigate once again through the implementation steps. Can you see clearly, that each step is correct? Can you prove that it is correct? Is the logical flow of each step clear?
Think about corner cases! Think twice about the corner cases or they will bite you later in the middle of your coding session. A good task for training this skill on [level: intermediate] linked lists.
Check integers for overflow. Are there any recursive functions you plan to write, which may cause stack overflow? Think of replacing them with the iterative approach.
After you have finished a problem, reflect a while on possible modifications or extensions of it or how you can connect it to any problems you already know. Can you solve the problem more effective using a different approach? Can you use this approach or method for solving some other problems?
This step will consolidate what you just learned and will enhance your understanding of the problem.
On the interview, test your code, including corner cases. If you found a bug, do not jump right into correcting the code! First, analyze, what is the cause of the bug. Second, think how you want to correct it, going from top to the bottom of your algorithm end ensure that all other parts of the code will still function correctly. Now you can do it:)
That’s it, guys! Hope, there were useful tips for you and if you have any experience to share – do it in the comments below!