1)How do you implement 2 stacks using only one array.Your stack routines should not indicate an overflow unless every slot in the array is used?
Solution:given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left. (By the way we can implement n stacks in 1 array, eg. of 3 stacks in 1 array is given in question 3 below)
2)Propose a data structure which supports the stack Push and Pop operations and a third operation FindMin,which returns the smallest element in the data strucuture all in O(1) worst case time.
Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.
Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).
You can refer the same implementation solution in java - http://k2code.blogspot.in/2011/12/stack-ds-to-implement-constant-time.html
3)Show how to implement 3 stacks in a single array efficiently?(debated question)
Solution:
Suppose
Stack A contains atmost x elements
Stack B contains atmost Y elements
Stack C contains atmost z elements
take a array of size x+y+z
Now the stack A will grow toward right,
and its operations are
POP_A,PUSH_A
Now stack B will grow towards left
and its operations are
POP_B,PUSH_B
similarly stack C will grow towards left
and its operations are
POP_C,PUSH_C
No OVERFLOW will occur durinng this operation for the stack ..............
The example diagram is
aaaaaaaaaaaa--> <--bbbbbbbbbbbbb <--cccccccccccccccc
grows towards right grows towards left grows towards left
Now stack A if from 0 to x elements ............
Stack B from x+1 to y
C from y+1 to z
More - http://k2code.blogspot.in/2011/12/implement-3-stacks-in-1-array.html
4)Consider a empty stack of integers.Let the numbers 1,2,3,4,5,6 be pushed on to this stack only in the order they appeared from left to right.Let S indicates a push and X indicate a pop operation.Can they be permuted in to the order 325641(output) and order 154623?(if a permutation is possible give the order string of operations.
(Hint: SSSSSSXXXXXX outputs 654321)
Solution: SSSXXSSXSXXX outputs 325641.
154623 cannot be output as 2 is pushed much before 3 so can appear only after 3 is output.
5)Given a string containing N S's and N X's where S indicates a push operation and X indicates a pop operation, and with the stack initially empty,Formulate a rule to check whether a given string S of operations is admissible or not (Hint: A string S of operations should always abide by the properties of the stack which in this case only means you never pop an element from an empty stack)
Solution:Given a string of length 2N, we wish to check whether the given string of operations is permissible or not with respect to its functioning on a stack.
The only restricted operation is pop whose prior requirement is that the stack should not be empty.So while traversing the string from left to right,prior to any pop the stack shouldn't be empty which means the no of S's is always greater than or equal to that of X's.
Hence the condition is at any stage on processing of the string,
no of S's > no of X's
6)Find a simple formula for An, the number of permutations the can be printed on an input of n distinct characters to a stack (similar to question 4)
Solution:The numbers are input in the order 1,2,3,...,N.
So the problem amounts to the number of strings each of N pushes(denoted by S) and N pops(denoted by X).
The only criteria to select a string is at any stage of its processing character by character we should have no of S's > no of X's .
This problem is no different from parentheses problem where N needs to give the no of possible permutations of N parentheses , which if given by Nth catalan number Cn=(2n)!/((n+1)! n!).
For more insite into catalan number refer this link.
http://en.wikipedia.org/wiki/Catalan_number
7)Show that it is possible to obtain the permutation P1P2.........Pn from 1,2,.........n using a stack
if and only if there are no indices i < j < k such that Pj < Pk < Pi.
Solution:The solution can be arrived simply by veirfying that among the 6 possible
orders of Pi,Pj,Pk the rest 5 are possible and the ordering in question i.e is Pi,Pj,Pk is not possible.
We leave it to the reader the verification of possibility of the 5 orderings and deal only with proving that the order Pi,Pj,Pk is not possible.
Suppose say that the order Pi,Pj,Pk is possible.
As Pi is the largest and printed first (i < j < k) followed by Pj and Pk,just before the popping of Pi the ordering of these 3 on the stack shall be Pi,Pk followed by Pj(from top).But as j
Solution:given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left. (By the way we can implement n stacks in 1 array, eg. of 3 stacks in 1 array is given in question 3 below)
2)Propose a data structure which supports the stack Push and Pop operations and a third operation FindMin,which returns the smallest element in the data strucuture all in O(1) worst case time.
Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.
Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).
You can refer the same implementation solution in java - http://k2code.blogspot.in/2011/12/stack-ds-to-implement-constant-time.html
3)Show how to implement 3 stacks in a single array efficiently?(debated question)
Solution:
Suppose
Stack A contains atmost x elements
Stack B contains atmost Y elements
Stack C contains atmost z elements
take a array of size x+y+z
Now the stack A will grow toward right,
and its operations are
POP_A,PUSH_A
Now stack B will grow towards left
and its operations are
POP_B,PUSH_B
similarly stack C will grow towards left
and its operations are
POP_C,PUSH_C
No OVERFLOW will occur durinng this operation for the stack ..............
The example diagram is
aaaaaaaaaaaa--> <--bbbbbbbbbbbbb <--cccccccccccccccc
grows towards right grows towards left grows towards left
Now stack A if from 0 to x elements ............
Stack B from x+1 to y
C from y+1 to z
More - http://k2code.blogspot.in/2011/12/implement-3-stacks-in-1-array.html
4)Consider a empty stack of integers.Let the numbers 1,2,3,4,5,6 be pushed on to this stack only in the order they appeared from left to right.Let S indicates a push and X indicate a pop operation.Can they be permuted in to the order 325641(output) and order 154623?(if a permutation is possible give the order string of operations.
(Hint: SSSSSSXXXXXX outputs 654321)
Solution: SSSXXSSXSXXX outputs 325641.
154623 cannot be output as 2 is pushed much before 3 so can appear only after 3 is output.
5)Given a string containing N S's and N X's where S indicates a push operation and X indicates a pop operation, and with the stack initially empty,Formulate a rule to check whether a given string S of operations is admissible or not (Hint: A string S of operations should always abide by the properties of the stack which in this case only means you never pop an element from an empty stack)
Solution:Given a string of length 2N, we wish to check whether the given string of operations is permissible or not with respect to its functioning on a stack.
The only restricted operation is pop whose prior requirement is that the stack should not be empty.So while traversing the string from left to right,prior to any pop the stack shouldn't be empty which means the no of S's is always greater than or equal to that of X's.
Hence the condition is at any stage on processing of the string,
no of S's > no of X's
6)Find a simple formula for An, the number of permutations the can be printed on an input of n distinct characters to a stack (similar to question 4)
Solution:The numbers are input in the order 1,2,3,...,N.
So the problem amounts to the number of strings each of N pushes(denoted by S) and N pops(denoted by X).
The only criteria to select a string is at any stage of its processing character by character we should have no of S's > no of X's .
This problem is no different from parentheses problem where N needs to give the no of possible permutations of N parentheses , which if given by Nth catalan number Cn=(2n)!/((n+1)! n!).
For more insite into catalan number refer this link.
http://en.wikipedia.org/wiki/Catalan_number
7)Show that it is possible to obtain the permutation P1P2.........Pn from 1,2,.........n using a stack
if and only if there are no indices i < j < k such that Pj < Pk < Pi.
Solution:The solution can be arrived simply by veirfying that among the 6 possible
orders of Pi,Pj,Pk the rest 5 are possible and the ordering in question i.e is Pi,Pj,Pk is not possible.
We leave it to the reader the verification of possibility of the 5 orderings and deal only with proving that the order Pi,Pj,Pk is not possible.
Suppose say that the order Pi,Pj,Pk is possible.
As Pi is the largest and printed first (i < j < k) followed by Pj and Pk,just before the popping of Pi the ordering of these 3 on the stack shall be Pi,Pk followed by Pj(from top).But as j
0 comments:
Post a Comment