Skip to content

Instantly share code, notes, and snippets.

@ffernand

ffernand/Complete DSA Guide for Google Interviews.mdx

Forked from carefree-ladka/Complete DSA Guide for Google Interviews.mdx
Created May 10, 2026 23:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ffernand/fcab56e8dd2b318c975da28712695ad5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ffernand/fcab56e8dd2b318c975da28712695ad5 to your computer and use it in GitHub Desktop.
Download ZIP
Complete DSA Guide for Google Interviews
Raw
Complete DSA Guide for Google Interviews.mdx

Complete DSA Guide for Google Interviews

https://gist.github.com/carefree-ladka/965124eb973eb448ad117016013ec0ec

image

📚 Essential Learning Resources

Documentation & Guides

Video Resources

Practice Platforms

Table of Contents

  1. Arrays & Strings
  2. Hashing (Map/Set)
  3. Intervals & Line Sweep
  4. Important Algorithms
  5. Searching & Sorting
  6. Linked Lists
  7. Stacks & Queues
  8. Recursion & Backtracking
  9. Trees
  10. Graphs
  11. Heaps/Priority Queue
  12. Greedy Algorithms
  13. Dynamic Programming
  14. Tries
  15. Bit Manipulation
  16. Math & Number Theory
  17. Advanced Topics
  18. System Design Foundations
  19. Google Interview Tips

Arrays & Strings

Core Topics

  • Array traversal (forward, backward, nested)
  • Prefix sum and suffix sum
  • Difference array
  • In-place modifications (constant space)
  • Custom sorting with comparators
  • Frequency arrays and counting
  • String parsing and manipulation
  • Character encoding (ASCII, Unicode)
  • String builders for efficiency

Key Patterns

  • Sliding Window (fixed and variable size)
  • Two Pointers (same direction, opposite direction)
  • Prefix Sum + HashMap (subarray problems)
  • Kadane's Algorithm (maximum subarray)
  • Cyclic Sort (missing/duplicate numbers)
  • Dutch National Flag (three-way partitioning)
  • Expand Around Center (palindromes)
  • Fast & Slow Pointers (cycle detection in arrays)
  • Matrix traversal (spiral, diagonal, layer-by-layer)

Common Problems

  • Rotate array
  • Product of array except self
  • Trapping rain water
  • Container with most water
  • Longest substring without repeating characters
  • Minimum window substring
  • String compression
  • Zigzag conversion

🔗 Practice Problems

Easy:

Medium:

Hard:

Hashing (Map/Set)

Core Topics

  • HashMap vs Object vs Map (language-specific)
  • Hash collisions and resolution strategies
  • Frequency counting
  • Grouping and bucketing
  • Set operations (union, intersection, difference)
  • LinkedHashMap for insertion order
  • Custom hash functions

Key Patterns

  • Two Sum / k-Sum variants
  • Anagram grouping
  • Subarray sum equals K
  • Longest substring with constraints
  • Seen-before logic (first unique, duplicates)
  • Complement pattern (pair finding)
  • Rolling hash (Rabin-Karp for pattern matching)

Common Problems

  • Group anagrams
  • Top K frequent elements
  • Longest consecutive sequence
  • Subarray sum divisible by K
  • Count distinct elements in window

🔗 Practice Problems

Easy:

Medium:

Hard:

Intervals & Line Sweep

Core Concepts

  • Interval representation [start, end]
  • Overlapping intervals
  • Merging intervals
  • Sorting by start/end times
  • Event-based processing
  • Sweep line technique

Key Patterns

Interval Merging

  • Sort by start time
  • Iterate and merge overlapping intervals
  • Track current interval

Interval Intersection

  • Two-pointer approach
  • Check overlap conditions
  • Generate intersection intervals

Interval Scheduling

  • Sort by end time (greedy)
  • Select non-overlapping intervals
  • Maximum activities selection

Line Sweep

  • Convert intervals to events (start/end)
  • Sort events by time
  • Process events in order
  • Track active intervals count
  • Use for overlap detection

