✅ Coding Interview Questions with Answers Part-3 🧠💻

21. Adjacency matrix vs adjacency list
Adjacency matrix:
• 2D array
• Space O(V²)
• Fast edge lookup
• Poor for sparse graphs
Adjacency list:
• List of neighbors
• Space O(V + E)
• Better for sparse graphs
• Used in real systems
Interview rule:
• Choose list unless graph is dense

22. What is sorting? Common sorting algorithms
Sorting arranges data in order.
Common algorithms:
• Bubble sort
• Selection sort
• Insertion sort
• Merge sort
• Quick sort
• Heap sort
Why it matters:
• Improves searching
• Simplifies data processing

23. Difference between quick sort and merge sort
Quick sort:
• Divide and conquer
• In-place
• Average O(n log n)
• Worst O(n²)
Merge sort:
• Divide and conquer
• Extra memory needed
• Always O(n log n)
• Stable
Interview pick:
• Quick sort for speed
• Merge sort for consistency

24. Which sorting algorithm is fastest and why
No single fastest algorithm.
General rules:
• Quick sort for average cases
• Merge sort for guaranteed performance
• Heap sort for memory control
Built-in sorts:
• Python uses Timsort
• Optimized for real data
Interview line:
• Depends on data and constraints

25. What is searching? Linear vs binary search
Searching finds an element.
Linear search:
• Checks one by one
• Time O(n)
• Works on any data
Binary search:
• Splits data
• Time O(log n)
• Needs sorted data

26. Why binary search needs sorted data
Binary search relies on order.
Reason:
• Decides left or right
• Without order, logic fails
Example:
• Phone book search
• Sorted arrays
Key point:
• Sorting enables efficiency

27. What is dynamic programming
Dynamic programming solves problems by storing results.
Core ideas:
• Overlapping subproblems
• Optimal substructure
Approaches:
• Top-down with memoization
• Bottom-up with tabulation
Classic problems:
• Fibonacci
• Knapsack
• Longest common subsequence

28. Greedy vs dynamic programming
Greedy:
• Takes local best
• Fast
• Not always correct
Dynamic programming:
• Considers all possibilities
• Slower
• Guarantees optimal result
Example:
• Coin change fails with greedy
• Works with dynamic programming

29. What is memoization
Memoization stores function results.
Purpose:
• Avoid recomputation
• Reduce time complexity
Example:
• Recursive Fibonacci with cache
Interview tip:
• Memoization trades memory for speed

30. What is backtracking
Backtracking explores all choices.
Steps:
• Choose
• Explore
• Undo
Used in:
• N-Queens
• Sudoku
• Permutations
Interview focus:
• Pruning reduces search space

Double Tap ♥️ For More