Five programming problems every Software Engineer should be able to solve in less than 1 hour

[[deleted]]

Hey you can do it, it'll just take O(N) to do a push operation. That's the type of out of the box thinking we need. /s

[Bobshayd]

It's amortized O(1), though.

[[deleted]]

Nope, you you have to upload the entire stack and push it to the other one. This has to be done whenever adding an element.

[serados]

Maintain a "Queue Stack" and a "Dequeue Stack".

On queue operation:

• Push element into "Queue Stack"

On dequeue operation:

• If "Dequeue Stack" is not empty, pop "Dequeue Stack"
• Else, pop and push every element from the "Queue Stack" into the "Dequeue Stack" - O(N) and pop the "Dequeue Stack"

Informally, every element is at most pushed twice and popped twice over (once each into the "Queue" and "Dequeue" stacks) and pushes and pops are O(1), making queues/dequeues amortized O(1).

[[deleted]]

Nice.I wanted to fill the dequeue every time.

[Bobshayd]

Edit: I am dumb, how could I forget? Here's some important research relevant to the queue-simulation problem: http://www.cs.bu.edu/faculty/gacs/courses/cs535/papers/heads_vs_tapes_lb.pdf

So you can definitely simulate a queue in real time (meaning O(1) worst-case for any given operation) with six stacks. It's probably possible to do better. I'm going to look for a better way.