Question

What structure would you select if a customer came and said, I want to have a program where I would be updating the data (I would be putting more data in) and later I want to retrieve in their initial order (I want to get them out in the order they were inserted). What would the most sufficient structure to do that? Explain in your own words.

Answer 1

Following are detailed operations.

insert(x)
1) Check if x is already present by doing a hash map lookup.
2) If not present, then insert it at the end of the array.
3) Add in the hash table also, x is added as key and last array index as the index.

remove(x)
1) Check if x is present by doing a hash map lookup.
2) If present, then find its index and remove it from a hash map.
3) Swap the last element with this element in an array and remove the last element.
Swapping is done because the last element can be removed in O(1) time.
4) Update index of the last element in a hash map.

getRandom()
1) Generate a random number from 0 to last index.
2) Return the array element at the randomly generated index.

search(x)
Do a lookup for x in hash map.

Below is the implementation of the data structure.

/* C++ program to design a DS that supports folloiwng operations 
in Theta(n) time 
a) Insert 
b) Delete 
c) Search 
d) getRandom */
  
#include<bits/stdc++.h> 
using namespace std; 
  
// class to represent the required data structure 
class myStructure 
{ 
    // A resizable array 
    vector <int> arr; 
      
    // A hash where keys are array elements and vlaues are 
    // indexes in arr[] 
    map <int, int> Map; 
  
    public: 
    // A Theta(1) function to add an element to MyDS 
    // data structure 
    void add(int x) 
    { 
        // If ekement is already present, then noting to do 
        if(Map.find(x) != Map.end()) 
            return; 
              
        // Else put element at the end of arr[] 
        int index = arr.size(); 
        arr.push_back(x); 
              
        // and hashmap also 
        Map.insert(std::pair<int,int>(x, index)); 
    } 
          
    // function to remove a number to DS in O(1) 
    void remove(int x) 
    { 
        // element not found then return 
        if(Map.find(x) == Map.end()) 
            return; 
              
        // remove element from map 
        int index = Map.at(x); 
        Map.erase(x); 
              
        // swap with last element in arr 
        // then remove element at back 
        int last = arr.size() - 1; 
        swap(arr[index], arr[last]); 
        arr.pop_back(); 
              
        // Update hash table for new index of last element 
        Map.at(arr[index]) = index; 
    } 
          
    // Returns index of element if element is present, otherwise null 
    int search(int x) 
    { 
        if(Map.find(x) != Map.end()) 
        return Map.at(x); 
        return -1; 
    } 
          
    // Returns a random element from myStructure 
    int getRandom() 
    { 
        // Find a random index from 0 to size - 1 
        srand (time(NULL)); 
        int random_index = rand() % arr.size(); 
              
        // Return element at randomly picked index 
        return arr.at(random_index); 
    }      
}; 
  
// Driver main 
int main() 
{ 
    myStructure ds; 
    ds.add(10); 
    ds.add(20); 
    ds.add(30); 
    ds.add(40); 
    cout << ds.search(30) << endl; 
    ds.remove(20); 
    ds.add(50); 
    cout << ds.search(50) << endl; 
    cout << ds.getRandom() << endl; 
}