Register

GATE IT 2004 | Question: 52

• edited by
6,149 views
24 votes
24 votes

A program attempts to generate as many permutations as possible of the string, '$abcd$' by pushing the characters $a, b, c, d$ in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?

  1. $abcd$
  2. $dcba$
  3. $cbad$
  4. $cabd$
• edited by
User Avatar

1 Answer

Best answer
37 votes
37 votes
  1. push $a$ & pop $a$, push $b$ & pop $b$, push $c$ & pop $c$, and finally push $d$ and pop $d$
    sequence of popped elements will come to $abcd$
  2. first push $abcd$, and after that pop one by one, sequence of popped elements will come to $dcba$
  3. push $abc$, and after that pop one by one sequence of popped elements will come to $cba$, now push $d$ and pop $d$, final sequence comes to $cbad$
  4. this sequence is not possible because '$a$' can not be popped before '$b$' any how
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

51 votes
51 votes
4 answers
1
Ishrat Jahan asked Nov 2, 2014
10,747 views
GATE IT 2004 | Question: 53
An array of integers of size $n$ can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node $\left \lfloor (n - 1) /2 \right \rfloor$ ... to construct a heap in this manner is $O(\log n)$ $O(n)$ $O (n \log \log n)$ $O(n \log n)$
An array of integers of size $n$ can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node $\left ...
User Avatar
65 votes
65 votes
9 answers
2
Ishrat Jahan asked Nov 1, 2014
24,860 views
GATE IT 2004 | Question: 13
Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to delete the node $x$ from the list ? $O(n)$ $O(\log^2 n)$ $O(\log n)$ $O(1)$
Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to del...
User Avatar
23 votes
23 votes
4 answers
3
Ishrat Jahan asked Nov 2, 2014
4,936 views
GATE IT 2004 | Question: 54
Which one of the following binary trees has its inorder and preorder traversals as $BCAD$ and $ABCD$, respectively?
Which one of the following binary trees has its inorder and preorder traversals as $BCAD$ and $ABCD$, respectively?
User Avatar
Link Copied!