Add 2 large numbers in the form of list, without reversing the linked lists
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
You are given two numbers in the form of linked list.Add them without reversing the linked lists. linked lists can be of any length.
Take two stacks and push a linked list to a stack. After done pushing, simply start popping the stacks, add the numbers, get the carry over, generate another node with the result and add to front to a new linked list.
We have already done this question here, which involves reversal of 2 numbers and then adding it.
[Read More]Stack DS to implement constant time Minimum element lookup
Posted on December 28, 2011
(Last modified on August 11, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: You need to implement a stack data structure that can also report the minimum element in constant-time.
Solution
Method 1 - Using extra stack
This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly.
[Read More]How to reverse a stack in place ?
Posted on December 20, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Reverse a stack, using just push(), pop(), top() operations, in its place itself.
You can not assign any known memory address.
Solution:
Simple methodology for this problem is, take last element from the stack i.e. you need to empty the stack [do it recursively, keeping other elements in memory].
Push the last element in the stack again.
Now while pushing each of earlier elements, first empty whole stack and then push them.
[Read More]Use some Datastructure to get O(1) stack operations
Posted on December 19, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal.
Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does.
Insight : compress the information using diff
PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)
POP :
min = pop()
elem = pop()
if elem is -ve
push(min-elem) // earlier min
return min
else
push(min)
return elem + min
MIN :
min = pop()
push(min)
return min
O(n+1) space and constant operations for pop push min
Sorting a Stack using push,pop,isEmpty and peek
Posted on September 11, 2011
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek.
This question is asked in cracking the coding interview. Other ways of asking the question
Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that
should be used to write this program: push | pop | peek | isEmpty Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see.
[Read More]Implement a Queue using two stacks
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Implement a Queue using two stacks.
Solution
Logic : We’ll implement a FIFO queue using two stacks.Lets call the stacks Instack and Outstack. Enqueue:
An element is inserted in the queue by pushing it into the Instack. ** Dequeue:**
An element is extracted from the queue by popping it from the Outstack. If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.
[Read More]Array implementation of stack
Posted on October 20, 2010
(Last modified on August 12, 2020)
| 3 minutes
| Kinshuk Chandra
Here will discuss the array implementation of stack.
Problems with array implementation
Underflow - Array may be empty but people may try to pop the element
Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html
Null items - Can nulls be added - Yes in this case, nulls can be added in stack
[Read More]Array implementation of stack
Posted on October 20, 2010
(Last modified on August 12, 2020)
| 3 minutes
| Kinshuk Chandra
Here will discuss the array implementation of stack.
Problems with array implementation
Underflow - Array may be empty but people may try to pop the element
Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html
Null items - Can nulls be added - Yes in this case, nulls can be added in stack
[Read More]The stack and the heap
Posted on September 1, 2010
(Last modified on August 7, 2020)
| 8 minutes
| Kinshuk Chandra
The memory a program uses is typically divided into four different areas:
The code area, where the compiled program sits in memory. The globals area, where global variables are stored. The heap, where dynamically allocated variables are allocated from. The stack, where parameters and local variables are allocated from. There isn’t really much to say about the first two areas. The heap and the stack are where most of the interesting stuff takes place, and those are the two that will be the focus of this section.
[Read More]Write a C Program to reverse a stack "in place" using recursion ?
Posted on April 10, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
**You can only use the following ADT functions on Stack: IsEmpty IsFull Push Pop Top** #include #include using namespace std;
stack S;
void func(int n){
if(S.empty())
S.push(n);
else{
int t= S.top();
S.pop();
func(n);
S.push(t);
}
}
void Rec(){
if(!S.empty()){
int t = S.top();
S.pop();
Rec();
func(t);
}
}
void printStack(){
if(!S.empty()){
int t= S.top();
S.pop();
cout«”,";
printStack();
S.push(t);
}
else{
cout«"Stack empty now”;
}
}
int main(int argc, char* argv[])
[Read More]