DEV Community: Pritam Chougale

What are some must-know algorithms to crack FAANG interviews?

Pritam Chougale — Mon, 04 Oct 2021 07:22:10 +0000

Going by our experience of training thousands of students at Programming Pathshala and helping them get successfully placed in these companies, the most important algorithms you need to cover for any major tech company are -

1. Precomputation Techniques: Many people do not consider them as important but they are extremely crucial. Many problems have prefix/suffix computations as an important step of optimisation.

2. Binary Search Algorithm: Binary search is not as simple as finding an element in a sorted array. It has much more complicated use cases which is important to know and work on. Concepts of monotonic functions and binary search on answer help you appreciate the beauty of this simple algorithm and make you a good problem solver.

3. Sorting Algorithms: Knowing different sorting algorithms like Bubble, Insertion, Selection, Merge, Quick and many more O(n) sorts is important. Also, these algorithms have associated techniques like Divide and Conquer in Merge and Quick Sort, Dutch National Flag problem, etc which are also important.

4.Two Pointers & Sliding Window: Two Pointer Approach is optimised Binary Search Approach in 90% of the cases. Optimising binary search solutions by using 2 Pointers is an important step asked in many interviews.

5.Greedy Algorithms: This is the most difficult algorithm to spot in a problem. Getting to know that a problem can be solved by a particular greed and proving it is very difficuly. Proof by induction, contradiction and mathematical proofs come handy for these problems.

6.Recursion, Backtracking and Dynamic Programming: I have clubbed them together because you can’t do Dynamic Programming without fully understanding Recursion & Backtracking. Understand concepts of Recurrence Relation, Stack and Tree Diagrams, Concept of Memoization, state, etc. Many people start solving DP without understanding the theory. This is one topic where if you are clear with the theory, you will not be stuck in many problems.

7.Graph Search Algorithms: No fancy Djikstra or Flow Algorithms. No fancy Segment Trees. The most important is mastering the two search algorithms - Depth First Search and Breadth First Search in detail.

There are other less important algorithms like Bit Manipulation, Mathematical Algorithms and other subjects that you also need to cover for these interviews (Data Structures, OOPs, OS, DBMS, etc.) For complete syllabus, you can go through our website.

Most important thing to note is “Focus more on covering every aspect of an algorithm you are learning and understand the patterns associated with it. Do not unnecessarily go for heavy algorithms like segment tree. Stick to the basics and you should be good”

If you want to master Data structures and algorithms and become 100% coding interview ready I have a good new for you.
You can start a 7-days free trial of our coding interview prep platform. No credit card required.

I have 6 months to prepare for placement. Basically, I'm a Computer Science student. How and what do I study?

Pritam Chougale — Mon, 04 Oct 2021 06:17:18 +0000

Let’s first look at what all skills you need to have for campus placements. Assuming that the companies are hiring for a software developer role, you would need:

Proficiency in any one programming language.
Very good problem solving skills and knowledge about data structures and algorithms like stacks, linked lists, searching, dynamic programming, etc. For complete list, can visit the syllabus at Programming Pathshala’s website and can follow that
A good project for your resume. Would suggest a full-stack project.
Maintaining a good CGPA (>=8/10 in Indian context) would be a good idea.
Clean coding skills, design principles and patterns (Part of Low-Level Design)
Subjects in Computer Science like Operating Systems, Computer Networks, DBMS.

For roles different from SDE, there might be some other things you need to do. Statistically speaking, SDE roles are the most common. So, it is a good idea to stick to those.

Now, all this might seem a little daunting, specially if you have to do it by yourself in 6 months. But, ideally it is very much possible if you put in the efforts.

Apart from that, if you think you would require guidance from alumni of top tech companies, do selected problems from each topic that cover all the subpatterns of a topic, give mock interviews and/or need referrals, you can also opt in for a 6-month interview preparation course with us at Programming Pathshala.

