Bloomberg LP Interview Question Financial Software Developers
0of 0 votesimplement a deque
Country: United States
Interview Type: Phone Interview
Not so fast. From a reference at cplusplus dot com:
Deques may be implemented by specific libraries in different ways, but in all cases they allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).
...
Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.
That doesn't sound too much like a doubly-ended linked list. Deques provide a random access iterator, but yet they're also not arrays; they split the storage into multiple chunks.
I don't know about C++ but Java provides the same "java.util.Deque" in two classes, one using an array and the other using a linked list. Also, refer to Data Structure in Java by Goodrich and Tamasia, they have also provided the implementation using LinkedList.
LinkedList may not be the ideal candidate for Deque but is definitely one of the best amongst the known data structures.
I see, Java also has an interface called Deque, which apparently is different from what's called a deque in C++. I've devleoped far more Java than C++, and yet I've never really heard much mention of these in Java, though I hear about them in C++ contexts. I suppose the thing to ask would be which deque we're discussing. Reviewing the Javadoc, I agree that Deques in Java seem to just be double ended queues with nothing too fancy. The array implementation is probably implemented as a circular buffer.
#include <iostream>
#include <deque>
using namespace std;
int main()
{
// Stack behavior using a STL deque
deque<int> q;
try {
if ( q.empty() )
{
cout << "Deque is empty" << endl;
}
// Push elements
q.push_back(100);
q.push_back(200);
q.push_back(300);
// Size of queue
cout << "Size of deque = " << q.size() << endl;
// Pop elements
cout << q.back() << endl;
q.pop_back();
cout << q.back() << endl;
q.pop_back();
cout << q.back() << endl;
q.pop_back();
}
catch (...) {
cout << "Some exception occured" << endl;
}
// Queue behavior using a STL deque
deque<int> q1;
try {
if ( q1.empty() )
{
cout << "Deque is empty" << endl;
}
// Push elements
q1.push_back(100);
q1.push_back(200);
q1.push_back(300);
// Size of queue
cout << "Size of deque = " << q1.size() << endl;
// Pop elements
cout << q1.front() << endl;
q1.pop_front();
cout << q1.front() << endl;
q1.pop_front();
cout << q1.front() << endl;
q1.pop_front();
}
catch (...) {
cout << "Some exception occured" << endl;
}
}
Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300
#include <iostream>
using namespace std;
template <class T>
class Node{
public:
Node();
Node(T item):next(NULL),prev(NULL),data(item){ }
~Node(){ prev = next = NULL; }
T data;
Node<T> *next;
Node<T> *prev;
};
class DequeEmptyException{
public:
DequeEmptyException(){
cout << "Deque is empty" << endl;
}
~DequeEmptyException(){ }
};
template <class T>
class Deque {
public:
Deque():front(NULL),rear(NULL),count(0){}
int AddFront(const T element);
T RemoveFront();
int AddBack(const T element);
T RemoveBack();
int Size() const;
T Front() const;
T Back() const;
int IsEmpty() const;
private:
Node<T> *front;
Node<T> *rear;
int count;
};
template <class T>
int Deque<T>::IsEmpty() const{
return count == 0 ? 1 : 0;
}
template <class T>
int Deque<T>::Size() const{
return count;
}
template <class T>
T Deque<T>::Front() const{
if(IsEmpty())
throw new DequeEmptyException();
return front->data;
}
template <class T>
T Deque<T>::Back() const{
if(IsEmpty())
throw new DequeEmptyException();
return rear->data;
}
template <class T>
int Deque<T>::AddFront(const T element){
Node<T> *newNode = new Node<T>(element);
cout << "item: " << newNode->data << endl;
if(IsEmpty()){
front = rear = newNode;
++count;
return 0;
}
newNode->next = front;
front->prev = newNode;
front = newNode;
++count;
return 0;
}
template <class T>
T Deque<T>::RemoveFront(){
if(IsEmpty()){
throw new DequeEmptyException();
}
T retVal = front->data;
Node<T> *tmp = front;
if( front->next != NULL){
front = front->next;
front->prev = NULL;
}
else{
front = NULL;
}
count--;
delete tmp;
tmp = NULL;
return retVal;
}
template <class T>
int Deque<T>::AddBack(const T element){
Node<T> *newNode = new Node<T>(element);
if(IsEmpty()){
front = rear = newNode;
++count;
return 0;
}
// append to the list
rear->next = newNode;
newNode->prev = rear;
rear = newNode;
count++;
}
template <class T>
T Deque<T>::RemoveBack(){
if(IsEmpty()){
throw new DequeEmptyException();
}
T retVal = rear->data;
// delete the back node
Node<T> *tmp = rear;
if( rear->prev != NULL){
rear = rear->prev;
rear->next = NULL;
}
else{
rear = NULL;
}
count--;
delete tmp;
tmp = NULL;
return retVal;
}
Create an array of proper size, and then start from the middle of array. Push_back : push after the current elements; push_front: push in front the the current elements.
When the array is not big enough for the front: create another array; its index 0 is the new front, and when ever we do push_front(), the new elements is put at the end of the new array.
When the array is not big enough for the deque back: create another array; new push_back() put the new element in the end of the new array.
in short, there are the front-arrays and the back-arrays, and the middle arrays.
A Deque is a doubly ended queue, that allows insertion and deletion at both the ends.This can be implemented by using a doubly linked list with all the operations in O(1).
- Achilles June 11, 2012Implementation can very easily be provided as follows by creating two extra empty nodes header and tailer pointing to each other at the start. Manipulate the pointers for adding and deleting.