Daily Coding Problem 1

reverse_interleave.rb

# This problem was asked by Google.
# 
# Given a stack of N elements, interleave the first half of the stack
# with the second half reversed using only one other queue. This should be done in-place.
# 
# Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue.

def reverse_interleave(stack)
  return stack if stack.length < 3
  
  stop = stack.length
  size = 1
  queue = []
    
  loop do
    while stack.length > size do
      queue.push stack.pop
    end
    
    while queue.length > 0 do
      stack.push queue.shift
    end
    
    size += 1
    break if size.eql? stop
  end
  
  return stack
end

reverse_interleave [1, 2, 3, 4, 5, 6, 8, 9, 10]
# For example, if the stack is [1, 2, 3, 4, 5], it should become [1, 5, 2, 4, 3]. If the stack is [1, 2, 3, 4], it should become [1, 4, 2, 3].
# for stack of size n
# first iteration goes through n-1 pops and n-1 enqueues
# second iteration goes through n-2 pops and n-2 enqueue
# n(n-1)/2 => n^2
# time O(n^2)
# space O(n)