Amazon Interview Question
Software Engineer / DevelopersCountry: -
Interview Type: In-Person
Its very easy question if its a simple Queue implementation. push() and pop() should be easily doable in O(1). It gets a little tricky when its random element deletion and not the first and last element.
In that case, you can swap the element to be deleted with the first or last element and do the appropriate push or pop operation on it.
#include<iostream>
#include<queue>
using namespace std;
template <class T>
void print(const queue<Y>&);
int main()
{queue<string>q; print(q);
q.push("jean"); print(q);
q.push("stefan"); print(q);
q.pop();
q.push("paul"); print(q);
q.push("jessica"); print(q);
q.push("david"); print(q);
q.pop();}
template <class T> void print(const queue<T>&q)
{queue<T>qq=q;
cout<<"size="<<qq.size();
if(qq.empty())cout<<";the queue is empty";
else{cout<<";front="<<qq.front()<<",back="<<qq.back()<<":("<<qq.front();
qq.pop();
while(!qq.empty())
{cout<<","<<qq.front();
qq.pop();}
cout<<").";}cout<<"\n";}
- Martin October 04, 2012