Name: Fabulous Adventures in Data Structures and Algorithms (Eric Lippert)（Z-Library）
Author: Unknown Author

Page 1

M A N N I N G Eric Lippert Foreword by Jon Skeet

Page 2

Fabulous Adventures in Data Structures and Algorithms Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 3

Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 4

MANN I NG Shelter ISland Eric Lippert Fabulous Adventures in Data Structures and Algorithms Foreword by Jon Skeet Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 5

For online information and ordering of this and other Manning books, please visit www.manning.com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact Special Sales Department Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 Email: orders@manning.com © 2026 Manning Publications Co. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps. Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid- free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine. ∞ Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 ISBN 9781633435032 Printed in the United States of America The author and publisher have made every effort to ensure that the information in this book was correct at press time. The author and publisher do not assume and hereby disclaim any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from negligence, accident, or any other cause, or from any usage of the information herein. Development editor: Doug Rudder Technical editor: Ted Neward Review editor: Radmila Ercegovac Production editor: Kathy Rossland Copy editor: Keir Simpson Proofreader: Olga Milanko Typesetter: Tamara ŠveliÊ SabljiÊ Cover designer: Marija Tudor Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 6

v brief contents 1 ■ Starting a fabulous adventure 1 Part 1 Extending the basics .................................................11 2 ■ Immutable stacks and queues 13 3 ■ An immutable deque 44 4 ■ Memoizing immutable quadtrees to make a better Life 68 5 ■ What’s up with you, Directed Acyclic Word Graph? 94 6 ■ Combinatorial algorithms 119 7 ■ First abstract nonsense interlude: Category theory 156 Part 2 Searching, solving, inferring ............................... 167 8 ■ Coloring graphs with backtracking search 169 9 ■ Greedy iterative pretty printing 188 10 ■ Unification and anti-unification 209 11 ■ Second abstract nonsense interlude: Monads 235 Part 3 Probabilities............................................................ 245 12 ■ A better abstraction for randomness 247 13 ■ Conditional probability with Bayes’ theorem 270 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 7

vi brief contents 14 ■ Third abstract nonsense interlude: The probability monad 286 15 ■ Sampling continuous distributions 293 16 ■ Markov processes and the Metropolis algorithm 309 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 8

vii contents foreword xiii preface xv acknowledgments xvii about this book xix about the author xxii about the cover illustration xxiii 1 Starting a fabulous adventure 1 1.1 Defining data structures, algorithms and complexity 3 1.2 An immutable linked list 5 Performance so far 6  ■  Reversing an immutable linked list 7 1.3 The challenges ahead 8 Part 1 Extending the basics ..................................11 2 Immutable stacks and queues 13 2.1 Why immutability? 14 Correctness 14  ■  Historical preservation 14  ■  Security 15 Safer multithreading 15  ■  Memoization for time performance 15 Persistence for space performance 16  ■  The functional programming attitude 16 2.2 An immutable stack 16 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 9

viii contents 2.3 A covariant immutable stack 21 2.4 A queue, a queue, an immutable queue 23 2.5 Mutable wrappers 28 2.6 Undo and redo 29 Create an army of clones 29  ■  Use a different data structure and the command pattern 30  ■  Undo and redo with mutable-over- immutable data structures 31 2.7 The Hughes list: Build it cheap, pay for it later 34 Reverse redux 34  ■  Currying and partial application 35 Implementing the Hughes list 36  ■  Complexity of the Hughes list 39 Where is the data in this data structure? 40  ■  A couple more performance considerations 42  ■  Reverse a linked list 42 3 An immutable deque 44 3.1 An immutable deque abstract data type 45 3.2 A bad naïve implementation 46 3.3 A finger tree 48 The mini-deque 48  ■  A new definition of a deque 50 3.4 Visualizing the data structure 54 3.5 Amortized performance of the deque 57 3.6 Are we abusing the type system? 58 3.7 Concatenation of deques 59 3.8 Performance after adding concatenation 66 3.9 Why is this tree called a finger tree? 66 4 Memoizing immutable quadtrees to make a better Life 68 4.1 The rules of Life 69 4.2 A typical first attempt 71 Performance of the naïve implementation 73  ■  Same algorithm, better constant factor 73  ■  Improving the algorithm with change tracking 74 4.3 An immutable quadtree 75 The IQuad interface 75  ■  Implementing the 0-quad leaf cells 75 A strategy for compressing space 76  ■  A general-purpose memoizer 77 A memoized quadtree implementation 78  ■  Indexing an immutable quadtree like an array 80  ■  A few more helpful extension methods 82 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 10

