CareerCup

A hash table + an array that contains all the keys. The order of the keys stored in the array is not important

add
- we insert the key of the element at the end of the array (push_back).
- the element is then added in the hash table.
- we also keep in the hash table the position where the key was stored in the array

remove
- from the hash table we determined the position where the key of the element is stored in the array. We need then to removed it (this will create a hole). We move then the last key from the array to the position of the removed key. Of course, we need to update the position which was stored in the hash table (for this last key).
- then we do the "normal" removal from the hash;

getrandom
- since all keys are stored in the array, it's really easy to determine a random key ( array[rand() % array.size()]. we then return the random element from the hash table

This is an implementation using two Hash Tables that has an approximate complexity of O(1) for every operation (Add, Remove, Search and Random) if the Hash Tables are well implemented (good hash function and load factor).

The Hash Tables are:
map1: Key(string)->(Value(int), Index of map2 (int))
map2: Key(int)-> Value(string)

The Key of map2 represents an index (from 0 to size of data-1) and its value maps with Key of Map1.

Below you can see the C++ implementation (I used STL <unordered_map> for Hash Table), and assumed the Key is a "string" and the value is an "int".

#include <unordered_map>
#include <string>
#include <array>

using namespace std;
class MyStruct
{
public:
	
	MyStruct() {size_of_data_=0;}

	virtual ~MyStruct(){}

	void Add(string str, int v){
		array<int,2> arr;
		arr[0] = v;
		arr[1]= size_of_data_;
		map1_[str] = arr;
		map2_[size_of_data_++]=str;
	}

	int Search(string str)
	{
		unordered_map<string,array<int,2> >::iterator it =
                map1_.find(str);

		if(map1_.find(str)!=map1_.end()) //Element found
			return it->second[0];
		else //Element not found
			return -1;
	}

	void Remove(string str)
	{
		unordered_map<string,array<int,2> >::iterator it = 
                 map1_.find(str);

		//If element to remove doesn't exist in our Data
		if(it==map1_.end()) 
			return;

		//Get the index element in the map2
		int map2_idx = it->second[1];
	
		//Get key (string) of last element in the map2
		string last_str = map2_[size_of_data_-1];

		//Replace with element to remove with the last element
		map2_[map2_idx] = last_str;

		//Update the map2_idx of last key of map2
		map1_[last_str][1] = map2_idx;

		//Erase element from map1
		map1_.erase(str);

		//Erase last element from map2
		map2_.erase(size_of_data_-1);

		//Decrement size_of_data
		size_of_data_--;
	}

	int Random()
	{
		//Generate big rand number - use your favorite randgen
		unsigned int rand_number = GetRandNumber();

		//If you want to return the value of the random element
		return map1_[map2_[rand_number%size_of_data_]][0];

		//If you want to return the key of the random element
		//uncomment next line
		//return map2_[rand_number%size_of_data];
	}

private:
	unordered_map<string, array<int,2> > map1_;
	unordered_map<int,string> map2_;
	int size_of_data_;
};

add remove search what? in a tree, array of Structure, Linked list...?? please make it clear..:-)

How about LRU cache ?
I think LRU cache using hashtable and Doubly linked list has O(1) insert, delete, search and random search too.