Common Problems

  • Merge Intervals
  • Insert Interval
  • Interval List Intersections
  • Non-overlapping Intervals (minimum removals)
  • Meeting Rooms (I, II)
  • Minimum Number of Arrows (burst balloons)
  • My Calendar (I, II, III)
  • Car Pooling
  • Corporate Flight Bookings
  • The Skyline Problem (advanced)
  • Rectangle Area (overlap/union)
  • Perfect Rectangle
  • Employee Free Time
  • Remove Covered Intervals
  • Video Stitching

Line Sweep Applications

  • Finding maximum overlapping intervals
  • Range queries with updates
  • Coordinate compression
  • 2D geometry problems
  • Event scheduling conflicts

🔗 Practice Problems

Easy:

Medium:

Hard:

Important Algorithms

Kadane's Algorithm

Purpose: Maximum subarray sum

Concept:

  • Track current sum and global max
  • Reset current sum if it becomes negative
  • O(n) time, O(1) space

Applications:

  • Maximum subarray sum
  • Maximum product subarray (variant)
  • Maximum circular subarray
  • Maximum sum rectangle in 2D array
  • Best time to buy and sell stock

Implementation Pattern:

maxSum = -infinity
currentSum = 0

for each element:
    currentSum = max(element, currentSum + element)
    maxSum = max(maxSum, currentSum)

Boyer-Moore Majority Vote Algorithm

Purpose: Find element appearing > n/2 times

Concept:

  • Maintain candidate and count
  • Cancel out different elements
  • O(n) time, O(1) space

Applications:

  • Majority element (> n/2)
  • Majority element II (> n/3) - needs 2 candidates
  • Finding dominant elements

Implementation Pattern:

candidate = null
count = 0

for each element:
    if count == 0:
        candidate = element
    count += (element == candidate) ? 1 : -1

// Verify candidate appears > n/2 times

