CareerCup

this can be solved using hash table + array implementation

hash data ---- index to array
40 -------------- 0
10 -------------- 1
20 -------------- 2
30 -------------- 3

array index -- 0 1 2 3 4
data ---------- 40 10 20 30

initially index = 0;

insert(data)
1. insert the data into hash table if it is not available
2. enter the index to the hash associated to the key (data)
3. enter the data into array[index] location
4. increment the index by 1 i.e.. index++;

delete(data)
1. verify the data is available in hash table if yes then get the index of the data
i = get_index(data) // index
2. move data from array in location index-1 to i
a[i] = a[index-1];
3. data in a[i] is changed now, so change the index of a[i] in hash table to i
4. decrement index by 1 i.e.. index--;
5. delete the data from the hash table...delete_hash(data)

get_random()
1. generate a random number 0 - (index-1)
r = rand() % index;
2. return array[r]

hi Epic coder,
After reading the question the first doubt that comes to my mind is, what would be arguments with insert(),remove(),get_random().
In case there is no argument then we can assume to operate on top most element as in your case.
But, suppose if the index is given then though it can still be done in O(1), itsnt there a need to rearrange the elements in our array after every remove() ?

public class RandHashAccess<T>
{
 private Map<T, Integer> elementMap;
 private List<T> elementArr;

  public RandHashAccess()
{
   elementMap =  new HashMap<T, Integer>();
   elementArr = new ArrayList<T>();
}

public void Insert(T element)
{
  int arrLength = elementArr.size();
  elementArr.add(element);
  elementMap.put(element, arrLength);
}

public void Remove(T element)
{
    Integer eleArrIndex = elementMap.get(element);
    
   if(eleArrIndex != null)
   {
         /* swap the element in cur position with nth element and
            remove the last element from the array */
         int arrSize = elementArr.size();
         T eleNth =  elementArr.get(arrSize-1);
         elementArr.set(eleArrIndex, eleNth);
         elementArr.remove(arrSize-1);
       
        /* adjust the nth element array order in the map, since it is swapped with cur element position */
        elementMap.put(eleNth, eleArrIndex);
        elementMap.remove(element);
}
public T get_random()
{
 int randElePos =  Math.random(0, elementArr.size() -1);
 return elementArr.get(randElePos);
}

}

So the answer here is a hash table because you can insert and remove in O(1). The tough part was the get_random() function because if you just try to generate random numbers until you get an index that actually has a value you will not get constant time.

public class HashTable {
    private DataItem [] data;
    private int size;
    private int [] keys;
    private int numKeys;
    
    private class DataItem {
        public int keyIndex;
        public object data;
        
        public DataItem(int k, object d) {
            keyIndex = k;
            data = d;
        }
    }

public HashTable() {
        size = 100;
        data = new DataItem[size];
        keys = new int[size];
        numKeys = 0;
    }
    
    public Insert (object newData) {
        int key = hash(newData);
        insertData = new DataItem(numKeys, newData)
        data[key] = newData;
        keys[numKeys] = key;
        numKeys++;
    }
    
    public Remove (object removeData) {
        int key = hash(removeData);
        int keyIndex = data[key].keyIndex;
        keys[keyIndex] = keys[numKeys];
        numKeys--;
        data[keys[keyIndex]].keyIndex = keyIndex;
        hash[key] = null;
    }
    
    public object GetRandom() {
        r = math.rand(0, numKeys-1);
        return data[keys[r]].data;
    }
}

I never like the idea of suggesting hash table for such problems because implementing a hashtable that gives you O(1) insertion and deletion is a big problem in itself. In this problem we are not required to lookup the element in O(1) time and we should exploit that fact.
My idea is to use a very large array and use it to implement a stack using this array. So
1. you can insert only at the top, O(1) time,
2. you can delete only from the top again O(1) time and
3. for finding random element, suppose that we have n elements in the array at the instant we have to generate a random number. Random number would be rand(n)th element of the array, where rand(n) is a random number generator between 0 and n-1. Again O(1) time.

Note that there is always a possibility of running out of space and in that case we'll have to expand the array(which could be visualized as equivalent of rehashing in hash tables)

Hashtable + a vector for quickly getting random elements seems an appropriate solution, with the following additions:
* keep the index of the array in the hash table, for fast deletions from the array
* delete from the array by swapping with the last element and then deleting last element, to make this operation o(1)

C++ solution is below.
* Assuming the elements you are storing are integers.
* Variable names could have been better.
* Handle collisions by "chaining" in a vector (easier to implement than linked list).

class HT
{
  // pair<int, int> - first is the elemet inserted in HT,
  // second is index of locations where you can find that element

  vector< vector< pair<int, int> > > ht;

  // use this to store elements in compact form and get random number
  vector<int> locations;

