Prev: how to use graphics.h in codeblocks
Next: Solutions for handling graphs - help?
From: mohangupta13 on 14 Nov 2009 09:54
On Nov 12, 3:49 pm, "Alf P. Steinbach" <al...(a)start.no> wrote:
> * 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/".
I don't have a solution for the question but neither i can say the
problem is insolvable ....If you can then can you kindly prove it or
at least tell with some reason why its not solvable.???
thanks
Mohan
>
> Cheers & hth.,
>
> - Alf

From: Alf P. Steinbach on 14 Nov 2009 11:07
* mohangupta13:
> On Nov 12, 3:49 pm, "Alf P. Steinbach" <al...(a)start.no> wrote:
>> * 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/".
> I don't have a solution for the question but neither i can say the
> problem is insolvable ....If you can then can you kindly prove it or
> at least tell with some reason why its not solvable.???

Rather, it's too easy to solve by almost any change to the as-is situation
that's described. It's like "the door is closed. at any time, a person may bang
against the door and hurt him/her self. how would you avoid that?" Opening the
door is one solution, putting up a don't bang against the door sign + barrier is
another, removing the something that attracts people here is a third, killing
any approaching person is a fourth, relocating the building with the door to
somewhere desolate is a fifth, demolishing that building with the door is a
sixth, adding lots of soft rubber foam to the door is a seventh, so on ad
nauseam, but which of these solutions are "allowed", what are the constraints?


Cheers & hth.,

- Alf
From: Ben Bacarisse on 14 Nov 2009 11:25
mohangupta13 <mohangupta13(a)gmail.com> writes:
<snip>
>> > 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..
<snip>
> I don't have a solution for the question but neither i can say the
> problem is insolvable ....If you can then can you kindly prove it or
> at least tell with some reason why its not solvable.???
> thanks

The trouble is, the specification is vague. I can't tell what is
allowed and what is not allowed. My best guess is that this is what
is intended. I use [ or ] to mark the bottom of a stack and ( or ) to
mark the top.

A B
[1 2 3 4) (]

If B is empty when we need to pop from it we do:

while (!empty(A)) push(B, pop(a))

A B
[1 2 3 4) -> (]
[1 2 3) -> (4]
[1 2) -> (3 4]
[1) -> (2 3 4]
[) (1 2 3 4]

so we can pop(B) to get 1 leaving:

A B
[) (2 3 4]

If, in addition, we need to explain how to pop from A when B is not
empty the we can do the following. Image two more items have bee
pushed onto A:

A B
[5 6) (2 3 4]

We pop(A) by taking 6 off putting it to one side:

A 6 B
[5) <- (2 3 4]
[5 2) <- (3 4]
[5 2 3) <- (4]
[5 2 3 4) <- (]

push the 6:

A B
[5 2 3 4) (6]
[5 2 3 4) -> (6]
[5 2 3) -> (4 6]
[5 2) -> (3 4 6]
[5) -> (2 3 4 6]

take the 5 off and put it to one side and drain more of B:

A 5 B
[) <- (2 3 4 6]
[2) <- (3 4 6]
[2 3) <- (4 6]
[2 3 4) <- (6]

push(B, 5) and the drain A again:

A B
[2 3 4) (5 6]
[2 3 4) -> (5 6]
[2 3) -> (4 5 6]
[2) -> (3 4 5 6]
[) -> (2 3 4 5 6]

and B is not in order again. I think this is what is suggested by the
"during the pop from A..." part. We can do stuff while the top value
of A is "in transit".

--
Ben.
From: stan on 14 Nov 2009 17:48
Ben Bacarisse wrote:
> mohangupta13 <mohangupta13(a)gmail.com> writes:
><snip>
>>> > 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..
><snip>
>> I don't have a solution for the question but neither i can say the
>> problem is insolvable ....If you can then can you kindly prove it or
>> at least tell with some reason why its not solvable.???
>> thanks
>
> The trouble is, the specification is vague. I can't tell what is
> allowed and what is not allowed. My best guess is that this is what
> is intended. I use [ or ] to mark the bottom of a stack and ( or ) to
> mark the top.

As written the spec seems like nonsense, using the apparently most
common interpretation.

If we can control time, then simply establish rules like we allow pusing
into A all day and then at night when everyone goes home you simply
pop A into B which reverses the order and then pop the result off
B. During the day we only allow pushing onto A.

With the written threading issues it becomes something more like a
quantum physics probability problem. Maybe the answer is to set up
conditions where the nodes simply tunnel over to the user and ignore
the stacks entirely.

I don't think I'd get the job because my bullshit filter is set too
low and I'd probably not get really high marks for being
serious. Maybe that's the actual purpose here; let's see how this
candidate approaches thnking about an unsolvable problem.

I'd probably come up with something smart assed like let me check with
the mice and I'll get back to you.
From: Daniel Pitts on 16 Nov 2009 17:55
arnuld wrote:
> 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 ?
>
>


Seems pretty simple to me:
in pseudo-code:

stack a;
stack b;
lock lock;

void enqueue(Item i) {
lock.aquire();
moveAll(b, a);
a.push(i);
lock.release();
}

Item deque() {
lock.aquire();
moveAll(a, b);
Item result = b.pop();
lock.release();
return result;
}

void moveAll(stack &source, stack &dest) {
while (!source.isEmpty()) {
dest.push(source.pop());
}
}



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