2  My Problem Solving Philosophy

3 My Approach to Problem Solving

3.1 Why I’m Doing This

Data structures and algorithms used to be my nemesis. I’d freeze up in interviews, unable to think clearly. But I realized that avoiding them wasn’t an option if I wanted to grow as an engineer.

This isn’t just about passing interviews anymore. It’s about:

  • Thinking clearly: Breaking down complex problems into manageable pieces.
  • Writing better code: Understanding the trade-offs I make every day.
  • Building confidence: Knowing that I can tackle hard problems.

3.2 How I Tackle Problems Now

Over time, I’ve developed a routine that helps me stay calm and focused.

3.2.1 1. The “Understand” Phase

Before writing a single line of code, I stop and ask: - Do I truly understand what’s being asked? - What are the edge cases? (Empty inputs? Negatives? Duplicates?) - Can I solve a simple example by hand?

3.2.2 2. The “Design” Phase

I resist the urge to start coding immediately. Instead, I: - Draw it out: I use diagrams to visualize the data flow. - Talk to myself: I explain the logic out loud (rubber duck debugging works!). - Start with Brute Force: It’s okay to have a slow solution first. Optimization comes later.

3.2.3 3. The “Code” Phase

When I finally code, I focus on readability. - Meaningful variable names (no more x, y, z). - Modular functions for distinct steps.

3.2.4 4. The “Review” Phase

I dry run my code with the examples I created in step 1. This catches 90% of my bugs before I even run the code.

3.3 Time and Space Complexity

3.3.1 Big-O Notation

Notation Name Example
O(1) Constant time Array access by index
O(log n) Logarithmic Binary search
O(n) Linear Finding max in array
O(n log n) Linearithmic Merge sort, Quick sort
O(n²) Quadratic Bubble sort, Selection sort
O(2ⁿ) Exponential Recursive Fibonacci
O(n!) Factorial Permutations

3.4 Common Data Structures

Data Structure Description Common Operations
Array Contiguous memory, fixed size Access: O(1), Search: O(n), Insert/Delete: O(n)
Linked List Nodes with pointers Access: O(n), Insert/Delete: O(1) at head
Stack LIFO (Last In, First Out) Push: O(1), Pop: O(1), Peek: O(1)
Queue FIFO (First In, First Out) Enqueue: O(1), Dequeue: O(1)
Hash Table Key-value pairs with hash function Insert/Delete/Search: O(1) average
Binary Tree Hierarchical structure with at most 2 children per node Varies by type
Graph Collection of nodes and edges Varies by representation

3.5 Algorithm Design Techniques

  1. Brute Force
    • Try all possible solutions
    • Simple but often inefficient
    • Good starting point for optimization
  2. Divide and Conquer
    • Break problem into smaller subproblems
    • Solve subproblems recursively
    • Combine solutions (e.g., Merge Sort)
  3. Greedy Algorithms
    • Make locally optimal choices
    • May not always produce optimal solution
    • Efficient for certain problems (e.g., Dijkstra’s, Kruskal’s)
  4. Dynamic Programming
    • Break problem into overlapping subproblems
    • Store solutions to subproblems (memoization/tabulation)
    • Build up to final solution (e.g., Fibonacci, Knapsack)
  5. Backtracking
    • Try different choices and backtrack if needed
    • Often uses recursion
    • Used in problems with multiple solutions (e.g., N-Queens, Sudoku)

3.6 Practice Problems

  1. Warm-up
    • Find the maximum number in an array
    • Check if a string is a palindrome
    • Find the first non-repeating character in a string
  2. Arrays
    • Two Sum
    • Best Time to Buy and Sell Stock
    • Product of Array Except Self
  3. Strings
    • Valid Parentheses
    • Longest Substring Without Repeating Characters
    • Group Anagrams

3.7 Next Steps

In the following chapters, we’ll dive deeper into each data structure and algorithm, with detailed explanations, visualizations, and practice problems. Each chapter builds upon the previous ones, so make sure you understand the fundamentals before moving on.

3.8 Resources

3.9 Exercises

  1. Implement a function to reverse a string in-place.
  2. Write a function to check if a number is prime.
  3. Find the most frequent element in an array.
  4. Implement a stack using arrays.
  5. Write a function to generate the first n Fibonacci numbers.
# Example solution for exercise 1
def reverse_string(s: list) -> None:
    """Reverse a string in-place using O(1) extra memory."""
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

# Test case
test_str = list("hello")
reverse_string(test_str)
print(''.join(test_str))  # Output: olleh

In the next chapter, we’ll start with Arrays and explore various techniques to solve array-based problems efficiently.