Interview Cake
A garbage collector automatically frees up memory that a program isn't using anymore.
For example, say we did this in Python 2.7:
Look at nums_sorted in get_min. We allocate that whole list inside our function, and once the function returns we don't need the list anymore. In fact, once the function returns we don't have any references to it anymore!
What happens to that list in memory? The Python 2.7 garbage collector will notice we don't need it anymore and free up that space.
How does a garbage collector know when something can be freed?
One option is to start by figuring out what we can't free. For example, we definitely can't free local variables that we're going to need later on. And, if we have a list, then we also shouldn't free any of the list's elements.
This is the main intuition behind one garbage collector strategy:
- Carefully figure out what things in memory we might still be using or need later on.
- Free everything else.
This strategy is often called tracing garbage collection, since we usually implement the first step by tracing references from one object (say, the list) to the next (an element within the list).
A different option is to have each object keep track of the number of things that reference it—like a variable holding the location of an array or multiple edges pointing to the same node in a graph. We call this number an object's reference count.
In this case, a garbage collector can free anything with a reference count of zero.
This strategy is called reference counting, since we are counting the number of times each object is referenced.
Some languages, like C, don't have a garbage collector. So we need to manually free up any memory we've allocated once we're done with it:
We sometimes call this manual memory management.
Some languages, like C++, have both manual and automatic memory management.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
