Complete DSA Guide for SDE Interviews
Product-Based Companies | 4+ Years Experience
Table of Contents
1. Introduction
2. Algorithm Templates
3. Data Structure Cheat Sheet
4. Important Questions by Topic
5. Company-Specific Questions
6. Time Complexity Cheat Sheet
7. Interview Tips & Tricks
Introduction
This comprehensive guide is designed for Software Development Engineers with 4+ years of
experience preparing for interviews at product-based companies like Google, Amazon,
Microsoft, Facebook, and other top tech companies.
What's Included:
✅ 7+ Algorithm Templates with Code
✅ 8+ Data Structure Reference
✅ 60+ Important Interview Questions
✅ Company-specific Question Lists
✅ Time/Space Complexity Reference
✅ Expert Interview Tips
Algorithm Templates
1. Two Pointers Pattern
When to Use: Sorted arrays, palindromes, pair finding
Time Complexity: O(n)
Space Complexity: O(1)
def two_pointers_template(arr):
left, right = 0, len(arr) - 1
while left < right:
# Check condition
if arr[left] + arr[right] == target:
return [left, right]
elif arr[left] + arr[right] < target:
left += 1
else:
right -= 1
return [-1, -1]
Common Problems: Two Sum II, Container With Most Water, Trapping Rain Water
2. Sliding Window Pattern
When to Use: Subarray/substring problems with size constraint
Time Complexity: O(n)
Space Complexity: O(1)
def sliding_window_template(arr, k):
if len(arr) < k:
return -1
# Initialize first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
Common Problems: Maximum Average Subarray, Longest Substring Without Repeating
Characters
3. Binary Search Pattern
When to Use: Sorted arrays, search space reduction
Time Complexity: O(log n)
Space Complexity: O(1)
def binary_search_template(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Common Problems: Search Insert Position, Find Peak Element, Search in Rotated Array
4. DFS (Depth-First Search) Pattern
When to Use: Tree/graph traversal, pathfinding
Time Complexity: O(V + E)
Space Complexity: O(V)
# For Trees
def dfs_tree_template(root):
if not root:
return
# Preorder: process current node first
result.append(root.val)
# Recursively traverse children
dfs_tree_template(root.left)
dfs_tree_template(root.right)
# For Graphs
def dfs_graph_template(node, visited, graph):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_graph_template(neighbor, visited, graph)
Common Problems: Binary Tree Traversals, Number of Islands, Path Sum
5. BFS (Breadth-First Search) Pattern
When to Use: Level-order traversal, shortest path
Time Complexity: O(V + E)
Space Complexity: O(V)
from collections import deque
def bfs_template(start, graph):
queue = deque([start])
visited = {start}
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
Common Problems: Binary Tree Level Order, Word Ladder, Minimum Depth
6. Backtracking Pattern
When to Use: All possible solutions, permutations, combinations
Time Complexity: Exponential
Space Complexity: O(depth)
def backtrack_template(path, choices, result):
# Base case
if is_valid_solution(path):
result.append(path[:])
return
# Try all possible choices
for choice in choices:
if is_valid_choice(choice, path):
path.append(choice)
backtrack_template(path, get_remaining_choices(), result)
path.pop() # backtrack
Common Problems: Permutations, N-Queens, Sudoku Solver
7. Dynamic Programming Pattern
When to Use: Overlapping subproblems, optimal substructure
Time Complexity: Varies
Space Complexity: O(n) to O(n²)
# Bottom-up approach
def dp_bottom_up(n):
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
dp[i] = min/max(dp[i-1] + cost, dp[i-2] + cost, ...)
return dp[n]
# Top-down with memoization
def dp_memoization(n, memo={}):
if n in memo:
return memo[n]
if n <= base_case:
return base_case_value
memo[n] = recurrence_relation(n)
return memo[n]
Common Problems: Fibonacci, Climbing Stairs, Coin Change, Edit Distance
Data Structure Cheat Sheet
Array
Access: O(1) | Search: O(n) | Insert: O(n) | Delete: O(n)
Use Cases: Random access, mathematical operations, simple data storage
Pros: Cache-friendly, simple, constant time access
Cons: Fixed size, expensive insertions/deletions
Linked List
Access: O(n) | Search: O(n) | Insert: O(1) | Delete: O(1)
Use Cases: Dynamic size, frequent insertions/deletions
Pros: Dynamic size, efficient insert/delete
Cons: No random access, extra memory overhead
Stack (LIFO)
Push: O(1) | Pop: O(1) | Peek: O(1)
Use Cases: Function calls, undo operations, expression evaluation
Implementation: Array or Linked List
Queue (FIFO)
Enqueue: O(1) | Dequeue: O(1) | Front: O(1)
Use Cases: BFS, task scheduling, buffer
Implementation: Array with two pointers or Linked List
Hash Table
Search: O(1) avg | Insert: O(1) avg | Delete: O(1) avg
Use Cases: Fast lookups, caching, counting
Collision Resolution: Chaining, Open Addressing
Binary Search Tree
Search: O(log n) avg | Insert: O(log n) avg | Delete: O(log n) avg
Use Cases: Sorted data, range queries
Note: Can degrade to O(n) if unbalanced
Heap (Priority Queue)
Insert: O(log n) | Extract Min/Max: O(log n) | Peek: O(1)
Use Cases: Priority scheduling, finding kth element
Types: Min-heap, Max-heap
Graph
Representation: Adjacency List O(V+E), Adjacency Matrix O(V²)
Use Cases: Networks, relationships, dependencies
Algorithms: DFS, BFS, Dijkstra, Kruskal
Important Questions by Topic
📊 Arrays (Must Know)
1. Two Sum - Hash map approach
2. Maximum Subarray (Kadane's Algorithm) - DP approach
3. Merge Intervals - Sorting + merging
4. Rotate Array - Reversal technique
5. Container With Most Water - Two pointers
6. 3Sum - Two pointers + sorting
7. Product of Array Except Self - Prefix/suffix products
8. Best Time to Buy and Sell Stock - One pass
9. Find Minimum in Rotated Sorted Array - Binary search
10. Search in Rotated Sorted Array - Modified binary search
🔗 Linked Lists (Must Know)
1. Reverse Linked List - Iterative and recursive
2. Merge Two Sorted Lists - Two pointers
3. Linked List Cycle - Floyd's algorithm
4. Remove Nth Node From End - Two pass/one pass
5. Intersection of Two Linked Lists - Two pointers
6. Add Two Numbers - Digit by digit addition
7. Copy List with Random Pointer - Hash map
8. Merge k Sorted Lists - Divide and conquer
9. Reorder List - Find middle + reverse + merge
10. Swap Nodes in Pairs - Iterative swapping
🌳 Trees (Must Know)
1. Binary Tree Inorder Traversal - Recursive/iterative
2. Maximum Depth of Binary Tree - DFS/BFS
3. Same Tree - Recursive comparison
4. Invert Binary Tree - Recursive/iterative
5. Binary Tree Level Order Traversal - BFS
6. Validate Binary Search Tree - Inorder/bounds checking
7. Lowest Common Ancestor - Path finding
8. Binary Tree Maximum Path Sum - DFS with global max
9. Serialize and Deserialize Binary Tree - Preorder
10. Construct Binary Tree from Preorder and Inorder - Recursion
🕸️Graphs (Must Know)
1. Number of Islands - DFS/BFS
2. Course Schedule - Topological sort
3. Clone Graph - DFS/BFS with hash map
4. Pacific Atlantic Water Flow - DFS from borders
5. Word Ladder - BFS
6. Network Delay Time - Dijkstra's algorithm
7. Minimum Spanning Tree - Kruskal/Prim
8. Shortest Path in Binary Matrix - BFS
9. Alien Dictionary - Topological sort
10. Critical Connections in Network - Tarjan's algorithm
💰 Dynamic Programming (Must Know)
1. Climbing Stairs - Basic DP
2. House Robber - DP with choice
3. Coin Change - Unbounded knapsack
4. Longest Increasing Subsequence - DP/Binary search
5. Unique Paths - 2D DP
6. Edit Distance - 2D DP
7. Maximum Product Subarray - Track min/max
8. Word Break - DP with dictionary
9. Palindromic Substrings - Expand around centers
10. Longest Common Subsequence - 2D DP
🔤 Strings (Must Know)
1. Longest Substring Without Repeating Characters - Sliding window
2. Longest Palindromic Substring - Expand around centers
3. Valid Anagram - Sorting/counting
4. Group Anagrams - Hash map with sorted keys
5. Longest Common Prefix - Vertical/horizontal scanning
6. Valid Parentheses - Stack
7. Palindrome Check - Two pointers
8. String to Integer (atoi) - State machine
9. Implement strStr() - KMP/Two pointers
10. Letter Combinations of Phone Number - Backtracking
Company-Specific Questions
🔍 Google (Focus: Algorithms & Math)
Find Missing and Repeating Number
Stock Buy and Sell (Multiple variations)
Next Permutation
Longest Valid Parentheses
Median in Data Stream
Maximum Rectangular Area in Histogram
Implement LRU Cache
Find Number of Closed Islands
Sorted Linked List to BST
📦 Amazon (Focus: Arrays & Strings)
Two Sum (All variations)
Add Two Numbers (Linked List)
Longest Substring Without Repeating Characters
LRU Cache Implementation
Trapping Rain Water
Word Break Problem
Number of Islands
Merge Intervals
Top K Frequent Elements
🪟 Microsoft (Focus: Trees & Graphs)
Reverse Integer
String to Integer (atoi)
Container With Most Water
Longest Common Prefix
Valid Parentheses
Binary Tree Level Order Traversal
Word Ladder
Clone Graph
Serialize and Deserialize Binary Tree
👥 Meta/Facebook (Focus: Data Structures)
Two Sum
Add Binary
Merge Intervals
Valid Number
Binary Tree Vertical Order Traversal
Remove Invalid Parentheses
Subarray Sum Equals K
Basic Calculator
Alien Dictionary
Time Complexity Cheat Sheet
Sorting Algorithms
QuickSort: Average O(n log n), Worst O(n²)
MergeSort: O(n log n) - Guaranteed
HeapSort: O(n log n) - Guaranteed
BubbleSort: O(n²)
InsertionSort: O(n²) - Good for small arrays
SelectionSort: O(n²)
RadixSort: O(d × n) where d is digits
Search Algorithms
Binary Search: O(log n) - Sorted array
Linear Search: O(n)
DFS: O(V + E) - Graph traversal
BFS: O(V + E) - Graph traversal
Data Structure Operations
┌─────────────────┬─────────┬─────────┬─────────┬─────────┐
│ Data Structure │ Access │ Search │ Insert │ Delete │
├─────────────────┼─────────┼─────────┼─────────┼─────────┤
│ Array │ O(1) │ O(n) │ O(n) │ O(n) │
│ Stack │ O(n) │ O(n) │ O(1) │ O(1) │
│ Queue │ O(n) │ O(n) │ O(1) │ O(1) │
│ Linked List │ O(n) │ O(n) │ O(1) │ O(1) │
│ Hash Table │ - │ O(1) │ O(1) │ O(1) │
│ Binary Tree │ O(log n)│ O(log n)│ O(log n)│ O(log n)│
│ Binary Heap │ - │ O(n) │ O(log n)│ O(log n)│
└─────────────────┴─────────┴─────────┴─────────┴─────────┘
Interview Tips & Tricks
🎯 Problem-Solving Approach
1. Understand the Problem
Read carefully and ask clarifying questions
Identify inputs, outputs, and constraints
Work through examples manually
2. Plan Your Solution
Start with brute force approach
Identify patterns and optimizations
Choose appropriate data structures
3. Implement Clean Code
Use meaningful variable names
Handle edge cases
Write modular, readable code
4. Test and Debug
Walk through with examples
Consider edge cases
Analyze time and space complexity
🧠 Mental Models
When to Use Each Pattern:
Two Pointers: Sorted array, pair problems
Sliding Window: Subarray with constraint
Binary Search: Sorted data, search space reduction
DFS: Tree problems, connected components
BFS: Shortest path, level-order
Backtracking: All solutions, permutations
DP: Optimal substructure, overlapping subproblems
Greedy: Local optimum leads to global optimum
💡 Common Optimizations
1. Hash Maps for O(1) lookups
2. Two Pointers to avoid nested loops
3. Sorting to enable two pointers/binary search
4. Sliding Window for subarray problems
5. Memoization for recursive solutions
6. Early Termination when possible
🚀 Final Tips
Practice coding on whiteboard/paper
Time yourself during practice
Explain your thought process aloud
Know your favorite programming language well
Study system design for senior roles
Practice mock interviews
Focus on problem patterns, not just individual problems
Resources for Continued Learning
📚 Recommended Platforms
LeetCode: Problem practice with company tags
AlgoMonster: Pattern-based learning
Grokking the Coding Interview: Systematic approach
InterviewBit: Structured interview preparation
Pramp: Mock interview practice
📖 Books
"Cracking the Coding Interview" by Gayle McDowell
"Elements of Programming Interviews" by Aziz, Lee, Prakash
"Algorithm Design Manual" by Steven Skiena
Good Luck with Your Interviews! 🎉
Remember: Consistent practice and understanding patterns is more valuable than memorizing
solutions.