ixcontents 4.4 The HashLife algorithm 84 The base case: Stepping a 2-quad produces a 1-quad 84  ■  A first attempt at a recursive algorithm 86  ■  The grid always shrinks 88 Is this algorithm inefficient? 88  ■  Take bigger steps forward 89 Putting it all together 90 5 What’s up with you, Directed Acyclic Word Graph? 94 5.1 Two problems, two weak solutions 95 Hash sets are a nonsolution 96  ■  Sorted lists are… fine? 96 5.2 The prefix tree 98 Nodes and edges 99  ■  The trie-building algorithm 101 Using a trie as a word list 102  ■  How much memory are we saving with a trie? 104 5.3 Tries are not-so-secretly finite state automata 106 5.4 Building a DAWG 107 What problems must we solve to build a DAWG? 111  ■  Equivalence of nodes 112  ■  The DAWG-building algorithm 114  ■  How much expense does optimizing the graph as you go add? 116 5.5 DAWG vs. trie for ENABLE 117 6 Combinatorial algorithms 119 6.1 The Cartesian product 120 The Cartesian product of a few sets or sequences 121  ■  The Cartesian product of arbitrarily many sequences 124  ■  The connection to the integers 127 6.2 Permutations 128 Lexicographic permutations with repetitions 130  ■  The factorial base representation of permutation numbers 135  ■  The Fisher–Yates shuffling algorithm 136  ■  A recursive change-ringing algorithm 137 Even’s change-ringing algorithm 141 6.3 Combinations 144 Lexicographic combinations with a twist 145  ■  Counting combinations 148  ■  The combinatorial base representation of combinations 151 7 First abstract nonsense interlude: Category theory 156 7.1 Category theory is generalized abstract nonsense 157 7.2 Covariant endofunctors in the category of types 160 7.3 Contravariant endofunctors in the category of types 163 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 11

x contents Part 2 Searching, solving, inferring ................ 167 8 Coloring graphs with backtracking search 169 8.1 Coloring South America 170 8.2 An immutable multidictionary 171 8.3 An immutable undirected graph 173 8.4 Coloring simple graphs 175 8.5 Solving Sudokus with backtracking search 178 Graph coloring is NP-complete 180  ■  Implementing a general backtracker 181  ■  How could we improve? 184 Backtracking and the Cartesian product 185 8.6 Scheduling problems are graph-coloring problems 185 9 Greedy iterative pretty printing 188 9.1 The pretty-printing problem 189 9.2 Greedy algorithms and making change 191 9.3 A greedy pretty-printing algorithm 191 The doc data structure 192  ■  Visualizing a doc: How deep does it get? 195  ■  Phase 2: Implementing Fits() without recursion 195 Phase 2 continued: Implementing Pretty() without recursion 198 9.4 Phase 1: Transforming parse trees with the visitor pattern 201 Implementing the visitor pattern 202  ■  From parse tree to doc 205 10 Unification and anti-unification 209 10.1 Unifying binary terms 210 Unifying binary terms, first attempt 213  ■  Unifying binary terms, this time with an occurs check 215 10.2 The performance of binary term unification 219 10.3 Type inference and logic programming 222 10.4 Anti-unifying binary terms 225 10.5 The first-order binary-term anti-unification algorithm 227 10.6 Clone detection and fix deduction 231 11 Second abstract nonsense interlude: Monads 235 11.1 What’s the value for OO programmers? 236 11.2 How hard can it be to divide by 2? 237 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 12

xicontents 11.3 Generalizing to arbitrary functions with Map and Bind 238 11.4 The sequence monad is an additive monad 240 Part 3 Probabilities ............................................. 245 12 A better abstraction for randomness 247 12.1 What are probabilities? 248 12.2 What are discrete probability distributions? 249 12.3 Generating uniform samples with Random 250 12.4 IDistribution<T> and IDiscreteDistribution<T> 250 12.5 Flipping an unfair coin with Bernoulli 252 12.6 Improving the ecosystem with extension methods 254 12.7 Representing unfair die rolls by adding a projection 256 12.8 Categorical algorithm 1: Make a big list 258 12.9 Categorical algorithm 2: Climb a ladder 259 12.10 Categorical algorithm 3: Rejecting rejection sampling 262 12.11 Categorical algorithm 4: The alias algorithm 263 12.12 Filtering out a category 268 13 Conditional probability with Bayes’ theorem 270 13.1 Bayes’ theorem 271 13.2 Likelihood functions and joint distributions 273 13.3 Updating priors by reasoning from effects to causes 277 13.4 Some applications of Bayesian reasoning 279 13.5 Unconditional likelihood functions are independent 283 14 Third abstract nonsense interlude: The probability monad 286 14.1 The requirements for a monad 286 14.2 Probability distributions as additive monads 289 14.3 A critique 290 15 Sampling continuous distributions 293 15.1 What is a continuous probability distribution? 293 15.2 Sampling the continuous uniform distribution 296 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 13

