AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Hardstackpermutation

~120s

An impossible stack output

The numbers 1, 2, 3, 4 are pushed onto a stack in that order, and a pop may be performed at any point. Which output sequence is impossible?

Show the answer and the worked solution

Correct answer: C.

3, 1, 2, 4

Worked solution

  1. To emit 3 first, the numbers 1, 2 and 3 must all have been pushed, leaving 1 at the bottom with 2 above it.
  2. After popping 3, the top of the stack is 2, so the next pop yields 2, or else a number pushed later.
  3. The sequence demands 1 next, but 1 is buried under 2, so 3, 1, 2, 4 cannot be produced.
  4. The other three are realisable: pushing and popping alternately gives 1, 4, 3, 2 and 2, 4, 3, 1, while pushing everything and then popping gives 4, 3, 2, 1.

Answer: 3, 1, 2, 4.

The idea

A stack output is impossible exactly when some later value is popped before an earlier value that lies above it. Checking what is trapped under the first popped element settles most of these instantly.

Shortcut. A push-in-order stack can never output the pattern high, low, middle (such as 3, 1, 2); scan each option for it, and only 3, 1, 2, 4 contains one.

Common trap. "2, 4, 3, 1" looks impossible because 1 comes out last, but push 1, push 2, pop 2, push 3, push 4, pop 4, pop 3, pop 1 produces it.

Data Structures & Algorithms

4 of 40

Level

Hard

Target time

~120s

PreviousNext
AI InterviewGet started

An impossible stack output — Aptitude Question

An impossible stack output: The numbers 1, 2, 3, 4 are pushed onto a stack in that order, and a pop may be… Answer and worked solution on CodeKairo.

Question

The numbers 1, 2, 3, 4 are pushed onto a stack in that order, and a pop may be performed at any point. Which output sequence is impossible?

Options

  1. 1, 4, 3, 2
  2. 2, 4, 3, 1
  3. 3, 1, 2, 4
  4. 4, 3, 2, 1
Show the answer and the worked solution

Correct answer: C. 3, 1, 2, 4

Worked solution

  1. To emit 3 first, the numbers 1, 2 and 3 must all have been pushed, leaving 1 at the bottom with 2 above it.
  2. After popping 3, the top of the stack is 2, so the next pop yields 2, or else a number pushed later.
  3. The sequence demands 1 next, but 1 is buried under 2, so 3, 1, 2, 4 cannot be produced.
  4. The other three are realisable: pushing and popping alternately gives 1, 4, 3, 2 and 2, 4, 3, 1, while pushing everything and then popping gives 4, 3, 2, 1.

Answer: 3, 1, 2, 4.

The idea

A stack output is impossible exactly when some later value is popped before an earlier value that lies above it. Checking what is trapped under the first popped element settles most of these instantly.

Shortcut. A push-in-order stack can never output the pattern high, low, middle (such as 3, 1, 2); scan each option for it, and only 3, 1, 2, 4 contains one.

Common trap. "2, 4, 3, 1" looks impossible because 1 comes out last, but push 1, push 2, pop 2, push 3, push 4, pop 4, pop 3, pop 1 produces it.

All Data Structures & Algorithms questions · placement mock tests