DSA Interview Questions

• Two Pointers: Sorted arrays, pair finding, palindrome checking
• Sliding Window: Subarray/substring problems, consecutive elements
• Fast & Slow Pointers: Cycle detection, middle of linked list
• Merge Intervals: Overlapping intervals, scheduling problems
• Cyclic Sort: Arrays with numbers in given range, find duplicates
• In-place Reversal: Linked list reversal, rotate operations
• BFS: Level-order traversal, shortest path (unweighted graphs)
• DFS: Path finding, connected components, backtracking
• Topological Sort: Dependency resolution, task scheduling
• Backtracking: Combinations, permutations, subsets, N-Queens
• Dynamic Programming: Optimization problems, counting problems
• Divide & Conquer: Merge sort, quick sort, binary search variations
• Bit Manipulation: XOR tricks, set operations, power of 2 checks
• Monotonic Stack: Next greater element, largest rectangle in histogram
• Heap/Priority Queue: Top-K elements, median finding, scheduling

• Base Case: The stopping condition — prevents infinite recursion
• Recursive Case: The function calls itself with a smaller input

# Factorial: n! = n × (n-1) × ... × 1
def factorial(n):
    # Base case
    if n == 0 or n == 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

factorial(5)  # 5 × 4 × 3 × 2 × 1 = 120

factorial(5)
  → 5 × factorial(4)
       → 4 × factorial(3)
            → 3 × factorial(2)
                 → 2 × factorial(1)
                      → 1 (base case!)
                 → 2 × 1 = 2
            → 3 × 2 = 6
       → 4 × 6 = 24
  → 5 × 24 = 120

#  Naive: O(2^n) - recalculates same values
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

#  Memoized: O(n) - caches results
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

• Without memo: fib(40) takes ~1 second (1+ billion calls)
• With memo: fib(40) takes ~0.0001 seconds (40 calls)

• Fibonacci Number — Base case + two recursive calls
• Climbing Stairs — How many ways to reach step n? (1 or 2 steps at a time)
• Reverse a String — Recursively reverse substring
• Power Function — Calculate x^n recursively (optimize with x^(n/2))
• Merge Sort — Divide array, sort halves, merge
• Quick Sort — Partition around pivot, sort partitions
• Binary Tree Traversals — In-order, pre-order, post-order
• Lowest Common Ancestor — Find LCA in BST
• Permutations/Subsets — Backtracking with recursion
• Combination Sum — Find all combinations that sum to target

# You can climb 1 or 2 steps at a time
def climbStairs(n):
    if n <= 2: return n
    return climbStairs(n-1) + climbStairs(n-2)

# With memoization
def climbStairs_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 2: return n
    memo[n] = climbStairs_memo(n-1) + climbStairs_memo(n-2)
    return memo[n]

1. "You need to be good at math" — Logic matters more than calculus. Most programming uses basic arithmetic.
2. "Memorizing syntax is key" — Understanding concepts > memorization. Docs exist for a reason.
3. "More code = better" — Concise, readable code is superior. Brevity with clarity wins.
4. "You need the 'perfect' IDE/language" — Tools don't make the programmer. Fundamentals transfer across languages.
5. "Debugging is failure" — Debugging IS programming. Even seniors debug for hours.
6. "You must code 8 hours/day" — Quality > quantity. Burnout kills progress. Consistent small efforts compound.
7. "AI will replace programmers" — AI augments, not replaces. Understanding fundamentals lets you verify AI output.

• Memory: Array = fixed contiguous block; LL = scattered nodes with pointer overhead
• Access: Array O(1) vs LL O(n)
• Insert/Delete at head: Array O(n) vs LL O(1)
• Cache friendliness: Arrays are cache-friendly; LLs cause cache misses

• O(1) — Constant: array index access, hash table lookup
• O(log n) — Logarithmic: binary search, BST operations
• O(n) — Linear: linear search, single loop
• O(n log n) — Merge sort, heap sort, Tim sort
• O(n²) — Quadratic: bubble/selection/insertion sort (worst case), nested loops
• O(2ⁿ) — Exponential: recursive Fibonacci, subset generation

• Search: O(log n) average, O(n) worst (skewed tree)
• Insert: O(log n) average, O(n) worst
• Delete: O(log n) average
• In-order traversal: produces sorted output

• Recursion: recomputes subproblems — exponential time in many cases
• DP (top-down memoization): recursion + caching = O(n) for Fibonacci
• DP (bottom-up tabulation): iterative, fills a table from base cases up

• Both: O(V + E) time, O(V) space
• BFS guarantees shortest path (unweighted); DFS does not

• Chaining: each bucket holds a linked list of entries
• Open Addressing: probe for next empty slot (linear probing, quadratic probing, double hashing)

• Merge Sort: O(n log n) always, stable, O(n) extra space (not in-place). Good for linked lists and external sorting.
• Quick Sort: O(n log n) average, O(n²) worst, O(log n) space (in-place). Faster in practice due to cache efficiency.

• Slow pointer moves 1 step, fast pointer moves 2 steps
• If there's a cycle, they will meet
• Time: O(n), Space: O(1)

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return True
    return False

• In-order (Left, Root, Right): BST gives sorted output
• Pre-order (Root, Left, Right): Used for tree copying, serialization
• Post-order (Left, Right, Root): Used for tree deletion, expression trees
• Level-order (BFS): Level by level using a queue

# In-order traversal
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

• Use a min-heap (priority queue)
• Always process the node with smallest tentative distance
• Relax edges: if dist[u] + weight < dist[v], update dist[v]