Note:
After considerable discussion with Bharat Khanna, co-founder of Programming Pathshala, I was able to formulate this response. Who also happened to be an ex-SDE at Tower Research and a codeforce candidate master.

Why is there so much fuss about dynamic programming in interviews, when it hardly matters in real-time projects?

Pritam Chougale — Wed, 29 Sep 2021 07:24:35 +0000

“When it hardly matters in real-time projects”. This statement is extremely incorrect. Just a few examples:

Machine learning algorithms like Viterbi algorithm or the ones using Markov Chain or HMM are infact completely based around Dynamic Programming

Bioinformatics requires a lot of sequencing algorithms which are rooted in DP.

String matching is done via KMP and uses of Edit Distance - Again extremely important for a lot of real world things like Autocompletion.

A common example would be, many delivery apps (I have heard of UrbanClap) model their problem as a graph and use greedy/dp algorithms to actually solve the delivery problem

More importantly - let us understand what is the principle behind Dynamic Programming?

It mainly consists of 3 steps:

Step 1: Dividing the original problem into smaller subproblems

Step 2: Solving these subproblems and combining their results to get the big problem’s result

Step 3: Remembering the subproblems you solved in the past and reusing the results rather than recalculating for them (Memoization)

Don’t you think these 3 steps are actually very important for solving real problems?

That is why they are given importance in an interview. The idea is to pick the best problem solvers.

Want to know how to start preparing for coding interviews?
Visit: programmingpathshala.com and take a 7 days free trial.

How Long does it Take to Prepare for Coding Interviews: Starting from Scratch

Pritam Chougale — Thu, 26 Aug 2021 06:05:20 +0000

The Coding Interview Preparation may seem like an endless task considering the staggering amount of resources available online. With this blog post, I want to help you all by giving a perfect preparation plan that is enough to crack software roles in the majority of the product based companies.

I am assuming that you have no prior knowledge of programming and programming languages, and you are starting from scratch. This plan will take a total of 8-12 months to complete.

We at Programming Pathshala have students who have made into companies like BharatPe and PayPal in a time period of less than a year by following this plan thoroughly with us.

So, here are the steps to prepare & get ready for coding interviews

Step 1: Learn a Programming Language [1-2 months]

First and foremost, the beginning point of your coding interview preparation is to learn any one programming language. If you are a complete beginner, I would advise you to choose one of C++, Python or Java for starting your journey.

Learn the basic constructs of programming: Data Types, Control Flow, Looping, Functions, Pointers, Structures and Classes etc.
Stick to one programming language and develop a command on it. Many people think that knowing programming is equivalent to knowing numerous coding languages which is not true.
Start implementing common out-of-the-box features supported by this language with respect to certain data structures and algorithms . For example, if you choose C++, learn how to use STL Map, sets, vectors, upper_bound, lower_bound, etc. If you choose Java, learn how to use HashMaps, TreeMaps, ArrayLists, etc.
Solve at least first 50-100 problems of basic implementations from platforms like Codeforces.

Step 2: Learn Basic Prerequisites before starting with Data Structures and Algorithms [1 month]

Before deep diving into Data Structures and Algorithms, make sure you are familiar with certain techniques that are used with almost every other DSA concept later on. These techniques include:

Precomputation techniques in Arrays like simple ideas to handle multiple queries by precomputating the answers.
Mathematical techniques like computing primes using sieves, doing factorisation, finding lcm & hcf, basic combinatorics. Recursion, recurrence relation and how to think in recursive terms.
Understand the concept of Backtracking, which helps in writing basic brute force solutions to almost all the problems.

Step 3: Dive Deep into Basic Data Structures and Algorithms [2-3 months]

Many people directly start learning Dynamic Programming as soon as they hear about Data Structures and Algorithms. The truth though is that many of the startups and, sometimes, even companies like Amazon focus more on basic Data Structures rather than DP.

