11. What is the difference between BFS and DFS?
- BFS (Breadth-First Search): Explores neighbors first (level by level). Uses a queue.
- DFS (Depth-First Search): Explores depth (child nodes) first. Uses a stack or recursion.
Used in graph/tree traversals, pathfinding, cycle detection.
12. What is a Heap?
A binary tree with heap properties:
- Max-Heap: Parent ≥ children
- Min-Heap: Parent ≤ children
Used in priority queues, heap sort, scheduling algorithms.
13. What is a Trie?
A tree-like data structure used to store strings.
Each node represents a character.
Used in: autocomplete, spell-checkers, prefix search.
14. What is a Graph?
A graph is a collection of nodes (vertices) and edges.
- Can be directed/undirected, weighted/unweighted.
Used in: networks, maps, recommendation systems.
15. Difference between Directed and Undirected Graph?
- Directed: Edges have direction (A → B ≠ B → A)
- Undirected: Edges are bidirectional (A — B)
Used differently based on relationships (e.g., social networks vs. web links).
16. What is the time complexity of common operations in arrays and linked lists?
- Array:
- Access: O(1)
- Insert/Delete: O(n)
- Linked List:
- Access: O(n)
- Insert/Delete: O(1) at head
17. What is recursion?
When a function calls itself to solve a smaller subproblem.
Requires a base case to stop infinite calls.
Used in: tree traversals, backtracking, divide & conquer.
18. What are base case and recursive case?
- Base Case: Condition that ends recursion
- Recursive Case: Part where the function calls itself
Example:
def fact(n):
if n == 0: return 1 # base case
return n * fact(n-1) # recursive case
19. What is dynamic programming?
An optimization technique that solves problems by breaking them into overlapping subproblems and storing their results (memoization).
Used in: Fibonacci, knapsack, LCS.
20. Difference between Memoization and Tabulation?
- Memoization (Top-down): Uses recursion + caching
- Tabulation (Bottom-up): Uses iteration + table
Both store solutions to avoid redundant calculations.
Double Tap ♥️ For Part-3