This interview question comes from chapter three, example one in the book *Cracking the Coding Interview.* I’ve been reading this book as I’ve been on my job hunt. This question was initially worked on by myself and one of my former co-workers on a whiteboard at our old office. And the question was:

Describe how you can take a single array to implement three stacks?

First off, what is a stack?

A stack is a data structure that is similar to an array. A stack can only take data in at the end, and it can only remove data from the end as well. This is usually remembered with the acronym LIFO ( last-in, first-out).

This is kind of a strange question to put into Ruby since stacks aren’t really a concept that gets mentioned often. The best we could do to replicate a stack in Ruby was to create separate arrays. The push method can be used to add elements to the end of an array but so can the special << indicator as well, and that’s syntax we chose to use.

Starting this problem we created our array with ten values and three different stacks that were empty.

array = [1,2,3,4,5,6,7,8,9,10] stack1 = [ ] stack2 = [ ] stack3 = [ ]

We wanted our stacks to be relatively even in size which meant we would need to divide the length of our array by our number of stacks, we stored this in a variable called stack_length.

stack_length = array.length / 3

This of course presents a new problem, our array cannot be divided evenly. So we decided to create a variable for the remainder as well.

remainder = array.length % 3

We then created two new variables for the first two stacks and passed them our original stack_length variable.

stack1_length = stack_length stack2_length = stack_length

For our third stack we set a conditional to see if the remainder value was greater than 0. If it was was we added the remainder to the stack length, if it wasn’t we just set stack3_length to stack_length.

if remainder != 0 stack3_length = stack_length + remainder else stack3_length = stack_length end

Finally we set a variable to the length of the array itself, called array_length. This variable is going to be used as our counter for the while loop we are about to make.

array_length = array.length

Our while loop is set to continue running while array_length is greater than 0.

while array_length > 0 end

Inside the while loop we set up the conditionals for each of the stacks. If the first stack is less than stack1_length we add the value to stack1. We then subtract one from the array_length variable. The logic is repeated for stacks two and three which are contained in elsif statements.

if stack1.length < stack1_length stack1 << array.shift array_length = array_length - 1 elsif stack2.length < stack2_length stack2 << array.shift array_length = array_length - 1 elsif stack3.length < stack3_length stack3 << array.shift array_length = array_length - 1 end

Finally we create some “puts” statements to test our results.

puts "#{stack1} is in stack1" puts "#{stack2} is in stack2" puts "#{stack3} is in stack3"

The final code when it’s all completed looks like this.

array = [1,2,3,4,5,6,7,8,9,10] stack1 = [] stack2 = [] stack3 = [] stack_length = array.length / 3 remainder = array.length % 3 array_length = array.length stack1_length = stack_length stack2_length = stack_length if remainder != 0 stack3_length = stack_length + remainder else stack3_length = stack_length end while array_length > 0 if stack1.length < stack1_length stack1 << array.shift array_length = array_length - 1 elsif stack2.length < stack2_length stack2 << array.shift array_length = array_length - 1 elsif stack3.length < stack3_length stack3 << array.shift array_length = array_length - 1 end end puts "#{stack1} is in stack1" puts "#{stack2} is in stack2" puts "#{stack3} is in stack3"