1+ class RandomizedSet {
2+ public:
3+
4+ unordered_map<int ,int > indices;
5+ vector<int > values;
6+ RandomizedSet () {
7+ }
8+
9+ bool insert (int val) {
10+
11+ if (indices.find (val)==indices.end ()){
12+ values.push_back (val);
13+ // store the index of that value
14+ indices[val] = values.size () -1 ;
15+ return true ;
16+ }
17+ return false ;
18+ }
19+
20+ bool remove (int val) {
21+
22+ if (indices.find (val)==indices.end ()){
23+ return false ;
24+ }
25+
26+ // find index of the value
27+ int idx = indices[val];
28+ // get the last value in the vector
29+ // and change its index to curr val's index
30+ indices[values[values.size ()-1 ]] = idx;
31+
32+ // replace curr vals index with last
33+ // last value
34+ values[idx] = values[values.size ()-1 ];
35+
36+ // so now the curr val is removed from the
37+ // vector replaced by last value and so
38+ // we could just remove last value
39+ values.pop_back ();
40+
41+ // also erase it from the hash map
42+ indices.erase (val);
43+ return true ;
44+ }
45+
46+ int getRandom () {
47+ return values[rand ()%values.size ()];
48+ }
49+ };
50+
51+ /* *
52+ * Your RandomizedSet object will be instantiated and called as such:
53+ * RandomizedSet* obj = new RandomizedSet();
54+ * bool param_1 = obj->insert(val);
55+ * bool param_2 = obj->remove(val);
56+ * int param_3 = obj->getRandom();
57+ */