Design and Build Great Web APIs

Cover
Table of Contents
Preface
	Who Is This Book For?
	What’s New in the Second Edition
	What’s in This Book?
	How to Read This Book
	Code Examples
	Online Resources
	Acknowledgments
	Connecting
1. Why Data Structures Matter
	Data Structures
	The Array: The Foundational Data Structure
	Measuring Speed
	Reading
	Searching
	Insertion
	Deletion
	Sets: How a Single Rule Can Affect Efficiency
	Wrapping Up
	Exercises
2. Why Algorithms Matter
	Ordered Arrays
	Searching an Ordered Array
	Binary Search
	Binary Search vs. Linear Search
	Wrapping Up
	Exercises
3. O Yes! Big O Notation
	Big O: How Many Steps Relative to N Elements?
	The Soul of Big O
	An Algorithm of the Third Kind
	Logarithms
	O(log N) Explained
	Practical Examples
	Wrapping Up
	Exercises
4. Speeding Up Your Code with Big O
	Bubble Sort
	Bubble Sort in Action
	The Efficiency of Bubble Sort
	A Quadratic Problem
	A Linear Solution
	Wrapping Up
	Exercises
5. Optimizing Code with and Without Big O
	Selection Sort
	Selection Sort in Action
	The Efficiency of Selection Sort
	Ignoring Constants
	Big O Categories
	Wrapping Up
	Exercises
6. Optimizing for Optimistic Scenarios
	Insertion Sort
	Insertion Sort in Action
	The Efficiency of Insertion Sort
	The Average Case
	A Practical Example
	Wrapping Up
	Exercises
7. Big O in Everyday Code
	Mean Average of Even Numbers
	Word Builder
	Array Sample
	Average Celsius Reading
	Clothing Labels
	Count the Ones
	Palindrome Checker
	Get All the Products
	Password Cracker
	Wrapping Up
	Exercises
8. Blazing Fast Lookup with Hash Tables
	Hash Tables
	Hashing with Hash Functions
	Building a Thesaurus for Fun and Profit, but Mainly Profit
	Hash Table Lookups
	Dealing with Collisions
	Making an Efficient Hash Table
	Hash Tables for Organization
	Hash Tables for Speed
	Wrapping Up
	Exercises
9. Crafting Elegant Code with Stacks and Queues
	Stacks
	Abstract Data Types
	Stacks in Action
	The Importance of Constrained Data Structures
	Queues
	Queues in Action
	Wrapping Up
	Exercises
10. Recursively Recurse with Recursion
	Recurse Instead of Loop
	The Base Case
	Reading Recursive Code
	Recursion in the Eyes of the Computer
	Filesystem Traversal
	Wrapping Up
	Exercises
11. Learning to Write in Recursive
	Recursive Category: Repeatedly Execute
	Recursive Category: Calculations
	Top-Down Recursion: A New Way of Thinking
	The Staircase Problem
	Anagram Generation
	Wrapping Up
	Exercises
12. Dynamic Programming
	Unnecessary Recursive Calls
	The Little Fix for Big O
	The Efficiency of Recursion
	Overlapping Subproblems
	Dynamic Programming through Memoization
	Dynamic Programming through Going Bottom-Up
	Wrapping Up
	Exercises
13. Recursive Algorithms for Speed
	Partitioning
	Quicksort
	The Efficiency of Quicksort
	Quicksort in the Worst-Case Scenario
	Quickselect
	Sorting as a Key to Other Algorithms
	Wrapping Up
	Exercises
14. Node-Based Data Structures
	Linked Lists
	Implementing a Linked List
	Reading
	Searching
	Insertion
	Deletion
	Efficiency of Linked List Operations
	Linked Lists in Action
	Doubly Linked Lists
	Queues as Doubly Linked Lists
	Wrapping Up
	Exercises
15. Speeding Up All the Things with Binary Search Trees
	Trees
	Binary Search Trees
	Searching
	Insertion
	Deletion
	Binary Search Trees in Action
	Binary Search Tree Traversal
	Wrapping Up
	Exercises
16. Keeping Your Priorities Straight with Heaps
	Priority Queues
	Heaps
	Heap Properties
	Heap Insertion
	Looking for the Last Node
	Heap Deletion
	Heaps vs. Ordered Arrays
	The Problem of the Last Node…Again
	Arrays as Heaps
	Heaps as Priority Queues
	Wrapping Up
	Exercises
17. It Doesn\'t Hurt to Trie
	Tries
	Storing Words
	Trie Search
	The Efficiency of Trie Search
	Trie Insertion
	Building Autocomplete
	Completing Autocomplete
	Tries with Values: A Better Autocomplete
	Wrapping Up
	Exercises
18. Connecting Everything with Graphs
	Graphs
	Directed Graphs
	Object-Oriented Graph Implementation
	Graph Search
	Depth-First Search
	Breadth-First Search
	The Efficiency of Graph Search
	Weighted Graphs
	Dijkstra’s Algorithm
	Wrapping Up
	Exercises
19. Dealing with Space Constraints
	Big O of Space Complexity
	Trade-Offs Between Time and Space
	The Hidden Cost of Recursion
	Wrapping Up
	Exercises
20. Techniques for Code Optimization
	Prerequisite: Determine Your Current Big O
	Start Here: The Best-Imaginable Big O
	Magical Lookups
	Recognizing Patterns
	Greedy Algorithms
	Change the Data Structure
	Wrapping Up
	Parting Thoughts
	Exercises
A1. Exercise Solutions
	Chapter 1
	Chapter 2
	Chapter 3
	Chapter 4
	Chapter 5
	Chapter 6
	Chapter 7
	Chapter 8
	Chapter 9
	Chapter 10
	Chapter 11
	Chapter 12
	Chapter 13
	Chapter 14
	Chapter 15
	Chapter 16
	Chapter 17
	Chapter 18
	Chapter 19
	Chapter 20
Index
	– A –
	– B –
	– C –
	– D –
	– E –
	– F –
	– G –
	– H –
	– I –
	– J –
	– K –
	– L –
	– M –
	– N –
	– O –
	– P –
	– Q –
	– R –
	– S –
	– T –
	– U –
	– V –
	– W –