Prev: how to use graphics.h in codeblocks
Next: Solutions for handling graphs - help?
From: arnuld on 12 Nov 2009 05:36
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 ?




--
www.lispmachine.wordpress.com
my email is @ the above blog.

From: Alf P. Steinbach on 12 Nov 2009 05:49
* 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
From: H. J. Sander Bruggink on 12 Nov 2009 06:08
On 11/12/2009 11:49 AM, Alf P. Steinbach wrote:
> * arnuld:

<snip>

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

What is wrong with (pseudocode):

function push(element):
push element to A

function pop():
if B is empty:
while A is not empty:
pop element from A
push element to B
pop element from B

It is not thread safe, but that is not a requirement.

groente
-- Sander
From: Alf P. Steinbach on 12 Nov 2009 06:58
* H. J. Sander Bruggink:
> On 11/12/2009 11:49 AM, Alf P. Steinbach wrote:
>> * arnuld:
>
> <snip>
>
>>>
>>> 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/".
>
> What is wrong with (pseudocode):
>
> function push(element):
> push element to A
>
> function pop():
> if B is empty:
> while A is not empty:
> pop element from A

Here "one or more elements may be pushed into A"

> push element to B

Here "one or more elements may be pushed into A"


> pop element from B
>
> It is not thread safe, but that is not a requirement.

The whole question, as formulated, is just silly -- trick question.


Cheers & hth.

- Alf
From: H. J. Sander Bruggink on 12 Nov 2009 07:51
On 11/12/2009 12:58 PM, Alf P. Steinbach wrote:
> * H. J. Sander Bruggink:
>> What is wrong with (pseudocode):
>>
>> function push(element):
>> push element to A
>>
>> function pop():
>> if B is empty:
>> while A is not empty:
>> pop element from A
>
> Here "one or more elements may be pushed into A"

Ah, right. I misunderstood condition 3. Apparently they mean that some
other process or thread can push onto A during push and pop operations,
so thread safety is a requirement after all.

>
>> push element to B
>
> Here "one or more elements may be pushed into A"
>
>
>> pop element from B
>>
>> It is not thread safe, but that is not a requirement.
>
> The whole question, as formulated, is just silly -- trick question.

Indeed.

groente
-- Sander

 |  Next  |  Last
Pages: 1 2
Prev: how to use graphics.h in codeblocks
Next: Solutions for handling graphs - help?