How to Prepare for SDE Interviews in 3–6 Months: A Complete Roadmap

• System Design: Scalability, databases, caching.
• Behavioral: Conflict resolution, leadership.
• Other: OS, Networks, Databases.

30. Real Interview Questions and In-Depth Solutions

Based on 2025 FAANG data, here are 30 actual questions asked, with categories and detailed solutions. I’ve included coding, system design, and behavioral for balance.

Coding Questions (DSA)

1. Subarray with Given Sum (Arrays, Amazon): Given an array of positive integers and sum S, find a contiguous subarray summing to S. Solution: Use a sliding window. Initialize two pointers, expand right until sum >= S, shrink left if exceeds. Time: O(N), Space: O(1). Code: Use cumulative sum map for negatives.
2. Kadane’s Algorithm (Arrays, Google): Find maximum subarray sum. Solution: Iterate, track current max and global max. If current < 0, reset. Time: O(N).
3. Missing Number in Array (Arrays, Microsoft): Find missing number in 1 to N array. Solution: XOR all elements with 1 to N. Result is missing. Time: O(N).
4. Sort an Array of 0s, 1s, 2s (Arrays, Meta): Sort without extra space. Solution: Dutch National Flag – three pointers for low, mid, high. Time: O(N).
5. Trapping Rain Water (Arrays, Amazon): Compute trapped water in bar graph. Solution: Precompute left/right max heights, sum min(left, right) – height. Time: O(N).
6. Reverse Words in a String (Strings, Google): Reverse words order. Solution: Split, reverse list, join. Time: O(N).
7. Longest Palindrome in a String (Strings, Meta): Find longest palindromic substring. Solution: Expand around centers for odd/even lengths. Time: O(N^2).
8. Anagram (Strings, Amazon): Check if two strings are anagrams. Solution: Sort or use frequency count. Time: O(N log N) or O(N).
9. Longest Common Prefix (Strings, Google): Find LCP in string array. Solution: Trie or horizontal scanning. Time: O(S) where S is total chars.
10. Implement strstr (Strings, Microsoft): Find substring index. Solution: KMP algorithm for O(N+M).
11. Reverse a Linked List (Linked List, Amazon): Reverse singly linked list. Solution: Iterative with three pointers. Time: O(N).
12. Detect Loop in Linked List (Linked List, Google): Check cycle. Solution: Floyd’s Cycle Detection (slow/fast pointers). Time: O(N).
13. Merge Two Sorted Linked Lists (Linked List, Meta): Merge into one. Solution: Recursive or iterative dummy node. Time: O(N+M).
14. Remove Loop in Linked List (Linked List, Amazon): Detect and remove cycle. Solution: Floyd’s, then move one pointer from head.
15. Check if Linked List is Palindrome (Linked List, Google): Verify palindrome. Solution: Reverse second half, compare.
16. Parenthesis Checker (Stack/Queue, Microsoft): Validate brackets. Solution: Stack for matching. Time: O(N).
17. Next Larger Element (Stack/Queue, Amazon): Find next greater for each. Solution: Monotonic stack. Time: O(N).
18. Get Minimum Element from Stack (Stack/Queue, Google): Design min stack. Solution: Auxiliary stack or single with encoding.
19. LRU Cache (Stack/Queue, Meta): Implement LRU. Solution: HashMap + Doubly Linked List. Time: O(1) get/put.
20. Rotten Oranges (Stack/Queue, Amazon): Time to rot all oranges. Solution: BFS from rotten. Time: O(M*N).
21. Print Left View of Binary Tree (Tree, Google): Leftmost nodes per level. Solution: Level order, print first per level.
22. Check for BST (Tree, Microsoft): Validate BST. Solution: Inorder traversal sorted check.
23. Lowest Common Ancestor in BST (Tree, Amazon): Find LCA. Solution: Traverse based on values.
24. Height of Binary Tree (Tree, Meta): Compute max depth. Solution: Recursive postorder.
25. Diameter of Binary Tree (Tree, Google): Longest path. Solution: Height + max left/right diameters.
26. Depth First Traversal (Graph, Amazon): DFS on graph. Solution: Recursive or stack.
27. Breadth First Traversal (Graph, Google): BFS. Solution: Queue.
28. Detect Cycle in Undirected Graph (Graph, Meta): Check cycle. Solution: Union-Find or DFS parent check.
29. Topological Sort (Graph, Microsoft): Linear ordering. Solution: Kahn’s BFS or DFS.
30. Find the Number of Islands (Graph, Amazon): Count connected components. Solution: DFS/BFS flood fill.

System Design Questions

From recent interviews:

• Design a URL Shortener: Use hash for short codes, database for mapping. Handle collisions with custom hash.
• Design a Ride-Sharing App: Components – users, drivers, matching algo (geohash), databases (NoSQL for locations).