Ruby Interview Question Practice: Array Into Stacks

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"
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s