Daily Coding Problem: Problem #1

problem1.py

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

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].

Hint: Try working backwords from the end state.

https://dailycodingproblem.com/
"""

def queue_interleave(stack):
  queue = []
  while len(stack) > 0:
    queue.append(stack.pop(0))
    if len(stack) > 0:
      queue.append(stack.pop())
  return queue
  
if __name__ == '__main__':
  # Read input, numbers separated by commas
  stack = [int(n) for n in input().split(',')]
  print(queue_interleave(stack))

At each iteration, we transfer all elements between the first and the last from the stack to the queue. We then push the first and the last elements back to the stack, and transfer all the elements from the queue back to the stack. Since this reverses the input order of the elements, we need to also reverse the order in which the first and the last elements are inserted in the stack at each iteration.
At each iteration, two elements are put in their goal position; we repeat the above process with the remaining elements.
At the end, the stack contains the elements in the reverse order of what we want. We transfer them to the queue, which gives us the desired answer.

Time complexity: We reduce the problem size by 2 at each iteration, and there are n // 2 iteration.
The number of stack and queue operations at each iteration is given by (n - i), where 0 <= i < n // 2.

= n * n // 2 - (1 + 2 + ... + n // 2 - 1)
= n * n // 2 - (n // 2 - 1) * (n // 2) / 2
= O(n^2)

def interleave(stack: Deque[int]) -> Sequence[int]:
    queue: Deque[int] = collections.deque()
    n = len(stack)

    for i in range(n // 2):
        first = None
        last = None
        for j in range(i, n - i):
            x = stack.popleft()
            if j == i:
                first = x
            elif j == n - i - 1:
                last = x
            else:
                queue.append(x)

        if i % 2 == 0:
            stack.appendleft(first)
            stack.appendleft(last)
        else:
            stack.appendleft(last)
            stack.appendleft(first)

        while queue:
            stack.appendleft(queue.popleft())

    while stack:
        queue.append(stack.pop())

    return queue

Instead why can't we just create classes for both Stack and Queue along with its FILO and FIFO properties with a few of the necessary properties like "push()" and "pop()" for Stack and "enqueue()" and "dequeue()" for Queue. And the a few helper classes to do the above program in place(Consisting of Stack and Queue only as per the question).

https://github.com/Nabushan/Interleave_Stack_using_Queue/blob/d1f8c4bdbc73846bcae976f773ee894ebc2b93ef/code.py#L11

Hope so it helps if there's any changes, correction or Suggestion feel free to Comment.

Thanks.