  int buckets;
  int hash(int n)
  {
    return (n % buckets);
  }

  int get_bucket_index(int bucket, int n)
  {
    for(int i = 0; i < ht[bucket].size(); i++)
    {
      if(ht[bucket][i].first == n)
      {
        return i;
      }
    }
    return -1;
  }

  public:
  HT(int buckets = 9973)
  {
    this->buckets = buckets;
    ht.resize(buckets);
  }

  void insert(int n)
  {
    int hashed_n = hash(n);
    if(get_bucket_index(hashed_n, n) != -1)
      return;

    ht[hashed_n].push_back(pair<int,int>(n,locations.size()));
    locations.push_back(n);
  }

  void remove(int n)
  {
    int hashed_n = hash(n);

    int i = get_bucket_index(hashed_n, n);

    if(i == -1)
      return;

    // find and remove in locations
    int loc = ht[hashed_n][i].second;
    swap(locations[loc], locations[locations.size()-1]);
    locations.pop_back();

    // update swapped value in ht
    int hashed_sw = hash(locations[loc]);
    int j = get_bucket_index(hashed_sw, locations[loc]);
    ht[hashed_sw][j].second = loc;

    // swap with last elem and delete
    int last = ht[hashed_n].size()-1;
    swap(ht[hashed_n][i], ht[hashed_n][last]);
    ht[hashed_n].pop_back();
  }

  int get_random()
  {
    int max_index = locations.size();
    return locations[rand() % max_index];
  }

};

#include <stdio.h>
#include <malloc.h>
#include <string.h>

struct link_node
{
	struct link_node *next;
	int index;
	int data;
};

class RequiredDataStructure
{
private:
	static const int hash_bits = 14;
	struct link_node **hash_table;
	int arr_ind;
	int arr_size;
	int *arr;

	int fibnocci_hash(int a, int bits)
	{
		return (int)(((long long)a * 11400714819323198485ULL) >> (64 - bits));
	}
public:
	RequiredDataStructure()
	{
		hash_table = (struct link_node **)malloc(sizeof(struct link_node *) * (1<<hash_bits));
		memset(hash_table, 0, sizeof(struct link_node *) * (1<<hash_bits));
	}

	void Insert(int data) 
	{
		struct link_node *node;

		if (arr_ind == arr_size) {
			/*realloc is O(n) but it will occur rarely. */
			arr = (int *)realloc(arr, sizeof(int) * arr_size * 2);
			arr_size <<= 1;
		}
		arr[arr_ind] = data;

		node = (struct link_node*)malloc(sizeof(struct link_node));
		node->data = data;
		node->index = arr_ind++;
		int hash = fibnocci_hash(data, hash_bits);
		node->next = hash_table[hash];
		hash_table[hash] = node;
	}

	void Remove(int data) 
	{
		int hash = fibnocci_hash(data, hash_bits);
		int index;
		struct link_node *curr, *prev = NULL;
		for (curr = hash_table[hash]; curr != NULL; prev  = curr, curr = curr->next) {
			if (curr->data == data) {
				break;
			}
		}

		/* only deleting if exists. */
		if (curr != NULL) {
			if (prev != NULL) {
				prev->next = curr->next;
			} else {
				hash_table[hash] = curr->next;
			}
			// remove element at curr->index
			--arr_ind;
			if (curr->index != arr_ind) {
				index = curr->index;
				arr[index] = arr[arr_ind];
				data = arr[index];
				hash = fibnocci_hash(data, hash_bits);
				for (curr = hash_table[hash]; curr != NULL; curr->next) {
					if (curr->data == data && curr->index == arr_ind) {
						curr->index = index;
						break;
					}
				}
			}
			free(curr);
		}
	}

