Skip to content

readme.md

Latest commit

 

History

History
641 lines (514 loc) · 29.9 KB

readme.md

File metadata and controls

641 lines (514 loc) · 29.9 KB

📘 FAANG Staff / Engineering Manager Preparation Kit

This kit is designed for FAANG-level Staff Software Engineer & Engineering Manager roles.
It covers core DSA, advanced patterns, system design, and leadership prep.
Solve 250–300 problems across these patterns for maximum coverage.

Must watch video - https://www.youtube.com/watch?v=WRA5OfeUP9I

📘 DSA Prep

Linear

1. Array

  • Subarray problems
  • Kadane’s Algorithm
  • Prefix / Suffix arrays

2. String

  • Palindrome
  • Two Pointer
  • Pattern Matching → KMP, Rabin-Karp, Z-algorithm
  • Anagram / Substring problems

3. Stack & Queue

  • Expression Problems (Valid Parentheses, Min Stack, Expression Evaluation)
  • Tree Traversal support
  • Graph traversal support
  • Monotonic Stack / Queue (Next Greater, Sliding Window Max)
  • Deque (Double-ended Queue)

4. Linked List

  • Reverse a Linked List
  • Detect a Loop
  • Merge K Sorted Lists
  • LRU Cache Implementation

5. HashTable

  • Frequency counting
  • Caching / Memoization

Non-Linear

1. Trees

  • Traversals (Inorder, Preorder, Postorder, Level Order)
  • Height, Diameter, Balance check
  • Segment Tree / Fenwick Tree (Range Queries)

2. Binary Search Tree (BST)

  • Insert, Delete, Lookup
  • BFS, DFS
  • Balanced BST
  • Lowest Common Ancestor

3. Heaps & Priority Queue

  • Top K Problems
  • Streaming Data (moving average, median)
  • Dijkstra’s Shortest Path
  • Scheduling & Load balancing (e.g., Zomato assigning nearest delivery person)

4. Graphs

  • DFS / BFS
  • Topological Sort + Cycle Detection
  • Shortest Path (Dijkstra, Bellman-Ford, Floyd-Warshall, A*)
  • Minimum Spanning Tree (Kruskal / Prim)
  • Connectivity with Union-Find

5. Tries

  • Auto-complete
  • Spell Check
  • Word Search
  • Longest Common Prefix

6. Union Find (Disjoint Set)

  • Path Compression
  • Union by Rank
  • Dynamic connectivity problems

7. Matrix Problems

  • DFS/BFS in 2D grids (Islands, Word Search, Shortest Path in Matrix)

Algorithms

1. Sorting

  • Merge Sort
  • Quick Sort
  • Selection Sort
  • Heap Sort

2. Binary Search

  • Classic binary search
  • Variants (first/last occurrence, peak element, rotated sorted array)

3. Bit Manipulation

  • XOR tricks
  • Bit Masking
  • Subsets with bitmask
  • State Compression DP

4. Tree Traversals

  • DFS
  • BFS
  • Morris Traversal

5. Graph Traversals

  • BFS, DFS
  • Topological Sort
  • Connected Components

6. Shortest Path Algorithm

  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
  • A* (heuristics based)

7. Randomized / Streaming Algorithms

  • Reservoir Sampling
  • Consistent Hashing

Problem Solving Techniques

1. Two Pointer

  • Subarray problems
  • Pattern Matching & Optimization

2. Sliding Window

  • Variable size window (Longest substring)
  • Fixed size window (Max sum, moving averages)

3. Prefix Sum

  • Range queries
  • Difference array

4. Fast & Slow Pointer

  • Cycle detection (Floyd’s)
  • Middle of linked list

5. Divide and Conquer

  • Binary Search
  • Merge Sort / Quick Sort
  • Matrix Exponentiation

6. Greedy

  • Interval Scheduling
  • Huffman Encoding
  • Top K problems
  • Dijkstra’s Algorithm

7. Recursion

  • Base cases & recursive tree
  • Tail recursion

8. Backtracking

  • N-Queens
  • Sudoku Solver
  • Subsets, Permutations

9. Dynamic Programming

  • Start with Recursion + Memoization
  • 1D DP (Fibonacci, Climbing Stairs)
  • 2D DP (Grid Paths, LCS)
  • Knapsack, Coin Change
  • State Compression DP (TSP, scheduling)

10. Heap-based Techniques

  • Top K Elements
  • Streaming Median

11. Meet in the Middle

  • Subset Sum
  • Partition Problems

