Interview Cake
When a program is running, variables are generally stored on the call stack or the process heap. Knowing where your variables are stored helps you understand your programs and track down subtle bugs.
In C
In C, you can explicitly control whether a variable should be stored on the stack or on the heap. Say we've got this function, which creates an array and fills it with random values:
When generateRandom gets called, space to hold i and randomValues gets allocated in its frame on the call stack.
generateRandom returns a pointer to the randomValues array, so that the caller can access the random values.
When generateRandom returns, its stack frame is de-allocated, freeing up the memory that held i and randomValues.
Whoops! The caller is left with a pointer to nowhere!
What happens when the caller tries to access the returned array? A few things might happen—the program might crash, it might read a value that makes sense, or it might read some random other data that's been written where the array used to be. This can cause security vulnerabilities!
Where can a programmer get memory that sticks around past the end of a function call? Enter the process heap, also sometimes just called "the heap."
Confusingly, "the heap" is not a heap data structure. If your interviewer starts talking about heaps and you're not sure which one they mean, just ask!
The heap is a region of memory that, like the stack, stores variables in a running program. Unlike the stack, memory in the heap isn't tied to a specific function. That means one function can allocate memory on the heap, and other functions can safely use that memory until it's no longer needed.
To fix our C function from before, we can use malloc when we create randomValues. malloc, short for "memory allocate," allocates space for a variable on the heap.
Now, when generateRandom gets called, memory for randomValues gets allocated on the heap, and our stack frame just stores a pointer to it. The memory for i is still on the stack.
When generateRandom returns randomValues, it's returning a pointer to the heap block that holds the array.
So, even after the stack frame for generateRandom gets de-allocated, that pointer is still valid and safe to read from.
It'll stay valid until its explicitly freed later on with a call to free:
In Python 2.7
Python hides all this complexity from you. Behind the scenes, almost everything is allocated on the heap, and garbage collection frees allocations once they're no longer needed.
This stack-vs-heap distinction helps us understand what's happening in in-place vs. out-of-place functions.
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!
