stack

Problem Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.  Example For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a corresponding pop sequence, but the sequence 4, 3, 5, 1, 2 is not. Solution An intuitive thought on this problem is to create an auxiliary stack. [Read More]

Problem In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints: (A) Only one disk can be moved at a time. (B) A disk is slid off the top of one rod onto the next rod. [Read More]

Problem In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions. Solution We can describe the problem input as an array of numbers/characters representing persons in the party. [Read More]

Problem - Implement a stack using a queue Solution Method 1 - Implement a stack using 2 queues We have already discussed the problems here. Method 2 - Implement a stack using a single queue Here are the operations(note that push operation is expensive) push: enqueue new element. If n is the number of elements in the queue, then remove and insert element n-1 times. pop: dequeue push 1 front +----+----+----+----+----+----+ | 1 | | | | | | insert 1 +----+----+----+----+----+----+ push2 front +----+----+----+----+----+----+ | 1 | 2 | | | | | insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | 2 | 1 | | | | remove and insert 1 +----+----+----+----+----+----+ insert 3 front +----+----+----+----+----+----+ | | 2 | 1 | 3 | | | insert 3 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | 1 | 3 | 2 | | remove and insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | | 3 | 2 | 1 | remove and insert 1 +----+----+----+----+----+----+ Code: [Read More]

Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size) Solution A similar problem has been blogged here, where we implement a queue using 2 stacks. There should be TWO versions of the solution. Version A: The stack should be efficient when pushing an item. Version B: The stack should be efficient when popping an item. Method 1 - When push is efficient and pop is costly [Read More]

Problem Stack with find-min/find-max in O(1) time Solution Method 1 - using extra stacks for min and max The basic idea of the solution can be found here. Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element. Now the operations will be following : push: - If the element being pushed is less than the top element of ‘min_stack’ then push it on ‘min_stack’ as well. [Read More]

**Question ** Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). [Read More]

Problem: How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space? Lets denote the stacks by suffix 1 and 2. Now we have to implement the following methods : push1(int x) –> pushes x to first stack push2(int x) –> pushes x to second stack pop1() –> pops an element from first stack and return the popped element [Read More]

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max \--------------- ----- $1 3 -1$ -3 5 3 6 7 3 1 $3 -1 -3$ 5 3 6 7 3 1 3 $-1 -3 5$ 3 6 7 5 1 3 -1 $-3 5 3$ 6 7 5 1 3 -1 -3 $5 3 6$ 7 6 1 3 -1 -3 5 $3 6 7$ 7 Input: A long array A[], and a window width w [Read More]