Design a O(1) data structure How would I implement a data structure that supports the following in constant time? I got this question at a job interview, and the following is my solution. Please check my approach, or suggest a better alternate approach, if you have one.

////////////////////////////////////////////////////////////////
// Implement a container that have the following methods:
// Java:
//     public class Container&lt;E&gt;
//     {
//         // data memebers
//         ...
//         public Container();
//             // constructor
//             // Complexity: Constant
//
//         public int size();
//              // return the total number of elements in the container
//              // Complexity: Constant
//
//         public E get(int index);
//              // get an element from the container by its index
//              // Complexity: Constant
//
//         public void set(int index, E element);
//              // set an element in the container by its index. index &gt;= 0 &amp;&amp; index &lt; size()
//              // Complexity: Constant
//
//         public void add_front (E element);
//              // add a new element to the front of the container i.e. its index is 0
//              // Complexity: Constant (amortized time)
//
//         public void remove_front ();
//              // remove the element at the front of the container
//              // Complexity: Constant
//
//         public void add_back (E element);
//              // add a new element to the back of the container i.e. its index is size()
//              // Complexity: Constant (amortized time)
//
//         public void remove_back ();
//              // remove the element at the back of the container
//              // Complexity: Constant
//     }
//
// Examples:
//   at beginning   =&gt; []

//   add_front(0)   =&gt; [0]
//   add_front(-1)  =&gt; [-1, 0]
//   add_back(1)    =&gt; [-1, 0, 1]
//   add_back(2)    =&gt; [-1, 0, 1, 2]
//   get(0)         =&gt; -1
//   get(3)         =&gt; 2
//   set(3, 8)      =&gt; [-1, 0, 1, 8]
//   remove_front() =&gt; [0, 1, 8]
//   remove_back()  =&gt; [0, 1]
////////////////////////////////////////////////////////////////


My approach

Use a Hashtable for storing values:

Hashtable&lt;Integer, Integer&gt; storage = new Hashtable&lt;&gt;();


Have two variable called front and back, which signify the start and end of the data structure's storage range.


add_front(E element)


low--;
storage.put(low, element);


add_back(E element)


high++; storage.put(high, element);


public void remove_front ();


low++;


public void remove_back ();


high--;


public E get(int index);


index = index-low; return storage.get(index);


public void set(int index, E element);


index = index-low; storage.put(index, element);


public int size();


return high-low+1;
You can use the union of two different data structures to have an O(1) data structure (thinking in terms of # of operations):


You need random access to element K in constant time (get and set), a hash table is a good candidate for this.
You want constant time inserts and deletes at the front and back of the structure (add_front, remove_back, etc.). This is what a deque is good for (double-ended queue).


So you can use both structures at the same time, and you'll solve some operations using one or the other structure. The key part is how to keep them synchronized in constant time, and the answer to that is: you only insert/remove elements using the deque, so once you insert/remove an element in the deque (which is O(1)) you go and insert/remove from the hash table too (which is also O(1)).

Some considerations:


This solution uses O(n) memory, but that is not a restriction of the statement of the problem.
A hash table's insert isn't actually O(1), they call it "amortized constant time" because at times the hash table needs to resize its internal storage to accommodate for the new element, which takes O(n) time.
A hash table's get/set is not O(1) either, it depends on the hash function and your elements (worst case scenario all elements fall in the same bucket and you have O(n) search time).