- Pages:
- 500
- Published:
- September 2025
- ISBN:
- 9798888651322
- Edition:
- 1
In Print
A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 2
Level Up Your Core Programming Skills
by Jay Wengrow
Want to write code that pushes the boundaries of speed, space savings, and scalability? Then you need more advanced data structures and algorithms. Go beyond Big O notation and evaluate the true efficiency of each algorithm you design. Pull out data structures such as B-trees, bit vectors, and Bloom filters to wrangle big data. Wield techniques like caching, randomization, and fingerprinting to tame even the most demanding applications. With simple language, clear diagrams, and practice exercises and solutions, this book makes these topics easy to grasp. Go beyond the basics and use these next-level concepts to build software that’s ready to take on the challenges of the real world.
Reader’s Note: This volume is the second in a series. A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 covers the foundational concepts of data structures and algorithms. This second volume builds on the knowledge presented there.eBook Formats:
PDF for desktop/tablets
epub for Apple Books, e-readers
mobi for Kindle readers
Get all eBook formats here for $43.95 (USD)
Paperback Formats:
Order via Bookshop (U.S. Only)
Please support indie bookstores!
Find indie bookstores in the U.S. Find indie bookstores around the world.
The applications you write get more complex by the day. To keep up, you need to ensure your knowledge and techniques grow, too. A mastery of data structures and algorithms lets you write software more quickly; software that works, performs, and scales. Volume 2 of the series takes your knowledge of data structures and algorithms to the next level. With this practical and easy-to-understand guide, you’ll create software that can tackle today’s challenging problems head on. This Python edition uses Python exclusively for all code examples, exercises, and solutions.
Benchmark your Python code to learn its true speed. Design fast and elegant solutions by connecting different data structures together. Use Monte Carlo algorithms to push the limits of your application’s speed and memory savings in surprising ways. Wrangle big data with B-trees and other specialized algorithms. Design efficient algorithms by cleverly sprinkling in a bit of randomization. Cram tons of data into tiny bit vectors and Bloom filters. And leverage caching to make your software blazingly fast.
Learn these sophisticated techniques and create great software that meets today’s challenges.
What You Need
To explore and execute the book’s code, you’ll need your favorite text editor and an environment that can run Python 3. While you needn’t have read Volume 1 of this book to understand the current volume, you do need to be familiar with the concepts discussed there.
Resources
Releases:
Contents & Extracts
- Preface
- Who Is This Book For?
- What’s in This Book?
- How to Read This Book
- A Note About the Code
- Online Resources
- Connecting
- Getting Things in Order with Mergesort
excerpt
- Merging Arrays
- Merging in Action
- The Efficiency of Merging
- Mergesort
- Mergesort in Action
- The Efficiency of Mergesort
- Comparing Mergesort and Quicksort: Lessons Learned
- Wrapping Up
- Exercises
- Benchmarking Code
- Benchmarking
- Using the timeit Module
- Benchmarking Gotchas
- Benchmarking Sorting Algorithms
- Mergesort vs. Insertion Sort
- Mergesort vs. Quicksort
- Using Python’s Built-In Sorting Algorithm
- Quicksorting a Sorted Array
- Wrapping Up
- Exercises
- How Random Is That?
- Randomized Quicksort
- Randomized Algorithms
- Generating Random Numbers
- TRNGs vs. PRNGs
- The Fisher-Yates Shuffle
- The Fisher-Yates Shuffle in Action
- The Efficiency of the Fisher-Yates Shuffle
- Shuffling the Wrong Way
- Binary Search Tree Randomization
- Randomization for Distribution
- Load Balancing
- Wrapping Up
- Exercises
- Cache Is King
excerpt
- Caching
- Eviction Policies
- LRU Cache
- The LRU Cache Data Structure
- Fixing the LRU Worst-Case Scenario with Randomization
- The Memory Hierarchy
- Writing Cache-Friendly Code
- Spatial Locality
- Wrapping Up
- Exercises
- The Great Balancing Act of Red-Black Trees
- Online Algorithms and Self-Balancing Trees
- Red-Black Trees
- The Red-Black Rules
- Red-Black Tree Insertion
- The Efficiency of Red-Black Trees
- Red-Black Tree Deletion
- Wrapping Up
- Exercises
- Randomized Treaps: Haphazardly Achieving Equilibrium
- Treaps
- Treap Insertion
- Self-Balancing Treaps in Action
- The Power of Random Priorities
- Treap Deletion
- Wrapping Up
- Exercises
- To B-Tree or Not to B-Tree: External-Memory Algorithms
excerpt
- External Memory
- Count I/Os, Not Steps
- External Binary Search
- Optimizing External-Memory Algorithms
- Binary Search Trees in External Memory
- B-Trees
- Implementing B-Trees
- B-Tree Insertion
- B-Tree Deletion
- The Balance of B-Trees
- B-Trees as Database Indexes
- Wrapping Up
- Exercises
- Wrangling Big Data with M/B-Way Mergesort
- External-Memory Sorting
- A First Attempt: Two-Way External Mergesort
- M = Main Memory Size
- A Second Attempt at External Mergesort
- Merging K Sorted Lists
- M/B-Way Mergesort
- Wrapping Up
- Exercises
- Counting on Monte Carlo Algorithms
- Monte Carlo Algorithms
- Monte Carlo Algorithms vs. Las Vegas Algorithms
- Obtaining Averages Through Random Sampling
- Primality Testing
- Monte Carlo Primality Testing
- Fermat’s Little Theorem
- Fermat’s Primality Test
- Wrapping Up
- Exercises
- Designing Great Hash Tables with Randomization
- Hash Functions: A Quick Review
- Scalable Hash Functions
- The Division Method
- Randomized Hashing
- Wrapping Up
- Exercises
- Keeping Your Text Search Sharp with a Little Rabin-Karp
- Substring Search
- Brute-Force Substring Search
- The Sliding Window Technique
- Rabin-Karp Substring Search
- Covering All Our Bases
- Perfecting Rabin-Karp with Base 26
- Handling Long Needles
- Monte-Carlo Rabin-Karp
- Converting Monte Carlo to Las Vegas
- Wrapping Up
- Exercises
- Saving Space: Every Bit Helps
- Sets
- Boolean Arrays
- Bit Vectors
- Bit Manipulation
- Bit Masks: The Key to Zeroing in on a Bit
- Benchmarking Space
- The Space Complexity of Sets
- Classic Set Operations
- Wrapping Up
- Exercises
- Cultivating Efficiency with Bloom Filters
- Finding Duplicates Revisited
- Bloom Filters
- Use Multiple Hash Functions
- Using Bloom Filters for Detecting Duplicates
- Bloom Filters in the Wild
- Wrapping Up
- Parting Thoughts
- Exercises
- 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
Author
Jay Wengrow is an experienced educator and software engineer. He is the founder of Actualize, an award-winning US coding school that has helped hundreds of people from all backgrounds launch their careers as software engineers. He is passionate about making software development more accessible by breaking the complex down into its simpler, easier parts.eBook Formats:
PDF for desktop/tablets
epub for Apple Books, e-readers
mobi for Kindle readers
Get all eBook formats here for $43.95 (USD)
Paperback Formats:
Order via Bookshop (U.S. Only)
Please support indie bookstores!
Find indie bookstores in the U.S. Find indie bookstores around the world.
Related Titles:
