Re: Converting a LIFO into FIFO

* arnuld:
Sometime ago, some friend of mine faced an interview for a programming position and he was asked this question:

----------------------------------------------------
Suppose you have two LIFOs: A and B. The only operations you can do on A and B are push() and pop(), These LIFOs have these properties:

1) Elements are always added into A (never into B) and are added in ascending order: 1,2,3,.... N.

2) You pop() an element from A and push() that into B.

3) During pop() from A and push() into B, 1 or more elements may or may not be pushed() into A.

4) The only elements added into B are the ones which are pop()ed from A.

Final question is how you can develop an algorithm so that whenever you pop() an element from B its in the same sequence as it was added. I mean when you push()ed elements into A in ascending order: 1,2,3,...N, hence when you pop from B, the first element should be 1, 2nd pop() should be 2 and so on..

-------------------------------------------------------


That seems like too much of theoretical question to me. Any ideas ?

It's just a problem due to a bunch of constraints.

If any of those constrains can be removed (doing anything else than the described situation) then there is no problem.

So the question is only what constraint(s) you are "allowed" to remove for your solution.

Sounds like a trick question.

"No, you can't do /that/".


Cheers & hth.,

- Alf
.

Relevant Pages

  • Converting a LIFO into FIFO
    ... some friend of mine faced an interview for a programming ... and B are pushand pop, These LIFOs have these properties: ... You popan element from A and push() that into B. ... when you pushed elements into A in ascending order: ...
    (comp.programming)
  • Re: Converting a LIFO into FIFO
    ... and B are push() and pop, These LIFOs have these properties: ... when you pushed elements into A in ascending order: ... It's just a problem due to a bunch of constraints. ...
    (comp.programming)
  • Re: Converting a LIFO into FIFO
    ... and B are pushand pop, These LIFOs have these properties: ... when you pushed elements into A in ascending order: ... With the written threading issues it becomes something more like a ... low and I'd probably not get really high marks for being ...
    (comp.programming)
  • Re: Converting a LIFO into FIFO
    ... and B are pushand pop, These LIFOs have these properties: ... when you pushed elements into A in ascending order: ... If B is empty when we need to pop from it we do: ... take the 5 off and put it to one side and drain more of B: ...
    (comp.programming)
  • Re: Converting a LIFO into FIFO
    ... Suppose you have two LIFOs: A and B. The only operations you can do on A and B are pushand pop, ... You popan element from A and push() that into B. ... void moveAll{ ...
    (comp.programming)