## Google Interview Question for Software Engineer Interns

• 0

Country: Brazil
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

Two stocks:

1) Enqueue by pushing into stack 1
2) Dequeue by popping from stack 2
3) ONLY when you dequeue and there is nothing in stack 2, lock both stacks and transfer all from stack 1 to stack 2 by popping-pushing. This is the worst case scenario for dequeue which is O(n) and the worst case scenario for enqueue if it has to wait for such lock. However, amortized time is constant O(1) for both, enqueue and dequeue

Believe it or not, this is useful. For instance, when there is an operation that exists for stock but not for queue. Such as, getting max in constant time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Stack 1 for enqueuing.
Stack 2 for dequeing. If this stack is empty then keep popping stack 1 and pushing into stack 2 until stack 1 is empty.

O(1) amortized cost in time for each operation since each element is pushed twice and popped twice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is possible without using two stacks (technically making using of recursion stack)

``````#include <iostream>
#include <stack>

template <typename T>
class FIFO {
private:
std::stack<T> STACK;
public:
FIFO() {}
void enqueue(T val);
void dequeue();
T front();
};

template <typename T>
void FIFO<T>::enqueue(T val) {
STACK.push(val);
}

template <typename T>
void FIFO<T>::dequeue() {
if(STACK.empty()) { return; }
if(STACK.size()==1) {
STACK.pop();
return;
}
T tmp = STACK.top();
STACK.pop();
dequeue();
STACK.push(tmp);
}

template <typename T>
T FIFO<T>::front() {
if(STACK.size()==1) {
return STACK.top();
}
T tmp = STACK.top();
STACK.pop();
T value = front();
STACK.push(tmp);
return value;
}

int main() {
FIFO<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << queue.front() << std::endl;
queue.dequeue();
queue.enqueue(4);
std::cout << queue.front() << std::endl;
queue.dequeue();
std::cout << queue.front() << std::endl;
queue.dequeue();
std::cout << queue.front() << std::endl;
queue.dequeue();
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use two stacks. One main to hold the values and an auxiliary stack.
To enqueue an item:
1. pop the whole stack and push it into the auxiliary.
2. push the new item into the main stack, pop the whole auxiliary stack and push it onto the main one.

This takes time proportional to 2N for enqueueing and constant to dequeue. You can make it more efficient by using more auxiliary stacks. E.g. with three stacks it takes N operations to enqueue. Still not optimal.

Comment hidden because of low score. Click to expand.
0

You achieved constant-time dequeue, but linear-time enqueue. While it works, it's not optimal.

There's a way to get constant-time enqueue and amortized constant-time dequeue using two stacks.

What if you kept one stack for enqueueing and the other for dequeueing?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.