CODEWITHSUNDEEP
javaalgorithmdata-structuresbig-ohashtable
tubby
tubby

Reputation: 2144

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<E>
//     {
//         // 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 >= 0 && index < 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   => []

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

My approach Use a Hashtable for storing values. Hashtable storage = new Hashtable<>(); Have two variable called front and back, which signify the start and end of the data structure's storage range.

  1. add_front(E element)
low--;
storage.put(low, element);
  1. add_back(E element)

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

  1. public void remove_front ();

low++;

  1. public void remove_back ();

high--;

  1. public E get(int index);

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

  1. public void set(int index, E element);

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

  1. public int size();

return high-low+1;

Upvotes: 1

Views: 482

Answers (1)

Hamid Alaei
Hamid Alaei

Reputation: 416

Since the complexity of add_front() and add_back() is needed to be amortized constant, and no memory efficiency required after remove_front() and remove(back), you can use arrays! They are simpler than hash tables and there is no "with high probability" in the run-time complexity.

You can start with an array of size 3, put the first element in the middle, so you have room for one add_front and one add_back. Then when it overflows, just move the elements in the middle of an array of size 6. Generally spaking, you double the array size on every overflow.

You obviously need to keep track of the start and end position of the array, and its current capacity, by some integer variables in your data structure.

Upvotes: 3

Related Questions