Quick Select (Hoare's Selection Algorithm)

Purpose: Find kth smallest/largest element

Concept:

  • Partition array like quicksort
  • Only recurse on relevant partition
  • Average O(n), worst O(n²)

Applications:

  • Kth largest/smallest element
  • Top K elements (alternative to heap)
  • Median finding
  • Quick select with random pivot (better average case)

Implementation Pattern:

function quickSelect(arr, k):
    pivot = partition(arr)
    if pivot == k:
        return arr[pivot]
    elif pivot > k:
        recurse on left partition
    else:
        recurse on right partition

Two Pointers Algorithm

Purpose: Optimize array/string problems from O(n²) to O(n)

Variants:

  1. Opposite Direction (start and end)

    • Two sum in sorted array
    • Container with most water
    • Valid palindrome
    • Trapping rain water

  2. Same Direction (slow and fast)

    • Remove duplicates
    • Move zeros
    • Partition problems

  3. Sliding Window (extension of two pointers)

    • Fixed size windows
    • Variable size windows

Floyd's Cycle Detection (Tortoise and Hare)

Purpose: Detect cycles in linked list/array

Concept:

  • Slow pointer moves 1 step
  • Fast pointer moves 2 steps
  • If cycle exists, they meet
  • O(n) time, O(1) space

Applications:

  • Linked list cycle detection
  • Find cycle start point
  • Find duplicate number (treating array as linked list)
  • Happy number problem

Finding Cycle Start:

1. Detect cycle (slow meets fast)
2. Reset slow to start
3. Move both one step at a time
4. Meeting point is cycle start

Sliding Window Algorithm

Purpose: Optimize substring/subarray problems

Types:

  1. Fixed Size Window

    • Maximum sum of k consecutive elements
    • Average of subarrays of size k

  2. Variable Size Window

    • Longest substring without repeating characters
    • Minimum window substring
    • Longest substring with at most k distinct

Pattern:

left = 0
for right in range(n):
    add arr[right] to window
    
    while window invalid:
        remove arr[left] from window
        left++
    
    update result

Dutch National Flag (3-Way Partitioning)

Purpose: Partition array into three sections

Concept:

  • Three pointers: low, mid, high
  • Elements < pivot go left
  • Elements == pivot stay middle
  • Elements > pivot go right
  • O(n) time, O(1) space

Applications:

  • Sort colors (0s, 1s, 2s)
  • Three-way quicksort
  • Partition array by pivot

KMP (Knuth-Morris-Pratt) Algorithm

Purpose: Efficient pattern matching

Concept:

  • Preprocess pattern to build LPS array
  • Avoid redundant comparisons
  • O(m + n) time vs O(m*n) naive

Applications:

  • String pattern matching
  • Repeated substring pattern
  • Shortest palindrome

Rabin-Karp Algorithm

Purpose: Pattern matching using rolling hash

Concept:

  • Hash the pattern
  • Roll hash through text
  • Compare only on hash match
  • Average O(m + n), worst O(m*n)

Applications:

  • Multiple pattern matching
  • Plagiarism detection
  • Longest duplicate substring

Union-Find (Disjoint Set Union)

Purpose: Track connected components efficiently

Operations:

  • find(x) - find root with path compression
  • union(x, y) - merge sets with union by rank

Time Complexity:

  • Nearly O(1) per operation with optimizations

Applications:

  • Number of connected components
  • Detect cycles in undirected graph
  • Kruskal's MST
  • Accounts merge
  • Redundant connection

Monotonic Stack/Queue

Purpose: Maintain elements in monotonic order

Monotonic Stack:

  • Next greater/smaller element
  • Largest rectangle in histogram
  • Trapping rain water

Monotonic Queue (Deque):

  • Sliding window maximum/minimum
  • Jump game variations

🔗 Practice Problems (Kadane's)

🔗 Practice Problems (Boyer-Moore)

🔗 Practice Problems (Quick Select)

🔗 Practice Problems (Union-Find)

Searching & Sorting

Searching

Sorting

  • Quick sort (and its variants)
  • Merge sort (and external sorting)
  • Counting sort
  • Radix sort
  • Bucket sort
  • Heap sort
  • Custom comparator logic
  • Stability in sorting
  • External sorting concepts

Key Patterns

  • Binary Search on monotonic condition
  • Divide & Conquer
  • Partitioning strategies
  • Invariant maintenance

🔗 Practice Problems

Binary Search:

Sorting:

Linked Lists

Core Topics

  • Singly linked list
  • Doubly linked list
  • Circular linked list
  • Fast & slow pointers (Floyd's algorithm)
  • Sentinel/dummy nodes
  • In-place modifications

Key Patterns

  • Reverse list (full/partial/k-groups)
  • Detect and remove cycle (Floyd's)
  • Find middle node
  • Merge sorted lists
  • K-group reversal
  • Copy list with random pointer
  • Intersection of lists
  • Palindrome check
  • Reorder list
  • Flatten multilevel list

Common Problems

  • Add two numbers
  • Remove Nth node from end
  • Rotate list
  • Sort list
  • Partition list

🔗 Practice Problems

Easy:

Medium:

Hard:

Stacks & Queues

Stack Patterns

  • Monotonic stack (increasing/decreasing)
  • Next greater/smaller element
  • Valid parentheses and variants
  • Expression evaluation (infix, postfix, prefix)
  • Histogram problems (largest rectangle)
  • Stock span problem
  • Decode string
  • Simplify path
  • Min/Max stack

Queue/Deque Patterns

  • Sliding window maximum (deque)
  • BFS (level-order traversal)
  • Circular queue
  • Design queue using stacks
  • Moving average from data stream
  • Recent counter/time-based problems

🔗 Practice Problems

Stack:

Queue/Deque:

Recursion & Backtracking

Core Topics

  • Call stack and memory
  • Base case design
  • Choice–Explore–Unchoose paradigm
  • Pruning techniques
  • State management
  • Tail recursion optimization

Key Patterns

  • Subsets (with/without duplicates)
  • Permutations (with/without duplicates)
  • Combinations
  • Combination sum (variants)
  • Palindrome partitioning
  • Sudoku solver
  • N-Queens
  • Word search (grid backtracking)
  • Generate parentheses
  • Letter combinations
  • Expression add operators
  • Restore IP addresses

🔗 Practice Problems

Medium:

Hard:

Trees

Binary Tree Fundamentals

  • DFS traversals (preorder, inorder, postorder)
  • BFS/Level order traversal
  • Height and depth
  • Diameter calculation
  • Path sum problems
  • Balanced tree check
  • Symmetric tree
  • Serialize/Deserialize
  • Iterative traversals using stack

Binary Search Tree (BST)

  • Insert/Delete/Search operations
  • Validate BST
  • Lowest Common Ancestor (LCA)
  • Kth smallest/largest element
  • Range sum query
  • Inorder successor/predecessor
  • Convert sorted array to BST
  • BST iterator

Advanced Tree Patterns

  • Tree paths (root to leaf, any path)
  • Tree pruning
  • Tree flattening
  • Boundary traversal
  • Vertical order traversal
  • Diagonal traversal
  • View problems (left, right, top, bottom)
  • Morris traversal (constant space)
  • Threaded binary trees
  • Construct tree from traversals
  • Maximum path sum

N-ary Trees

  • Traversal variations
  • Level order with null markers
  • Encode/decode

🔗 Practice Problems

Easy:

Medium:

Hard:

Graphs

Graph Basics

  • Adjacency list vs matrix
  • Directed vs undirected
  • Weighted vs unweighted
  • Sparse vs dense graphs
  • Edge list representation

Traversals

  • BFS (shortest path in unweighted)
  • DFS (recursive + iterative)
  • Multi-source BFS
  • Bidirectional BFS

Core Patterns

  • Connected components
  • Cycle detection (directed using colors, undirected using parent)
  • Topological sort (Kahn's algorithm + DFS)
  • Shortest path (BFS, Dijkstra, Bellman-Ford)
  • Union Find (DSU) (path compression, union by rank)
  • Flood fill
  • Bipartite graph check
  • Strongly connected components (Kosaraju's, Tarjan's)
  • Minimum spanning tree (Kruskal's, Prim's)
  • Bridges and articulation points
  • Eulerian path/circuit

Advanced Graph Problems

  • Course schedule variations
  • Word ladder
  • Alien dictionary
  • Network delay time
  • Cheapest flights within K stops
  • Critical connections (bridges)
  • Reconstruct itinerary (Eulerian path)
  • Evaluate division
  • Accounts merge (Union-Find)
  • Clone graph
  • Smallest string with swaps (Union-Find)
  • Optimize water distribution

🔗 Practice Problems

Medium:

Hard:

Heaps/Priority Queue

Core Topics

  • Min heap and max heap
  • Heapify operation
  • Custom comparators
  • Heap as array representation
  • Building heap from array (O(n))

Key Patterns

  • Top K elements (K largest/smallest)
  • Kth largest/smallest
  • Merge K sorted lists/arrays
  • Sliding window median
  • Median from data stream (two heaps)
  • Task scheduling problems
  • Meeting rooms variations
  • K closest points
  • Reorganize string
  • Find K pairs with smallest sum
  • IPO problem (maximize capital)

🔗 Practice Problems

Easy:

Medium:

Hard:

Greedy Algorithms

Core Concepts

  • Greedy choice property
  • Optimal substructure
  • Proof of correctness
  • When greedy works vs when it doesn't

Key Patterns

  • Interval scheduling (activity selection)
  • Merge intervals
  • Minimum platforms/meeting rooms
  • Jump game (I, II)
  • Gas station
  • Candy distribution
  • Partition labels
  • Remove K digits
  • Bag of tokens
  • Queue reconstruction
  • Fractional knapsack
  • Huffman encoding (conceptual)

🔗 Practice Problems

Easy:

Medium:

Hard:

Dynamic Programming

Fundamentals

  • Overlapping subproblems
  • Optimal substructure
  • Memoization (top-down) vs Tabulation (bottom-up)
  • State definition and transitions
  • Space optimization techniques
  • Identifying DP problems

1D DP

  • Fibonacci variations
  • House robber
  • Climbing stairs
  • Decode ways
  • Maximum product subarray
  • Coin change (ways and minimum)
  • Perfect squares
  • Integer break

2D DP

  • Grid paths
    • Unique paths
    • Unique paths with obstacles
    • Min path sum
    • Dungeon game
    • Cherry pickup

Subsequence DP

  • Longest Common Subsequence (LCS)
  • Longest Increasing Subsequence (LIS)
  • Edit distance (Levenshtein)
  • Longest palindromic subsequence
  • Shortest common supersequence
  • Distinct subsequences
  • Minimum ASCII delete sum

Knapsack Family

  • 0/1 knapsack
  • Unbounded knapsack
  • Subset sum
  • Partition equal subset sum
  • Target sum
  • Last stone weight II

DP on Strings

  • Palindrome partitioning (I, II, III)
  • Word break (I, II)
  • Regex matching
  • Wildcard matching
  • Interleaving strings
  • Scramble string

DP on Trees

  • Tree DP fundamentals
  • Maximum path sum (any to any)
  • House robber III
  • Binary tree cameras
  • Longest univalue path

Interval DP

  • Burst balloons
  • Minimum cost tree from leaf values
  • Remove boxes
  • Strange printer

Bitmask DP

  • State compression techniques
  • Traveling salesman problem (TSP)
  • Partition to K equal sum subsets
  • Minimum XOR sum of two arrays
  • Maximum students taking exam

Game Theory DP

  • Stone game variations
  • Predict the winner
  • Cat and mouse game

Advanced DP Patterns

  • Digit DP
  • DP with optimization (monotonic queue, divide and conquer)
  • Probability DP
  • Expected value DP

🔗 Practice Problems

1D DP:

2D DP:

Knapsack:

Advanced:

📚 DP Learning Resources

Tries

Core Topics

  • Insert, search, prefix search
  • Trie node structure
  • Trie vs HashMap tradeoffs
  • Space optimization (compressed trie)
  • Delete operations

Key Patterns

  • Word search (grid + trie)
  • Auto complete/suggestions
  • Replace words
  • Longest word in dictionary
  • XOR maximum problems (binary trie)
  • Design search autocomplete system
  • Map sum pairs
  • Stream of characters

🔗 Practice Problems

Medium:

Hard:

Bit Manipulation

Core Topics

  • Bitwise operators (AND, OR, XOR, NOT)
  • Left shift and right shift
  • Two's complement
  • Signed vs unsigned
  • Bitwise tricks and optimizations

Key Patterns

  • Single number (variants I, II, III)
  • Power of two
  • Count set bits (Hamming weight)
  • Subsets using bitmask
  • XOR tricks (swap without temp, missing number)
  • Gray code
  • Reverse bits
  • Number complement
  • Maximum XOR (binary trie)
  • Bitwise AND of numbers range
  • Divide two integers (bit manipulation)

🔗 Practice Problems

Easy:

Medium:

Math & Number Theory

Topics

  • GCD/LCM (Euclidean algorithm)
  • Prime numbers
    • Sieve of Eratosthenes
    • Prime factorization
    • Count primes
  • Modular arithmetic
    • Properties
    • Modular inverse
    • Fast exponentiation (binary exponentiation)
  • Combinations & permutations
  • Pascal's triangle
  • Catalan numbers
  • Probability basics
  • Matrix operations
    • Multiplication
    • Rotation
    • Spirals
  • Number systems (binary, decimal, hex)
  • Perfect squares/cubes
  • Ugly numbers
  • Happy numbers

Advanced Topics

Segment Tree

  • Build, query, update
  • Range sum/min/max queries
  • Lazy propagation
  • Applications in range problems

Fenwick Tree (Binary Indexed Tree)

  • Build and query
  • Range sum queries
  • Point updates
  • 2D Fenwick tree

Sweep Line Algorithm

  • Interval problems
  • Skyline problem
  • Rectangle overlap/area

Geometry Basics

  • Point, line, and segment operations
  • Convex hull
  • Closest pair of points
  • Line intersection

Randomized Algorithms

  • Quick select (randomized)
  • Reservoir sampling
  • Random pick with weight
  • Shuffle array

String Algorithms

  • KMP (Knuth-Morris-Pratt pattern matching)
  • Rabin-Karp (rolling hash)
  • Z-algorithm
  • Manacher's algorithm (longest palindrome in O(n))
  • Suffix array
  • LCP array (Longest Common Prefix)
  • Aho-Corasick (multiple pattern matching)
  • Boyer-Moore (pattern matching with bad character/good suffix rules)

Monotonic Queue/Deque

  • Sliding window problems
  • Jump game variations

Disjoint Set Union (Advanced)

  • Path compression
  • Union by rank/size
  • Applications beyond basic union-find

System Design Foundations

While not strictly DSA, Google interviews may touch on:

  • Scalability concepts
  • Caching strategies (LRU, LFU cache)
  • Rate limiting (token bucket, leaky bucket)
  • Consistent hashing
  • Load balancing basics
  • Database indexing (B-trees, hash indexes)
  • Distributed systems concepts (CAP theorem basics)
  • Design problems
    • Design Twitter/Instagram feed
    • Design URL shortener
    • Design LRU cache
    • Design hit counter
    • Design rate limiter

Google Interview Tips

What Google Emphasizes

  1. Problem Decomposition

    • Break complex problems into manageable parts
    • Identify subproblems
    • Explain your thought process

  2. Clear State Definition (especially DP)

    • Define what each state represents
    • Explain transitions
    • Justify correctness

  3. Edge Cases

    • Empty inputs
    • Single elements
    • Duplicates
    • Null/undefined
    • Integer overflow
    • Negative numbers

  4. Time-Space Tradeoffs

    • Discuss multiple approaches
    • Optimize when asked
    • Know when to use extra space

  5. Code Quality

    • Readable variable names
    • Modular functions
    • Clean logic flow
    • Consistent style

  6. Communication

    • Think aloud
    • Ask clarifying questions
    • Explain before coding
    • Test your solution

Practice Strategy

  • LeetCode patterns: Focus on medium/hard problems
  • Mock interviews: Practice explaining solutions
  • Time yourself: Aim for 30-35 minutes per problem
  • Review solutions: Learn optimal approaches
  • Weekly targets:
    • 15-20 problems for active prep
    • Focus on weak areas
    • Revisit problems after a week

Interview Day

  • Clarify requirements and constraints
  • Discuss brute force first (shows problem understanding)
  • Optimize before coding (saves time)
  • Write clean code with good variable names
  • Test with examples (normal, edge, large)
  • Be open to hints and feedback

Priority Order for Study

Must Master (Core)

  1. Arrays & Strings
  2. Important Algorithms (Kadane's, Boyer-Moore, Quick Select, etc.)
  3. Intervals & Line Sweep
  4. Hashing
  5. Trees (especially BST)
  6. Graphs (BFS/DFS/shortest path)
  7. Dynamic Programming
  8. Binary Search

High Priority

  1. Heaps/Priority Queue
  2. Stacks & Queues
  3. Linked Lists
  4. Recursion & Backtracking

Important

  1. Greedy
  2. Tries
  3. Bit Manipulation
  4. Sorting algorithms

Advanced (Differentiators)

  1. Segment Tree/Fenwick Tree
  2. Advanced graph algorithms
  3. String algorithms
  4. Bitmask DP

Remember: Google values problem-solving ability and clear communication over memorization. Focus on understanding patterns and explaining your reasoning!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment