Google Interview Question for Software Engineer Interns


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.

- CT November 28, 2014 | Flag Reply
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.

- Xuan Luong January 15, 2015 | Flag Reply
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;
}

- Anonymous January 25, 2015 | Flag Reply
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.

- Francesco November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Victor November 22, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More