Algorithms underpin almost everything we do in programming and in problem solving in general.
Yet many of us have partial or incomplete knowledge of the most important and common ones.
In this episode, you'll meet Adit Bhargava, the author of The Light and Playful Grokking Algorithms, an illustrated guidebook.
If you struggle to understand and learn the key algorithms, this episode is for you.
This is Talk Python to me, episode 82, recorded October 24th, 2016.
Welcome to Talk Python to me, a weekly podcast on Python.
The language, the libraries, the ecosystem, and the personalities.
This is your host, Michael Kennedy. Follow me on Twitter where I'm @mkennedy.
Keep up with the show and listen to past episodes at talkpython.fm.
And follow the show on Twitter via at Talk Python.
This episode is brought to you by Capital One and Intel.
Thank them both for sponsoring the show by checking out what they're offering during their segments.
Adit, welcome to Talk Python.
Thank you.
I'm really enjoying your book that I started reading a little while ago, Grokking Algorithms
with Python.
And I think we're going to have a great time talking about it.
But before we do, tell us your story.
How did you get into programming in Python?
Well, I think I have a slightly atypical route.
Because I got into programming with this thing called Thing Maker.
I don't know if anyone remembers this.
It was, you know, back in the day, WWE had put it out, like the World Wrestling Entertainment
guys.
Okay.
Yeah.
And it was just a simple way to, like, make little games or, you know, make a website.
And I started playing around with that.
And then I thought, you know, I would love to make my own games.
And then I started playing with Flash.
So now you know how old the story is.
Yep.
Flash was probably new and exciting at the time.
It was.
And, like, it wasn't even owned by Adobe.
It was owned by Macromedia.
And Macromedia Director was a big thing.
Anyway, so I, like, started, you know, started with ActionScript.
And I sold a game.
And that's when I thought, you know, I could do programming.
This is really fun.
Oh, yeah.
That's cool.
So that's a ways away from Python.
How did you get over to the Python world?
Eventually, I was, like, because I had learned C, C++, kind of the standard route that a lot
of people take.
And I just wanted to get back to those Flash days when, you know, I mean, to me, I would
rather work with a simple language that can execute my ideas.
And that's when I found Python.
And it was so easy to use.
You know, it's like you can think about something and type it out as you're thinking about it.
Yeah, that's cool.
It's like programming is fun again, right?
Yeah.
Exactly.
It reminds me of that XKCD Python.
All right.
Well, that's excellent.
Did you go to a university and do a computer science degree?
I actually did my undergrad in graphic design.
Okay.
Because, you know, I mean, I love drawing.
It's been a hobby for me for a long time.
And then I worked as a designer for a while.
But I realized that I would enjoy programming more as a job.
So then I went to UChicago and got a master's in computer science.
Okay, cool.
Yeah, I guess that makes a lot of sense.
Like the illustrated part of your book, which we're going to get to, which is very cool.
You know, there's a lot of things you can learn.
You can just self-teach yourself about programming.
You know, there's a lot of good boot camps.
There's a lot of good online classes.
Things like that.
But I do feel one of the shortcomings of that type of education really is around the proper use of data structures and algorithms.
And not necessarily being able to write them, but knowing sort of the trade-offs, right?
Yeah, exactly.
You decided to solve that problem.
And you took your graphic arts skills and applied them, not just your programming skills, but your graphic arts skills,
and applied them to this problem with this book you wrote called Grokking Algorithms,
an illustrated guide for programmers and other curious people.
Yeah.
So I read your book, a good portion of it.
I find it delightful.
I think it is really, really nice.
You know, there's a lot of these concepts that if I remember reading algorithm-type books,
and it's just, you know, you're about to fall asleep.
It's just so dense and so hard to make it real, right?
It's like, I don't know, it's just tough to grok them, I guess, right?
And your book is filled with playful examples and fun pictures and things like that, right?
What was inspiration for that?
This whole thing started because I wrote a blog post on Haskell,
and it's this blog post about monads, which is a tough concept for a lot of people to understand.
The post got really popular, and still, you know, to this day, I see it being tweeted.
That's when, you know, I was like, you know, using pictures can really make a big difference
when you're trying to explain hard concepts.
So that's where I started with the book.
It was like, I would love to do, because I've always known I would love to do a book on algorithms.
Like you said, there's all the ones that I've read so far are so hard to read,
and I had a very good algorithms professor at Chicago, and she made things so easy.
So, you know, that's when I thought it would be great to have a book that makes it as easy as she made it for me.
And it just, you know, it just seemed like a good fit.
You started your blog at audit.io, and I'll be sure to link to that, right?
And you started doing these visual sort of explanation posts.
Yeah.
Did like, so this book is published by Manning, is that right?
Yes.
Yeah, so did Manning reach out to you and go, hey, this illustrated idea is really cool,
or did you approach him and say, I'd like to do something more torturous to myself?
No.
They reached out to me.
It was just the craziest.
After that, I kind of joked, like, this is how I get success.
I just sit back and wait for people to come to me.
There's a lesson there, though, I think, and that's really cool to hear.
I think there's a really important lesson there that you don't know what opportunities are out there or how they're going to come to you.
But if you don't ever put yourself out there and you don't try to do things in public, they're absolutely not going to come, right?
Like, there's so many opportunities have come to me from because of the podcast, but I never even imagined that they would.
I wasn't looking for them, and I didn't do the podcast for them or anything like that.
But just, like you said, being out there makes a big difference.
I agree.
And I put in so much work into those blog posts.
Like, it used to take me weeks to write a single post.
And it's kind of like just throwing a note in a bottle, right?
Like, you don't know if anyone's even reading it or even cares.
But somehow, you know, I mean, I enjoyed it.
That's why I kept doing it, and things just worked out.
So your book on algorithms is written in Python, and you could have chosen many languages, Java, JavaScript, and so on.
Why Python?
It's just the easiest language for me.
It's the easiest to learn.
I used to teach a course on Python, and it was just people picked it up so quickly.
Yeah, I totally agree with that.
You know, I was thinking earlier as you were talking about you want to get back to the ActionScript days and things that are easy.
A lot of people know JavaScript, but I feel like JavaScript has, by way of its popularity, become hard again.
You know, like all the Node.js dependencies, all the layers piled on top of it.
Somehow, Python has managed to avoid that fate, which keeps it simple but powerful.
I think it's great.
I'm constantly confused by JavaScript.
I think it's a...
I love JavaScript because it has a lot of those functional parts that I really like.
But yeah, the JavaScript community is moving so fast, it's hard to keep up.
Yeah, for sure.
So one thing that you said when you were talking in the preface of your book, you said that for everything that you describe, you like to lead with examples.
Yes.
Well, so this is part of my...
I mean, I have this, you know, some ideas about like what it means to teach something well.
And I think one big piece of that is you have to make things concrete.
I'm reading this book on probability right now.
And one thing that really frustrates me about this book is they'll start with a simple problem.
So they'll say, you know, for example, one of the problems in the book is this classic random walk idea.
So you have a man standing at the edge of a cliff.
And there's a one-third chance that he'll step towards the cliff.
And there's a two-third chance that he'll step away from the cliff.
And he's drunk, so he doesn't know which direction he's going to step in.
So, of course, if he takes a step towards the cliff, he's just going to fall off.
But there's a two-third chance he'll step away.
And, you know, again, there's a one-third chance that he'll step towards, two-thirds that he'll step away.
So the question is, does he escape the cliff or does he eventually fall off?
So a pretty good probability problem, you know, because it's simple to state and pretty hard to solve.
But then I read their answer in the back and they're like, okay, let's generalize this problem.
And let's say X is the probability of him stepping towards and Y is the probability of stepping away.
And I was like, no, you have concrete numbers.
Isn't it so much better to be able to visualize the problem as you're stepping through it?
And the only way to do that is by having a concrete example.
Yeah.
Yeah, I agree.
I feel like a lot of things, the concreteness of it and sort of the reason the whole thing came to be interesting in the first place gets, it kind of gets sterilized and all that stuff gets lost.
And you're down to just the essence of the abstract problem.
But then the joy of the problem is kind of gone in some ways, right?
So I really like that you have examples.
And these are like really playful examples.
I think it's important to start with making things concrete and then you can get into the theory and the abstract and so on.
Yeah.
I think I also try to choose pretty real world examples so people can, you know, look at the problem and think about all the different ways they could use it in their work.
Yeah.
I really like the one about Maggie and the checkout counter.
We'll get to that one.
Thank you.
So I have a pretty diverse listenership and people, a lot of people have, you know, PhDs in computer science, but a lot of people have come from different areas.
So just real quickly, what, tell us, what's an algorithm for those of us who don't know?
An algorithm is a set of instructions for accomplishing a task.
So really any piece of code could be an algorithm, right?
But there are certain pieces that are more interesting, maybe because they solve a hard problem really well, or maybe they can be used at a lot of different places.
So that's really what we talk about when we say algorithms, you know.
Yeah.
Okay.
I totally agree.
I think it's the reusability is definitely an interesting part.
Like the way you might log something to disk might be an algorithm, but it's not reusable in any way because it's exactly specific to a thing.
So you wouldn't call it an algorithm per se, right?
Yeah.
Cool.
All right.
So in your book, you broke it down to, like you said, there's going to be two major things that you learned.
One, you said you're going to learn about performance and the other, you're going to learn about solving problems.
How's that work?
The solving problems one is the really big one that I focused on.
Back when I was starting out, I just used to run into walls sometimes where you like come across a problem and you just don't know how you're going to solve it because you've never solved a problem like that before.
Or you don't really have a lot of tools in your tool belt.
So you can't say like, oh, maybe I'll use a hash table for this and see if that works.
Or maybe I should try to use some kind of a machine learning approach.
If you, you know, there's this idea of you don't know what you don't know.
And if you don't know that those tools exist, you're just stuck.
You can't solve those problems.
So this book is really about giving you all those tools like that should be able to solve most of the problems you encounter day to day.
Yeah, that's really cool.
And some of the examples you give are like, if you're making a video game, you could learn how to create an AI system that can find its way through pass or a recommendation system kind of like Amazon.
So that you might like, or even things that knowing that there are problems that are basically not solvable in a quick way.
Yeah, those NP complete problems.
Yeah, yeah.
That's a whole different interesting area.
I think performance is also interesting.
I mean, you talked about hash tables just a minute ago and dictionaries.
Like, knowing that if I have this type of thing I need to do, it's 100 times faster using this data structure than that data structure and being able to express that.
It helps you design how you solve a problem.
If you're like, you know, if I can coerce it into this shape, it will be rocket fast.
Absolutely.
That's something, to me, that is really about the craft of engineering.
One reason I love Python is you can write beautiful code with it.
And I think thinking about performance is just another aspect of that craft where you like, you know, you want to write something that runs well, that's dependable.
And that means it should run as fast as it can run.
Yeah.
Yeah, up to the point where it becomes, like, you can optimize something so much that it becomes write only.
Like, you wrote it and it works, but you can't understand it and nobody else can certainly understand it, right?
Oh, yeah.
So there has to be this tradeoff of maintainability.
But, yeah, knowing the data structure definitely is the right in algorithms and how that works in terms of performance is key.
So the algorithms, your algorithm book is not, like, comprehensive.
It's not like an encyclopedia of all known algorithms or anything like that, right?
It's more a special list.
You said the topics that you cover are all things you've used at work, which is pretty cool.
Exactly.
I think if you're looking for an encyclopedia, like, you could just read the Wikipedia articles or, like, one of those algorithms books that are, like, a thousand pages long.
You know, I didn't want to, I didn't want my book to be, like, we printed out Wikipedia and bound it into a book format.
Yeah.
Thank you for not doing that.
So we're going to talk in depth about some of the algorithms and stuff.
But can you just give us, like, a quick flyover of what's covered and things like that?
Sure.
So the first part of the book is, like, foundational work that I'll be using in the rest of the book.
So chapter one introduces you to a very basic algorithm and then talks about big O notation, which is something a lot of people get very confused by.
But it's an important concept.
And then chapters, chapter two is about memory.
Chapter three is about recursion.
So you can see I'm kind of building the foundation, like, the very basics.
And then we get into the interesting stuff.
So, like, chapter four, this is where I introduce one of those tools that I was talking about called divide and conquer, where, you know, you get a problem.
I don't know how to solve this.
Well, you could think, like, maybe I'll use divide and conquer and see if that works.
Chapter five is hash tables, which is the most useful tool in my tool belt.
I totally agree with you.
Yeah, you had a good quote.
You said, when I want to solve a problem, there are two planes of attack I start with.
Like, can I make this hash table problem?
Can I solve it with a graph, maybe?
One of those two, right?
Exactly.
I feel like, I mean, this is kind of a secret tip.
But when I get into an interview and someone gives me a problem, I immediately just think hash tables or graphs.
And it works, like, 90% of the time, you know.
Nice.
So, yeah, obviously, I think graphs are really important.
So chapter six and seven are graphs, another very useful tool.
Chapter eight is another good tool, and it's so easy.
Like, this might be the easiest chapter in the book, because chapter eight is really, like, do the dumbest thing you can think of, and it'll probably work.
And that's what a greedy algorithm is.
Yeah.
Sometimes, you know, computers are fast.
Sometimes the problems aren't that big.
Just solve it simply, right?
Exactly.
Chapter nine is probably the one I'm most proud of and the one that people have complimented me the most on,
because it's dynamic programming, and it is this really hard way to solve things.
That's not the same as programming with a dynamic language versus static languages.
It's something different, right?
Yeah.
It's all about creating this 2D array and splitting a problem up into sub-problems and then using those solutions for those sub-problems for the bigger problem.
It kind of, I feel like it just blows people's minds.
It's just so hard to use.
I mean, I spent maybe three or four months on this chapter alone, and I think it's really well-written, and a lot of people have found it very useful.
So that's chapter nine.
And then chapter 10, I just wanted to put a little thing about machine learning in here, because key nearest neighbors is so easy to use, and it's so effective.
And it was just, you know, you could read this chapter before bed, and you would know how to build a recommendations engine.
Oh, that's great.
That's really cool.
Yeah.
And then you finish out with saying, basically, now that you're inspired, you know the foundational algorithms.
Here's a whole bunch more things you can go do, right?
Yeah.
And then there's 10 things in chapter 11 that I think are really neat, and they're just, oh, I wish I could have put all 10 of these in the book also, but I just gave a little tidbit about each one.
Sure.
That'll be the follow-on, the second version.
Yeah.
So one thing that I liked about your book is you have little short exercises, like a couple minutes, two or three minutes at the end of each section, each chapter, that you can do to sort of test your thinking.
And I found those to be really nice.
Thank you.
I've been reading this book called A Book of Abstract Algebra, and it's got a great model where all the chapters are like two pages followed by six pages of exercises.
I found that those exercises helped me so much, so I figured, you know, I need to put more exercises in my book.
So who did you have in mind?
Like, if I have no programming or very little program experience, would this book be useful?
If I had a computer science degree, would it still be useful?
So it's been really popular with boot camp students so far.
I have a few friends who went to boot camps, and, you know, I have a friend who's in a boot camp right now, and he kind of told other students in the camp,
about it, and they all seem to like it.
I think it's also useful for people who have a computer science degree.
So I work at Etsy, and I kind of, you know, just sent an email out when the book came out saying, like, hey, I've published a book.
You know, isn't that cool?
And I've had people email me, like, really senior people, you know, people who are, like, two levels above me at Etsy.
And they're like, wow, I, finally I have great examples to explain these concepts with.
Because it's so hard to come up with a good example to explain something.
Yeah, absolutely.
It's one thing to know it.
It's another to teach it to another person.
And I think it is really, I think it's really accessible in that way.
Thank you.
It also doesn't require a lot of math, which I like.
You know, you don't need calculus or linear algebra or anything.
It's really, like, if you know the basics of algebra, like, if you know what a function is, you can read this book.
Yeah.
I like that you said that.
You know, I was talking to a friend of mine about sort of what does it take to become a programmer?
Like, how much math do you need to know?
And I think there's an outside of the programming field, like, people who are not programmers,
I feel like programming is very, very mathematical, right?
Like, if you don't know how to do calculus and differential equations, you'll never be a good programmer.
And to be honest, I find I do very little actual advanced math in anything that I do,
except for when I was working for, like, a scientific visualization company.
But outside of that context, like, it's more just knowing, like, critical thinking and problem solving.
And so I think that they give people feel like they need to learn a lot of math.
I mean, math is not a bad thing, but I don't think it's required.
Do you?
I don't think it's required either.
I think, especially for something like this, where, like, algorithms are the first step to, like, long journey in computer science.
And that first step should be as easy as possible.
There shouldn't be, like, big hurdles to get to that first step.
Yeah, totally agree.
Totally agree.
Okay, cool.
So let's talk about some of the algorithms and some of the things that you covered in the book.
The very first one that you covered was sort of different types of searching in sets and really leading towards binary search.
Yeah.
This is my favorite algorithms example because anyone can understand it.
Like, you don't even need to know anything about computers.
But because a lot of people, you know, when they heard I'm writing a book, they were like, tell me what is an algorithm.
So I gave them this example where I was like, you know, think of a, I'm thinking of a number between 1 and 100.
Take a guess.
And they would say, you know, 55.
And I'd say, well, that's too high.
Take another guess.
And they'd say 30.
And that's interesting because people automatically divide the space in half when they guess, almost on instinct.
Like, maybe they don't even understand what they're doing, but they're running binary search in their mind.
You know, that's all binary search is.
Divide the space in half every time to get to the results or to find the result as quickly as you can.
Yeah, it's such a simple example.
And yet I think it really dramatically points out the power of taking that, formalizing it just a little bit and making it really fast.
Capital One has a special message for you.
They need Python pros who love to work with data.
Put your Python experience at work at Capital One and help them use data to make life better for millions of customers.
Capital One is employing the latest tools and approaches to do data analytics and data science
from the ground up.
They're smart, creative professionals who love to explore new ways to interact with data.
They're interested in figuring out novel, advanced Python techniques,
and even more interested in finding more people who will help them do that.
When you join their state-of-the-art Python community, you'll work with people you really like,
people who might be listening to this podcast right now.
Relentless innovation is their way of life.
Make it yours at Capital One.
Visit jobs.capitalone.com slash talkpython to learn more and apply today.
You had a cool example.
You said, you know, imagine that you play this.
You have a couple of ways which you could do it.
Like you could just say like, I've got a list of 100 things and you want to search for something in there.
Right?
Kind of like the example you just gave.
One option is to look at the first one, check it next one.
Just go through it in order, right?
Another way is to apply this binary search thing, assuming that set is somehow ordered like an address book or something.
And you said, well, for 100 items, if you go straight through it, you know, worst case, you'll have to go,
you'll search until you get to the end.
That's 100.
But if you use the binary search because you half it and half it and half it, worst case scenario, you get seven.
But then you said, well, let's think about it, four billion.
Yeah.
And it's so crazy because now the difference, you know, now it's really obvious.
Like for searching through four billion items is too much.
But with binary search, it's just 32.
Maximum of 32 guesses, right?
Even if it's I'm guessing between a number between zero and four billion.
Yeah.
Isn't that such a huge difference?
Yeah.
It's it's insane.
I mean, it makes sense.
But at the same time, you don't think such a simple idea is going to reduce it from four
billion comparisons to 32 at worst case.
Yeah.
It's really amazing.
Yeah.
So one of the things I think is hard for people who have not gone through a formal computer science
background and just for everybody listening, I don't have a computer science degree, but
I have a minor in computer science.
So I've gone through some of it.
So I guess I'm somewhere in the middle of this.
But if you are self-taught, if you've gone to a boot camp or if you're just really new,
people often talk about big O notation around performance of algorithms.
And I think that that's kind of mysterious to people.
And it also seems to be something that ends up on job interviews often.
And so if you don't have that experience, you're like, I don't even know what big O is.
Like, well, sorry, you're out or something, right?
Like it can be a bigger problem than it maybe really deserves to be.
But I think it's worth knowing big O notation for a couple reasons.
Yeah.
Dude, this was a really good way for you to introduce that concept, I thought.
Like, pretty crazy, right?
Yeah, exactly.
And I won't, you know, get into the full explanation here.
But I do want to say, I think every beginner engineer I meet has trouble with big O notation.
So, you know, if some of your listeners are still new to engineering, just to say, like, that's not just you.
Don't feel that.
That's right.
Yeah.
But that's why I, you know, it's right up front in the book.
And then I talk about it again in chapter four.
So, I spend a lot of time trying to explain big O notation in this book.
Yeah, absolutely.
So, I think it's pretty interesting.
You've got the linear search, which is what they call O of N.
So, as if you have N items, you have to do N comparisons.
If you have two N items, you have to do two N comparisons.
It grows basically linearly.
But this binary search one is log of N, which doesn't sound like that big of a difference.
So, you realize it's 4 billion versus 32.
You know?
Which is pretty amazing.
So, knowing this relative scale, that doesn't actually tell you how fast it is, does it?
That just tells you, like, relatively how much slower does it get as you get more data.
Exactly.
Because everyone's computer, you know, calculates at a different speed.
So, you can't put a time on it.
Yeah.
And that becomes interesting later when you find algorithms that are actually look worse in big O, but often they're not.
And so, you talked about this idea of average time versus worst case time.
I think that's also important to understand.
Yeah.
That's another really interesting one where, you know, if you can say that your algorithm is going to take a short time on average and a really long time, worst case, maybe that's fine.
And, you know, if you're just a website or, you know, you have a basic consumer app and you're like, well, it'll run fast most of the time.
So, that's fine.
If you're NASA and you have to guarantee a certain time, then you really care about that worst case time also.
Yeah.
Any real-time system.
So, if you were doing like a flight control system on a spaceship or if you're doing trading in some sort of high-speed trading system or I worked on a system that would actually analyze eye tracking data in real time.
And it would get 250 samples per second.
And if it couldn't process using some very advanced sort of wavelet decomposition algorithms and whatnot.
If you couldn't process that in, you know, four milliseconds.
Well, then it just couldn't keep up because that was how fast data was coming, right?
I mean, there's these situations where worst case time maybe is super important.
But a lot of times, like you said, average time I think is fine.
So, give us some, like for some algorithms that we might know, give us a big O performance stats.
Sure.
So, binary search, we already talked about log N and searching, you know, linear search, looking at one item at a time is big O of N.
And like we just talked about, that's a big difference, right?
Log N versus N.
So, again, if you think about that, a slow sorting algorithm is N squared.
And my example is selection sort.
A fast sorting algorithm is going to be N log N.
So, again, you have that log N versus N difference.
So, the fast sorting algorithm is much faster.
Yeah.
And after that, there's like N cubed algorithms.
My extreme example is you can get big O of N factorial algorithms.
And, you know, if people don't know what a factorial is, that's like 5 factorial would be 1 times 2 times 3 times 4 times 5.
6 factorial would be 1, 2, 3, 4, 5, 6.
Factorial grows really fast.
If you have an N factorial algorithm, that just means you just can't use it most of the time.
It only works on extremely small data sets, right?
Yeah.
So, the example, probably the canonical example for that is the traveling salesperson problem.
Yep.
And this is one of those NP complete problems we have talked about where, you know, the problem is really simple.
You're a traveling salesman and you have a list of cities that you want to travel to.
And you want to figure out the shortest route that hits all of those cities.
So, it just seems so simple.
Like, you know, why couldn't you calculate that?
And, of course, you can.
It means that you have to come up with every permutation of cities, of the order of cities.
Which, if you have 6 cities, it's 6 factorial permutations.
If you have 100 cities, it's 100 factorial permutations.
And just to give you an example of how crazy that is, 6 factorial is 720, which, you know, your computer can do.
100 factorial is 9 followed by 157 zeros.
Wow.
Yeah.
That means you're going to run out of time or you're going to run out of memory.
One of those first.
But you're probably going to run out of something, right?
Yeah.
I think the universe will end before you can make that.
Absolutely.
All right.
So, the next thing that you talked about that I thought was cool was selection sort.
And you took a moment to say, like, let's think about the two data structures that hold stuff in just like a list style.
And that was linked lists and arrays.
And I thought that was a really interesting tradeoff, knowing how you're going to use them and so on.
So, tell us about that comparison you made.
Sure.
So, the example I use in the book is this idea of, you know, you're going to watch a movie.
And let's say you're going there.
There's eight of you.
Eight people are going.
And you're trying to find seats.
So, maybe you can find eight seats all together and then you can all sit together.
Maybe there's no set of eight seats together.
So, you have to kind of sit all over the theater.
And you know where each other, you know where your group is, but they're not all in one place.
And that's this idea of linked lists versus arrays.
Where arrays, you're all sitting together.
Link lists, you're all sitting separately.
You know, your data is together in memory or apart.
So, with arrays, you basically have a contiguous block.
Exactly.
And with linked lists, each element knows how to find the next element.
Sometimes you have doubly linked lists.
So, you can start at the back and go forward or forwards and go backwards.
But each element is more or less in charge of going to a new memory location to find the next or be in the end.
Exactly.
And if I could stretch this movie analogy a little bit.
Let's say, you know, you have a bag of popcorn.
And you're kind of passing it down the row.
Really easy to do if you're all sitting together, right?
Because you can just, you know, the next person is just to your right.
And you just keep passing the bag to your right.
And that's what arrays are.
So, it's really easy to access the next element in an array.
And it's easy to say, like, you know, I want to find the fifth item in my array.
Because every once together, you can just do the math.
Like, zero plus five equals five.
Linked list, it's like, now you're passing this bag of popcorn around.
You have to go to the next person in the movie theater.
And then they have to go to the next person.
It's a little more arduous.
And if you want to find the fifth person, you can't just go directly to that person.
You have to go to the first one.
And the first one has to go to the second one.
Second one has to go to the third one.
So, you have to, like, follow these links down.
Yeah, that makes perfect sense.
So, I mostly, if I think of the data structures I use, I mostly use arrays.
So, lists.
And dictionaries.
And then sometimes I want distinct stuff.
So, sets.
I don't find myself using linked lists so often.
But they do have some interesting trade-offs.
Like, when is an array good versus when is a linked list good?
So, again, going back to this movie example.
Sometimes you go to the theater and you just don't have eight seats together, right?
Like, sometimes you just can't fit an array in memory because you don't have, you know,
if your array, if the array you want to create is too big, you just don't have space for it.
Or, what can be bad also is, let's say, eight of you sits down at the theater and you found
eight seats, everything's great, and now another person shows up.
So, now you have nine people.
But there's no space for a ninth person.
So, now you have to all get up and go around trying to find that ninth seat.
So, you know, similarly, when you want to add elements to an array, let's say you allocated
memory for 100 elements.
And now you want to increase the size of your array to 200.
Well, it's going to be a lot of work to move those, all those items to a different part of
memory.
You know, that's bad performance set.
Right.
If you have a linked list.
Or if I want to insert one in the middle, something like that, right?
Exactly.
Like, it's hard to move all those items.
But for the linked list, you can just put them somewhere and just change the links around.
Yeah.
So, you talked about the big O performance of both of those.
And basically, inserts for lists are O1.
So, constant, like super fast.
But, like, random access is order in, which is not so great.
But it's almost the reverse for arrays, right?
Random access is just instant, more or less.
But adding something grows as you have more items, right?
Because you've got to copy and reallocate and all that.
So, they're almost like counterpart, like opposites in some way from a performance tradeoff.
Exactly.
And that's kind of, you know, you hear all that and you start thinking, gosh, I wish I had something that was as good as arrays for reads and as good as link lists for inserts.
And that's when you start getting into, like, the more complex data structures.
Right.
Absolutely.
So, another thing that you covered that I recall, like, this has burnt a spot into my brain from when I learned it is recursion.
And I just remember recursion, like, blowing my mind when I first thought of problem solving with recursion.
Oh, my gosh.
Yeah.
This is another one that's so hard for people to start thinking about it because it's just, you know, a function calling itself.
That just seems crazy.
But that's why I have a lot of examples about recursion and I have a lot of exercises.
And I kind of try to break it down so people understand the structure of a recursive solution.
Even if you never plan to use recursion in a problem, there are plenty of algorithms that other people have created that use recursion.
So, if you want to understand those algorithms, you need to know what recursion is.
Yeah, absolutely.
And there are times when you can solve a problem without recursion.
But the data you're trying to understand is so perfectly lined up for recursion that the solution is just dead simple.
If you realize that that's something in your toolbox, right?
Like tree, like depth first sort of tree type processing and things like that.
Exactly.
Yeah.
So, one thing that you had at the beginning was this example with boxes.
And you have like a little box story in the attic for loops and recursions.
Yeah.
So, this was a toy example where, you know, you're going to your grandma's attic and you're looking for this key and she has so many boxes.
And it could be among these boxes.
So, you open a box and then you see more boxes inside that box.
So, now you can think about, you know, there's two ways you could find this key.
You could kind of keep this list of boxes, right?
So, like you open a box, you see more boxes and you just add them to your pile of boxes to check.
And you, the algorithm you're running is you pick up a box from the pile, look for the key.
If you see some boxes, you add it to the pile.
And until you find the key, you just grab another box from the pile and check it for the key.
And that's the while loop approach, right?
Because while you don't have the key, go to the pile, pick up a box, search for the key.
And the recursive approach would be open a box.
If there's a key, you're done.
If there's a box, open the box.
If there's a key, you're done.
If there's a box, open the box, you know.
Yeah.
It's got this beautiful, very simple quality to me where you can express it in two lanes.
Like, if key, done.
Else, keep going.
Do it again.
Just open the box and see if there's a key in it.
Yeah, it's got this very natural way of solving the problem, doesn't it?
That's cool.
Yeah.
We all love Python for its tremendous productivity benefits.
But getting the best performance takes some work.
What if you could get out of the box, easy access to high-performance Python?
Intel distribution for Python developers delivers just that.
Get close to 100 times better performance for certain functions when using NumPy, SciPy,
Scikit-learn, linked with optimized native libraries like Intel Math Kernel Library,
access-efficient multi-threading, and Python projects like Numba and Scithon.
Try the Intel distribution for Python and experience performance today at talkpython.fm/Intel.
And profile your Python and native C, C++ applications for performance hotspots with Intel VTune amplifier.
With Intel, it's all about performance.
I like how you've got some nice pictures and the pictures are even simpler.
It just feels really great.
The other thing that was interesting was in your first example, you talked about having this list of boxes.
And you put the stuff in the list and you take the stuff out of the list.
In the recursion example, you don't have anything that is the storage of where you are or what box you're working on or anything like that.
Like, how do you keep track of the boxes?
So that's a really interesting part of recursion, where you're kind of making the computer do the work for you, right?
Because you call, let's say you call the look for key function.
So you've called it once, and the computer has that, you know, that information noted.
Like, okay, he's called look for key once.
And then you call it again inside look for key.
So the computer says, okay, that's the second call to the look for key function.
And then you call it again, and it says, okay, that's the third call.
So it's kind of keeping track of those calls for you.
And those function calls is your array, basically.
You're keeping track of all the boxes you have to check through that array of function calls.
But the computer is doing it all for you behind the scenes.
You don't even have to think about it.
Yeah, absolutely.
It's just, it's the way programs execute, right?
And you're just taking advantage of that.
It lines that up for you.
That's cool.
So this whole recursion thing is more or less, is very good at solving this kind of divide and conquer inductive problem.
If you can talk about some kind of base case, and you can talk about, well, how do I take like one step away from there?
You can probably apply recursion.
Yep.
I'm reading this book called How to Solve It, which is a famous math book about like solving hard problems.
And I love one of the parts in this book.
He says, if you come across a problem you can't solve, change it into a problem that you can solve and solve that problem instead.
I mean, that's so easy.
And that's the same thing with divide and conquer, where it's really hard to solve this problem.
But I'm going to just take it down to the smallest component that I can solve and use the solution for that to solve this bigger problem.
Yeah.
It kind of gives you a foothold on climbing the solution or whatever.
Yeah.
So you have two examples of divide and conquer that you gave in this area.
Yeah.
And I'm going to talk about the quick sort one because it's so elegant.
Yeah.
It's a great example of divide and conquer.
And again, such a simple idea.
You have an array of elements that you want to sort, but you don't know how to sort an array.
Well, what's an array you can sort?
How about if the array had zero elements?
That's pretty easy to sort.
It's just there's nothing to sort.
It's sorted.
Similarly, if you have an array with one element, pretty easy.
If you have an array with two elements, it's still, you know, you just check which one's bigger and put it at the end.
So all of these are the easy examples.
Now you get to an array with three elements.
And quick sort says, just pick an element from the array.
So it doesn't matter which one.
So I'll just pick the first one.
So let's say your array is 5, 3, 7.
So I pick 5 as my, it's called the pivot element.
And now I look at the rest of the elements in the array.
So 3 and 7.
And I know that 3 is less than 5.
And I know that 7 is greater than 5.
So now I have these two sub-arrays, right, of elements less than the pivot and elements greater than the pivot.
And now I just call quick sort again on those two arrays separately.
So I call quick sort of this array that only has the element 3.
And we know how to solve, we know how to sort an array with one element.
It's just 3.
And then you have the pivot because that's the number greater, you know, we know that that's greater than 3.
And then you call quick sort on the second array, which has the 7.
And again, it's just one element, we know how to sort that.
So you end up with these three sub-arrays, one with just a 3, one with just a 5, and one with just a 7.
And you just smash them all together and you have a sorted array.
So using just the knowledge of how to sort an array with 0, 1, or 2 elements, you started an array with 3 elements.
And now that you can do that, you can sort an array with 4 or 5 elements.
And you can kind of sort any array you want just by solving that small problem.
Yeah, you just continue to break it down, even if you have a million, right?
Exactly.
Nice.
Yeah, quick sort is lovely.
And the history of quick sort is pretty interesting.
So another thing, the next thing in your book that you talked about is one of my favorite data structures.
I don't necessarily use it the most, but when I do use it, it's so awesome.
And that's hash tables or dictionaries, right?
Yeah.
I mean, this is one of the reasons I love JavaScript is, you know, JavaScript objects are just hash tables.
So hash tables are such a big part of JavaScript.
And it's, I mean, like I said, I feel like almost any problem, I could just, you know,
if I just want the quick and dirty solution, I can just do the hash table and call it done.
Yeah.
So you had a really nice example of a checkout person.
Oh, yeah.
The Maggie.
Yes.
You need a Maggie.
How much is an avocado?
It's $1.49.
Thank you, Maggie.
Yeah.
Isn't, I mean, that's exactly what a hash table is, where you can either look up prices
in this book and it kind of takes you some time.
Or you just have a person there who has it all memorized.
And I just say, you know, it's 67 cents.
Thank you.
Maggie is my wife's name.
And I feel like she is so much smarter than I am.
So I knew I needed to make her a character in this book.
Oh, that's a nice touch.
Yeah.
Very cool.
Yeah.
So if people want to get a sense of like how powerful hash tables or dictionaries are,
I just last week wrote a search engine so people could search every single bit of content of
all the podcast episodes.
So if you go to talkpython.fm, there's like a little search thing in the top right.
And you can click it and you can type in complex searches and it'll find basically anything that
matches all those keywords.
And the way it works is it goes through all the transcripts.
It goes through all of the show notes.
It goes through all the titles, all those various things and a few others.
And it turns it into a bunch of keywords and turns that into a dictionary.
And then for each keyword it finds, it figures out if there's a piece that matches, you know,
what pieces match this keyword and it puts that in there.
And if you go there, you know, it's like 80 hours of conversation plus some other stuff.
And you can type in a keyword and hit enter and it runs in sub millisecond time, 100% in Python.
You know, so you, yeah, you can search for like five,
finding the things that contain these five words across 80 hours of conversation, 0.1 milliseconds.
100% by all.
Beautiful.
I mean, that is like, think of if that was trying to, you know, regular expression, the text,
or it was trying to like, you know, literally search it or whatever, right?
Like it would be insane.
You just, you're like, ah, this is too slow.
But yeah, it's so like things like that are just so possible with dictionaries.
They make me happy.
Cool.
So let's talk about some of the other algorithms.
And we're kind of getting short on time.
So maybe just sort of skip over and just touch on them a bit.
Sure.
Again, chapters five and six are super useful to me, you know, hash tables and graphs.
And a graph is this really simple idea where you model a problem using nodes and edges.
So my example is, you're trying to get from Twin Peaks to the Golden Gate Bridge.
And this is how you can tell that I live in San Francisco.
And you're trying to figure out what is the least number of bus transfers I have to do to get to from Twin Peaks to the Golden Gate Bridge.
And so you can model that, you can model it using a graph where you have one node, which is the Golden Gate, which is Twin Peaks.
And then you kind of puts out edges, which are all the different bus routes you can take to the next part, to the next transfer stop.
And then that one puts out edges of all the buses you can take from that one to the next transfer stop and so on until you hit the Golden Gate Bridge.
And it's a, this is a classic, it's called the shortest path problem.
Another example would be, you're on Facebook and you're trying to find, you really want to talk to, I don't know, someone famous, Brad Pitt, for example.
And so you're trying to figure out what is the shortest number of connections to Brad Pitt?
Like, you know, what is the least number of people?
Which one of your friends could introduce you indirectly?
Something like this, right?
Exactly.
I mean, LinkedIn does this where they say, like, you're, you know, so many connections away from this person.
And it's just graphs.
It's a graph problem.
Nice.
Okay.
And then you talk about greedy algorithms and your dynamic programming.
Yep.
And again, greedy algorithms are so simple.
It's just do the simplest thing you can do.
So, you know, my example is you are a thief.
This is the classic knapsack problem.
So, you're a thief in a department store and you have a knapsack and you're trying to figure out what items can I steal to get the maximum value, to steal the maximum value of items.
And different items have different values, but there's only so much space in your knapsack.
So, the greedy approach says, pick the most expensive item that will fit in your knapsack and put it in there and then steal the next most expensive item that will fit and keep going until you have filled your knapsack.
And it doesn't give you a perfect solution, but it gives you a good enough solution where it's good enough for most cases.
Yeah, this optimization problem.
Interesting.
Yeah.
And then recommendations with K nearest neighbors.
Oh, yes.
Again, really simple concepts.
My example is, let's say you are a Netflix user and Netflix is trying to recommend movies to you.
And they know that you have, I love the Matrix, for example.
So, they know that I've rated the Matrix five stars on Netflix and a bunch of other movies.
So, they look for other users that have similar ratings on those movies.
So, they might say, like, you rated the Matrix five stars.
It looks like Keanu Reeves rated the Matrix five stars also.
And then you rated, I don't know, 101 Dalmatians five stars.
And Keanu Reeves rated 101 Dalmatians five stars also.
So, it seems like the two of you have a common taste in movies.
We're just going to look at what other movies Keanu likes that you haven't seen.
And we'll just recommend them to you because you probably will like them also.
Yeah, that's cool.
That's a pretty simple recommendation engine.
But I recall a few years ago that Netflix had, like, a challenge to the community to build the best recommendation engine.
And they had, like, a million dollar prize or something big like that, right?
Do you remember?
Did you hear about this?
Yeah, I did.
And I think they used to use K-nearest neighbors.
I'm not 100% sure.
But I think they used K-nearest neighbors before that price came out.
So, that's how, you know, it worked for them for so long.
And I think the current version uses a modified version of K-nearest neighbors.
Yeah, I don't see how you get around something like this being at least part of the solution, right?
Yeah.
Awesome.
I think that's quite a good introduction to algorithms.
You know, if you're out there listening and you didn't have a formal computer science education or, like me, you kind of paid attention and you forgot and these ideas were living in the edge of your memory, but you wouldn't mind a reminder.
I think this is a really interesting way to learn it with this nice illustrations and simple stories.
I really appreciate your book.
I think we're probably out of time, so I have to leave it there.
Let me ask you a couple of questions before I let you go, though.
I always ask my guests.
Sure.
Yeah, there's now over 90,000 PyPI packages out there, distinct packages.
I'm sure you've come across some that you found interesting that maybe not everybody knows of.
Anything come to mind you want to recommend?
Oh, my gosh.
I'm sure everyone knows about the one I'm going to recommend, but it's called NumPy.
Oh, yeah.
And it's, you know, I'm starting to get more into machine learning and it's so useful.
Yeah, I think the whole things like NumPy and SciPy and the whole data science story has really opened up a whole new avenue for Python to grow, right?
It's not just a web development technology.
It's also so much for science and it's amazing what people are doing with it.
Editor, if you're going to write some Python code, what editor do you use?
I have to go with Vim.
All right, Vim, right on.
Okay, so any final call to action?
How do people find your book?
Things like that.
So if they just go to my website, it's audit.io, A-D-I-T dot I-O.
There's a link to my book and there's blog posts there.
Oh, you said that people can get the pictures and use them like for their classes if they're a teacher or something.
Yes, that's something not a lot of people know.
But all the images from the book are available for free online and high res.
So if you're a teacher and you want more images related to algorithms, there's like 400 images from this book and they're all on my GitHub.
So it's github.com/Egon Schiele.
And maybe you can add a link so I don't have to spell that out.
Yeah, I'll definitely link to that.
No problem.
That'll be in the show notes.
All right.
Well, it's been great to talk to you and I definitely recommend your book to people.
I think it's very approachable.
So if this kind of thing is interesting to you, check it out.
Thank you so much.
You're welcome.
Thanks for being on the show.
Talk to you later.
Take care.
This has been another episode of Talk Python to Me.
Today's guest has been Adit Bhargava.
And this episode has been sponsored by Capital One and Intel.
Thank you both for supporting the show.
Are you a data scientist or Python developer who loves data?
If you're looking for a place to work on data science with truly big data that can affect millions of lives,
then head on over to jobs.capitalone.com slash talkpython and check out the wide range of jobs that Capital One is trying to fill right now.
The Intel distribution for Python delivers the high performance Intel C libraries built right into Python.
Get close to 100 times better performance for certain functions when using NumPy, SciPy, and Scikit-learn.
Check them out at talkpython.fm/intel.
Are you or a colleague trying to learn Python?
Have you tried books and videos that just left you bored by covering topics point by point?
Well, check out my online course Python Jumpstart by building 10 apps at talkpython.fm/course to experience a more engaging way to learn Python.
And if you're looking for something a little more advanced, try my Write Pythonic Code course at talkpython.fm/pythonic.
You can find the links from this episode at talkpython.fm/episodes slash show slash 82.
Be sure to subscribe to the show.
Open your favorite podcatcher and search for Python.
We should be right at the top.
You can also find the iTunes feed at /itunes, Google Play feed at /play,
and direct RSS feed at /rss on talkpython.fm.
Our theme music is Developers, Developers, Developers by Corey Smith, who goes by Smix.
Corey just recently started selling his tracks on iTunes, so I recommend you check it out at talkpython.fm/music.
You can browse his tracks he has for sale on iTunes and listen to the full-length version of the theme song.
This is your host, Michael Kennedy.
Thanks so much for listening.
I really appreciate it.
Smix, let's get out of here.
Stating with my voice, there's no norm that I can feel within.
Haven't been sleeping, I've been using lots of rest.
I'll pass the mic back to who rocked it best.
Thank you.