#include <iostream>
#include <unordered_map>
#include<vector>
#include<stdlib.h>
#include<time.h>

using namespace std;

class MyDS
{
	private:
	std::unordered_map<int,int> ht;
	std::vector<int> vec;
	
	public:
	void add(int num);
	void remove(int num);
	int getRandom();
	int search(int num);
	void traverse();
};

    void MyDS::add(int num)
	{
		cout<<"In add"<<endl;
		if(ht.find(num)==ht.end())
		{
			vec.push_back(num);
			int sz = vec.size();
			ht.insert(pair<int,int>(num,sz-1));
		}
		else
		   return;
	}
	
	void MyDS::remove(int num)
	{
		if(ht.find(num)!=ht.end())
		{
			int indx = ht.find(num)->second; 
			int sz = vec.size();
			vec[indx] = vec[sz-1];
			vec.erase(vec.begin() + sz-2);
			ht.erase(ht.find(num)->first);
		}
		else
			return;
	}
	
	int MyDS::getRandom()
	{
		srand (time(NULL));
		int rnum = rand();
		int indx = rnum%(vec.size());
		return vec[indx];
	}
	
	int MyDS:: search(int num)
	{
		if(ht.find(num)!=ht.end())
		{
			return ht.find(num)->second;
		}
		else
			return -1;
	}
	
	void MyDS:: traverse()
	{
		for(int i=0;i<vec.size();i++)
			cout<<" "+vec[i];
		cout<<endl;
	}

int main() {
        MyDS ds;
        ds.add(10);
        ds.add(20);
        ds.add(30);
        ds.add(40);
        ds.traverse();
        cout<<ds.search(30)<<endl;
        ds.remove(20);
        ds.add(50);
        ds.traverse();
        cout<<ds.search(50)<<endl;
        cout<<ds.getRandom()<<endl;
	return 0;
}