Dell Technologies Interview Question: You are given a dynamic stack... | Glassdoor.co.in

Interview Question

Software Developer Interview(Student Candidate) Bengaluru

You are given a dynamic stack, with random numbers

  constantly being pushed in, and popped out. At any given time, what is the smallest number in the stack. Condition 1 - You are not allowed to scan the entire stack and search for the smallest number. Condition 2 - You cannot use more storage space than the stack itself.
Tags:
brain teaser, algorithm
Answer

Interview Answer

2 Answers

3

While this question seems direct, you can store the smallest number as and when you push items into the stack, but if the smallest number is popped out, you are left with no idea what lies beneath in the the stack.
The interviewer appreciated that this catch was identified quickly, but I don't believe this problem can be solved without running through the entire stack.

Interview Candidate on 29-Aug-2012
0

it is also possible to use an array-based heap. it will require more space, but it will be possible to get the min element within expected time O(logn) (the numbers are in random order)

Anonymous on 10-Sep-2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.