Bloomberg LP Interview Question
InternsTeam: Financial Software Developer
Country: United States
Interview Type: Phone Interview
Algorithm:
Suppose we have two stacks (stackOne & stackTwo).
Insert new item in queue (Enqueue):
if stackOne is empty
Push this item on stackOne.
else
if stackTwo is empty
then pop possible items from stackOne and push on stackTwo
then push new item on stackOne.
else
print mesaage queue is full
Remove item from queue (Dequeue):
if stackTwo is not empty
then Pop item from stackTwo
else
if stackOne in not empty
Pop all Items from stackOne any place them on stackTwo in poped order.
Pop top item from stackTwo.
else
print message queue is empty.
i am coding only push and pop part
template<typename T>
void push(T x) {
stck.push(x);
}
T pop() {
if (s.empty()) throw error;
T ret = pop_bottom(s);
}
T pop_bottom(stack<T> s)
{
T top = s.top(); s.pop();
if (s.empty()) return top;
else {
T ret = pop_bottom(s);
s.push(top);
return ret;
}
}
suppose the functions in stack include:
void empty();
element pop();
void push(element);
then
class queue{
stack stack1;
stack stack2;
void push_back(element)
{stack2.push(element);
}
void push_front(element)
{stack1.push(element);
}
element pop_front()
{ if (stack1.empty())
restack(stack1, stack2);
if (stack1.empty()) return null; else return stack1.pop();
}
element pop_back()
{ if (stack2.empty())
restack(stack2, tack1);
if (stack2.empty()) return null; else return stack2.pop();
}
void restack(stack stack1, stack stack2)
{while (!stack2.empty())
{element = stack2.pop();
stack1.push(element);
}
}
class queue_using_stack
{
stack<int> st1, st2;
public:
queue_using_stack()
{
}
~queue_using_stack()
{
}
void enqueue(int d)
{
st1.push(d);
}
int dequeue()
{
int val = -1;
if(st1.empty() && st2.empty())
return val;
else if(!st2.empty())
{
val = st2.top();
st2.pop();
return val;
}
else
{
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
val = st2.top();
st2.pop();
return val;
}
}
};
class queue_using_stack
{
stack<int> st1, st2;
public:
queue_using_stack()
{
}
~queue_using_stack()
{
}
void enqueue(int d)
{
st1.push(d);
}
int dequeue()
{
int val = -1;
if(st1.empty() && st2.empty())
return val;
else if(!st2.empty())
{
val = st2.top();
st2.pop();
return val;
}
else
{
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
val = st2.top();
st2.pop();
return val;
}
}
};
- Shashi January 25, 2013