Listening to Data Structure Designing, A lot of people might want to run away looking at the title itself. Those who know me know that I am not leaving until I explain the concept entirely. Embark with me on a journey to learn a problem and a few ideas on our way today!
Many of us would have pored over the term “CRUD”.For those who do not know it, CRUD stands for create read update delete.
Table of Contents
Example
You are creating a database of all your favorite artists.
C-Create
- Let’s say you discovered a new artist and want to put it in the database. You will be creating an entry.
R-Read
- You want to listen to an old artist. Thus, you will be reading a data entry out of the database.
U-Update
- You mistakenly put Rihanna under Pop instead of R&B and need to correct your mistake. Thus, you will update.
D-Delete
- You do not like listening to Tori Kelly anymore. Thus you delete the entry.
In today’s problem, we are to “Design a Data Structure” that performs Insert, Delete, and GetRandom Methods.
Inserting:
Adding an element to the existing data structure
Removing:
As we are designing the data structure, we will be removing the element only if it exists.
GetRandom:
I am returning a random element considering that the probability of selecting any of the existing features is the same.
Data Structure That Can Be Used
A host of data structures can be considered while trying to think of a way to perform the operations. We can use arrays or LinkedList to efficiently add the elements. However, LinkedList and Arrays both are incapable of doing the remove operation in O(1) time which leads us to another data structure. Hash Maps.
While Hash Maps can make adding data and getting random data as per the index will be becoming a breeze. However, trying to remove data points with certain values will become quite a task.
Necessity is the mother of invention and our situations lead us to a new hybrid
In the given approach we take a hybrid of
HashMap+ArrayList(Any flexible collection framework can be used i.e Set, Vector, etc)
Let me present a synopsis of all the methods and how we can design them to suit the conditions
Insert Method
- We insert our values into both the array and the HashMap
- If the value is already contained we return false
Remove Method
- This is where the ArrayList delivers us real help
- We get the position of the element from the ArrayList with the get method
- With set the element on the last position in the ArrayList
- The element from the last is put on the position of the element to be removed
- The element is then removed from both the hashmap and the ArrayList
- The size is decreased
- If the element does not exist we return false
GetRandom Method
- We use the inbuilt random method in Java and C++ to generate a random number
- We return the element at that position
Java Code for given Data Structure
class RandomizedSet
{
/** Initialize your data structure here. */
HashMap<Integer,Integer>hash;
ArrayList<Integer>store;
java.util.Random rand=new java.util.Random();
public RandomizedSet()
{
hash=new HashMap<Integer,Integer>();
store=new ArrayList<Integer>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val)
{
if(hash.containsKey(val))
return false;
else
{
hash.put(val,store.size());
store.add(val);
}
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val)
{
if(!hash.containsKey(val))
return false;
else
{
int cur_pos=store.get(val);
int last=store.get(store.size()-1);
store.set(cur_pos,last);
hash.put(last,cur_pos);
store.remove(val);
hash.remove(store.size()-1);
}
return true;
}
/** Get a random element from the set. */
public int getRandom()
{
return store.get(rand.nextInt(store.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/C++ Code for given Data Structure
#include<time.h>
class RandomizedSet {
public:
/** Initialize your data structure here. */
map<int,int>hash;
vector<int>store;
int size=0;
RandomizedSet() {
size=0;
srand(time(0));
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if(hash.find(val)!=hash.end())
return false;
if (store.size() == size)
store.push_back(val);
else
store[size]=val;
hash.insert({val,size});
size++;
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
auto srch=hash.find(val);
if(hash.find(val)==hash.end())
return false;
int ele=(*srch).second;
if(size>1)
{
store[ele]=store[size-1];
(*hash.find(store[size-1])).second=ele;
}
size--;
hash.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom() {
if(size==1)
return store[0];
return store[rand()%size];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]
[null,true,false,true,2,true,false,2]
Time Complexities for given Data Structure
Insert: O(1) for both HashMap and the ArrayList thus O(1)
GetRandom: O(1).As it takes O(1) time for HashMap to return data
Delete: O(n).
We delete the data from the hashmap in O(1) time however the preprocessing calls for O(N) time. As the operation to get the index is O(n) in an ArrayList.