xii contents 15.3 Sampling the normal distribution 298 15.4 The inverse transform method 300 15.5 Rejection sampling 303 Clamping with rejection sampling 306  ■  Problems with rejection sampling 308 16 Markov processes and the Metropolis algorithm 309 16.1 What is a Markov process? 310 16.2 Markov texts 313 16.3 Computing posteriors of continuous distributions 317 16.4 The Metropolis algorithm 319 16.5 Sampling posteriors with Metropolis 322 appendix A Notes on C# 327 appendix B Further reading 332 index 335 Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 14

xiii foreword The difference between a cow and a bean is a bean can begin an adventure. —Jack in Into the Woods, by Stephen Sondheim and James Lapine While reading this book, I’ve had the preceding lyrics from Stephen Sondheim’s mag- nificent musical going round my head, and for a long time, I wasn’t quite sure why. Obviously, the “adventures” in the title of the book are relevant, but on reflection, I think more is going on than that. This is a book that strongly advocates for mutability—not in data structures but in us. I’ve been struck by how many times Eric writes “This changed how I think about...” or “This changed how I approached...”—and for me, that’s the heart of the book. I may never end up using the specific data structures and algorithms described here, but going on the adventure invites us to change our own ways of thinking. An adventure from which you come back exactly the way you left is hardly an adventure at all, let alone a fabulous one. As the Baker’s Wife tells the Baker in the musical, “You’ve changed, you’re thriving, there’s something about the woods. Not just surviving, you’re blossoming in the woods.” This book gives each of us rich material in which to thrive and blossom, but it may not be in the form you expect. You probably expect to end up with a different way of thinking about data structures and algorithms. Maybe you’ve always heard about embracing immutability, but the sub- ject has always ended up feeling a bit too counterintuitive, or you didn’t feel that you had the right tools and examples on hand. Good news: you do now. Perhaps fewer curi- ous readers would expect to find a more principled approach to handling randomness, Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 15

xiv foreword but again, you’re well covered here. I’ll stop listing examples. This is meant to be a fore- word, not a table of contents. But leaving the more obvious stuff aside, I think I most enjoyed the side quests along the way. These quests include encouragement to build domain-specific languages to describe data readably and the use of wrapper types to ensure that we don’t mistake an implementation for the data structure it’s meant to describe. Those are practical “while you’re coding” ideas, but there are invitations to ponder higher-level concepts too. This book isn’t just about how to approach problems; it’s also about how we think about approaching problems and how different problem spaces interact. Above all, a call to intention flows through the book, which may be more important right now than at any previous time in software engineering. Eric explains some of this intention explicitly in some chapters, but it’s present in every discussion of what should be present in an abstract data type and how things are named. It’s demonstrated in the careful progression through ideas, building layers of understanding. It’s problem- solving through storytelling, making the adventures literally fabulous: the stuff of fables. As the Witch in Into the Woods warns, “Careful the tale you tell; that is the spell.” Data structures, algorithms, and code aren’t just ambiently present for no reason; they rep- resent intention. It’s our responsibility to make sure we know what we intend and to express that intention as clearly as we can. I expect to come back to this book periodically. That will clearly be true if one of the data structures or algorithms meets a specific need, but even if I never implement a sin- gle one of these algorithms, I expect that the book will provide value in changing how I think time and time again. I’m already itching to see how my changes in thinking will be reflected in the code I write and the stories that code tells. So yes—come for the data structures and algorithms. They provide fabulous adven- tures, as promised. But stay for the wit, wisdom, and space to change the way you think. —Jon Skeet Author of C# in Depth and co-author of Software Mistakes and Tradeoffs Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 16

xv preface The Puget Sound region gets snow only a couple of days a year in the lowlands, so people were unprepared for the blizzard that shut down most roads on my Microsoft interview day in January 1996. Because none of my scheduled interviewers made it to work, recruiting had to scramble to find people who could see a candidate at the last minute. My first technical interviewer that morning was a young, irritated, and (understandably) unprepared database developer. He set me what was already in 1996 a cliché coding exam: write the code to reverse a linked list. Microsoft interviewers then and now expect candidates to ask clarifying questions about even trivial problems before diving in and writing the code, so I did: “Can I use an object-oriented language?” “Sure.” “Can I assume that I have a list class implemented?” “Sure.” “Can I make the list immutable?” “Uh . . . sure. I guess.” “Great! ” I dashed off four lines of C++ code to reverse an immutable linked list. “That’s wrong.” Things didn’t improve from there; I didn’t get any offer that day. Fortunately, I had an offer in hand from the Visual Basic team on which I’d interned, so the day wasn’t a total loss. In the months that followed, I thought hard about what went wrong in that first inter- view. I’ve been on both sides of plenty of interviews since and made lots of mistakes, but I promise that I did know how to reverse a linked list on that snowy day in Redmond. Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 17

