We use cookies to personalize content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners. By clicking "Accept Cookies," scrolling this page, clicking a link or continuing to browse otherwise, you agree to the use of cookies. Privacy and Cookie Policies
You only have 3 free questions left (including this one).
But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.
You're in!
Write a function that takes
an array of characters and reverses the
letters in place.↴
An in-placefunction
modifies data structures or objects outside of its
own stack frame↴
Overview
The call stack is what a program uses to keep
track of function calls. The call stack is
made up of stack frames—one for
each function call.
For instance, say we called a function that
rolled two dice and printed the sum.
defroll_die():return random.randint(1,6)defroll_two_and_sum():
total =0
total += roll_die()
total += roll_die()print total
roll_two_and_sum()
We're still translating this code to Swift. Here it is in Python 2.7:
First, our program calls rollTwoAndSum(). It goes
on the call stack:
rollTwoAndSum()
That function calls rollDie(), which gets pushed
on to the top of the call stack:
rollDie()
rollTwoAndSum()
Inside of rollDie(), we call random.randint().
Here's what our call stack looks like then:
random.randint()
rollDie()
rollTwoAndSum()
When random.randint() finishes, we return back to
rollDie() by removing
("popping") random.randint()'s stack frame.
rollDie()
rollTwoAndSum()
Same thing when rollDie() returns:
rollTwoAndSum()
We're not done yet! rollTwoAndSum()
calls rollDie()again:
rollDie()
rollTwoAndSum()
Which calls random.randint() again:
random.randint()
rollDie()
rollTwoAndSum()
random.randint() returns, then rollDie() returns,
putting us back in rollTwoAndSum():
rollTwoAndSum()
Which calls print():
print()
rollTwoAndSum()
What's stored in a stack frame?
What actually goes in a function's
stack frame?
A stack frame usually stores:
Local variables
Arguments passed into the function
Information about the caller's stack frame
The return address—what the program should do
after the function returns (i.e.: where it should "return
to"). This is usually somewhere in the middle of the caller's
code.
Some of the specifics vary between processor architectures. For
instance, AMD64 (64-bit x86) processors pass some arguments in
registers and some on the call stack. And, ARM processors (common
in phones) store the return address in a special register instead
of putting it on the call stack.
The Space Cost of Stack Frames
Each function call creates its own stack
frame, taking up space on the call stack. That's important
because it can impact the space complexity of an algorithm.
Especially when we use recursion.
For example, if we wanted to multiply all the numbers
between 1 and n,
we could use this recursive approach:
funcproduct1ToN(_ n:Int)->Int{// we assume n >= 1return(n >1)?(n *product1ToN(n -1)):1}
What would the call stack look like
when n = 10?
First, product1ToN() gets called
with n = 10:
product1ToN() n = 10
This calls product1ToN() with
n = 9.
product1ToN() n = 9
product1ToN() n = 10
Which calls product1ToN()
with n = 8.
product1ToN() n = 8
product1ToN() n = 9
product1ToN() n = 10
And so on until we get to n = 1.
product1ToN() n = 1
product1ToN() n = 2
product1ToN() n = 3
product1ToN() n = 4
product1ToN() n = 5
product1ToN() n = 6
product1ToN() n = 7
product1ToN() n = 8
product1ToN() n = 9
product1ToN() n = 10
Look at the size of all those stack frames! The entire call stack
takes up O(n) space. That's right—we
have an O(n) space cost even though
our function itself doesn't create any data
structures!
What if we'd used an iterative approach instead of a recursive one?
funcproduct1ToN(_ n:Int)->Int{// we assume n >= 1var result =1for num in1...n {
result *= num
}return result
}
This version takes a constant amount of space. At the beginning of the loop,
the call stack looks like this:
product1ToN() n = 10, result = 1, num = 1
As we iterate through the loop, the local variables change, but we
stay in the same stack frame because we don't call any other
functions.
product1ToN() n = 10, result = 2, num = 2
product1ToN() n = 10, result = 6, num = 3
product1ToN() n = 10, result = 24, num = 4
In general, even though the compiler or interpreter will take
care of managing the call stack for you, it's important to consider the
depth of the call stack when analyzing the space complexity of an
algorithm.
Be especially careful with recursive functions!
They can end up building huge call stacks.
What happens if we run out of space? It's a stack
overflow! In Swift, the program will just crash and exit.
If the very last thing
a function does is call
another function, then its stack frame
might not be needed any more. The functioncould free up its stack frame before doing its final
call, saving space.
This is called tail call optimization
(TCO). If a recursive function is optimized with TCO, then it
may not end up with a big call stack.
In general, most languages don't provide TCO. Scheme
is one of the few languages that guarantee tail call
optimization. Some Ruby, C, and Javascript
implementations may do it. Python and Java decidedly
don't.
(i.e.: stored on
the process heap or in
the stack frame of a calling function). Because of this, the
changes made by the function remain after
the call completes.
In-place algorithms are sometimes called
destructive, since the original input is
"destroyed" (or modified) during
the function call.
Careful: "In-place" does not mean "without
creating any additional variables!" Rather, it means
"without creating a new copy of the input." In general, an
in-place function will only create
additional variables that are O(1) space.
An out-of-placefunction
doesn't make any changes that are visible to
other functions. Usually,
those functions copy any data structures or objects
before manipulating and changing them.
In many languages, primitive values (integers,
floating point numbers, or characters) are copied when passed as
arguments, and more complex data structures
(arrays, heaps, or hash tables) are
passed by
reference. In Swift, arguments with the inout keyword can be modified in place.
Here are two functions that do the same
operation on an array, except one is
in-place and the other is out-of-place:
funcsquareArrayInPlace(_ numbers:inout[Int])->Void{for i in0..<numbers.count{
numbers[i]*= numbers[i]}// NOTE: no need to return anything - we modified// numbers in place}funcsquareArrayOutOfPlace(_ numbers:[Int])->[Int]{// we allocate a new array with the length of the input arrayvar squaredArray =Array(repeating:0,count: numbers.count)for i in0..<numbers.count{
squaredArray[i]= numbers[i]* numbers[i]}return squaredArray
}
Working in-place is a good way to save time and
space. An in-place algorithm avoids the cost of
initializing or copying data structures, and it usually has
an O(1) space cost.
But be careful: an in-place algorithm can cause side effects.
Your input is "destroyed" or "altered," which can affect
code outside of your function. For
example:
var originalArray =[2,3,4,5]squareArrayInPlace(&originalArray)print("original array: \(originalArray)")// prints: original array: [4, 9, 16, 25], confusingly!
Generally, out-of-place algorithms are considered safer
because they avoid side effects. You should only use an
in-place algorithm if you're space constrained or
you're positive you don't need the original input
anymore, even for debugging.
Why an array of
characters instead of a string?
The goal of this
question is to practice manipulating arrays
in place. Since Swift strings support
unicode, a single character in a string might
be multiple bytes. There's
no O(1) way to get
the ith character in a
Swift string.
To sidestep this complexity, we'll work with
arrays of characters instead, which let us
quickly access characters at any offset.
Breakdown
Start your free trial!
Log in or sign up with one click to get immediate access to 3 free mock interview questions
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
“I started Interview Cake a few weeks before my interview. It really gave me an edge and made me feel more confident with appropriate and challenging practice problems. Thanks!
—
Jake