Get a strong grasp on Searching algorithms. It is important to understand what kinds of problems are optimized using the Binary Search algorithm. There are several popular commonly asked patterns like Binary Search on Answer.
Explore different sorting algorithms and the corresponding concepts involved in it. For example: Merge sort requires the Divide and Conquer algorithm and Two pointers for merging, while Quicksort uses an efficient partitioning mechanism.
Explore Stacks, Queues and Deques in-depth. Understand what patterns of problems are understandable using Stacks. Some very difficult problems can be solved using Stacks. Eg. Remove K digits to find the minimum number
Solve a lot of problems on Linked Lists and Binary Trees. Although simple, some problems require very specific solutions, and it is a good idea to know some techniques beforehand. Eg. Watch this Linked List & Binary Tree Live Class by ex-SDE Amazon

Step 4: Start with Intermediate Data Structures and Algorithms [2-3 months]

Now is the time to start learning Heaps, Greedy, Graphs and Dynamic Programming. These are relatively harder Data Structures and Algorithms, but are extremely important for coding interviews.

Learn about Heaps Data Structure: Common Operations on Heap like Tying Ropes, Kth Min/Max problems and Heapsort are important.
Understand Greedy Algorithms and how to prove greed for certain problems. Classical problems like Activity Selection and Job Scheduling should be understood thoroughly as to why particular greed works and others do not.
Explore Dynamic Programming: Build on Recursion & Backtracking to memorize and convert it into Recursive DP Solution. Tabulate it to convert the same into Iterative DP and also learn how to optimize space.
Learn about Graph Traversal Algorithms like Depth First Search(DFS) and Breadth First Search(BFS).
Explore the shortest path algorithms like Dijkstra and Minimum Spanning Trees.

Step 5: Learn about Computer Science Core Subjects [1 month]

Now that we are done with most of our Data Structures and Algorithms syllabus, it is time to start learning certain core Computer Science subjects, which are equally important for being a good Software Engineering student and being prepared for coding interviews.

Operating Systems: Learn about Process Management Mechanism, Memory Management Mechanisms and Concurrency Problems & Solutions
Databases: Understand different databases and how their data models look like. Learn how to model data in case of relational databases using ER Diagram and Normal Forms. Apart from that, understand Transactions and ACID Properties
Networks: Understand different layers in OSI Model. Learn about common networking devices and protocols and what functions they serve.

Step 6: Learn about Low and High Level Design [1 month]

After covering theory related ideas in Computer Science, it's time to get some practical knowledge that will make you industry ready.

Codes written in the software Industry are generally organized as classes. Also, there are certain components at System Level that you need to know about.

Learn about Classes and Objects and understand common Object-Oriented Design Concepts like Polymorphism, Abstraction, Inheritance, Encapsulation, etc.
Learn about Clean Coding Practices and concepts of Modularity. Understand Design Principles like SOLID Principle
Learn about Different Design Patterns.
Learn about Distributed Database Systems, concepts like Sharding, Replication and how systems scale
Know about concepts like Load Balancers, Microservice Architecture and Forward/Reverse Proxies.

Step 7: Explore Advanced Data Structures, Give Mock Interviews, Make a project [1 month]

At this point, you would be mostly prepared for any big company out there. You can do a few more things to become more confident in cracking them.

Create at least one good working project using any latest technology like MERN stack. You can deploy it at some open source platform like Firebase or Heroku and put its link in your resume.
Give some mock interviews with industry experts or your peers.
Read some more interview experiences of different people and if you feel weak in any topic, try to revise and practice it more.
If you get some time, explore some advanced data structures like Tries, Segment Trees, Range Queries, String Matching Algorithms, etc.

Explore advanced data structure here

This is how in 8-12 months you can easily become a very good software engineering resource for any company that you go to. Not only will you prepare for the interview, but also will become a better software developer.

Conclusion

The above blog post covers the sure shot steps to become interview ready within 8-12 months. Many of our students have undergone this curriculum, and we have seen it working. It only requires discipline, dedication and constant endeavors to succeed.