Essential content & how to solve algorithms
π Essential content and how to solve these questions
In general, technical interviews are not based on tests to assess your knowledge, they are based on your abilities to solve algorithms. It is assumed that candidates already have the fundamental knowledge necessary to solve difficult algorithm questions - since they will repeatedly need this knowledge to do their job.
π½ What is necessary to know?
There are concepts that are essential to know. These will not only serve you for interviews but in general in your career as a programmer. There are data structures, ways of writing algorithms and key concepts that we consider essential when interviewing for companies with a strong engineering culture.
Data structures | Algorithms | Concepts |
---|---|---|
Linked Lists | Breadth First Search | Bit Manipulation |
Trees | Depth First Search | Memory (Stack vs Heap) |
Stacks & Queues | Binary Search | Recursion |
Heaps | Merge Sort | Dynamic Programming |
Vectors / ArrayLists | Quick Sort | Big-O Notation |
HashTables |
If you are not comfortable with the data structures in the table above, I recommend that you learn to implement them from the beginning. Knowing the complexities and details of each one will be very useful during your career.
It is important to note that in general HashTables will be extremely important and it is good to feel very comfortable with them.
πΆ How to solve these questions?
It is important that you try to solve these problems on your own first - the only way to become a good programmer is to practice. There is no such thing as memorizing solutions when it comes to being a good programmer.
π£ Tips to solve these problems
- For each problem try to solve it on your own and not see the solution. I will also give you tips on how you could solve them - but I still recommend using as little help as possible.
- Write code or pseudo code on paper. Many interviews and algorithm discussions will be like this and you will not have the luxury of having syntax highlighting and other advantages that you would have in a code editor.
- Have proof of your code on paper, remember to think about all possible cases, errors, maximum capacities, etc.
- Then put your code into the editor and try to start detecting your mistakes, making a list of them and correcting them one by one.
π Flow of how to solve a problem
- Listen or read the question well: Be sure to clarify anything you don't feel sure about. Pay special attention to details as if an Array is ordered or not, since the most optimal solution might be different than if it were unordered. Or if they tell you to design an algorithm that will be used repeatedly on a server - since the solution may be different than if an algorithm is only run once.
- Draw an example: Make sure it is as close as possible to a true example. Many people make the mistake of drawing a very small or very perfect example, when in reality what interests the people who read your algorithm is the ability you have to cover all possible cases.
- Write a solution by brute force: Do not be afraid to write a terrible or even incomplete solution, since nobody expects you to write a perfect algorithm at first. Having even an incomplete solution can lead you to have a non-optimal solution. With a brute force solution you can start optimizing the complexity of the code, as well as the complexity of the space/time of the algorithm.
- Optimization: This is what you should always be thinking about after the first solution that works. The next section of this page is entirely dedicated to explaining techniques on optimization. But things you should be thinking about are these:
- Look for any details that you have been given that you are not using - surely they have given it to you for a reason.
- Use several examples, sometimes just writing a completely different example can help you find different ways to see the problem.
- Solve incorrectly: This is something that took me a long time to understand when making solutions - but extremely valuable. Just like when you write a non-optimal solution - that leads you to optimize the solution. Writing an incorrect solution puts you on the path to a correct solution.
- Make comparisons between time and space. Many times saving some status locally will lead you to do less computation and therefore optimize the runtime.
- Precompute information. Is there any way to rearrange the data so that the runtime is smaller?
- Think if it will be better with a HashTable. This is something you should not forget in interviews as it comes on a regular basis.
- Think about whether you can write in a way that has a better runtime.
- Check your solution again: and carefully read the code or pseudo-code you have written. Make sure you are sure of what happens with the variables you are using, that you understand the problem and the solution you want to implement very well.
- Implement: Now that you have a good idea of how to solve the problem you have to start focusing on writing good code. By this I mean that you keep in mind that your code is modular. Check if you need to write error cases - if you don't have time during the interview at least put a comment. Use sensible names for variables such as a, b, i, j etc. Except if you are inside a loop.
- Test: Make sure your code has been tested with enough examples like the ones you wrote at the beginning. Do a conceptual read - making sure you understand each line of the code and that they serve a purpose. If there is something strange in the code like
// x = length / 2
// for(i = 1, β¦), etc.
that you can explain why it is so. Finally, make sure that your code has ways to deal with special cases, for example null checks, if an array has only one negative element, number, etc.