Basics of Data Structures & Algorithms interview prep
To students and professionals looking to brush up basics of Data Structures & Algorithms (DSA) for software engineering roles, I humbly present a few resources and a suggested preparation plan that had worked for me in the past (2019).
Before you proceed further, this is NOT a roadmap or bible that can guarantee cracking all DSA interviews. It is simply a structured preparation plan for getting into good shape, readers need to advance skills further depending on the company they aspire for.
Core & Advanced DSA Concepts
To simplify things, I have categorized some frequently asked stuff as “core” DSA concepts (bold are even more important) and other VERY rarely asked (if ever) tougher ones as “advanced” concepts.
Core DSA
- Data Structures : Arrays & Structures, Stacks & Queues, Linked Lists, Trees (Binary, Binary Search), Graphs, Heaps & Priority Queues, Hash Maps
- Algorithms : Brute Force, Divide & Conquer, Decrease & Conquer (DFS, BFS, Tarjan’s, Kosaraju’s), Transform & Conquer, Dynamic Programming, Greedy Technique (Prim’s, Kruskal’s, Dijkstra’s)
Advanced DSA
- Data Structures : Tries, 2–3 trees, Red black trees, AVL Trees, Splay Trees, m-way Search Trees, B-Trees, B+-Trees,
- Algorithms : Iterative Improvement, Backtracking, Branch & Bound, Approximation Algorithms for NP-hard problems, Algorithms for solving non linear equations
Beginner Stage
Note: I’ve added free links where possible, in some cases they might differ from the paid hard copy which you can verify.
College textbooks
At the early stages of DSA and problem solving, your college textbooks should be good to get started if the curriculum is of decent standard. Below were textbooks prescribed in my syllabus for reference
- Fundamentals of Data Structures in C: Free link
- Introduction to The Design & Analysis of Algorithms: Free link
External sources
Additionally these are highly vetted external sources for DSA
Suggested routine
As a complete beginner, spend ~2 weeks of ONLY reading and doing exercise questions (not actual coding) from above textbooks —college textbooks first, and additional ones later (can mix both as well but read 1 topic at a time). My suggestion is to read and practice topic by topic for continuity and flow of understanding. Focus on core DSA topics 90% of the time, and 10% for advanced DSA for which mainly theory and some exercise problems are enough.
Estimated time per day: ~4–5 hours (cover 2 or more topics per day)
Intermediate Stage
Once you have the minimum theoretical knowledge and basic understanding of core DSA concepts through theory and some textbook exercises (2 weeks of reading), it is time to move to practice. No amount of theory will make up for lack of practice so definitely focus a LOT on practicing!
Note: Just because we start practicing does not mean we stop reading (it is unlikely everything is fully grasped in 2 weeks anyway). So at this stage we will do both reading + practice by splitting the total time.
Main websites/sources to practice
Suggested routine
At this stage — depending on how well you have the theory understanding, vary amount of time you spend on reading vs practice. Suggested is 40% reading time and 60% practice time in the 1st week, and increase practice as you understand the topics better. Again, it is suggested to do topic by topic for 1–2 weeks, and after that mix up topics while practicing and try to solve questions without knowing which topic it is for (at random).
In the first week you can do easy questions for confidence, but from 2nd week onwards you should focus mostly on medium questions and a few hard questions (say 80–20 ratio). For practice questions, solutions should be available so read them & watch videos when you get stuck (after trying for at least 1 hour) — but don’t make it a habit to see answers, try your hardest to solve questions first. Then try to solve similar problems also.
Also when preparing for specific companies, it is a useful idea to filter and prioritize that company tagged questions on above websites.
Estimated time per day: ~4–5 hours (cover 2 or more topics per day — reading & practice)
Advanced Stage
This is a somewhat unfamiliar area for me as well, but I’ve explored a bit here and collected info from some awesome DSA experts I know. Naturally, feel free to correct anything wrong here.
At this stage you should largely be confident in theory (at least of core DSA concepts) and have a decent amount of practice (say 3–4 weeks) in doing many medium and some hard questions.
Now to simulate tough and random questions in time pressure and to have optimal space/time complexity constraints, coding contests are the best way as far as I know.
Personally, I was not too interested in contests but still have done a decent number of them to get used to time pressure and solving random questions fast. But if you’re passionate about Competitive Programming (CP) / Competitive Coding (CC) by all means keep going and try to achieve a good rating, it is most definitely useful for hard advanced interviews (like Google). It is also useful for your resume to have CC ratings, so definitely consider doing it. :)
Websites for coding contests
Suggested routine
At this stage — you should have a lot of theory and good practice as mentioned above. So, we will again combine reading (10%)+ practice (50%)+ contests (40%) in the total time we have per day. This is just a rough estimate, some times for long contests you may need to spend more continuous time on only the contest in a day — in which case you can skip reading/practice.
It is suggested to do at least 3–4 contests per week based on their availability. CodeChef/CodeForces are more recommended as they are standard and their ratings are more recognized. To improve after each contest, it is suggested to read editorials and explore further for solutions & related topics of questions we couldn’t solve during the contest.
Continue with reading + practice + contests for 2–3 weeks at least for visible results.
Estimated time per day: ~4–5 hours (cover 2 or more topics per day + 1 contest)
Summary of timeline
Assume you start today at beginner, you should target interviews 2 months from now (work backwards from that based on your placements).
- Beginner stage: Day 1- Day 14
- Intermediate stage: Day 14-Day 30
- Advanced stage: Day 30-Day 60* (tentative, it definitely takes much longer to grow in advanced stage but this is a minimum required time)
As mentioned advanced stage takes longer (say 4–6 months) to really grasp things, and crack hard interviews like Google. However, with above schedule followed punctually in 2 months you should be ready for most medium level interviews (including Amazon).
Bonus
Core CS
Since you’ve anyway come to this article, let me remind you of the importance of Computer Science (CS) fundamentals i.e. theory of core subjects which will likely be asked in most companies’ interviews.
Use below sources depending on time you have
- If you have more time — College textbooks
- If you have less time or to revise — GeeksForGeeks topic summaries & last minute notes. Eg: Operating Systems summary and last minute notes
- To practice after reading — InterviewBit important interview questions. Eg: Operating Systems interview questions
The core subjects and their most important topics are
- Operating Systems (OS) : Multi-threading/concurrency, scheduling algorithms, memory management, deadlocks, bootstrap, paging & segmentation, IPC, zombie process, starvation & aging, Semaphore, Kernel & types, spooling.
- Computer Networks : Network types, IP and packets, VPN, CDN, Network topology, OSI and TCP/IP reference model, HTTP/HTTPS/SMTP, TCP vs UDP, Router vs Gateway, Types of casting, Steps in opening URL, Hubs & Switches, MAC & NIC, Firewall, Proxies.
- Database Management Systems (DBMS) : RDBMS, DBMS advantages, DBMS languages, ACID properties, Data warehousing, data abstraction, E-R model, Types of relationships, DBMS commands, Normalization & denormalization, Normalization forms & conversion, Types of keys, 2-tier & 3-tier architecture.
- Object Oriented Programming System (OOPS) : OOPS definition, need and other paradigms, OOPS features, Classes/objects, Encapsulation, Polymorphism (Compile time vs runtime), Inheritance types, examples & limitations, Constructor & types, Destructor, Class vs structure, Subclass & superclass, Interface vs abstract class, Access specifier, Exception handling, Garbage collection.
Leadership principles
For companies like Amazon you also need to prepare for Leadership Principles (see this). For each Leadership principle, prepare a scenario from your experience at companies (preferred) or college projects (if fresher) in STAR (Situation, Action, Task, Result) format to be answered during interviews. Keep metrics handy for Results achieved. See more in my resume article here.
Suggested routine
Spend at least 1 hour per day on CS fundamentals over 1–2 months along with DSA preparation. Leadership principles can be prepared with dedicated 1–2 days with all scenarios, just revise them 1 day before interview.
The interview mindset
A few final words before you jump into interviews. You must have certainly put in a lot of effort and practice into DSA and core CS subjects, and have a lot of things on your mind so a good mindset is important for performance.
Before the interview
It is suggested to relax a bit 1 day before actual interview to keep a calm mindset. You can read some quick notes on any DSA/CS topics for last minute revision but don’t try to keep solving questions till the end.
During the interview
DSA
Tip: DO NOT give up to the extent possible. It sounds cliché, but hanging in there despite facing a tough unknown question and even barely solving it is good as compared to completely giving up in my experience. There may be contradictory opinions on this, but this is my take — if I compare it to a real project we can not have teammates simply giving up and passing it on.
- Ask questions about the question, not to puzzle or impress the interviewer but to ensure you have all the information you need to solve it.
- Discuss any assumptions you have made with the interviewer.
- If you know the most efficient approach, directly explain it and there is no need to waste time on brute force in this case. If not, start with brute force and work your way towards optimizing it.
- Code with clarity in modular and easy to follow fashion. Do a dry-run of your code before you can say it works.
- Be clear on time and space complexity of your solution, and after you finish your optimal approach think again if anything more efficient might be possible. Compare with alternative approaches which would be slower/faster.
Manage your time overall per question.
- Medium level : ~20min (max 30min)
- Hard level : ~30min (max 40min)
Core CS Subjects
- Usually there should be theoretical questions on OS, Networks and DBMS. For these, try to give the specific objective answer with technical keywords where applicable. If not, explain the answer in simple terms.
- For exercise problems (like based on scheduling algorithms or caching), work through the solution like you would dry-run in coding DSA solutions.
Leadership principles
- Identify which leadership principle is being discussed based on the interviewer’s probe question.
- Recollect your experience at work (preferred) or college project closest to the scenario in a STAR format. Provide metrics like $ amount saved / % effort reduced / % latency improved etc as applicable.
That’s it, good luck to the readers and hope you crack all the companies you want to! And remember, each rejection only makes you stronger. Keep working hard till you are satisfied. :)
