Software Developer Interview Preparation
### Yes, practicing at least one question a day can help you crack any SDE interview.
𝟭. 𝗙𝗼𝗰𝘂𝘀 𝗼𝗻 𝗗𝗲𝗽𝘁𝗵 𝗼𝘃𝗲𝗿 𝗕𝗿𝗲𝗮𝗱𝘁𝗵:
- Don't solve 500 coding problems aimlessly. Master around 100 core problems deeply instead: https://lnkd.in/dmukJy93
- 40 Problems on Array, Strings, LinkedList, Stack & Queue, Binary Search, Trees, Graph, Sorting and Searching: https://lnkd.in/djnaPkeD
- 40 Problems on Dynamic Programming (DP), Backtracking, Hashing, Heap, Tries, and Greedy Algorithms: https://lnkd.in/dF3h-Khk
- 40 most asked DSA interview questions: https://lnkd.in/d5yMRNuC
𝟮. 𝗖𝗿𝗲𝗮𝘁𝗲 𝗮 𝗹𝗶𝘀𝘁 𝗼𝗳 𝗸𝗲𝘆 𝗾𝘂𝗲𝘀𝘁𝗶𝗼𝗻𝘀:
- Use resources like "Strivers A2Z DSA Sheet" by Raj Vikramaditya to curate around 100 core problems.
- https://lnkd.in/dQMGy9z
𝟯. 𝗠𝗮𝘀𝘁𝗲𝗿 𝗲𝗮𝗰𝗵 𝗱𝗮𝘁𝗮 𝘀𝘁𝗿𝘂𝗰𝘁𝘂𝗿𝗲:
- Understand and implement them by hand. Know how they work internally to ace interview questions.
- Basic to Advance DSA topics: https://lnkd.in/d4ws9xfr
𝟰. 𝗣𝗿𝗮𝗰𝘁𝗶𝗰𝗲 𝘄𝗶𝘁𝗵 𝗦𝗽𝗮𝗰𝗲𝗱 𝗥𝗲𝗽𝗲𝘁𝗶𝘁𝗶𝗼𝗻:
- Revisit problems after 3 days, a week, and 15 days. Break down solutions instead of rote memorization.
- 3:7:15 Rule for DSA: https://lnkd.in/dW6a8wcg
𝟱. 𝗜𝗱𝗲𝗻𝘁𝗶𝗳𝘆 𝗿𝗲𝘂𝘀𝗮𝗯𝗹𝗲 𝘁𝗲𝗰𝗵𝗻𝗶𝗾𝘂𝗲𝘀 𝗮𝗻𝗱 𝗰𝗼𝗱𝗲 𝗯𝗹𝗼𝗰𝗸𝘀:
- Isolate common patterns like Binary Search or DFS for focused practice.
- 14 problem-solving patterns: https://lnkd.in/daysVFSz
https://lnkd.in/dqNwG-AT
- Tips to solve any DSA question by understanding patterns: https://lnkd.in/d9GVyfBY
𝟲. 𝗘𝘅𝗽𝗮𝗻𝗱 𝗶𝗻𝘁𝗼 𝗕𝗿𝗲𝗮𝗱𝘁𝗵:
- Once you've mastered core problems and techniques, tackle a wider range of questions. Keep it realistic and relevant to interview scenarios.
Here are a few steps you can follow that will help you crack this interview round:
1. Understand the requirements and write down important keywords.
2. Ask for edge cases in the input.
3. Explain the brute force solution in a minute.
4. Explain the optimal solution and discuss its asymptotic complexity quickly.
5. Write code in the language you're comfortable with. Dry run the code line by line to find mistakes.
6. Review the solution's asymptotic complexity.
7. Ask if tests or concurrent cases are necessary.
8. Ask for the interviewer's feedback.
Consistency is the key
Here are some of the best platforms to practice DSA problems
1. HackerRank
2. LeetCode
3. GeeksforGeeks
4. takeUforward Youtube Channel: https://lnkd.in/d-UNHu6B
===================================================================
### Here are 40 most asked DSA questions to ace your next interview -
𝗔𝗿𝗿𝗮𝘆𝘀 𝗮𝗻𝗱 𝗦𝘁𝗿𝗶𝗻𝗴𝘀:
1. Find the maximum sum subarray.
2. Find all substrings that are palindromes.
3. Implement the "two sum" problem.
4. Implement Kadane's algorithm for maximum subarray sum.
5. Find the missing number in an array of integers.
6. Merge two sorted arrays into one sorted array.
7. Check if a string is a palindrome.
8. Find the first non-repeating character in a string.
9. Write a program to remove duplicates from a sorted array.
𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁𝘀:
10. Reverse a linked list.
11. Detect a cycle in a linked list.
12. Find the middle of a linked list.
13. Merge two sorted linked lists.
14. Implement a stack using linked list.
15. Find the intersection point of two linked lists.
𝗦𝘁𝗮𝗰𝗸𝘀 𝗮𝗻𝗱 𝗤𝘂𝗲𝘂𝗲𝘀:
16. Implement a stack using an array.
17. Implement a stack that supports push, pop, top, and retrieving the minimum element.
18. Implement a circular queue.
19. Design a max stack that supports push, pop, top, retrieve maximum element.
20. Design a queue using stacks.
𝗧𝗿𝗲𝗲𝘀 𝗮𝗻𝗱 𝗕𝗶𝗻𝗮𝗿𝘆 𝗦𝗲𝗮𝗿𝗰𝗵 𝗧𝗿𝗲𝗲𝘀:
21. Find the height of a binary tree.
22. Find the lowest common ancestor of two nodes in a binary tree.
23. Validate if a binary tree is a valid binary search tree.
24. Serialize and deserialize a binary tree.
25. Implement an inorder traversal of a binary tree.
26. Find the diameter of a binary tree.
27. Convert a binary tree to its mirror tree.
𝗚𝗿𝗮𝗽𝗵𝘀:
28. Implement depth-first search (DFS).
29. Implement breadth-first search (BFS).
30. Find the shortest path between two nodes in an unweighted graph.
31. Detect a cycle in an undirected graph using DFS.
32. Check if a graph is bipartite.
33. Find the number of connected components in an undirected graph.
34. Find bridges in a graph.
𝗦𝗼𝗿𝘁𝗶𝗻𝗴 𝗮𝗻𝗱 𝗦𝗲𝗮𝗿𝗰𝗵𝗶𝗻𝗴:
35. Implement (bubble, insertion, selection, merge) sort.
36. Implement quicksort.
37. Implement binary search.
38. Implement interpolation search.
39. Find the kth smallest element in an array.
40. Given an array of integers, count the number of inversions it has. An inversion occurs when two elements in the array are out of order.
-> But wait, there's more! Next week, on Dynamic Programming (DP), Backtracking, Hashing, Heap, Tries, and Greedy Algorithms.
-> Get ready for 40 questions that will test your problem solving skills and help you master DSA
====================================================================
### 40 most asked DSA questions to clear your next interview
1. Reverse a linked list.
2. Find the middle element of a linked list.
3. Implement a stack using arrays/linked list.
4. Implement a queue using arrays/linked list.
5. Find the factorial of a number using recursion.
6. Implement binary search in an array.
7. Find the largest/smallest element in an array.
8. Implement merge sort.
9. Implement quick sort.
10. Detect a cycle in a linked list.
11. Find the intersection point of two linked lists.
12. Check if a binary tree is a binary search tree (BST).
13. Print all leaf nodes of a binary tree.
14. Reverse a binary tree.
15. Find the height of a binary tree.
16. Implement depth-first search (DFS) on a graph.
17. Implement breadth-first search (BFS) on a graph.
18. Check if a graph is connected.
19. Implement Dijkstra's algorithm for shortest path.
20. Implement Prim's algorithm for minimum spanning tree.
21. Implement Kruskal's algorithm for minimum spanning tree.
22. Find the longest common subsequence of two strings.
23. Find the longest increasing subsequence of an array.
24. Implement the Knuth–Morris–Pratt (KMP) algorithm for string matching.
25. Implement the Rabin-Karp algorithm for string matching.
26. Check if a string is a palindrome.
27. Check if two strings are anagrams of each other.
28. Find the next greater element in an array.
29. Find the kth smallest/largest element in an array.
30. Find the median of two sorted arrays.
31. Implement a trie (prefix tree).
32. Find all subsets of a set.
33. Find all permutations of a string.
34. Implement the Josephus Problem.
35. Implement an LRU (Least Recently Used) Cache.
36. Find the longest palindrome substring in a string.
37. Implement a priority queue.
38. Implement a hashmap (dictionary).
39. Count the number of inversions in an array.
40. Find the shortest path in a maze.
====================================================================
### How much DSA is enough to crack your dream job?
I get this question many times, so I'm sharing a roadmap that covers all the aspects:
➤ 𝗙𝗼𝘂𝗻𝗱𝗮𝘁𝗶𝗼𝗻𝗮𝗹 𝗞𝗻𝗼𝘄𝗹𝗲𝗱𝗴𝗲
𝗕𝗮𝘀𝗶𝗰 𝗗𝗮𝘁𝗮 𝗦𝘁𝗿𝘂𝗰𝘁𝘂𝗿𝗲𝘀:
- Arrays
- Linked Lists
- Stacks
- Queues
- Hash Tables/Hash Maps
- Strings
𝗙𝘂𝗻𝗱𝗮𝗺𝗲𝗻𝘁𝗮𝗹 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀:
- Sorting (Bubble Sort, Quick Sort, Merge Sort, etc.)
- Searching (Binary Search, Linear Search)
- Basic String Manipulations (Substrings, Palindromes, Anagrams)
➤ 𝗜𝗻𝘁𝗲𝗿𝗺𝗲𝗱𝗶𝗮𝘁𝗲 𝗞𝗻𝗼𝘄𝗹𝗲𝗱𝗴𝗲
𝗔𝗱𝘃𝗮𝗻𝗰𝗲𝗱 𝗗𝗮𝘁𝗮 𝗦𝘁𝗿𝘂𝗰𝘁𝘂𝗿𝗲𝘀:
- Trees (Binary Trees, Binary Search Trees, AVL Trees, Segment Trees)
- Heaps
- Graphs (Representation, Traversal techniques - BFS, DFS)
- Tries
𝗔𝗱𝘃𝗮𝗻𝗰𝗲𝗱 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀:
- Dynamic Programming
- Greedy Algorithms
- Backtracking
- Divide and Conquer
- Bit Manipulation
➤ 𝗔𝗱𝘃𝗮𝗻𝗰𝗲𝗱 𝗧𝗼𝗽𝗶𝗰𝘀
𝗖𝗼𝗺𝗽𝗹𝗲𝘅 𝗗𝗮𝘁𝗮 𝗦𝘁𝗿𝘂𝗰𝘁𝘂𝗿𝗲𝘀:
- Red-Black Trees
- B-Trees
- Fenwick Trees (Binary Indexed Trees)
- Suffix Trees/Arrays
𝗖𝗼𝗺𝗽𝗹𝗲𝘅 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀:
- Advanced Graph Algorithms (Dijkstra’s, Floyd-Warshall, A*)
- Network Flow (Ford-Fulkerson)
- Computational Geometry
- String Matching Algorithms (KMP, Rabin-Karp)
➤ 𝗣𝗿𝗼𝗯𝗹𝗲𝗺-𝗦𝗼𝗹𝘃𝗶𝗻𝗴 𝗦𝗸𝗶𝗹𝗹𝘀
𝗣𝗿𝗮𝗰𝘁𝗶𝗰𝗲:
- Solve problems on LeetCode and HackerRank.
- Aim to solve problems of varying difficulty (Easy, Medium, Hard).
𝗨𝗻𝗱𝗲𝗿𝘀𝘁𝗮𝗻𝗱𝗶𝗻𝗴:
- Understand the underlying principles and logic.
- Be able to explain your thought process and solutions clearly.
𝗧𝗶𝗺𝗲 𝗮𝗻𝗱 𝗦𝗽𝗮𝗰𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆:
- Analyze and optimize the time and space complexity of your solutions.
- Be comfortable with Big O notation and its implications.
➤ 𝗖𝗼𝗺𝗽𝗮𝗻𝘆-𝗦𝗽𝗲𝗰𝗶𝗳𝗶𝗰 𝗙𝗼𝗰𝘂𝘀
𝗕𝗶𝗴 𝗧𝗲𝗰𝗵 𝗖𝗼𝗺𝗽𝗮𝗻𝗶𝗲𝘀 (FAANG - Facebook, Amazon, Apple, Netflix, Google):
- Extensive and in-depth understanding of DSA.
- Focus on medium to hard problems on LeetCode.
- Prepare for system design interviews if applying for senior positions.
𝗠𝗶𝗱-𝗦𝗶𝘇𝗲𝗱 𝗧𝗲𝗰𝗵 𝗖𝗼𝗺𝗽𝗮𝗻𝗶𝗲𝘀:
- Good grasp of fundamental and intermediate DSA.
- Practice problems on LeetCode and HackerRank (mainly easy to medium).
- Be ready for coding interviews and practical coding tests.
𝗦𝘁𝗮𝗿𝘁𝘂𝗽𝘀 𝗮𝗻𝗱 𝗦𝗺𝗮𝗹𝗹 𝗖𝗼𝗺𝗽𝗮𝗻𝗶𝗲𝘀:
- Solid understanding of basic and some intermediate DSA.
- Focus on practical problem-solving skills and coding abilities.
- Emphasize on your ability to learn and adapt quickly.
This roadmap covers most of the essential topics in data structures and algorithms.
➤ 𝗪𝗵𝘆 𝘀𝘁𝘂𝗱𝘆 𝗗𝗦𝗔?
Understanding DSA is crucial for:
- Writing optimized, efficient code.
- Systematically solving complex problems.
- Acing technical interviews to secure your dream job.
- Gaining deep insights into how technologies work.
================================================================
### 3-7-15 rule: DSA is really tough, but you don't seem to struggle?
I get this question a lot.
Here are some of the hardest questions you might face in an interview.
Practice these using the 𝟯-𝟳-𝟭𝟱 𝗿𝘂𝗹𝗲:
First solve the question, then note down the answer. After three days, try to remember the question from the answer and solve it again.
Repeat the same after 7 and 15 days.
This way, you'll solve the same question 4 times in 15 days, making it easier if you encounter it again.
𝟭. 𝗔𝗿𝗿𝗮𝘆𝘀 & 𝗦𝘁𝗿𝗶𝗻𝗴𝘀
- Minimum Window Substring
- Trapping Rain Water
- Largest Rectangle in Histogram
𝟮. 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁𝘀
- Merge k Sorted Lists
- Reverse Nodes in k-Group
- LFU Cache
𝟯. 𝗧𝗿𝗲𝗲𝘀
- Binary Tree Maximum Path Sum
- Serialize and Deserialize Binary Tree
- Vertical Order Traversal of a Binary Tree
𝟰. 𝗗𝘆𝗻𝗮𝗺𝗶𝗰 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴
- Edit Distance
- Burst Balloons
- Shortest Common Supersequence
𝟱. 𝗚𝗿𝗮𝗽𝗵𝘀
- Alien Dictionary
- Minimum Cost to Make at Least One Valid Path in a Grid
- Swim in Rising Water
𝟲. 𝗥𝗲𝗰𝘂𝗿𝘀𝗶𝗼𝗻 & 𝗕𝗮𝗰𝗸𝘁𝗿𝗮𝗰𝗸𝗶𝗻𝗴
- N-Queens II
- Sudoku Solver
- Word Search II
𝟳. 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 & 𝗦𝗲𝗮𝗿𝗰𝗵𝗶𝗻𝗴
- Count of Smaller Numbers After Self
- Median of Two Sorted Arrays
- Split Array Largest Sum
𝟴. 𝗗𝗲𝘀𝗶𝗴𝗻
- Design Search Autocomplete System
- Design In-Memory File System
- Design Excel Sum Formula
𝟵. 𝗚𝗿𝗲𝗲𝗱𝘆
- Minimum Number of Arrows to Burst Balloons
- Candy
- Patching Array
𝟭𝟬. 𝗕𝗶𝘁 𝗠𝗮𝗻𝗶𝗽𝘂𝗹𝗮𝘁𝗶𝗼𝗻
- Maximum Product of Word Lengths
- Smallest Sufficient Team
- Minimum Cost to Connect Two Groups of Points
𝟭𝟭. 𝗧𝘄𝗼 𝗣𝗼𝗶𝗻𝘁𝗲𝗿𝘀
- Minimum Window Subsequence
- Minimum Operations to Make a Subsequence
- Minimum Adjacent Swaps to Reach the Kth Smallest Number
𝟭𝟮. 𝗛𝗲𝗮𝗽
- Minimum Number of Refueling Stops
- Sliding Window Median
- Minimum Number of K Consecutive Bit Flips
16 𝗜𝗺𝗽𝗼𝗿𝘁𝗮𝗻𝘁 𝗮𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 𝘁𝗵𝗮𝘁 𝘆𝗼𝘂 𝘀𝗵𝗼𝘂𝗹𝗱 𝗸𝗻𝗼𝘄 𝘁𝗼 𝗯𝘂𝗶𝗹𝗱 𝗮 𝘀𝘁𝗿𝗼𝗻𝗴 𝗯𝗮𝘀𝗲:
- https://lnkd.in/dfjm8ked
𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 𝗜𝗺𝗽𝗼𝗿𝘁𝗮𝗻𝘁 𝗣𝗮𝘁𝘁𝗲𝗿𝗻𝘀:
- https://lnkd.in/d3rRHTfE
𝗧𝗶𝗽𝘀 𝘁𝗼 𝘀𝗼𝗹𝘃𝗲 𝗮𝗻𝘆 𝗗𝗦𝗔 𝗾𝘂𝗲𝘀𝘁𝗶𝗼𝗻 𝗯𝘆 𝘂𝗻𝗱𝗲𝗿𝘀𝘁𝗮𝗻𝗱𝗶𝗻𝗴 𝗽𝗮𝘁𝘁𝗲𝗿𝗻𝘀:
- https://lnkd.in/dy5zSXgv
By following the 3-7-15 rule and practicing these tough questions regularly, you'll build strong problem-solving skills and be well-prepared for your interviews.
==================================================================
### 14 Problem Solving Patterns⚡ (DSA was extremely HARD Until I found these)
1. Two Pointer Problems:
https://lnkd.in/dK_fB-Eg
2. Backtracking Pattern:
https://lnkd.in/dDGsdfps
3. Dynamic Programming Patterns:
https://lnkd.in/dX7a4cau
4. Dynamic Programming Patterns 2:
https://lnkd.in/db2tAp27
5. Powerful Ultimate Binary Search Template:
https://lnkd.in/dxk7kdeb
6. A general approach to backtracking questions:
https://lnkd.in/drsHxsZh
7. Binary Tree Traversal & Views:
https://lnkd.in/dxGcKx65
8. Graph For Beginners [Problems | Pattern | Sample Solutions]:
https://lnkd.in/dkpyiB3R
9. A comprehensive guide and template for monotonic stack based problems:
https://lnkd.in/dtmFMzDJ
10. All Types of Patterns for Bits Manipulations and How to use it:
https://lnkd.in/d-rfVNx2
11. Collections of Important String questions Pattern:
https://lnkd.in/dCy_j-vw
12. Leetcode Pattern 1 | BFS + DFS == 25% of the problems:
https://lnkd.in/dtaEpzrC
13. Template that can solve most 'substring' problems:
https://lnkd.in/dEbVbBu4
14. C++ Maximum Sliding Window Cheat sheet Template:
https://lnkd.in/dPiMzzpA
==============================================================