Placement Sheet ( https://docs.google.com/spreadsheets/d/16jJF7OohnOTGCCoqepDsv5FtnDwAG6Z1njvkcEHtHxw/edit?usp=sharing )

🔹 Problem Distribution (Target Breakdown)

1. Arrays & Strings → 40–50 problems

  • Patterns: Sliding Window, Two Pointers, Prefix Sum, Kadane’s Algorithm

2. Linked List → 25–30 problems

  • Patterns: Reverse, Detect Cycle, Merge K Lists, LRU Cache

3. Stack & Queue → 25–30 problems

  • Patterns: Min Stack, Valid Parentheses, Monotonic Stack, Queue via Stack

4. Binary Trees & BST → 40–50 problems

  • Patterns: DFS, BFS, Diameter, LCA, Serialize/Deserialize

5. Graphs → 30–40 problems

  • Patterns: BFS/DFS, Dijkstra, Union-Find, Topological Sort

6. Dynamic Programming (DP) → 50–60 problems

  • Patterns: Fibonacci, Coin Change, Knapsack, Longest Subsequence, Matrix Path

7. Tries & Strings (Advanced) → 15–20 problems

  • Patterns: Word Dictionary, Prefix Trees, MapSum, Word Search

8. Backtracking → 20 problems

  • Patterns: N-Queens, Sudoku Solver, Subsets, Permutations

9. Greedy → 15 problems

  • Patterns: Interval Scheduling, Gas Station, Jump Game

10. Miscellaneous → 20–30 problems

  • Patterns: Hashmaps, Heaps/Priority Queues, Bit Manipulation

🔹 Total Target

✅ 250–300 problems across all categories.
Focus on patterns, not repetition — solving a balanced set across these topics will make you interview-ready for FAANG-level roles.

📂 Table of Contents

  1. Stack
  2. Queue
  3. Linked List
  4. Tries
  5. Binary Search Trees & Traversals
  6. Sliding Window
  7. Two Pointer
  8. Dynamic Programming
  9. Backtracking
  10. Greedy
  11. Kadane’s Algorithm
  12. Tower of Hanoi
  13. Graphs
  14. Heaps & Priority Queues
  15. Hashing & HashMaps
  16. Bit Manipulation
  17. Math & Combinatorics
  18. System Design (Critical for Staff/EM)
  19. Leadership & Behavioral Prep

1. Stack

2. Queue

3. Linked List

4. Tries

5. Binary Search Trees & Traversals

6. Sliding Window

7. Two Pointer

8. Dynamic Programming

9. Backtracking

10. Greedy

11. Kadane’s Algorithm

12. Tower of Hanoi

  • Classic: Tower of Hanoi recursion (not on LeetCode)
  • Print all steps of Tower of Hanoi (custom implementation)
  • Variants: 4 Pegs (research problem, not on LeetCode)

13. Graphs

14. Heaps & Priority Queues

15. Hashing & HashMaps

16. Bit Manipulation

17. Math & Combinatorics

18. System Design (Critical for Staff/EM)

High-Level Design (HLD)

  • URL Shortener
  • Twitter/Instagram/WhatsApp
  • Google Docs (collaborative editing)
  • YouTube recommendation system
  • Distributed cache

Low-Level Design (LLD)

  • Parking Lot System
  • Elevator System
  • Food Delivery App
  • Rate Limiter
  • Notification System

Scalability Concepts

  • Load balancing, sharding, replication
  • CAP theorem, consistency models
  • Message queues (Kafka, RabbitMQ, SQS)
  • Caching strategies (LRU, LFU, write-through, write-back)
  • CDN design (CloudFront, Akamai)

19. Leadership & Behavioral Prep

  • Mentoring & growing engineers
  • Driving cross-team initiatives
  • Handling ambiguity and prioritization
  • Conflict resolution & communication
  • Delivering impact at org level

Practice STAR Method Stories:

  • Scaling systems you built (e.g., Zoom/VMware projects)
  • Mentorship examples (juniors → seniors)
  • Cross-functional collaboration (PMs, designers, customers)
  • Driving innovation (AI agents, serverless infra, etc.)

20. Core Algorithms & Techniques (Missing Additions)

🟢 Pointer Tricks

🟢 Searching / Sorting Variants

🟢 Tree & Graph Traversal

🟢 Graph Shortest Path / MST

🟢 Topological Sort & DAG DP

🟢 Dynamic Programming (Classics You’ll Be Asked)

🟢 Greedy / Interval / Sweep-Line

🟢 Math / Number Theory Essentials

🟢 String Algorithms (Pattern Matching & Friends)

🟢 Majority / Voting / Frequency

🟢 Monotonic Structures

🟢 Advanced Data Structures

🟢 Extras That Interviewers Love