Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
This is wrong as shown below:
---------------------------------------
1 3 2
----------------------------------------
1,2,3 represent the stacks.
In the below case this answer will go wrong.
a. Keep adding elements in the '3' stack
b. Once '3' reaches '2'.
c. start growing '2' now but as there is no space, you algo will say out of space but in actual there is still space between '1' and '3'.
@anish.. Check the Adjustment Part AGAIN where I am recalculating the stackbase of third stack and shifting elements and lemme know if you fail to understand again.. :)
-------
1 3 2
-------
So as I understand:
a. if you grow '3' and if it reaches '2' there will be collision
b. you will again rebase '3' to be between '1' and former '3' starting place(bottom of the stack).
c. However if we grow '2' and it hit '3' then also you will rebase '3' as explained in above point and re-arrange all the elments of '3' stack and once after re-arrangement you will get space which will be used for growing '2'.
Am I right?
U Got that.. So as I mentioned clearly the Collision cases would be cumbersome.
People may throw better ideas around.. I guess for me.. this itself is bit complex to implement.
Lets assume that the stack has integers. Now the 2 MSB of the integer tell us the stack and the rest 30 bits will represent the number.
If 2 MSB's are
00 -> stack 1
01 -> stack 2
10 -> stack 3.
We will have 3 variables that point to the top of the stacks. Push is O(1). But worst case complexity of pop is O(n)
0.1) Assume: ThreeWayStack<T> is a single class/interface provides 3 stacks of 'T' in one instance
0.2) Assume: ThreeWayStack.Push(int stackId, T item) - Notice extra 'stackId' param
0.3) Assume: ThreeWayStack.Pop(int stackId) - Notice extra 'stackId' param
0.4) Assume: TWS is short form of ThreeWayStack
1) Define StackItem<T> as { T userItem; int link; }
1.1) Link is used as 'previous' item for stacks
1.2) Link is used as 'next' item for free
1.3) UserItem is actual user item
2) TWS has members as:
2.1) top[3] is an array integers initialized to -1
2.2) items[MAX_SIZE] is an array of StackItem<T> - initialized to item(null, slotId+1)
2.2.1) Ex: items[0] = (null, 1), items[1] = (null, 2)
2.3) free - integer representing the free slot id - initialized to 0
3) None
4) TWS.Push(stackId, item)
4.1) Get free slot id (using member var 'free')
4.2) If free slot can't be found, return stack full error
4.3) Take copy of current 'top' as prevTop, and set top of the stack to this free slot
4.4) Move free slot to next free slot using 'link'
4.5) Update a stack item at top slot with userItem = input item and link = prevTop
5) TWS.Pop(stackId)
5.1) Check if top of the given stack id is < 0; if true, return stack empty error
5.2) Take out the stack item at the top of stack id
5.3) Update top of that stack id to the stack item's 'link' value
5.4) Get stack item's userItem in a local variable, say userItem
5.5) Update stack item, with userItem as null and 'link' as current free slot id
5.6) Update current free slot to this slot id
5.7) Return userItem
Time Complexity: O(1) for push and pop
Thanks,
Laxmi
Lets say we are 3 stacks
1 3 2 Now 3 will grow in right side and 2 will grow in left side. For example, there are 12 spaces in entire array, hence all 3 stacks get 4 each. Now we have filled 8 elements for the stack ID 3 and 2 and for stack 1 we just free 2 elements. Now we want to fill more element in stack 2 or 3 then your program will give Error.
In my opinion, in this case, we need to shift the starting index of stack 3 to left so that we can make spaces for Stack 3 or 2.
What do u think?
I think we can maintain a DOUBLE LINKED LIST
I use nxt[x] to indicates the next node of node x ( if next node is empty, then nxt[x] = -1)
I use pre[x] to indicates the previous node in the Stacks.
In the following code, "cur" is the HeadPoint of the vacant list, and "las" is the last node of the vacant list.
For
(1) push, we simply check whether cur is valid.
(2) pop, we may add one node to the vacant list, we have to note that in this time, the list may be empty.
#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;
#define mp make_pair
#define pb push_back
typedef double db;
typedef long long LL ;
const int MAXN = 5;
int cur, las;
int arr[ MAXN ];
int pre[ MAXN ];
int nxt[ MAXN ];
struct Stack{
int top ;
bool push( int x) {
if(cur == - 1) return false ; //overflows
arr[ cur ] = x;
pre[ cur ] = top ;
top = cur; cur = nxt[ cur ];
return true;
}
void init(){
top = - 1;
}
bool pop(){
if(top == -1) return false;
if(cur == -1) cur = las = top; //the vacant list is empty
else nxt[ las ] = top,las = top;// otherwise
nxt[top]=-1;
top = pre[ top ];
return true ;
}
}S[3];
int main(){
for(int i=0;i<MAXN-1;++i) nxt[i]=i+1; nxt[MAXN-1]=-1;
cur = 0; las = MAXN - 1;
for(int i = 0; i < 3; ++ i) S[i].init();
S[0].push( 5 );
S[0].push( 4 );
S[1].push( 3 );
S[2].push( 2 );
S[0].push( 1 ); // {5, 4, 3, 2, 1}
cout << S[0].push( 7 ) << endl; // FULL
S[2].pop(); // {5, 4, 3, x, 1}
cout << S[0].push( 7 ) << endl; //{5,4,3,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
S[1].pop();//{5,4,x,7,1}
cout << S[2].push(6) << endl;//{5,4,6,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
cin >> cur ;
return 0;
}
how about using a datastructure Node {int value; int indexOfNextElement} as array element and then having three index references, one each for each stack pointing to the position of top element of each stack....adding a new element will simply be at the array index equal to the sum of number of elements in the three stacks or simply max of the top position of the three stack + 1
Here is an other solution with LINK LIST
we maintain a list indicates the vacant space stack, whose top node is "cur"
For
(1) Push, we simply add node(cur) to the stack respectively,and pop node(cur) from the vacant stack.
(2) Pop, we add node( Stack_now.top ) to the top of the vacant space stack.
#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;
#define mp make_pair
#define pb push_back
typedef double db;
typedef long long LL ;
const int MAXN = 5;
int cur;
int arr[ MAXN ];
int pre[ MAXN ];
struct Stack{
int top ;
bool push( int x) {
if(cur == - 1) return false ; //overflows
int p=pre[cur];
pre[ cur ] = top ;
arr[ cur ] = x;
top = cur;cur=p;
return true;
}
void init(){
top = - 1;
}
bool pop(){
if(top == -1) return false;
int p=pre[top];
pre[top]=cur;
cur=top;top=p;
return true ;
}
}S[3];
int main(){
for(int i = 1; i < MAXN; ++ i) pre[i]=i-1; pre[0]=-1;
cur = MAXN - 1;
for(int i = 0; i < 3; ++ i) S[i].init();
S[0].push( 5 );
S[0].push( 4 );
S[1].push( 3 );
S[2].push( 2 );
S[0].push( 1 ); // {5, 4, 3, 2, 1}
cout << S[0].push( 7 ) << endl; // FULL
S[2].pop(); // {5, 4, 3, x, 1}
cout << S[0].push( 7 ) << endl; //{5,4,3,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
S[1].pop();//{5,4,x,7,1}
cout << S[2].push(6) << endl;//{5,4,6,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
cin >> cur ;
return 0;
}
Store it as a String array where the data has two parts "<Data>:<index>" . Here address points to the previous index of that stack. When a new 'Push' comes in we place it in the next empty slot. If we could not find a empty slot and return back to the same address then we have run out of space throw a OutOfBoundsException. The very first element will have index as -1 so when pop-ing pop till index == -1.
How does pop happens? for that also some index to point to its pre-decesssor is needed right? so, do we need to store two indexes here?
The program returns the current index when you push to stack. So say you create an new stack by calling createStack(data) which adds the data array[0]:"e1:-1" , when you add the second element you call push(prevIndex) and it will add array[1]:"e2:0" and it returns 1. So when you pop(currentIndex) you start from 1 and you get the index of the previous element in the stack it 0 and return that.
=> O(1) time complexity for push-pop
=> No shifting required
=> Efficient only if array elements are +ve or in a particular range, otherwise it requires extra O(n) memory [ which is ridiculous because if we already have some extra memory why would we want to do such thing in a single array :) ]
Suppose given array is A[n].
X: First stack starts from A[0] and grows towards right [ maintain only top pointer ]
Y: Second stack starts from A[n-1] and grows towards left.[ maintain only top pointer ]
Z: Third stack starts from A[n/2] and can grow on either side and we can switch the end depending upon availability of space [ maintain left and right pointer + boolean switch for setting direction change for push/pop for its each element + current_top ]
Stack X : Push p
if X.top+1 != Z.left :
A[++X.top] = p
else If Z.right+1 != Y.top:
A[++Z.right] = A[Z.left]
Z.left++
Z.right.direction_change = true
A[++X.top] = p
else
overflow
Stack X: Pop p
Pop A[X.top--] with stack underflow check
Push/Pop strategy for stack Y is same as stack X.
Stack Z: Push p
if current_top is right:
if Z.right+1 != Y.top:
A[++Z.right] = p
else if Z.left-1 != X.top
A[--Z.left] = p
Z.left.direction_change = true
current_top = left
else
overflow
else //current_top is left
if Z.left-1 != X.top:
A[--Z.left] = p
else if Z.right+1 != Y.top
A[++Z.right] = p
Z.right.direction_change = true
current_top = right
else
overflow
Stack Z : Pop p
//with stack underflow check
if current_top is right:
pop p
if Z.right.direction_switch = true
Z.right.direction_switch = false
currect_top = left
Z.right--
else //current_top is left
pop p
if Z.left.direction_switch = true
Z.left.direction_switch = false
currect_top = right
Z.left++
Idea for stack Z is we push on current_top if space is available, otherwise we push on other end
and set the newly pushed element's direction switch flag as true i.e we will use this direction switch
flag while pop operation. This sounds tricky but its better than shifting the middle stack elements.
Moreover if stack elements are all +ve or in some range then there is no need for using extra memory
for direction_switch as we can convert elements to corresponding negative value to denote the flag being set as true.
@cerberuz: Is it allowed to switch sides in a stack?
And, why do you need the elements to be +ve or belonging to a particular range for this to work?
Yes, i think we can switch sides because we need end result i.e O(1) push-pop-top operations + we know linear structure of stack.
If elements are positive then we can set A[i] as negative to indicate that there is a direction change at this position for stack Y. So we don't need any extra memory. Otherwise we have to use a separate boolean array for indicating direction changes for middle stack Y. ( u can think same reason for elements in range also )
P.S : i might have made some mistakes while writing pseudo-code but i hope idea is clear.
It doesn't work. Z will get all scrambled up.
Popping from Z always returns an outermost element, yet pushing enough stuff onto X when the current top element of Z is on the right buries that top element under things that used to be at the left end of Z.
Theres a simple trick that might be useful:
Maintain a data structure which can store 3 elements of required types each accessible independently.
{{
struct node{
<Type1> stack1_data;
<Type2> stack2_data;
<Type3> stack3_data;
};
}}
Maintain 3 variables top1,top2,top3 (each showing TOP of individual stack).
Functions will look like :
push(node,stack_id,value)
pop(stack_id)
Pushing element in stack 1 means setting stack1_data and keeping the other 2 either zero or NULL meaning they are not occupied.
Poping takes stack_id and returns corresponding value using tuple < stack_id , topi > (i 1-3)
Comments are welcome.
Linked list approach to handle N number of stacks in an array:
- Each Node in the array keeps the link to previous item in the list.
- FreeStore is singleton stack which tracks the free nodes in the array.
- to push an element in stack, get an free Node from free store and add the value. O(1)
- to pop. reset the top of the stack. release the popped node to FreeStore. Time O(1).
//Note: code below is not tested completely. Correction/suggestions are appreciated.
#include <iostream>
using namespace std;
struct Node {
int data;
int prev;
};
const int MAX = 5;
// Singleton FreeStore
class FreeStore {
public:
static FreeStore& getFreeStore() {
static FreeStore freeStore;
return freeStore;
}
int pop() {
int ret = top;
if(top != -1) {
top = nodes[top].prev;
}
return ret;
}
void push(int i) {
nodes[i].prev = top;
top = i;
}
Node& getNode(int index) {
return nodes[index];
}
void printNodes() {
for(int i=0; i<MAX; ++i) {
cout << nodes[i].data << ":" << nodes[i].prev << " ";
}
cout << endl;
}
private:
FreeStore() : top(-1) {
cout << "Creating FreeStore" << endl;
for(int i=0; i<MAX; ++i) {
nodes[i].prev = top;
++top;
}
}
private:
int top;
Node nodes[MAX];
};
class Stack {
public:
Stack() : top(-1) {}
void push(int data) {
int index = FreeStore::getFreeStore().pop();
if(index != -1) {
FreeStore::getFreeStore().getNode(index).data = data;
FreeStore::getFreeStore().getNode(index).prev = top;
top = index;
}
else {
cout << "Overflow" << endl;
}
}
int pop() {
int data = -1;
if(top != -1) {
data = FreeStore::getFreeStore().getNode(top).data;
int oldtop = top;
top = FreeStore::getFreeStore().getNode(top).prev;
FreeStore::getFreeStore().push(oldtop);
}
else {
cout << "Stack is empty" << endl;
}
return data;
}
private:
int top;
};
int main() {
Stack st1, st2, st3;
cout << "Poping : " << st1.pop() << endl;
st1.push(5);
st2.push(4);
st3.push(3);
st1.push(2);
st1.push(1);
cout << "Poping : " << st1.pop() << endl;
st1.push(0);
cout << "Poping : " << st3.pop() << endl;
cout << "Poping : " << st2.pop() << endl;
st1.push(6);
st3.push(7);
st2.push(8);
cout << "Poping : " << st2.pop() << endl;
cout << "Poping : " << st1.pop() << endl;
cout << "Poping : " << st3.pop() << endl;
return 0;
}
Divide Array into three portions 0 --- N/3, N/3 --- 2*(N/3), 2*(N/3) --- N.
S1 will start from index 0 and move towards right, S2 will start at N/3 and move towards left. S3 will start at 2*(N/3) and move towards left. If S1 and S2 meet between 0 and N/3, S1 will continue from N and move towards left and S2 will continue from N/3 and move towards right. If S2 and S3 meet in N/3 and 2*(N/3), S3 will continue from 2*(N/3) and move towards right.
The logic is This is like If I assume 3 Stacks A, B, C, I will subdivide A into A1, A2, B into B1 and B2, and C into C1 and C2.
I use 0 to N/3 for A1 and B1, N/3 to 2*(N/3) for B2 and C1 and 2*(N/3) to N for C2 and A2. In this way we can manage three stacks in an array ... I didn't cross check my logic ;) ...
A 2D integer array arr[3][n] where arr[0],arr[1],arr[2] list of indices for the respective stacks' values. For eg. arr[0][0] = 1 arr[0][1] = 2 arr[0][2] =5 will mean that indices 1, 2 and 5 in the given array(of size n) will hold values for the given stack. Also keep 3 counters l1, l2, l3 which will hold the lengths of the respective stacks.
The length of the three stacks doesn't matter. Divide the array into three parts according to your wish with the condition that the new stack must have starting index as the next value of previous stack end (initially assigned)
Store the starting point of the stacks in some location. Now keep track of the top of the stacks as elements are entered. When a stack has reached the end, i.e., reached location one index behind the next stack, check whether the next stack is full or not via the same method. If its not full,move the entire stack elements one position right(not the array) and change the top as well as starting point of the corresponding stack. If the second stack is also ful, turn to third and check the conditions. If thats also full, then array is fully loaded.
this was the case if the first stack overflows.
For the second stack, check the first stack for empty space first, if not present, look the third stack.
For the third stack, check the second stack first, followed by first if no space in second.
1. Build a new Data structure: Node { int nextIndex, T val};
2. Create three integer variables: s1_top, s2_top, s3_top, for tracking the top index for each stack, create method to read and update top index for all stacks.
3. Create a LinkedList for tracking vacant space in the array: list;
3. Implements method:
T pop(int stack_no){
int top = getStackTopIndex(stack_no);
if(top==-1) return null; //stack is empty, nothing to pop up
list.add(top);
int newtop = T.nextIndex;
setStatckTopIndex(stack_no, newtop);
return array[top].val;
}
push(int stack_no, int data){
if(list.isEmpty) return;
int vacant_index = list.getFirst();
int top = getStackTopIndex(stack_no);
array[vacant_index]=new T(data, top);
setStatckTopIndex(stack_no, vacant_index);
list.removeFirst();
}
T peek(int stack_no){
int top = getStackTopIndex(stack_no);
if(top==-1) return null; //stack is empty, nothing to peek
return array[top].val;
}
All O(1) in time.
Here is my solution:
I am storing the MID stack starting initially in the middle of the array.
Then onwards every push to the MID stack is done on either side of the mid variable, depending on the current size of the MID stack.
When performing a push to the MID stack, following collision might occur:
If there is a possible collision with the LEFT stack on a particular push, then i shift the entire mid stack to the RIGHT by half the value of available free space, and then execute the push to the mid stack
Similarly, if there is collision with the RIGHT stack, then I shift the MID stack to the LEFT by half the value of the available free space.
When pushing to the LEFT or RIGHT stack, if there is a possible collision with MID, then I move, the MID stack in the other direction by half the available freespace.
If there is now free space available, then we have an Overflow.
This implementation, doesnt use any extra space.
Every push that results in a shift operation, will take O(n), otherwise all operations are O(1).
enum stackId{LEFT, MID, RIGHT };
class threeStacks {
int* arr;
int leftSize;
int rightSize;
int midSize;
int mid;
int maxSize;
public:
threeStacks(int n):leftSize(0), rightSize(0), midSize(0), mid(n/2), maxSize(n)
{
arr = new int[n];
}
void push(stackId sid, int val){
switch(sid){
case LEFT:
pushLeft(val);
break;
case MID:
pushMid(val);
break;
case RIGHT:
pushRight(val);
}
}
int pop(stackId sid){
switch(sid){
case LEFT:
return popLeft();
case MID:
return popMid();
case RIGHT:
return popRight();
}
}
int top(stackId sid){
switch(sid){
case LEFT:
return topLeft();
case MID:
return topMid();
case RIGHT:
return topRight();
}
}
void pushMid(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(midSize % 2 == 0){
if(mid - ((midSize+1)/2) == leftSize-1){
//left side OverFlow
if(!shiftMid(RIGHT)){
cout << "Overflow!!"<<endl;
return;
}
}
midSize++;
arr[mid - (midSize/2)] = val;
}
else{
if(mid + ((midSize+1)/2) == (maxSize - rightSize)){
//right side OverFlow
if(!shiftMid(LEFT)){
cout << "Overflow!!"<<endl;
return;
}
}
midSize++;
arr[mid + (midSize/2)] = val;
}
}
int popMid(){
if(midSize == 0){
cout << "Mid Stack Underflow!!"<<endl;
return -1;
}
int val;
if(midSize % 2 == 0)
val = arr[mid - (midSize/2)];
else
val = arr[mid + (midSize/2)];
midSize--;
return val;
}
int topMid(){
if(midSize == 0){
cout << "Mid Stack Underflow!!"<<endl;
return -1;
}
int val;
if(midSize % 2 == 0)
val = arr[mid - (midSize/2)];
else
val = arr[mid + (midSize/2)];
return val;
}
bool shiftMid(stackId dir){
int freeSpace;
switch (dir){
case LEFT:
freeSpace = (mid - midSize/2) - leftSize;
if(freeSpace < 1)
return false;
if(freeSpace > 1)
freeSpace /= 2;
for(int i=0; i< midSize; i++){
arr[(mid - midSize/2) - freeSpace + i] = arr[(mid - midSize/2) + i];
}
mid = mid-freeSpace;
break;
case RIGHT:
freeSpace = maxSize - rightSize - (mid + midSize/2) - 1;
if(freeSpace < 1)
return false;
if(freeSpace > 1)
freeSpace /= 2;
for(int i=0; i< midSize; i++){
arr[(mid + midSize/2) + freeSpace - i] = arr[(mid + midSize/2) - i];
}
mid = mid+freeSpace;
break;
default:
return false;
}
}
void pushLeft(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(leftSize == (mid - midSize/2)){
//left side OverFlow
if(!shiftMid(RIGHT)){
cout << "Overflow!!"<<endl;
return;
}
}
arr[leftSize] = val;
leftSize++;
}
int popLeft(){
if(leftSize == 0){
cout << "Left Stack Underflow!!"<<endl;
return -1;
}
leftSize--;
return arr[leftSize];
}
int topLeft(){
if(leftSize == 0){
cout << "Left Stack Underflow!!"<<endl;
return -1;
}
return arr[leftSize - 1];
}
void pushRight(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(maxSize - rightSize - 1 == (mid + midSize/2)){
//right side OverFlow
if(!shiftMid(LEFT)){
cout << "Overflow!!"<<endl;
return;
}
}
rightSize++;
arr[maxSize - rightSize] = val;
}
int popRight(){
if(rightSize == 0){
cout << "Right Stack Underflow!!"<<endl;
return -1;
}
int val = arr[maxSize - rightSize];
rightSize--;
return val;
}
int topRight(){
if(rightSize == 0){
cout << "Right Stack Underflow!!"<<endl;
return -1;
}
return arr[maxSize - rightSize];
}
};
split array into 3 parts such as 0 -- n/3, n/3 -- 2n/3, 2n/3 -- n.
use each of them as separate stack.
You may use one byte in the bottom of each partition for tracking the current top location in the present stack.
@bvg rao: If I perform the push operation on stack1 for more than n/3 times, it'll overflow, won't it? None of the stacks should overflow till the no. of elements is less than or equal to n. For example when you implement two stacks, one which is filled from left to right and the other from right to left, none of them overflows until the no. of elements becomes greater than n.
Correct me if I am wrong.
Well, I guess the way I would like to Achieve this is by something like this.
- hprem991 December 13, 20121> Grow First Stack from the array[0].
2> Grow Second Stack from array[n-1].
3> Here Comes the Challenge. For which I may go for something like this.
Initially I assume array[n/2] and the third array and start growing it accordingly. but when I hit the stacktop of third Stack to the stacktop of any of the other stack, I would recalculate the stackbase of the third array and shift all of its allocated value accordinly.
To recalculate the stackbase of third array probably I may use, the stacktop of the array which does not collide to the stackbase of the third array to find the spacing still available in an array and then divide by 2 to make sure I have spaces left for all the three stack to grow again.
Similarly I would think of stackbase of third array to the stacktop of either array and make again adjustments accordingly.
Ofcourse the collision case would create the time complexity JUMP hugely.. coz I need all stack operation working on together again right from the beginning.