FB, MSFT interview: Case study

Here is the article. 

Hello everyone, I got multiple good questions asked in my interview experience with Microsoft and one of the requests was to provide a summary of my preparation journey. There was a time (couple of years back) when writing a iterative pre-order traversal of binary tree, or even a basic stairs dynamic problem used to be a daunting task for me. Then I accepted my current situation and came up with a plan to improve my coding skills and system design skills which I will share with you along with my learnings during this journey.

Micorsoft Interview Experience (just in case you missed it) :
https://leetcode.com/discuss/interview-experience/1260613/microsoft-engineering-manager-hyderabad-may-2021-offer/969476

Before I start, I would like to thank the entire LeetCode Community for all the help and encouragement over the last few years for the interview preparation.

Familiarising with basic algorithms and data structures

Coding Book I followed - The book which was highly recommended to me was Cormen and I quickly glanced thorugh few chapters and I realised though this is an excellent text - it is not suited for improving my coding practices. I was looking for some book which would explain the concept and also have a working code in some languages (preferably C or Java) and after exploring around 8-10 books I narrowed down to the following:

1. Algorithms (4e) - Robert Sedgewick
2. The Algorithm Design Manual - Skienna
3. Elements of Programming Interview - Adnan Aziz

If you want to know all the books that I explored then let me know in the comments. I have a small library where those books are still lying peacefully :D.

I learned the basic implementation of Heap, Trie, Graphs and their traversals, Dynamic Programming and its basics, Stack and Queues etc. from the first book. I also referred second book time to time. Once I had learnt all the basic implementation of all the data structures and classic algorithms next step was to solve some problems.

And for the problem solving I explored the following books:

1. Elements of Programming Interview (Java edition) - excellent choice as the number and quality of problems is good and explanation is also very good.
2. Cracking the coding interview - descent book but the quality of problems is not great IMO. It may be an excellent book few years back but now its just okay.
3. DS and Algo made easy - poorly written book with some random code samples collected together without any continuity and explanation is almost non-existent. Please avoid this book.

Coding Platform I followed - I explored hcker-rank, hcker-earth, gek-for-geks(G4G) and leetcode. My experience is that first two platforms will have lengthy description of the problem before coming to the real problem and that was frustrating for me because of the time I was wasting in reading that huge description of the problem. The G4G was having too many problems and majority of them are not well defined, solutions not well explained and absolutely no categorization of the problems and solutions - same problem repeated multiple times with different solutions and zero organization. So I did not use any of those platforms any longer.

I was quite impressed with the quality of the problems in leetcode. Also it was also highly recommended by some of my friends in Google/FB/MS and hence I followed only one platform and that is leetcode. The first thing after that I did was to get subscription of premium as that is highly useful. You can have five sessions under one subscription.

========================== Fun Begins Now ================================

Phase 1 - Baby Steps
In the beginning, I focused on easy questions to gain confidence and get some consistency. Once I overcame the friction of doing questions, I moved onto the medium and hard questions. I followed 60-30-10 rule where 60 percent of the problems I solved were easy, 30 percent were medium and only 10 percent were hard.

How did I select those problems? The answer is I divided the problems into multiple topics and for each topic I targeted the problems which were asked in companies (locked problems which can be seen if you have premium) and the commonly asked problems in interviews (as discussed on leetcode community). In phase one I targeted the following topics:

1. Sliding Window
2. Two Pointers
3. Array problems (Search, Sort etc) - mastered Binary Search also
4. Tree based problems (Binary Tree and Binary Search Tree only)
5. Stack and Queue based problems
6. Heap problems

I also referred to a link (cannot locate it) for dividing problems on basis of topic (similar to the below link):
https://leetcode.com/discuss/career/448024/Topic-wise-problems-for-Beginners

Note: Whatever problems I solved I kept all my learning and solutions in a word document which I could refer whenever and wherever I want. This is very important in case you want to revise any concept or a problem in future.

You will get an urge to see the solution during early phase esp - but do not look at the solution until and unless you are sure that you have tried all your ideas. If you have tried all then look at the solution, try to see what did you miss and do keep that in mind. Also even if you have solved the problem and it is accepted - do check the discuss tab and look for top 5 or top 10 highly voted solutions. I have learnt a lot from them.

Phase 2 - Trying to Stand up
In this phase I targeted the topics which were slightly difficult to grasp:

1. Dynamic Programming
2. Backtracking
3. Divide-And-Conquer
4. Graph problems

I took the help of tags here e.g. for graphs we can use the link: https://leetcode.com/tag/graph/ and then I sorted the problems on the basis of frequency and started targetting the most frequent problems (imo this is a premium feature). I spend a lot of time in understanding the underlying concept of graph traversals, how they relate to tree traversal e.g. similarity in BFS of graph and level order traversal of tree, how and why we use queue for BFS, how and when we can use stack in graph traversal, topological sort, pattern of backtracking - a result container which would store the value from temp, conditional return of temp, exploring paths, and backtracking by removing last item in temp etc. I divised some of my own patterns for backtracking and other areas and then I tried to reuse them into different problems.

