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