DSA Interview Preparation (Questions & Detailed Answers)

1. What is a String?
   A sequence of characters stored in contiguous memory.
2. Are strings mutable?
   Depends on language (immutable in Java, Python).
3. How to reverse a string?
   Use two-pointer approach or built-in functions.
4. Check palindrome string?
   Compare characters from both ends.
5. What is substring?
   Continuous part of a string.
6. What is subsequence?
   Characters in order but not necessarily continuous.
7. Find length of string?
   Using length function or loop.
8. Count vowels?
   Traverse and check vowels.
9. Remove spaces?
   Replace or filter characters.
10. Convert case?
    Use built-in functions.
11. Check anagram?
    Sort strings or use frequency array.
12. Find duplicate characters?
    Use hashmap.
13. First non-repeating character?
    Frequency count.
14. Remove duplicates?
    Set or visited array.
15. String concatenation?
    Join two strings.
16. Find frequency of characters?
    Use hashmap.
17. Longest substring without repeating?
    Sliding window.
18. Check rotation of string?
    s1+s1 contains s2.
19. Find all substrings?
    Nested loops.
20. Find longest palindrome substring?
    Expand around center.
21. Implement strstr?
    Pattern matching.
22. KMP algorithm?
    Efficient pattern matching.
23. Rabin-Karp?
    Hash-based pattern matching.
24. Z-algorithm?
    Pattern matching technique.
25. Split string?
    Use delimiter.
26. Trim string?
    Remove leading/trailing spaces.
27. Replace character?
    Use replace method.
28. Check substring?
    Use contains method.
29. Reverse words in string?
    Split and reverse.
30. Count words?
    Split by space.
31. Check valid parentheses?
    Use stack.
32. Minimum insertions palindrome?
    DP approach.
33. Longest common prefix?
    Compare strings.
34. String compression?
    Count repeating chars.
35. Roman to integer?
    Mapping values.
36. Integer to Roman?
    Greedy approach.
37. Decode string?
    Stack-based.
38. Check isomorphic strings?
    Mapping characters.
39. Group anagrams?
    Sort keys.
40. Word break problem?
    DP.
41. Minimum window substring?
    Sliding window.
42. Longest repeating character replacement?
    Window technique.
43. Check balanced string?
    Stack.
44. Remove adjacent duplicates?
    Stack.
45. Find all permutations?
    Backtracking.
46. Check subsequence?
    Two-pointer.
47. Count palindromic substrings?
    Expand center.
48. Edit distance?
    Dynamic programming.
49. Longest common subsequence?
    DP.
50. Shortest common supersequence?
    DP.

🔹 PART 2: LINKED LIST (Q51–Q100)

51. What is Linked List?
    A linear data structure of nodes connected by pointers.
52. Types?
    Singly, Doubly, Circular.
53. Advantages?
    Dynamic size.
54. Disadvantages?
    No random access.
55. What is node?
    Contains data and pointer.
56. Insert at beginning?
    Update head pointer.
57. Insert at end?
    Traverse and add node.
58. Delete node?
    Adjust pointers.
59. Search element?
    Traverse list.
60. Reverse linked list?
    Iterative or recursive.
61. Find middle?
    Slow and fast pointer.
62. Detect cycle?
    Floyd’s algorithm.
63. Remove cycle?
    Find meeting point.
64. Merge two lists?
    Compare nodes.
65. Sort linked list?
    Merge sort.
66. Remove duplicates?
    Use set or pointer.
67. Find nth node?
    Traverse.
68. Find nth from end?
    Two pointers.
69. Check palindrome?
    Reverse second half.
70. Intersection point?
    Two pointers.
71. Rotate list?
    Adjust pointers.
72. Flatten list?
    Merge lists.
73. Add two numbers?
    Digit by digit sum.
74. Clone list?
    Hashmap.
75. Segregate even odd?
    Two lists.
76. Reverse in k-group?
    Group reversal.
77. Remove nth node?
    Two pointers.
78. Swap nodes?
    Change pointers.
79. Partition list?
    Based on pivot.
80. Merge k lists?
    Heap.
81. Sort 0s,1s,2s?
    Counting.
82. Delete middle?
    Slow-fast pointer.
83. Odd-even list?
    Rearrange nodes.
84. Split list?
    Divide into halves.
85. Convert to BST?
    Inorder method.
86. Detect loop start?
    Floyd algorithm.
87. Remove duplicates sorted?
    Skip duplicates.
88. Remove duplicates unsorted?
    Hashset.
89. Reorder list?
    Merge halves.
90. Find length?
    Traverse.
91. Check circular?
    Loop detection.
92. Split circular list?
    Two pointers.
93. Insert in sorted list?
    Find position.
94. Delete last node?
    Traverse to second last.
95. Copy random pointer list?
    Hashmap or O(1) method.
96. Reverse doubly list?
    Swap next-prev.
97. Flatten multilevel list?
    DFS approach.
98. Remove zero sum sublist?
    Prefix sum.
99. Find pair sum?
    Two-pointer (DLL).
100. LRU cache?
     DLL + hashmap.