xvi preface I realized later that the interviewer likely expected me to answer the question “How do you reverse a mutable linked list in place in C?” and was unprepared for an answer to a different question. This experience got me thinking about what tools are in the line-of-business pro- grammer’s toolbox. The immutable linked list was fresh in my mind that day; I had a brand-new Bachelor of Computer Science degree, and that list was in my curriculum. Plainly, though, it wasn’t in my interviewer’s toolbox, to the detriment of both of us. I’ve thought about that interview ever since. I spent the next 25-plus years trying to get more tools in my toolbox and the toolboxes of everyone around me. In doing so, I often ran into data structures and algorithms that weren’t just useful but also changed how I think about software development. This book is a collection of some of those fab- ulous adventures in programming. Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 18

xvii acknowledgments My sincere thanks to everyone who helped make this book a reality. Without the edito- rial, marketing, graphics, and administration people I worked with at Manning—Aira Dučić, Azra Dedic, Breckyn Ely, Radmila Ercegovac, Matko Hrvatin, Joanne Lovell, Jonathan Gennick, Melissa Ice, Rebecca Rinehart, Sam Wood, and many more—this book would still be a bunch of poorly organized Word files. Many thanks to Jon Skeet for his lovely foreword. Particular thanks to development editor Doug Rudder and technical editor Ted Neward for their insightful advice. Ted is an industry software architecture and development professional with 30 years of experi- ence and a dozen books to his name. Thanks also to the many readers who reviewed proposals and early versions of the book and made helpful comments: Adrian Cucoș, Aidas Liaudanskas, Alisson Sol, Andrea Mascaretti, Andrew Dunleavy, Ben Evans, Bruno Sonnino, Chris Sharp, Christof Ullwer, Christopher Kardell, Clyde Kallahan, Cristina Vasco, Erin Colvin, Esa Koponen, Federico Kircheis, Frances Buontempo, Francesco Basile, George Kuan, Ines Sch- weigert, Ivan Čukić, Jason Overholt, Jeff Neumann, Joe Justesen, Johannes Ball, John Montgomery, Jon Riddle, Jort Rodenburg, Juan Rufes, Kevin Mukhar, Marc Roulleau, Nick Decroos, Nicolas Bievre, Nir Dobovizki, Ockert du Preez, Oleksandr Kaleniuk, Paul Go, Rich Yonts, Ronald Mak, Stepan Plotytsia, Timo Salomäki, Tom Gueth, and Zoran Horvat. Your suggestions helped make this book better. The mentors, managers, colleagues, and friends who taught me so much during my time at Microsoft, Coverity, and Facebook are too numerous to mention here, but I appreciate all of them. I’ll single out Erik Meijer, who has been part of all four groups. Erik’s unmatched ability to bridge the worlds of academic computer science and practi- cal engineering was an inspiration to me throughout my career. Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 19

xviii acknowledgments Thanks to my wife, Leah, for her patience during the lengthy writing process and to all my family members, chosen and biological, who supported me throughout it. All of you make my life a truly fabulous adventure. Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Page 20

xix about this book Despite the motivating anecdote in the preface, my aim here isn’t to provide yet another book designed to help readers get past the gatekeepers who pose coding prob- lems in interviews. If this book helps you do well in a coding interview, I’d be thrilled, of course, but that’s not what this book is for. Neither is it intended to be an academic textbook. You won’t find formal proofs, difficult equations, or exercises at the end of each chapter. Almost all the algorithms and data structures I cover in this book are ones I had to learn about to solve real, practical problems when building developer tools. One of the secrets of my success was taking ideas from academic computer science that weren’t covered in the undergraduate curriculum and applying them to practical problems. Having these tools in my toolbox was very helpful. The few algorithms that were not germane to a specific work-related problem are included here because they’re fun. Most of you reading this book started programming for the thrill that comes from having an idea, writing it down in a special language, and seeing that idea comes to life as a running program you can interact with. I’ve been writ- ing programs for more than 45 years, and I still get joy from making a thing that works. I learned a lot from that practice; I hope that you do too. Who should read this book This book is for all programmers who think it’s both fun and useful to learn about some of the more offbeat data structures and algorithms. Professional software devel- opers, recreational programmers, and computer science students are all intended readers. A working knowledge of C# is ideal but not strictly necessary; any Java, C++, or Python programmer will understand most of the code samples. Licensed to THIAGO BANDEIRA <thiago@lar.ifce.edu.br>

Tip the Site

Fabulous Adventures in Data Structures and Algorithms (Eric Lippert)（Z-Library）

Fabulous Adventures in Data Structures and Algorithms (Eric Lippert)（Z-Library）

Registered users can read the full content for free

AI Reading Assistant

Passage locations

Recommended for You

Tip the Site