Basic Problems (1–20)

1. Subarray Sum and Product Problems

1. Subarray with Given Sum
Find a contiguous subarray that sums to a target value.
o Example:
Input: arr = [1, 2, 3, 7, 5], target = 12
Output: [2, 4] (Subarray is [3, 7, 2])
2. Maximum Subarray Sum (Kadane's Algorithm)
Find the maximum sum of any contiguous subarray.
o Example:
Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (Subarray is [4, -1, 2, 1])
3. Count Subarrays with Sum Equal to Target
Count all contiguous subarrays that sum to a target.
o Example:
Input: arr = [1, 1, 1], target = 2
Output: 2
4. Find All Subarrays with Zero Sum
Identify all contiguous subarrays in an array that sum to zero.
o Example:
Input: arr = [3, 4, -7, 1, 2, -6, 1, -4]
Output: [(0, 2), (3, 5), (6, 7)]
5. Longest Subarray with Equal 0s and 1s
Find the longest contiguous subarray with equal numbers of 0s and 1s in a binary array.
o Example:
Input: arr = [0, 1, 0, 1, 0, 1, 1]
Output: 6
6. Subarray with Maximum Product
Find the maximum product of any contiguous subarray.
o Example:
Input: arr = [2, 3, -2, 4]
Output: 6 (Subarray is [2, 3])

2. Rearrangement and Rotation Problems

7. Rearrange Array Alternately
Rearrange an array to alternate between the largest and smallest values.
o Example:
Input: arr = [1, 2, 3, 4, 5, 6]
Output: [6, 1, 5, 2, 4, 3]
8. Cyclically Rotate an Array
Rotate an array k times to the right.
o Example:
Input: arr = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
9. Reverse an Array
Reverse an array in-place.
o Example:
Input: arr = [1, 2, 3, 4]
Output: [4, 3, 2, 1]
10. Move All Zeros to the End
Move all zeroes to the end of the array while maintaining the order of other elements.
o Example:
Input: arr = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

3. Missing, Duplicate, and Special Elements

11. Find Missing Number in a Subarray
Identify the missing number from a sequence of integers.
o Example:
Input: arr = [1, 2, 4, 5, 6]
Output: 3
12. Find Duplicate in an Array
Detect the duplicate element in an array.
 o Example:
Input: arr = [1, 3, 4, 2, 2]
Output: 2
13. Find the Majority Element
Find an element that appears more than n/2 times in an array.
o Example:
Input: arr = [3, 3, 4, 2, 3]
Output: 3
14. Find the Kth Largest Element in an Array
Find the kth largest element in an unsorted array.
o Example:
Input: arr = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
15. Find the Second Largest Element
Find the second largest element in an array.
o Example:
Input: arr = [1, 2, 3, 4]
Output: 3

4. Sorting and Searching Problems

16. Sort an Array of 0s, 1s, and 2s
Sort an array containing only 0, 1, and 2 without using a sorting algorithm.
o Example:
Input: arr = [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
17. Find the Minimum Element in a Rotated Sorted Array
Find the smallest element in a rotated sorted array.
o Example:
Input: arr = [4, 5, 6, 7, 0, 1, 2]
Output: 0

5. Intersection, Union, and Pair Problems

18. Find the Intersection of Two Arrays
Find common elements between two arrays.
o Example:
Input: arr1 = [1, 2, 2, 1], arr2 = [2, 2]
Output: [2]
19. Find the Union of Two Arrays
Combine two arrays into one without duplicates.
o Example:
Input: arr1 = [1, 2, 3], arr2 = [2, 3, 4]
Output: [1, 2, 3, 4]
20. Check for a Pair with Given Sum
Check if there exists a pair of elements with a given sum.
o Example:
Input: arr = [10, 15, 3, 7], target = 17
Output: True

INTERMEDIATE
Subarray/Subsequence Problems
These problems focus on properties or operations involving contiguous subarrays or subsequences.
21. Longest Increasing Subarray
Description: Find the length of the longest contiguous subarray where each element is greater than the previous one.
Example:
Input: arr = [1, 2, 2, 4, 5]
Output: 3 (Subarray: [2, 4, 5])
Explanation: Subarrays [1, 2] and [4, 5] are increasing, but [2, 4, 5] is the longest.

22. Smallest Subarray with Sum ≥ Target

Description: Find the smallest contiguous subarray whose sum is greater than or equal to a target.
Example:
Input: arr = [2, 3, 1, 2, 4, 3], target = 7
Output: 2 (Subarray: [4, 3])
Explanation: [4, 3] is the shortest subarray with sum ≥ 7.

27. Find the Minimum Length Subarray with Sum = Target

Description: Find the smallest contiguous subarray that sums to exactly the given target.
Example:
Input: arr = [1, 2, 3, 4, 5], target = 9
Output: 2 (Subarray: [4, 5])
Explanation: [4, 5] sums to 9, and it's the smallest such subarray.

23. Count Subarrays with Product Less Than K

Description: Count all contiguous subarrays where the product of elements is less than a given target.
Example:
Input: arr = [10, 5, 2, 6], k = 100
Output: 8
Explanation: Subarrays: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].

42. Maximum Length of Subarray with Sum Equal to K

Description: Find the longest subarray with a sum equal to the target.
Example:
Input: arr = [1, 2, 3, 7, 5], k = 12
Output: 2 (Subarray: [7, 5])
Explanation: Only [7, 5] sums to 12.

36. Count Subarrays with Equal Number of 0s and 1s

Description: Find the number of contiguous subarrays with an equal number of 0s and 1s.
Example:
Input: arr = [0, 1, 0, 1]
Output: 4
Explanation: Subarrays: [0, 1], [1, 0], [0, 1, 0, 1], [1, 0, 1].

37. Find the Maximum Circular Subarray Sum

Description: Find the maximum sum of a subarray, considering the array as circular.
Example:
Input: arr = [1, -2, 3, -2]
Output: 3
Explanation: Max sum is 3, from subarray [3].

59. Find Subarray with Given Sum in Circular Array

Description: Identify a subarray with a given sum in a circular array.
Example:
Input: arr = [5, -3, 2, 8], target = 7
Output: [3, 0]
Explanation: Subarray [8, -3] wraps around and sums to 7.

Sliding Window and Fixed Size Problems

These problems involve finding optimal results for fixed-size or sliding-window subarrays.
25. Sliding Window Maximum
Description: Find the maximum value in every subarray of size k.
Example:
Input: arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: Max values for windows: [1,3,-1] → 3, [-1,-3,5] → 5, etc.

44. Count Distinct Elements in Every Subarray of Size K

Description: Count distinct elements in all subarrays of size k.
Example:
Input: arr = [1, 2, 1, 3, 4, 2, 3], k = 4
Output: [3, 4, 4, 3]
Explanation: First window: [1, 2, 1, 3] → 3 distinct.

49. Longest Subarray with Absolute Difference ≤ K

Description: Find the longest subarray where the difference between the max and min is ≤ k.
Example:
Input: arr = [8, 2, 4, 7], k = 4
Output: 2
Explanation: [2, 4] satisfies the condition, and it's the longest.

24. Find All Subarrays with a Given XOR

Description: Count all subarrays in which the XOR of the elements equals a given value.
Example:
Input: arr = [4, 2, 2, 6, 4], target = 6
Output: 4
Explanation: Subarrays: [4, 2], [2, 6], [4, 2, 2].

Sorting and Rearrangement

These problems involve reordering or merging elements based on certain criteria.
28. Rearrange Array by Index
Description: Rearrange the array using the given indices.
Example:
Input: arr = [10, 11, 12], indices = [1, 0, 2]
Output: [11, 10, 12]
Explanation: Reorder based on indices.

52. Rearrange an Array Such That arr[i] Becomes arr[arr[i]]

Description: Rearrange the array so that each element becomes the value at the index it points to.
Example:
Input: arr = [3, 2, 1, 0]
Output: [0, 1, 2, 3]
Explanation: Transform as per the rule.

46. Merge Two Sorted Arrays Without Extra Space

Description: Merge two sorted arrays into one, without using additional space.
Example:
Input: arr1 = [1, 3, 5], arr2 = [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Combine into one sorted array.

Partitioning Problems
Divide the array into parts based on given constraints.
31. Find the Minimum Difference Between Two Subarrays
Description: Split the array into two subarrays to minimize the difference between their sums.
Example:
Input: arr = [1, 2, 3, 4, 5]
Output: 1
Explanation: [1, 2, 3] and [4, 5] minimize the difference.

55. Array Partitioning to Minimize Sum Difference

Description: Partition an array into two parts to minimize the absolute difference between their sums.
Example:
Input: arr = [1, 6, 11, 5]
Output: 1
Explanation: [1, 11] and [6, 5] have a minimal difference.

50. Partition Array into Two Subarrays with Equal Sum

Description: Partition the array into two subarrays such that their sums are equal.
Example:
Input: arr = [1, 2, 3, 4, 5, 5]
Output: [1, 2, 3, 4] and [5, 5]
Explanation: Both have sum 10.

54. Maximize the Minimum Difference of Array Partitions

Description: Divide the array into k partitions to maximize the minimum difference between sums.
Example:
Input: arr = [1, 2, 3, 4, 5, 6], k = 2
Output: 9
Explanation: Partition [1, 2, 3] and [4, 5, 6].
HARD
______________________________________xxxxxxxxxxxxxx_________________________________________
Basic Matrix Problems (1–10)
1. Matrix Addition
o Given two matrices of the same size, write a function to add them.

2. Matrix Multiplication
o Given two matrices, write a function to multiply them. Ensure that the number of columns in the first matrix equals the number of rows in the second
matrix.
3. Matrix Transpose
o Write a function to find the transpose of a matrix.

4. Diagonal Sum
o Write a function to calculate the sum of the diagonal elements of a matrix.

5. Check for Identity Matrix

o Write a function to check if a given matrix is an identity matrix.

6. Matrix Subtraction
o Given two matrices of the same size, write a function to subtract one matrix from another.

7. Matrix Scalar Multiplication

o Multiply a matrix by a scalar (a single number). Implement the function.

8. 90 Degree Matrix Rotation (Clockwise)

o Write a function to rotate a given square matrix by 90 degrees in the clockwise direction.

9. Find the Trace of a Matrix

o Write a function to compute the trace of a matrix (sum of diagonal elements).

10. Check for Diagonal Matrix

o Write a function to check if a given matrix is a diagonal matrix.

Intermediate Matrix Problems (11–20)

11. Matrix Inversion
o Write a function to compute the inverse of a matrix. Handle edge cases like non-invertible matrices.

12. Symmetric Matrix Check

o Write a function to check if a matrix is symmetric (it is equal to its transpose).

13. Row and Column Sum

o Write a function to compute the sum of elements in each row and each column of a matrix.

14. Find Maximum Element in Matrix

o Write a function to find the maximum element in a matrix.

15. Rotate Matrix by 180 Degrees

o Write a function to rotate a matrix by 180 degrees.

16. Element-wise Matrix Multiplication (Hadamard Product)

o Implement element-wise multiplication (Hadamard product) of two matrices.

17. Rank of a Matrix

o Write a function to calculate the rank of a matrix.

18. Check if a Matrix is Sparse

o Write a function to check if a matrix is sparse (more than half of its elements are zero).

19. Upper Triangular Matrix

o Write a function to convert a matrix into its upper triangular form (all elements below the diagonal should be zero).

20. Lower Triangular Matrix

o Write a function to convert a matrix into its lower triangular form (all elements above the diagonal should be zero).

Advanced Matrix Problems (21–30)

21. Matrix Multiplication with Strassen’s Algorithm
o Implement matrix multiplication using Strassen's algorithm (a divide-and-conquer approach for faster multiplication).
 22. Find the Determinant of a Matrix
o Write a function to calculate the determinant of a matrix. Handle edge cases for small matrices (e.g., 2x2 or 3x3).

23. Find the Eigenvalues and Eigenvectors of a Matrix

o Write a function to find the eigenvalues and eigenvectors of a matrix.

24. Matrix Chain Multiplication

o Implement the Matrix Chain Multiplication algorithm using dynamic programming to find the optimal way to multiply a chain of matrices.

25. Zigzag Level Order Traversal in Matrix

o Write a function to perform a zigzag level order traversal of a matrix, similar to a binary tree.

26. Matrix Search

o Given a matrix sorted in both rows and columns, write a function to search for a target value in the matrix.

27. Spiral Traversal of Matrix

o Write a function to print the elements of a matrix in a spiral order.

28. Find Submatrix with Sum Equal to Target

o Write a function to find a submatrix in a given matrix whose sum is equal to a given target value.

29. Find the Longest Increasing Path in a Matrix

o Write a function to find the longest increasing path in a matrix, where you can only move to adjacent cells with larger values.

30. Unique Paths in a Matrix

o Given a matrix, write a function to find the number of unique paths from the top-left corner to the bottom-right corner, moving only down or right.

Expert Matrix Problems (31–40)

31. Find the Shortest Path in a Matrix
o Given a matrix with obstacles (represented by 0s and 1s), find the shortest path from the top-left to the bottom-right corner.

32. Matrix Rotation Without Extra Space

o Rotate a matrix 90 degrees clockwise without using extra space (modify the matrix in place).

33. Find the Saddle Point of a Matrix

o Write a function to find the saddle point of a matrix (an element that is the minimum in its row and maximum in its column).

34. Matrix Spiral Traversal (Anti-clockwise)

o Write a function to traverse a matrix in anti-clockwise spiral order.

35. Transpose Matrix with Diagonal Reflection

o Write a function to reflect the matrix along its diagonal (transpose).

36. Find All Pairs in Matrix with Sum Equal to Target

o Write a function to find all pairs of numbers in a matrix whose sum equals a given target value.

37. Flatten Matrix

o Write a function to flatten a matrix into a 1D array.

38. Check for Magic Square

o Write a function to check if a given matrix is a magic square (sum of each row, column, and diagonal is the same).

39. Diagonal Difference

o Given a square matrix, compute the absolute difference between the sums of its diagonals.

40. Longest Path in a Matrix

o Write a function to find the longest path in a matrix where you can move in any of the four cardinal directions (up, down, left, right) from a given cell.

Hard Matrix Problems (41–50)

41. Find the Minimum Path Sum in a Matrix
o Write a function to find the minimum path sum from the top-left to the bottom-right corner, only moving down or right.

42. Matrix Product of Two Matrices (Parallel Approach)

o Implement matrix multiplication using a parallel approach to improve performance.

43. Rotate Matrix in Layers

 o Rotate a matrix in concentric layers (rotate each layer by 90 degrees).

44. Largest Rectangle in Histogram (Matrix-based)

o Given a matrix where each row represents a histogram, find the largest rectangle that can be formed from the matrix.

45. Median of a Matrix

o Given a matrix where each row is sorted, find the median of the matrix.

46. Boolean Matrix Problem

o Given a matrix of 0s and 1s, update the matrix so that if an element is 1, all elements in its row and column are set to 1.

47. Matrix with Minimum Sum Path

o Given a matrix with costs, find the minimum path sum from top-left to bottom-right corner, where you can move down, up, left, or right.

48. Find the Kth Smallest Element in a Sorted Matrix

o Given a matrix sorted row-wise and column-wise, write a function to find the Kth smallest element in the matrix.

49. Longest Palindromic Subsequence in Matrix

o Given a matrix, find the longest palindromic subsequence within the matrix.

50. Maximum Sum Rectangle in Matrix

o Given a matrix, find the submatrix that has the maximum sum of its elements.

String
Basic Problems (1–30)

1. Reverse a String
Reverse the order of characters in a string.
Example:
 Input: "hello"
 Output: "olleh"

2. Check if String A is a Substring of String B

Determine if string A is a part of string B.
Example:
 Input: A = "world", B = "hello world"
 Output: true

3. Count Characters in a String

Count the number of characters in a string, including spaces.
Example:
 Input: "hello world"
 Output: 11

4. Check Palindrome
Check if a string reads the same forward and backward.
Example:
 Input: "radar"
 Output: true

5. Remove Duplicates in a String

Eliminate duplicate characters from a string.
Example:
 Input: "programming"
 Output: "progamin"
6. Convert Uppercase to Lowercase
Convert all uppercase letters to lowercase.
Example:
 Input: "Hello World"
 Output: "hello world"

7. Split a String into Words

Split a sentence into individual words.
Example:
 Input: "hello world"
 Output: ["hello", "world"]

8. Count Occurrences of a Character

Count how many times a character appears in a string.
Example:
 Input: "hello world", 'o'
 Output: 2

9. Compare Two Strings Lexicographically

Compare two strings and determine their order in lexicographical order.
Example:
 Input: "apple", "banana"
 Output: "apple" < "banana"

10. Find All Indices of a Character in a String

Find all positions where a specific character occurs.
Example:
 Input: "hello world", 'o'
 Output: [4, 7]

11. Find the First Unique Character in a String

Find the first character that does not repeat.
Example:
 Input: "swiss"
 Output: 'w'

12. Find the Frequency of Words in a Sentence

Count how many times each word appears.
Example:
 Input: "the quick brown fox jumps over the lazy dog"
 Output: { "the": 2, "quick": 1, "brown": 1, ... }

13. Replace Spaces in a String with %20

Replace all spaces with %20.
Example:
 Input: "hello world"
 Output: "hello%20world"
14. Check if Two Strings are Equal
Check if two strings are identical.
Example:
 Input: "hello", "hello"
 Output: true

15. Check if a String Contains Only Alphabets

Verify if the string contains only alphabetic characters.
Example:
 Input: "Hello"
 Output: true

16. Concatenate Two Strings

Join two strings into one.
Example:
 Input: "hello", "world"
 Output: "helloworld"

17. Convert a String to Integer (atoi Implementation)

Convert a numeric string to an integer.
Example:
 Input: "123"
 Output: 123

18. Find the Longest Word in a Sentence

Identify the longest word.
Example:
 Input: "The quick brown fox"
 Output: "quick"

19. Find the Shortest Word in a Sentence

Identify the shortest word.
Example:
 Input: "The quick brown fox"
 Output: "The"

20. Remove Vowels from a String

Eliminate all vowels (a, e, i, o, u).
Example:
 Input: "hello"
 Output: "hll"

21. Find the Second Most Frequent Character

Find the second most repeated character.
Example:
 Input: "success"
 Output: 'u'
22. Check if Two Strings are Case-Insensitive Equal
Compare two strings ignoring case.
Example:
 Input: "Hello", "hello"
 Output: true

23. Count the Number of Words in a String

Count the total words in a string.
Example:
 Input: "hello world"
 Output: 2

24. Reverse Words in a Sentence

Reverse the order of words in a sentence.
Example:
 Input: "hello world"
 Output: "world hello"

25. Check if a String is a Valid IPv4 Address

Verify if the string represents a valid IPv4 address.
Example:
 Input: "192.168.1.1"
 Output: true

26. Remove Special Characters from a String

Remove non-alphanumeric characters.
Example:
 Input: "hello@world!"
 Output: "helloworld"

27. Convert a Sentence to Title Case

Capitalize the first letter of each word.
Example:
 Input: "hello world"
 Output: "Hello World"

28. Check if a String Contains Only Numbers

Verify if the string contains only digits.
Example:
 Input: "123456"
 Output: true

29. Find the Most Frequent Word in a Sentence

Identify the word with the highest occurrence.
Example:
 Input: "the fox and the hound"
 Output: "the"
30. Remove All Occurrences of a Substring
Remove all instances of a specific substring.
Example:
 Input: "hello world", "world"
 Output: "hello"

Intermediate Problems (31–70)

31. Longest Substring Without Repeating Characters
 Input: "abcabcbb"
 Output: 3 (substring: "abc")
32. Longest Palindromic Substring
 Input: "babad"
 Output: "bab" or "aba"
33. Check if Two Strings Are Rotations
 Input: "abcd", "cdab"
 Output: true
34. Check if Two Strings are Anagrams
 Input: "listen", "silent"
 Output: true
35. Word Break Problem
 Input: "leetcode", wordDict = ["leet", "code"]
 Output: true
36. Z-Algorithm for Pattern Matching
 Input: text = "abcxabcdabcdabcy", pattern = "abcdabcy"
 Output: true (pattern found at index 8)
37. String Compression
 Input: "aaabbc"
 Output: "a3b2c1"
38. Find All Permutations of a String
 Input: "abc"
 Output: ["abc", "acb", "bac", "bca", "cab", "cba"]
39. Generate All Substrings of a String
 Input: "abc"
 Output: ["a", "b", "c", "ab", "bc", "abc"]
40. Check if String Follows a Pattern (like ABBA)
 Input: string = "dog cat cat dog", pattern = "abba"
 Output: true
41. Count and Group Anagrams in a List of Strings
 Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
 Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
42. Find Longest Common Prefix of a List of Strings
 Input: ["flower", "flow", "flight"]
 Output: "fl"
43. Remove Adjacent Duplicates in a String
 Input: "abbaca"
 Output: "ca"
44. Check if a String is a Valid Parentheses Expression
 Input: "(()())"
 Output: true
45. Remove All White Spaces from a String
 Input: "a b c d"
 Output: "abcd"
46. Find All Palindromic Substrings
 Input: "aaa"
 Output: ["a", "a", "a", "aa", "aa", "aaa"]
47. Find Longest Prefix Suffix Using KMP Algorithm
 Input: "abacab"
 Output: 2
48. Count Binary Substrings
 Input: "00110011"
 Output: 6 (substrings: "0011", "01", "1100", "10", "0011", "01")
49. Check if a String is a Subsequence of Another
 Input: "abc", "ahbgdc"
 Output: true
50. Check if Two Strings Share a Common Subsequence
 Input: "hello", "world"
 Output: true

51. Generate All Possible Abbreviations of a String

 Input: "word"
 Output: ["word", "w1rd", "wo1d", "wor1", "w2d", "w3", "1ord", "1o1d", "1or1", ...]
52. Find the Minimum Window Substring
 Input: s = "ADOBECODEBANC", t = "ABC"
 Output: "BANC"
53. Split String into Balanced Parentheses Groups
 Input: "(()())"
 Output: ["(())", "(())"]
54. Find the Longest Balanced Substring of Parentheses
 Input: "(()())"
 Output: "(()())"
55. Shuffle Characters to Avoid Adjacent Duplicates
 Input: "aaabb"
 Output: "ababa"
56. Find the Number of Distinct Substrings
 Input: "abc"
 Output: 6 (substrings: "a", "b", "c", "ab", "bc", "abc")
57. Reorganize String (No Adjacent Duplicates)
 Input: "aaabb"
 Output: "ababa"
58. Find Smallest Period of Repeating String
 Input: "ababab"
 Output: "ab"
59. Find Lexicographically Smallest Rotation
 Input: "cba"
 Output: "acb"
60. Find All Words Formed by Concatenation
 Input: s = "barfoothefoobarman", words = ["foo", "bar"]
 Output: [0, 9]
61. Longest Substring with At Most K Distinct Characters
 Input: "eceba", k = 2
  Output: 3 (substring: "ece")
62. Find All Indices of a Pattern in Text
 Input: text = "ababcabcab", pattern = "abc"
 Output: [2, 5]
63. Transform String with Minimum Cost
 Input: "abc", "bcd"
 Output: 3
64. Find the Number of Good Splits
 Input: "aacaba"
 Output: 2
65. Convert Roman Numerals to Integer
 Input: "XIV"
 Output: 14
66. Convert Integer to Roman Numerals
 Input: 58
 Output: "LVIII"
67. Decode a String Encoded with Count (e.g., a2b3)
 Input: "a2b3"
 Output: "aabbb"
68. Check if String is Valid After Replacements
 Input: "aabcbc"
 Output: true
69. Count Palindromic Subsequences
 Input: "aaa"
 Output: 6
70. Count Subsequences That Match a Target String
 Input: s = "rabbbit", t = "rabbit"
 Output: 3

Advanced Problems (71–100)

71. Edit Distance Between Two Strings

 Input: "kitten", "sitting"

 Output: 3 (operations: replace 'k' with 's', replace 'e' with 'i', add 'g')

72. Find Longest Common Subsequence of Two Strings

 Input: "abcde", "ace"

 Output: "ace"

73. Find Longest Common Substring of Two Strings

 Input: "abcdef", "zbcdf"

 Output: "bcd"

74. Find Smallest Subsequence Covering All Characters of Target

 Input: s = "ADOBECODEBANC", t = "ABC"

 Output: "BANC"

75. Find Lexicographical Rank of a String

 Input: "string"
 Output: 598

76. Find the Minimum Insertions for Palindrome

 Input: "abc"
 Output: 2 (insert 'cba')

77. Generate All Palindromic Partitions of a String

 Input: "aab"
 Output: [["a", "a", "b"], ["aa", "b"]]

78. Find the Number of Unique Subsequences

 Input: "abcb"
 Output: 15

79. Check if a String is Valid After Removal of Substrings

 Input: s = "abcabc", substr = "abc"

 Output: true

80. Find Longest Palindrome by Removing at Most One Character

 Input: "abca"
 Output: 4 (result: "aba")

81. Longest Substring with Equal Number of 0s and 1s

 Input: "1100011"
 Output: 6

82. Longest Substring with Equal Number of Vowels and Consonants

 Input: "abcdeiouxyz"
 Output: 6

83. Find the Lexicographically Smallest Substring

 Input: "bca"
 Output: "a"

84. Find the Lexicographically Largest Substring

 Input: "bca"
 Output: "c"

85. Find All Distinct Permutations of a String

 Input: "abc"
 Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

86. Split String into Groups of Equal Characters

 Input: "aaabbbcdd"
 Output: ["aaa", "bbb", "c", "dd"]

87. Find All Strings That Can Be Formed by Replacing Wildcards

 Input: "1?0?"
 Output: ["1000", "1001", "1100", "1101"]

88. Find Maximum Length of Concatenated String with Unique Characters

 Input: ["un", "iq", "ue"]

 Output: 4 (result: "uniq")

89. Check if Two Strings are Buddy Strings

 Input: "ab", "ba"

 Output: true

90. Find Minimum Cuts for Palindrome Partitioning

 Input: "aab"
 Output: 1

91. Find the Minimum Number of Steps to Make Strings Equal

 Input: "abcdef", "azced"

 Output: 4

92. Generate Shortest Supersequence Covering Two Strings

  Input: "AGGTAB", "GXTXAYB"
 Output: "AGGXTXAYB"

93. Generate All Valid Parentheses Combinations

 Input: n = 3
 Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

94. Find the Maximum Length of Repeated Subarray

 Input: nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]

 Output: 3 (subarray: [3, 2, 1])

95. Find Longest Word in Dictionary Formed by Deletion

 Input: s = "abpcplea", dictionary = ["ale", "apple", "monkey", "plea"]

 Output: "apple"

96. Count Occurrences of a Word in a Grid of Characters

 Input:

css
Copy code
grid = [["a", "b", "c"],
["d", "e", "f"],
["g", "h", "i"]],
word = "abc"`

 Output: 1

97. Find the Longest Zig-Zag Substring

 Input: "abacbab"
 Output: 5 (substring: "abacb")

98. Count Unique Characters in All Substrings

 Input: "abc"
 Output: 10

99. Find Number of Ways to Split a String into Palindromes

 Input: "aab"
 Output: 2

100. Determine if a String Can Be Split into Fibonacci Sequence

 Input: "11235813"
 Output: true

1. Minimum Number of Operations/Steps

These problems involve finding the fewest number of operations or steps to achieve a given task.
1. Find the Minimum Steps to Reach a Target Using Given Operations
o Example: Find the minimum number of steps to reach from number X to Y using operations such as addition or multiplication.

2. Minimum Number of Coins for Change

o Example: Given an array of coin denominations and a target amount, find the minimum number of coins required to make the target amount.

3. Minimum Steps to Transform One String to Another

o Example: Given two strings, find the minimum number of edit operations (insertions, deletions, substitutions) required to convert one string to another.

4. Minimum Path Sum in a Grid

o Example: Given a grid of m x n, find the minimum path sum from the top-left to the bottom-right corner, where you can only move down or right.

5. Minimum Number of Jumps to Reach the End

o Example: Given an array where each element represents the maximum number of steps you can take forward, find the minimum number of jumps needed
to reach the end of the array.
6. Minimum Distance Between Two Nodes in a Binary Tree
o Example: Given a binary tree and two nodes, find the minimum number of edges between them.
2. Maximum Steps/Operations
These problems require you to find the maximum number of operations or steps possible.
1. Maximum Product of Two Numbers in an Array
o Example: Given an array, find the maximum product that can be obtained by multiplying two distinct elements.

2. Maximum Steps to Reach Zero

o Example: Given a number n, find the maximum number of steps to reduce n to zero using operations such as subtracting 1, dividing by 2, etc.

3. Maximum Sum of Non-Adjacent Elements

o Example: Given an array of integers, find the maximum sum of elements that are not adjacent to each other.

4. Maximum Path Sum in a Grid

o Example: Given a 2D grid, find the path with the maximum sum from the top-left corner to the bottom-right corner, where you can only move right or
down.
5. Maximum Length of a Substring Without Repeating Characters
o Example: Given a string, find the length of the longest substring without repeating characters.

6. Maximum Number of Cuts to Divide a Cake

o Example: Given a cake represented by a 2D grid, determine the maximum number of pieces you can obtain with a certain number of straight cuts.

3. How Many Ways (Combinatorics)

These problems involve counting the number of possible ways to do something, often using combinations or dynamic programming.
1. Number of Ways to Climb Stairs
o Example: You can climb a staircase by taking 1 or 2 steps at a time. Given n stairs, find how many distinct ways you can reach the top.

2. Number of Ways to Reach the End of a Grid

o Example: Given a grid where you can only move right or down, find the number of ways to reach the bottom-right corner from the top-left corner.

3. Number of Ways to Arrange Coins in a Circle

o Example: Given n coins, how many different ways can they be arranged in a circle?

4. How Many Ways to Partition a Set into Subsets

o Example: Given n items, how many ways can they be partitioned into subsets?

5. Number of Ways to Distribute Candies

o Example: If you have n candies and k children, how many ways can you distribute the candies such that each child gets at least one candy?

6. Number of Ways to Form a Palindrome

o Example: Given a string, find how many ways you can rearrange the characters to form a palindrome.

7. Number of Ways to Make Change for a Given Amount

o Example: Given an array of coin denominations and a target amount, find how many ways you can make change for the target amount.

8. Number of Ways to Arrange Words in a Sentence

o Example: Given a sentence, how many ways can you rearrange the words without changing their internal order?

9. How Many Ways to Reach the Top of a Stairs with Jumps

o Example: Given n stairs, and the ability to jump 1 or 2 steps at a time, how many different ways can you reach the top?

10. How Many Ways to Form a Triangle from Three Side Lengths
o Example: Given three side lengths, how many ways can you form a valid triangle (triangle inequality theorem)?

4. Mixed Problems Involving Both Minimum and Maximum

These problems require you to both minimize and maximize certain parameters, often using dynamic programming or greedy approaches.
1. Find the Maximum Profit from Stock Prices with Cooldown Period
o Example: Given an array representing stock prices, find the maximum profit you can make by buying and selling stocks, with a cooldown period between
buys.
2. Find the Minimum and Maximum Sum of Subarrays
o Example: Given an array of integers, find both the minimum and maximum sum of contiguous subarrays.

3. Find the Maximum Number of Distinct Pairs in an Array

o Example: Given an array, find the maximum number of pairs you can form, such that no two pairs share an element.

4. Minimum and Maximum Path in a Grid

o Example: Given a 2D grid of integers, find both the minimum and maximum sum paths from the top-left corner to the bottom-right corner.
_______________________________________________________________________________________
1-10: Basic Logical Puzzles
1. The Two Doors Puzzle: You are in a room with two doors: one leads to freedom, the other to a deadly trap. One guard always tells the truth, and the other always
lies. What question can you ask to determine which door leads to freedom?
2. The Family Puzzle: A man is looking at a picture of someone. His friend asks, “Who are you looking at?” The man replies, “Brothers and sisters, I have none. But
the father of the person in the picture is my father’s son.” Who is the person in the picture?
3. The Two Sons Puzzle: A man has two sons. One always tells the truth, and the other always lies. He tells you, “One of my sons will say that the other is lying.”
Which son is which?
4. The Missing Dollar Puzzle: Three friends check into a hotel room that costs $30. They each contribute $10. Later, the manager realizes the room only costs $25
and gives $5 to the bellboy to return. The bellboy keeps $2 for himself and gives $1 back to each of the three friends. Now, each friend has paid $9, and the bellboy
kept $2. But 9 × 3 = 27, and 27 + 2 = 29, not 30. Where is the missing dollar?
5. The River Crossing Puzzle: You are on a riverbank with a wolf, a goat, and a cabbage. You have a boat that can carry only one of them at a time. If you leave the
wolf and goat together, the wolf will eat the goat, and if you leave the goat and cabbage together, the goat will eat the cabbage. How do you get all three across the
river?
6. The Poisonous Wine Puzzle: You have 1000 bottles of wine, and one is poisoned. The poison is lethal after 24 hours. You have 10 people to test the wine. How do
you find the poisoned bottle with the least number of tests?
7. The Three Friends on a Bench Puzzle: Three friends are sitting on a bench. One says, "The man to my left is the father of my child," and the other says, "The
man to my right is my brother." Who is sitting on the left and who is sitting on the right?
8. The Truth-Teller and Liar Puzzle: You are in a room with two individuals. One always tells the truth, and the other always lies. They are asked a question: “If I
were to ask your companion who is lying, what would they say?” What do you ask to determine who is who?
9. The Birthday Puzzle: A man is born on February 29. How often does he get to celebrate his birthday?
10. The Box and Balls Puzzle: You have three boxes: one containing only red balls, one containing only green balls, and one containing both. The boxes are
incorrectly labeled. You are allowed to pick only one ball from one box. How can you label all the boxes correctly?
11-20: Number-based Puzzles
11. The Counterfeit Coin Problem: You have 12 coins, one of which is counterfeit. The counterfeit coin is either heavier or lighter. Using a balance scale, how do
you find the counterfeit coin in 3 weighings?
12. The 100 Coins Puzzle: You have 100 coins, and you know that one is heads up and all others are tails. You are blindfolded and must divide the coins into two
piles, each with the same number of heads. How do you do it?
13. The Hourglass Puzzle: You have two hourglasses: one measuring 7 minutes and the other 11 minutes. How can you measure exactly 15 minutes?
14. The Number Lock Puzzle: A safe has a 3-digit combination lock. The first number is 2 more than the second number. The third number is 3 less than the first
number. What is the combination?
15. The Missing Digit Puzzle: There is a number with missing digits. You know that the sum of the digits is 9, and the number is divisible by 3. What could the
number be?
16. The Sum Puzzle: You are given a set of numbers, and you need to find two numbers whose sum is equal to a specific target number. How do you solve it?
17. The Three Light Bulbs Puzzle: You are in a room with three light bulbs and three switches outside the room. Each switch controls one bulb. You can only enter
the room once. How do you determine which switch controls which bulb?
18. The Fibonacci Puzzle: How would you calculate the nth Fibonacci number?
19. The Simple Math Puzzle: A man gives a piece of paper with the numbers 1, 2, and 3. What is the sum of all possible combinations of those numbers?
20. The Factorial Puzzle: Find the factorial of a number N (denoted as N!) and explain how to calculate it.
21-30: Logical Deduction Puzzles
21. The Clock Puzzle: What is the angle between the hour and minute hands of a clock at 3:15?
22. The Hat Puzzle: 100 people are in a line, and each person has a hat of either red or blue. They can see the hats of everyone in front of them but not their own.
They are told to guess the color of their own hat. What strategy maximizes the number of correct guesses?
23. The 3 Prisoners Puzzle: Three prisoners are told that one of them will be released. They can ask the guard one question to figure out who will be released. What
should they ask?
24. The Light Bulb Puzzle: You have 3 light bulbs in a room and 3 switches outside the room. Each switch controls one bulb. How can you figure out which switch
controls which bulb if you can only enter the room once?
25. The Ant and the Grasshopper Puzzle: An ant and a grasshopper are on a 100-meter-long straight path. The ant moves 1 meter every second, while the
grasshopper moves 2 meters every second. They start at opposite ends of the path at the same time. Will the grasshopper ever catch up to the ant?
26. The 8-coin Puzzle: You are given 8 identical-looking coins, but one is either heavier or lighter. Using a balance scale, how can you find the counterfeit coin in 2
weighings?
27. The Water Jug Puzzle: You have a 5-liter jug and a 3-liter jug. How can you measure exactly 4 liters using these two jugs?
28. The Crossing Puzzle: A farmer needs to cross a river with a wolf, a goat, and a cabbage. The farmer can only take one at a time in the boat. How does the farmer
ensure that nothing gets eaten?
29. The Six Friends Puzzle: Six friends are sitting in a row. They are told to sit such that the person in the middle is always in between two people who are the same
height. How do they arrange themselves?
30. The Two Ropes Puzzle: You have two ropes, each of which takes exactly one hour to burn but burns unevenly. How can you measure exactly 45 minutes using
these ropes?
31-40: Pattern Recognition Puzzles
31. The Sequence Puzzle: What comes next in the following sequence? 1, 1, 2, 6, 24, ___
32. The Number Puzzle: Find the next number in the sequence: 1, 4, 9, 16, ___
33. The Alphabet Puzzle: What comes next in the sequence: A, C, E, G, ___?
34. The Puzzle Box: You are given a box with a set of instructions, but some instructions are missing. Can you figure out how to open the box with the information
provided?
35. The Color Puzzle: You are given a series of colors in a particular order. Find the next color in the pattern.
36. The Missing Number Puzzle: Find the missing number in the series: 2, 5, 10, 17, 26, ___.
37. The Triangle Puzzle: How many triangles are in the given figure?
38. The Coin Puzzle: You have a number of coins in a row, with each coin facing heads or tails. How many ways can you flip the coins to make all coins face heads?
39. The Word Puzzle: What word is made by rearranging the letters in the following sequence: E, L, T, C, A, R?
40. The Missing Element Puzzle: In the sequence 3, 9, 27, ___, what is the missing element?
41-50: Riddle-based Logical Puzzles
41. The Sphinx Riddle: “What walks on four legs in the morning, two legs at noon, and three legs in the evening?”
42. The String Puzzle: You have two pieces of string of unequal length. How can you measure an exact amount of time by burning them simultaneously?
43. The Time Puzzle: What is the angle between the hour and minute hands of a clock at 9:15?
44. The Man and the City Puzzle: A man walks into a city, but no one knows who he is. He meets a person who knows everyone. How can he figure out if he's in the
right city?
45. The Bridge Puzzle: Four people need to cross a bridge at night. The bridge can only hold two people at a time, and they have one flashlight. How do they all get
across in the least amount of time?
46. The Family of 5 Puzzle: A family of five is sitting at a table. Each person shakes hands with every other person exactly once. How many handshakes will there
be?
47. The Guessing Puzzle: A man is on a game show. He is given the option to guess the number of marbles in a jar. What strategy should he use to maximize his
chances of guessing correctly?
48. The Coin Flipping Puzzle: You flip a coin 5 times, and the outcome is heads every time. What are the odds that the next flip will be heads?
49. The Prisoner Hat Puzzle: A prisoner is given a choice to wear one of two hats: black or white. He is told that one hat is black and the other is white. What color
hat should he choose to ensure he survives?
50. The Chessboard Puzzle: How many squares are there on a standard 8x8 chessboard?
51-60: Logical Deduction Puzzles
51. The Clue Puzzle: You are given a series of clues that lead to a specific solution. What is the solution based on the clues provided?
52. The Parallel Line Puzzle: How many parallel lines are in a given diagram?
53. The Coin Puzzle: You have two identical-looking coins, but one is heavier than the other. How do you find the heavier coin using the least number of weighings?
54. The Time of Day Puzzle: A clock shows the time as 3:15. What is the angle between the hour and minute hands?
55. The Number Grid Puzzle

Basic OOP Concepts

1. Create a Class for a Rectangle
o Attributes: Length, Breadth

o Methods: Calculate Area, Calculate Perimeter

2. Create a Class for a Circle

o Attributes: Radius

o Methods: Calculate Area, Calculate Circumference

3. Implement a Bank Account Class

o Attributes: Account Number, Balance

o Methods: Deposit, Withdraw, Check Balance

4. Create a Class for a Car

o Attributes: Model, Make, Year, Color

o Methods: Start, Stop, Accelerate

5. Create a Student Class

o Attributes: Name, Roll Number, Marks

o Methods: Calculate Average Marks, Display Details

6. Class for Complex Numbers

o Attributes: Real Part, Imaginary Part
 o Methods: Add, Subtract, Multiply Complex Numbers

7. Create a Book Class

o Attributes: Title, Author, Price

o Methods: Display Book Details

8. Create a Person Class

o Attributes: Name, Age, Gender

o Methods: Greet

9. Create a Dog Class

o Attributes: Breed, Age

o Methods: Bark, Fetch

10. Create an Employee Class

o Attributes: Employee ID, Name, Salary

o Methods: Calculate Bonus, Display Details

Inheritance
11. Create a Shape Class
o Base Class: Shape (Attributes: Sides)

o Derived Classes: Triangle, Rectangle, Circle

12. Vehicle Class with Inheritance

o Base Class: Vehicle

o Derived Classes: Car, Truck, Motorcycle

13. Bank System Using Inheritance

o Base Class: Account (Attributes: Balance)

o Derived Classes: SavingsAccount, CurrentAccount

14. Create an Animal Class

o Base Class: Animal

o Derived Classes: Dog, Cat, Bird

15. Create a University Class

o Base Class: University

o Derived Classes: College, Department

Polymorphism
16. Method Overloading Example
o Class: Calculator

o Overloaded Methods: Add (for integers, doubles)

17. Method Overriding Example

o Base Class: Animal (Method: Speak)

o Derived Classes: Dog (Bark), Cat (Meow)

18. Dynamic Polymorphism

o Example: Shape Class with a Method draw() that is overridden in Circle and Rectangle

19. Abstract Class Example

o Base Class: Shape (Abstract Method: CalculateArea)

o Derived Classes: Circle, Rectangle

20. Interface Implementation

o Interface: Payment

o Implementations: CreditCardPayment, DebitCardPayment

Encapsulation
21. Create a Private BankAccount Class
o Private Attributes: Account Number, PIN
 o Methods: Deposit, Withdraw (Using PIN Validation)

22. Encapsulate Student Details

o Attributes: Name, Roll Number, Marks (Private)

o Methods: Getters and Setters

23. Encapsulation Example in Inventory Management

o Class: Product

o Private Attributes: ID, Price, Quantity

24. Encapsulation Example in Library System

o Class: Book (Private Attributes with Getter/Setter)

25. Encapsulation Example in an ATM System

o Class: ATM (Private Data for PIN, Account Balance)

Advanced OOP Concepts

26. Singleton Pattern Implementation
27. Factory Design Pattern
28. Builder Design Pattern for Complex Objects
29. Observer Design Pattern for Event Handling
30. Strategy Design Pattern for Payment Methods
31. Decorator Pattern Example for Adding Features
32. Adapter Pattern Example for Data Conversion
33. Proxy Pattern Example for Access Control
34. Command Pattern Example for Undo/Redo Operations
35. Template Method Pattern for Workflow Management

File Handling and Serialization

36. Serialize and Deserialize an Object
37. Read and Write Student Records to a File
38. Implement File-Based Library System
39. Create a System to Log Errors Using File Handling
40. Serialize and Deserialize Complex Objects with Relationships

Design-Based Problems
41. Design a Library Management System
42. Design a Parking Lot System
43. Design a Movie Ticket Booking System
44. Design a Hotel Booking System
45. Design an Elevator System
46. Design a Food Delivery System
47. Design a Ride-Sharing System
48. Design a Bank Management System
49. Design a Vending Machine
50. Design an Airline Reservation System

Real-Life Simulations
51. Create a Chess Game Using OOP Concepts
52. Create a Snake and Ladder Game
53. Create a Tic-Tac-Toe Game
54. Create a Virtual ATM System
55. Create a Stock Management System

Collections with OOP

 56. Manage a Student Record System Using HashMap
57. Implement a Library System with HashMap and List
58. Create a System to Track Product Stock Using Collections
59. Track Employee Salaries Using a HashMap
60. Create a Contact Book Application Using TreeMap

Multithreading and OOP

61. Create a Multi-Threaded Banking System
62. Simulate Producer-Consumer Problem Using Threads
63. Create a Chat Application with Multi-Threading
64. Implement a Concurrent Library System
65. Create a Ticket Booking System with Thread Safety

OOP for Competitive Programming

66. LRU Cache Implementation Using OOP Concepts
67. Design a Trie for String Operations
68. Create a Priority Queue Using OOP Concepts
69. Implement a Graph Class with BFS and DFS
70. Create a Matrix Class for Operations (Transpose, Multiplication)

Edge Cases and Robustness

71. Handle Invalid Data in Banking System
72. Prevent Double Booking in Movie Ticket System
73. Handle Overlapping Reservations in Hotel System
74. Ensure Thread-Safe Transactions in Multi-Threaded Bank System
75. Prevent Invalid Moves in Chess Game Design

Miscellaneous OOP Challenges

76. Design a Digital Wallet System
77. Design a Weather Monitoring System
78. Create a Shopping Cart System
79. Implement a Music Playlist Application
80. Create a Warehouse Management System

Testing and Optimization

81. Optimize a Library Management System for Large Data
82. Test a Banking System for Edge Cases
83. Test and Debug a Game System Design
84. Optimize the Search System in Library Design
85. Create Unit Tests for an ATM System

Customizable Features
86. Add Logging to a Banking System
87. Add Discounts in a Shopping Cart System
88. Add Notifications in a Library System
89. Add Reporting Features in a Hotel Booking System
90. Add Analytics to a Ride-Sharing System

Project-Based OOP
91. E-Commerce System
92. Social Media Application
 93. Job Portal System
94. Learning Management System
95. Hospital Management System

Advanced OOP
96. Design a Compiler Using OOP Concepts
97. Design a Cache System Using OOP
98. Design an API Rate Limiter
99. Design a Chatbot System
100. Design a Distributed Logging System

1. Strategy Pattern

 Definition: Encapsulates a family of algorithms (strategies) into separate classes and makes them interchangeable. The client dynamically selects the
desired algorithm.
 Purpose: Reduces if-else or switch-case logic and promotes flexibility by allowing dynamic behavior changes.
 Common Interview Question:
o Question: Design a system where a user can calculate a discount for items based on different strategies (e.g., seasonal discount, festival
discount).
o Example:

java
Copy code
interface DiscountStrategy {
double calculateDiscount(double price);
}
class SeasonalDiscount implements DiscountStrategy {
public double calculateDiscount(double price) { return price * 0.1; }
}
class FestivalDiscount implements DiscountStrategy {
public double calculateDiscount(double price) { return price * 0.2; }
}

The user selects the appropriate strategy at runtime to apply discounts.

2. Observer Pattern

 Definition: Defines a one-to-many dependency, where multiple observers are notified of changes in the subject.
 Purpose: Ensures that multiple objects stay updated when the state of a subject changes.
 Common Interview Question:
o Question: Design a stock price monitoring system where users get notifications when stock prices change.
o Example:

java
Copy code
interface Observer {
void update(String stock, double price);
}
class Investor implements Observer {
public void update(String stock, double price) {
System.out.println("Stock: " + stock + " Price: " + price);
}
}
class StockMarket {
private List<Observer> observers = new ArrayList<>();
void addObserver(Observer o) { observers.add(o); }
void notifyObservers(String stock, double price) {
for (Observer o : observers) o.update(stock, price);
}
}

The Investor objects are updated automatically whenever a stock price changes.

3. Decorator Pattern

 Definition: Dynamically adds additional responsibilities to an object without modifying its code.
 Purpose: Achieves flexibility and avoids subclassing for extending functionality.
 Common Interview Question:
o Question: Design a coffee shop billing system where a customer can add extras like milk, cream, or sugar to their coffee dynamically.
o Example:

java
Copy code
 interface Coffee {
double cost();
String description();
}
class SimpleCoffee implements Coffee {
public double cost() { return 5.0; }
public String description() { return "Simple Coffee"; }
}
class MilkDecorator implements Coffee {
private Coffee coffee;
public MilkDecorator(Coffee coffee) { this.coffee = coffee; }
public double cost() { return coffee.cost() + 1.5; }
public String description() { return coffee.description() + ", Milk"; }
}

Add multiple layers of decorators dynamically for additional functionality.

4. Factory Pattern

 Definition: Provides a method to create objects without specifying the exact class of the object being created.
 Purpose: Abstracts object creation to avoid tight coupling.
 Common Interview Question:
o Question: Design a factory that creates different types of vehicles (e.g., Car, Bike, Truck).
o Example:

java
Copy code
interface Vehicle {
void drive();
}
class Car implements Vehicle {
public void drive() { System.out.println("Driving a car"); }
}
class Bike implements Vehicle {
public void drive() { System.out.println("Riding a bike"); }
}
class VehicleFactory {
public static Vehicle createVehicle(String type) {
if (type.equals("Car")) return new Car();
else if (type.equals("Bike")) return new Bike();
else throw new IllegalArgumentException("Unknown type");
}
}

The factory encapsulates the logic for object creation.

5. Abstract Factory Pattern

 Definition: Provides a way to create families of related objects without specifying their concrete classes.
 Purpose: Supports multiple families of products.
 Common Interview Question:
o Question: Design a system that creates GUI components (e.g., Windows or MacOS buttons and checkboxes) based on the operating system.
o Example:

java
Copy code
interface Button {
void render();
}
class WindowsButton implements Button {
public void render() { System.out.println("Rendering Windows Button"); }
}
class MacOSButton implements Button {
public void render() { System.out.println("Rendering MacOS Button"); }
}
interface GUIFactory {
Button createButton();
}
class WindowsFactory implements GUIFactory {
public Button createButton() { return new WindowsButton(); }
}
class MacOSFactory implements GUIFactory {
public Button createButton() { return new MacOSButton(); }
}

The abstract factory allows switching between Windows and MacOS components dynamically.

6. Chain of Responsibility Pattern

 Definition: Passes a request along a chain of handlers where each handler decides whether to process the request or pass it further.
 Purpose: Decouples sender and receiver of requests.
 Common Interview Question:
o Question: Design an ATM system where the withdrawal amount is dispensed in denominations (e.g., 1000s, 500s, 100s).
 o Example:

java
Copy code
abstract class Handler {
protected Handler next;
void setNext(Handler next) { this.next = next; }
abstract void handle(int amount);
}
class ThousandHandler extends Handler {
void handle(int amount) {
int count = amount / 1000;
System.out.println("Dispense " + count + " thousand notes");
if (next != null) next.handle(amount % 1000);
}
}

Requests flow through each handler in the chain.

7. Proxy Pattern

 Definition: Provides a placeholder or surrogate to control access to another object.

 Purpose: Adds a level of control or functionality, such as caching or access control.
 Common Interview Question:
o Question: Design a proxy for accessing a remote database to cache frequently requested data.
o Example:

java
Copy code
interface Database {
String fetchData(String query);
}
class RealDatabase implements Database {
public String fetchData(String query) { return "Real Data"; }
}
class DatabaseProxy implements Database {
private RealDatabase database;
private Map<String, String> cache = new HashMap<>();
public String fetchData(String query) {
if (cache.containsKey(query)) return cache.get(query);
if (database == null) database = new RealDatabase();
String result = database.fetchData(query);
cache.put(query, result);
return result;
}
}

The proxy caches data to minimize database calls.

8. State Pattern

 Definition: Allows an object to change its behavior based on its internal state.
 Purpose: Encapsulates state-specific behavior in separate classes.
 Common Interview Question:
o Question: Design a vending machine that behaves differently in states like No Money, Has Money, and Out of Stock.
o Example:

java
Copy code
interface State {
void handle();
}
class NoMoneyState implements State {
public void handle() { System.out.println("Insert money to proceed"); }
}
class HasMoneyState implements State {
public void handle() { System.out.println("Dispensing item"); }
}
class VendingMachine {
private State state;
void setState(State state) { this.state = state; }
void request() { state.handle(); }
}

Behavior changes based on the current state

9. Composite Pattern

 Definition: Composes objects into tree-like structures to represent part-whole hierarchies. Treats individual objects and compositions uniformly.
 Purpose: Simplifies operations on hierarchies like directories or organizational structures.
 Common Interview Question:
o Question: Design a file system where a folder can contain files or other folders, and both share common operations like size calculation or
display.
o Example:
 java
Copy code
interface FileSystemComponent {
void showDetails();
}
class File implements FileSystemComponent {
private String name;
public File(String name) { this.name = name; }
public void showDetails() { System.out.println("File: " + name); }
}
class Folder implements FileSystemComponent {
private String name;
private List<FileSystemComponent> components = new ArrayList<>();
public Folder(String name) { this.name = name; }
public void addComponent(FileSystemComponent component) { components.add(component); }
public void showDetails() {
System.out.println("Folder: " + name);
for (FileSystemComponent component : components) {
component.showDetails();
}
}
}

You can add files and folders recursively to create a directory structure.

10. Adapter Pattern

 Definition: Converts one interface into another that the client expects. Acts as a bridge between incompatible interfaces.
 Purpose: Helps integrate legacy systems or third-party APIs with your application.
 Common Interview Question:
o Question: Design a media player that supports both MP3 and MP4 formats using an adapter.
o Example:

java
Copy code
interface MediaPlayer {
void play(String fileName);
}
class MP3Player implements MediaPlayer {
public void play(String fileName) { System.out.println("Playing MP3: " + fileName); }
}
class MP4Player {
void playMP4(String fileName) { System.out.println("Playing MP4: " + fileName); }
}
class MediaAdapter implements MediaPlayer {
private MP4Player mp4Player;
public MediaAdapter() { this.mp4Player = new MP4Player(); }
public void play(String fileName) { mp4Player.playMP4(fileName); }
}

The adapter bridges the gap between the MediaPlayer interface and the MP4Player.

11. Singleton Pattern

 Definition: Ensures a class has only one instance and provides a global point of access to it.
 Purpose: Useful for managing shared resources like configurations, database connections, or logging services.
 Common Interview Question:
o Question: Design a logger system that ensures only one logger instance exists in the application.
o Example:

java
Copy code
class Logger {
private static Logger instance;
private Logger() {}
public static Logger getInstance() {
if (instance == null) {
instance = new Logger();
}
return instance;
}
public void log(String message) { System.out.println("Log: " + message); }
}

All logging calls in the system use the same logger instance.

12. Builder Pattern

 Definition: Separates the construction of a complex object from its representation, allowing for step-by-step creation.
 Purpose: Builds objects with varying configurations while keeping the code clean and maintainable.
 Common Interview Question:
o Question: Design a builder for constructing a house with optional features like a garden, swimming pool, and garage.
 o Example:

java
Copy code
class House {
private String garden;
private String pool;
private String garage;
public void setGarden(String garden) { this.garden = garden; }
public void setPool(String pool) { this.pool = pool; }
public void setGarage(String garage) { this.garage = garage; }
}
class HouseBuilder {
private House house = new House();
public HouseBuilder addGarden(String garden) { house.setGarden(garden); return this; }
public HouseBuilder addPool(String pool) { house.setPool(pool); return this; }
public HouseBuilder addGarage(String garage) { house.setGarage(garage); return this; }
public House build() { return house; }
}

You can create a house with different configurations using the builder.

13. Prototype Pattern

 Definition: Creates new objects by copying existing ones instead of instantiating new ones.
 Purpose: Useful when creating new objects is expensive or complex.
 Common Interview Question:
o Question: Design a prototype pattern for creating different shapes like Circle and Rectangle.
o Example:

java
Copy code
interface Shape extends Cloneable {
Shape clone();
}
class Circle implements Shape {
public Shape clone() { return new Circle(); }
}
class Rectangle implements Shape {
public Shape clone() { return new Rectangle(); }
}

Objects can be cloned instead of created from scratch.

14. Null Object Pattern

 Definition: Provides a default behavior or do-nothing implementation instead of null references to avoid null pointer exceptions.
 Purpose: Avoids repeated null checks in the code.
 Common Interview Question:
o Question: Design a logging system where no logger is used if logging is disabled.
o Example:

java
Copy code
interface Logger {
void log(String message);
}
class ConsoleLogger implements Logger {
public void log(String message) { System.out.println(message); }
}
class NullLogger implements Logger {
public void log(String message) {} // Does nothing
}

Depending on whether logging is enabled, you use either ConsoleLogger or NullLogger

1. Parking Management System

 Pattern 1: Singleton Pattern (to ensure a single instance of parking lot management system for all parking operations)
  Pattern 2: Factory Pattern (to create parking slots for different types of vehicles dynamically)
 Pattern 3: Strategy Pattern (for different pricing or allocation strategies based on vehicle type or duration)
 Pattern 4: Observer Pattern (to notify when slots are available or full)

2. Bank Management System

 Pattern 1: Singleton Pattern (to ensure a single instance of the core banking system)
 Pattern 2: Factory Pattern (to create different types of accounts, e.g., savings, current, loans)
 Pattern 3: Command Pattern (to manage customer transactions like deposit, withdraw, transfer)
 Pattern 4: Observer Pattern (to notify customers of balance changes or new transactions)
 Pattern 5: Strategy Pattern (for implementing loan calculation or interest rate policies)

3. Employee Management System

 Pattern 1: Singleton Pattern (to manage the central database of employees)

 Pattern 2: Factory Pattern (to create different types of employees like full-time, part-time, contractors)
 Pattern 3: Builder Pattern (to configure employee profiles with optional details like benefits, perks)
 Pattern 4: Observer Pattern (to notify employees of updates like appraisals or shifts)
 Pattern 5: Strategy Pattern (to implement salary calculation algorithms for different roles)

4. Lift System

 Pattern 1: Singleton Pattern (to control the central elevator system)

 Pattern 2: Observer Pattern (to notify displays or passengers about elevator status)
 Pattern 3: Command Pattern (to encapsulate floor requests and execute them in sequence)
 Pattern 4: Strategy Pattern (for different scheduling algorithms like nearest-first or least busy elevator)
 Pattern 5: State Pattern (to manage elevator states like idle, moving, or maintenance)
 Pattern 6: Builder Pattern (to configure elevators with optional features like alarms or voice guidance)

5. Railway Ticket Booking Application

 Pattern 1: Factory Pattern (to create tickets for different types like sleeper, AC, general)
 Pattern 2: Observer Pattern (to notify users of ticket confirmation or waiting list updates)
 Pattern 3: Builder Pattern (to create customizable tickets with optional features like meals or insurance)
 Pattern 4: State Pattern (to manage ticket states like confirmed, waiting, or canceled)

6. Taxi Booking System

 Pattern 1: Factory Pattern (to create ride objects for different vehicle types like sedans, SUVs, or auto-rickshaws)
 Pattern 2: Strategy Pattern (for fare calculation strategies based on time, distance, or surge pricing)
 Pattern 3: Observer Pattern (to notify drivers and riders of booking or ride status)
 Pattern 4: Command Pattern (to handle ride requests and execute them sequentially)
 Pattern 5: State Pattern (to manage ride states like available, booked, or completed)

7. Games (Sudoku, N-Queens, Snake and Ladder, etc.)

 Pattern 1: Factory Pattern (to create game objects like boards, pieces, or levels)
 Pattern 2: State Pattern (to manage game states like start, pause, or end)
 Pattern 3: Strategy Pattern (for algorithms to solve or simulate moves, e.g., AI)
 Pattern 4: Command Pattern (to manage player moves and actions)

8. Bus Ticket Booking System

 Pattern 1: Factory Pattern (to create tickets for different types of buses like luxury, semi-luxury, sleeper)
 Pattern 2: Builder Pattern (to configure tickets with optional features like seat selection or meals)
 Pattern 3: Observer Pattern (to notify users of booking status or schedule changes)
 Pattern 4: State Pattern (to manage ticket states like confirmed, waiting, or canceled)

9. Elevator

 Pattern 1: Singleton Pattern (to control the central elevator system)

 Pattern 2: Observer Pattern (to notify displays or passengers about elevator status)
 Pattern 3: Command Pattern (to encapsulate floor requests and execute them in sequence)
  Pattern 4: Strategy Pattern (for different scheduling algorithms like nearest-first or least busy elevator)
 Pattern 5: State Pattern (to manage elevator states like idle, moving, or maintenance)
 Pattern 6: Builder Pattern (to configure elevators with optional features)

10. Flight Reservation System

 Pattern 1: Factory Pattern (to create flight tickets for different classes like economy, business, or first-class)
 Pattern 2: Builder Pattern (to configure tickets with add-ons like luggage, meals, or insurance)
 Pattern 3: Observer Pattern (to notify passengers of booking status or flight delays)
 Pattern 4: State Pattern (to manage ticket states like booked, checked-in, or canceled)

11. Chess Tournament

 Pattern 1: Factory Pattern (to create players, matches, or game boards dynamically)
 Pattern 2: Observer Pattern (to notify players and organizers of match results or updates)
 Pattern 3: Strategy Pattern (for AI algorithms or match scheduling strategies)
 Pattern 4: Command Pattern (to handle moves or actions in a match)

12. Mail Server

 Pattern 1: Singleton Pattern (to manage the core mail server instance)
 Pattern 2: Observer Pattern (to notify users of incoming or outgoing emails)
 Pattern 3: Command Pattern (to handle email sending and queuing)

13. Invoice Management

 Pattern 1: Singleton Pattern (to manage the central invoice system)

 Pattern 2: Factory Pattern (to create invoices for different types like services or products)
 Pattern 3: Builder Pattern (to configure invoices with optional details like discounts or taxes)
 Pattern 4: Observer Pattern (to notify users of payment updates)

14. Toll Payment Processing

 Pattern 1: Singleton Pattern (to manage a central toll collection system)

 Pattern 2: Observer Pattern (to notify drivers of toll deductions or alerts)
 Pattern 3: Factory Pattern (to create toll passes or receipts for different vehicle types)
 Pattern 4: Strategy Pattern (to calculate toll fees based on distance, vehicle type, or time)