	bool GetRandom(int *ran) {
		if (arr_ind != 0) {
			*ran = arr[rand() % arr_ind];
			return true;
		}
		return false;
	}
}

Second vincent, expanding on the same idea.
DS: hashmap (unordered) + DL. (maintaing head pointer).

generate_random:
map.size() gives us number of elelments at any given instance. Exploit this fact and access node such as: (rand() % size) from the head pointer.

DL should provide O(1) insertion and O(1) deletion. Furthe, for O(1) random number generation cache the node access and apply rand() function to generate new random node to access, such as:

first time:
return head_; // store this pointer.

second time:
return lastAccess +/- rand()%5 based on pointer location.

Class Set{
ArrayList<T> al;
Random r;
public Set(){
al=new ArrayList<T>();
r=new Random();
}
public add(T element){
if(!al.contain(element)){
al.add(element);
}
}
public remove(T element){
if(al.contain(element){
al.remove(element)
}

public T getRandomElement(){
int temp= r.nextInt( al.size());
return al.get(temp);


}
}
}

algos solution is good. But to optimize insert and add to O(1) we have to implment our own hash. So it will be array of size (lets say 65535). For any elemtent array index K will be key an value will be array[K]

In that case we need our own hash function, for which we can use md5. So add and remove remains O(1) and getRandom can be pure random by fetching any value of rand(size of array)

We can have array of size 65535.
hash function => decimal value of ( last 4 bytes of md5 ) // maximum will be FFFF which is 65535.

For hash function collision, we can use chaining. So each array element will be linked list of data. If array index chosen by random function has more than 1 element, we can again choose rand(size of linked-list) to get Nth element in that linked list.

package cc.goog;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class SpecialSet<T> {
	
	private Map<T, Integer> elementVsIndex = new HashMap<T, Integer>();
	private Map<Integer, T> indexVsElement = new HashMap<Integer, T>();
	private Random r = new Random();
	
	public void insert(T t) {
		if (elementVsIndex.containsKey(t))
			return;
		int maxIndex = elementVsIndex.size();
		elementVsIndex.put(t, maxIndex);
		indexVsElement.put(maxIndex, t);
	}
	
	public void remove(T t) {
		int maxIndex = elementVsIndex.size() - 1;
		Integer removedIndex = elementVsIndex.remove(t);
		if (removedIndex != null) {
			T e = indexVsElement.remove(maxIndex);
			if (e != null) {
				elementVsIndex.put(e, removedIndex);
				indexVsElement.put(removedIndex, e);
			}
		}
	}
	
	public T getRandomElement() {
		int maxIndex = elementVsIndex.size();
		int randomIndex = r.nextInt(maxIndex);
		return indexVsElement.get(randomIndex);
	}
}

Java implementation of the algorithm outlined by algos

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;



public class RandomSet<T> {


	public RandomSet(){

	}

	public boolean add(T obj){
		if(data_.containsKey(obj)) return false;

		data_.put(obj,elems_.size());
		elems_.add(obj);			

		return true;
	}

	public boolean remove(T obj){
		Integer idx = data_.remove(obj);
		if(idx  == null) return false;

		int lastIdx = elems_.size()-1;
		if(lastIdx != idx.intValue()){
			T moved = elems_.get(lastIdx);
			elems_.set(idx, moved);
			data_.put(moved, idx);
			
			
		}
		
		elems_.remove(lastIdx);		
		return true;

	}
	
	public T getRandomObject(){
		return elems_.get(rand_.nextInt(elems_.size()));

	}



	private Random rand_ = new Random(0);
	private final ArrayList<T> elems_ = new ArrayList<>();
	private HashMap<T,Integer> data_ = new HashMap<>();

	@Override
	public String toString() {
		return data_.toString();
	}
	
	public static void main(String[] args) {
		RandomSet<Character> rset = new RandomSet<>();
		for(char ch = 'A'; ch <= 'Z'; ch++){
			System.out.println("adding " +ch);
			rset.add(ch);			
		}
		System.out.println(rset);
		System.out.println(rset.getRandomObject());
		for(char ch = 'D'; ch <= 'Z'; ch++){
			rset.remove(ch);			
		}
		
		System.out.println(rset);
		System.out.println(rset.getRandomObject());
	}
	

}

Java implementation of the algorithm outlined by algos

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;



public class RandomSet<T> {


	public RandomSet(){

	}

	public boolean add(T obj){
		if(data_.containsKey(obj)) return false;

		data_.put(obj,elems_.size());
		elems_.add(obj);			

		return true;
	}

	public boolean remove(T obj){
		Integer idx = data_.remove(obj);
		if(idx  == null) return false;

		int lastIdx = elems_.size()-1;
		if(lastIdx != idx.intValue()){
			T moved = elems_.get(lastIdx);
			elems_.set(idx, moved);
			data_.put(moved, idx);
			
			
		}
		
		elems_.remove(lastIdx);		
		return true;

	}
	
	public T getRandomObject(){
		return elems_.get(rand_.nextInt(elems_.size()));

	}



	private Random rand_ = new Random(0);
	private final ArrayList<T> elems_ = new ArrayList<>();
	private HashMap<T,Integer> data_ = new HashMap<>();

	@Override
	public String toString() {
		return data_.toString();
	}
	
	public static void main(String[] args) {
		RandomSet<Character> rset = new RandomSet<>();
		for(char ch = 'A'; ch <= 'Z'; ch++){
			System.out.println("adding " +ch);
			rset.add(ch);			
		}
		System.out.println(rset);
		System.out.println(rset.getRandomObject());
		for(char ch = 'D'; ch <= 'Z'; ch++){
			rset.remove(ch);			
		}
		
		System.out.println(rset);
		System.out.println(rset.getRandomObject());
	}
	

}

I think hashtable + double linked list is a solution.

void main()
{
printf("You all are fools");
}