[Amazon][Microsoft] Design Data Structure with Insert, Delete, GetRandom at O(1)

Problem: Implement the RandomizedSet class:

• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

Approach: We can use hash and array combination here. In the hash val will be the key and value is the index at which we put the val in the array. Here are the algorithm for each operation:

1. Insert: 
• Check if val is in hash or not, if yes, then return false.
• Insert val at the end of array
• Make an entry in hash: hash[val] = Length of array - 1 
2. Remove:
• Check if val is in hash or not, if not, then return false.
• Copy the last element of array to hash[val]. Basically overwrite val with last element of array.
• Update hash with hash[last element of array] = hash[val]
• Remove the last element.
3. GetRandom:
• Return element from array at any random index.

Implementation in C#:

public class RandomizedSet

{

    public RandomizedSet()

    {

        this.map = new Dictionary<int, int>();

        this.list = new List<int>();

    }

   

    public bool Insert(int val)

    {

        if (this.map.ContainsKey(val))

        {

            return false;

        }

        this.list.Add(val);

        this.map[val] = this.list.Count - 1;

        return true;

    }

   

    public bool Remove(int val)

    {

        if (!this.map.ContainsKey(val))

        {

            return false;

        }

        int valIndex = this.map[val];

        this.list[valIndex] = this.list[this.list.Count - 1];

        this.map[this.list[valIndex]] = valIndex;

        this.list.RemoveAt(this.list.Count - 1);

        this.map.Remove(val);

        return true;

    }

   

    public int GetRandom()

    {

        return this.list[new Random().Next() % this.list.Count];

    }

    private Dictionary<int, int> map;

    private List<int> list;

}

Complexity: O(1) for all three operations.