Phase 3 - Trying to Run Now
In this phase I tried to solve all the locked problems (asked in companies), also mastered many patterns till now so used to revise them timely, also checked out top questions asked in leading companies like Microsoft, Facebook, Google etc. and tried to solve them. I focussed on some tricky topics:

1. Intervals based problems
2. Segment/Fenwick Tree
3. Union Find (Connected Components)
4. Hard Miscellaneous problems

I realized though I could solve easy problems most of the times and medium problems some times, I was still struggling with hard problems a lot. Some problems never crossed my mind even after spending 5-8 hours and that was hurting me a lot. So I changed my stratgey to focus on the problem for 20-30 minutes and if I could not make progress I will check the solution (and also the discuss tabs for most voted solutions) and will try to understand the solution and then keep the learning in my notes - which I would revise time to time.

It is very difficult to get time for coding practices esp when you are working so I used to take 30-40 minutes in morning where I will read about a problem, will brain storm to find the solution, used to discuss sometimes with my like minded peers, and will see the solution if I eventually give up. I used to address problems from diverse topics so that I wont loose the interest and also it is more effective stragetgy imo.

Try to solve a problem using multiple concepts
I used to try solving a problem using multiple ways and then try to compare complexity and other aspects.

Try to figure out if a problem can be mapped to a more commonly asked problem and use that solution.
This has been a good learning where I learnt how to solve a classic problem and then during my journey realised that multiple problems can be mapeed to same problem. For example 960. Delete Columns to Make Sorted III and 354. Russian Doll Envelopes are very similar to the problem 300. Longest Increasing Subsequence and solution for that can be reused to solve other two problems as well.

Do not spend too much time on a single problem
I have solved 300+ problems and this is what I learnt. Always try 10-15 minutes in a problem to find the pattern e.g. check if it needs exhaustive search (may be we can use BFS), or it needs backtrack, or it can be solved by DP after we have explored and sovled for multiple given inputs etc.
If the pattern is too obvious then sometimes I skip the problem to focus on other problems.

Keep eye on locked and tricky problems
Always look out for problems which have some tricks underlying them - IMO they have high chance of being asked in upcoming interviews.
I recommend to take the leetcode premium subscription then you can also unlock the locked problems and articles. You can have five active session in one subscription and can share with friends to share cost.

Phase 4 - System Design
Honestly I have been designing systems in my current job profile so I did not spend too much time on this. But I still found the following materials useful for my preparation:

1. Course Gr**** the System Design Course from Ed**** (Sorry for the * as LeetCode does not allow me to write those words in the post. I hope you can guess the course) very useful. This course is highly recommended and is worth it.
2. Famous System Design Primer on Github
3. Articles on high scalability - Highscalability.com
4. Posts tagged under System Design on LeetCode Discuss - https://leetcode.com/discuss/interview-question?currentPage=1&orderBy=most_votes&query=&tag=system-design

There are too many youtube channels having system design videos - imo they are mostly useless as they are not comprehensive and some of them are even plain wrong about the design idea. I suggest to follow official videos from various companies, infoQ videos, Facebook Developers videos etc. They are really useful to get that final feather in your hat!

I would like to conclude this with some interesting links:
https://leetcode.com/discuss/career/449135/how-to-effectively-use-leetcode-to-prepare-for-interviews
https://leetcode.com/discuss/general-discussion/665604/Important-and-Useful-links-from-all-over-the-LeetCode
https://leetcode.com/discuss/general-discussion/494279/comprehensive-data-structure-and-algorithm-study-guide
https://leetcode.com/discuss/general-discussion/459286/Best-Posts-of-2019
https://leetcode.com/discuss/general-discussion/522705/1000-leetcode-problems-within-a-year
https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns/544912

=============== Books I explored ================
Some of you are showing interest in the books I explored so I have listed them below and rating is as per my opinion(rated out of 5):

Algorithms Prep
Algorithms 4e(4.5) - excellent book for algorithms and DS
Algorithm design manual (4) - very good
Cormen (4) - good text book but voluminous and more for academic and research
DS and Algo made easy (2) - poor book so avoid it. Its more of a collection of random code samples without any continuity. Too many coding errors and poor explanation.
Algo in a nutshell (2.5) - descent for overview of algo
DS by Lafore (2) - text book kind of not much useful
DS by Weiss (3) - text book

Problem Solving
Element of Programming Interview (4.5) - excellent book for coding prep
Cracking the coding (3) - descent book for coding prep
Programming Interviews exposed (3) - okayish book

Coding Practices
Clean Code (4) - excellent book
Clean Coder (3.5)
Programming Pearls (4) - just covered half of the book only

Architecture
Clean Architecture (3.5)
Design Patterns by Gamma (4) - classical text
Patterns of Enterprise app architecture (4) - great book by Fowler

System Design
Designing Data-Intensive Applications (4) - great book but takes time to cover everything
Gr***ng the system design (4.5) - excellent choice

githubmicrosoft