Coding Round Preparation for Engineer

Pattern for Programming

• Sliding Window
  
  
• Two Pointer link link2

       Some limitations of using 2-pointers:

1. Not Suitable for Dynamic Arrays: When working with dynamic arrays, the Two-Pointer technique may not be as straightforward, especially if the size of the array can change dynamically during the algorithm execution
2. Not Suitable for All Arrays: For problems involving arrays with irregular patterns or unsorted elements, using the Two-Pointer technique might not be the optimal choice. Sorting the array may be necessary first, which could have its time complexity
3. Limited Applicability: The Two-Pointer technique is most effective when the problem involves a sorted array or a linked list. Not all problems can be efficiently solved using this approach

• Fast And Slow Pointer 
•  Subset problem
• Top k element link

Any problem that asks us to find the top/smallest/frequent ‘K’ elements among a given set falls under this pattern.

The best data structure that comes to mind to keep track of ‘K’ elements is Heap. This pattern will make use of the Heap to solve multiple problems dealing with ‘K’ elements at a time from a set of given elements.

• K-way merge link1
  
  
  
• Graph traversal
  
  
  
• Two Heaps
  
  
  
• BFS
  
  
  
• DFS
  
  
  
• Modified BFS
  
  
  
• In place traversal of Linked List
  
  
  
• 
  
• 
  
  
• Backtracking
  
  
  
• Dynamic Programming
  
  
  
• Cyclic sort
  
  
  
• Merge Interval
  
  
  

Time and Space Complexity Cheatsheet

https://www.bigocheatsheet.com/ 

 

Question Collection

https://leetcode.com/studyplan/leetcode-75/

https://leetcode.com/problem-list/oizxjoit/

Solution: https://takeuforward.org/interviews/blind-75-leetcode-problems-detailed-video-solutions

https://github.com/vikasmishra5599/leetcode-75-solutions-java

Type of Data Structure

 1. Linear Data Structure

• Array
• Matrix
• List
• Linkedlist
    Single LL
     Double LL
     Circular LL
• Stack 
• Queue

Alogrithm :

•  Recursion
•  Backtracking
•  Sliding Window
•  Greedy Algo
• Branch and Bound Algo

2. Non Linear Data Structure

•   Tree
•   Graph

   Algorithm:

• BFS
• DFS
• Dijkstra Algo
• Floyd Warshal Algo
• Prims Algo
• Kruskal Algo
• Topological Sorting
• Bellman Ford
• Normal DSU
• DSU by Rank
• KMP's Algo
• Dials Algo
• Top-K Algo

Sorting and Searching Algorithm

• Search Algo link
• Sorting Algo link

Question Collection

• Pattern Question collection Grokking-the-Coding-Interview-Patterns 
• Patternwise solution Several-Coding-Patterns
• longest common subsequence
• longest common substring
• longst common suffix
• lonngest common prefix
• Longest Common Prefix using Sorting
• Longest Common Prefix using Word by Word Matching
• Deadlock of 2 threads
• 3 thread printing in sequence
• Minimum cost path in graph

String Question

1. How do you reverse a given string in place? (solution)
2. How do you print duplicate characters from a string? (solution)
3. How do you check if two strings are anagrams of each other? (solution)
4. How do you find all the permutations of a string? (solution)
5. How can a given string be reversed using recursion? (solution)
6. How do you check if a string contains only digits? (solution)
7. How do you find duplicate characters in a given string? (solution)
8. How do you count a number of vowels and consonants in a given string? (solution)
9. How do you count the occurrence of a given character in a string? (solution)
10. How do you print the first non-repeated character from a string? (solution)
11. How do you convert a given String into int like the atoi()? (solution)
12. How do you reverse words in a given sentence without using any library method? (solution)
13. How do you check if two strings are a rotation of each other? (solution)
14. How do you check if a given string is a palindrome? (solution)
15. How do you find the length of the longest substring without repeating characters? (solution)
16. Given string str, How do you find the longest palindromic substring in str? (solution)
17. How to convert a byte array to String? (solution)
18. how to remove the duplicate character from String? (solution)
19. How to find the maximum occurring character in given String? (solution)
20. How do you remove a given character from String? (solution)
21. Given an array of strings, find the most frequent word in a given array, I mean, the string that appears the most in the array. In the case of a tie, ​the string that is the smallest (lexicographically) ​is printed. (solution)

https://www.ccbp.in/blog/articles/java-8-coding-interview-questions-and-answers

Until I found these 14 Problem Solving Patterns

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

By mastering these 22 DSA patterns

1. Fast and Slow Pointer
- Cycle detection method
- O(1) space efficiency
- Linked list problems

2. Merge Intervals
- Sort and merge
- O(n log n) complexity
- Overlapping interval handling

3. Sliding Window
- Fixed/variable window
- O(n) time optimization
- Subarray/substring problems

4. Islands (Matrix Traversal)
- DFS/BFS traversal
- Connected component detection
- 2D grid problems

5. Two Pointers
- Dual pointer strategy
- Linear time complexity
- Array/list problems

6. Cyclic Sort
- Sorting in cycles
- O(n) time complexity
- Constant space usage

7. In-place Reversal of Linked List
- Reverse without extra space
- O(n) time efficiency
- Pointer manipulation technique

8. Breadth First Search
- Level-by-level traversal
- Uses queue structure
- Shortest path problems

9. Depth First Search
- Recursive/backtracking approach
- Uses stack (or recursion)
- Tree/graph traversal

10. Two Heaps
- Max and min heaps
- Median tracking efficiently
- O(log n) insertions

11. Subsets
- Generate all subsets
- Recursive or iterative
- Backtracking or bitmasking

12. Modified Binary Search
- Search in variations
- O(log n) time
- Rotated/specialized arrays

13. Bitwise XOR
- Toggle bits operation
- O(1) space complexity
- Efficient for pairing

14. Top 'K' elements
- Use heap/quickselect
- O(n log k) time
- Efficient selection problem

15. K-way Merge
- Merge sorted lists
- Min-heap based approach
- O(n log k) complexity

16. 0/1 Knapsack (Dynamic Programming)
- Choose or skip items
- O(n * W) complexity
- Maximize value selection

17. Unbounded Knapsack (Dynamic Programming)
- Unlimited item choices
- O(n * W) complexity
- Multiple item selection

18. Topological Sort (Graphs)
- Directed acyclic graph
- Order dependency resolution
- Uses DFS or BFS

19. Monotonic Stack
- Maintain increasing/decreasing stack
- Optimized for range queries
- O(n) time complexity

20. Backtracking
- Recursive decision-making
- Explore all possibilities
- Pruning with constraints

21. Union Find
- Track and merge connected components
- Used for disjoint sets
- Great for network connectivity

22. Greedy Algorithm
- Make locally optimal choices
- Efficient for problems with optimal substructure
- Covers tasks like activity selection, minimum coins