✅ Coding Interview Questions with Answers [Part-2] 💻🚀

11. What is a sliding window algorithm?
A technique for solving problems involving arrays or strings by maintaining a window that slides over data. It helps reduce time complexity by avoiding nested loops.
Example: Finding the max sum of subarrays of size k.

12. Detect cycle in a linked list.
Use Floyd's Cycle Detection Algorithm (Tortoise and Hare).
⦁ Move two pointers at different speeds.
⦁ If they meet, a cycle exists.
⦁ To find the cycle start, reset one pointer to head and move both one step until they meet again.

13. Find the intersection of two arrays.
Use a HashSet to store elements of the first array, then check each element in the second array.
⦁ Time: O(n + m)
⦁ Space: O(min(n, m))

14. Reverse a string or linked list.
⦁ For a string: Use two-pointer swap or Python's slicing.
⦁ For a linked list: Use three pointers (prev, curr, next) and iterate while reversing links.

15. Check if a string is a palindrome.
Use two pointers from start and end, compare characters.
Return false if mismatch, true if all characters match.

16. What are the different sorting algorithms?
⦁ Bubble Sort
⦁ Selection Sort
⦁ Insertion Sort
⦁ Merge Sort
⦁ Quick Sort
⦁ Heap Sort
⦁ Radix Sort
Each has different time and space complexities.

17. Explain quicksort vs. mergesort.
⦁ Quicksort: Divide and conquer, picks a pivot.
⦁ Average: O(n log n), Worst: O(n²), Space: O(log n)
⦁ Mergesort: Always divides array into halves, then merges.
⦁ Time: O(n log n), Space: O(n), Stable sort

18. What is a binary search tree (BST)?
A tree where left child < node < right child.
⦁ Efficient for searching, insertion, deletion: O(log n) if balanced.
⦁ Unbalanced BST can degrade to O(n)

19. Inorder, Preorder, Postorder traversals.
⦁ Inorder (LNR): Sorted order in BST
⦁ Preorder (NLR): Used to copy or serialize tree
⦁ Postorder (LRN): Used to delete tree

20. Implement LRU Cache.
Use a combination of HashMap + Doubly Linked List.
⦁ HashMap stores key-node pairs.
⦁ Linked list maintains access order.
⦁ When cache is full, remove the least recently used node.
Operations (get, put): O(1) time.

💬 Double Tap ♥️ For Part-3!