The Self-Taught Computer Scientist

Introduction xiv I Introduction to Algorithms 1 1 What Is an Algorithm? 3 Analyzing Algorithms 4 Constant Time 8 Logarithmic Time 9 Linear Time 10 Log-Linear Time 11 Quadratic Time 11 Cubic Time 13 Exponential Time 14 Best- Case vs. Worst-Case Complexity 15 Space Complexity 15 Why Is This Important? 16 Vocabulary 17 Challenge 18 2 Recursion 19 When to Use Recursion 23 Vocabulary 23 Challenge 23 3 Search Algorithms 25 Linear Search 25 When to Use a Linear Search 27 Binary Search 27 When to Use a Binary Search 30 Searching for Characters 32 Vocabulary 34 Challenge 35 4 Sorting Algorithms 37 Bubble Sort 37 When to Use Bubble Sort 41 Insertion Sort 42 When to Use Insertion Sort 45 Merge Sort 45 When to Use Merge Sort 52 Sorting Algorithms in Python 53 Vocabulary 54 Challenge 54 5 String Algorithms 55 Anagram Detection 55 Palindrome Detection 56 Last Digit 57 Caesar Cipher 58 Vocabulary 61 Challenge 61 6 Math 63 Binary 63 Bitwise Operators 66 FizzBuzz 70 Greatest Common Factor 72 Euclid’s Algorithm 74 Primes 75 Vocabulary 77 Challenge 78 7 Self- Taught Inspiration: Margaret Hamilton 79 II Data Structures. 81 8 What Is a Data Structure? 83 Vocabulary 85 Challenge 86 9 Arrays 87 Array Performance 88 Creating an Array 90 Moving Zeros 91 Combining Two Lists 94 Finding the Duplicates in a List 95 Finding the Intersection of Two Lists 98 Vocabulary 99 Challenge 100 10 Linked Lists 101 Linked List Performance 103 Create a Linked List 104 Search a Linked List 107 Removing a Node from a Linked List 108 Reverse a Linked List 109 Finding a Linked List Cycle 110 Vocabulary 111 Challenges 112 11 Stacks 113 When to Use Stacks 114 Creating a Stack 115 Using Stacks to Reverse Strings 119 Min Stack 120 Stacked Parentheses 123 Vocabulary 125 Challenges 125 12 Queues 127 When to Use Queues 128 Creating a Queue 129 Python’s Built- In Queue Class 134 Create a Queue Using Two Stacks 134 Vocabulary 136 Challenge 136 13 Hash Tables 137 When to Use Hash Tables 140 Characters in a String 141 Two Sum 143 Vocabulary 144 Challenge 145 14 Binary Trees 147 When to Use Trees 150 Creating a Binary Tree 153 Breadth- First Tree Traversal 155 More Tree Traversals 157 Invert a Binary Tree 160 Vocabulary 162 Challenges 162 15 Binary Heaps 163 When to Use Heaps 167 Creating a Heap 167 Connecting Ropes with Minimal Cost 169 Vocabulary 171 Challenge 171 16 Graphs 173 When to Use Graphs 177 Creating a Graph 178 Dijkstra’s Algorithm 180 Vocabulary 186 Challenge 187 17 Self- Taught Inspiration: Elon Musk 189 18 Next Steps 191 What’s Next? 191 Climbing the Freelance Ladder 192 How to Get an Interview 192 How to Prepare for a Technical Interview 193 Additional Resources 194 Final Thoughts 194 Index 195