Leetcode 380 - insert, delete, getRandom in O(1) - understand the challenge and solution, the design until reading blog: http://www.guoting.org/leetcode/leetcode-380-insert-delete-getrandom-o1/

Leetcode380_Practice3.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetcodeInsertDeleteGetRandomO_1__Practice2
{           
    class RandomizedSet
    {
        /*
         * August 16, 2016
         * 
         * Leetcode 380 
         * 
         * Design a data structure that supports all following operations in O(1) time.

            insert(val): Inserts an item val to the set if not already present.
            remove(val): Removes an item val from the set if present.
            getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
         * 
         * Source code from:
         * http://www.programcreek.com/2014/08/leetcode-insert-delete-getrandom-o1-java/
         * 
         * Understand the challenge and solution by reading the blog: 
         * http://www.guoting.org/leetcode/leetcode-380-insert-delete-getrandom-o1/
         * 
         * Julia started to understand the real issue after a few hours coding/ playing test cases: 
         * 
         * Use one hashmap to store the key value pairs, we can achieve O(1) time for insertion/ deletion, 
         * but cannot achieve getRandom in O(1)
         * 
         * Even though we can know the range of key from min value to maximum value, but any random number
         * generated from the range, will be checked if it is in the hashmap or not. 
         * 
         * So, the time complexity will go up to O(max - min) range 
         * 
         * So, we have to do a mapping, store all the keys of map to another container, like an array, value from 0 to n, one to one mapping. 
         * 
         * But, in the second container, like an array, when deletion happens, we need to make the deletion to the end of the array, so, need to design API to move last entry to the slot removed. 
         * 
         * Last minute, Julia understands the issues - challenge and solution. 
         */
        static void Main(string[] args)
        {
            RandomizedSet randomSet = new RandomizedSet();

            randomSet.insert(1);
            bool result = randomSet.remove(2); // should be false

            randomSet.insert(2);

            int res2 = randomSet.getRandom();  // should be 1 or 2
            bool res3 = randomSet.remove(1);   // return true
            randomSet.insert(2);   // return false

            int res4 = randomSet.getRandom(); 
        }

        Dictionary<Int32, Int32> map1;
        Dictionary<Int32, Int32> map2;

        Random rand;
 
        /** Initialize your data structure here. */
        /*
         * http://stackoverflow.com/questions/4016483/get-time-in-milliseconds-using-c-sharp
            issue: long -> int 
         * 
         *  Figure out later 
         */
        public RandomizedSet() {
            map1 = new Dictionary<Int32, Int32>();
            map2 = new Dictionary<Int32, Int32>();  // actually map2 is like an array, 
            // to maintain the key value from 0 to n without any break. 

            rand = new Random((int)(DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond));
        }
 
        /**
        * 
        * Inserts a value to the set. Returns true if the set does not contain 
        * the specified element.    
         *   
         * Time complexity: 
         * 1. O(1) for map1 - since it is a hashmap
         * 2. O(1) from map2 - actual map2 is like an array, add to the end of the array
        */
        public bool insert(int val) {
            if(map1.ContainsKey(val))
                return false;
            
            int[] arr = new int[2]{map1.Count, map2.Count}; 

            map1.Add(val, arr[0]);
            map2.Add(arr[1], val);             

            return true;
        }

        /**
         * Analysis: 
         * read the blog: 
         * http://www.guoting.org/leetcode/leetcode-380-insert-delete-getrandom-o1/
         * 
         * And then, understand the design: 
         * Actually the map2 looks like an array, how to implement delete in O(1)? 
         * 
         * In map2, remove is always done at the end of the array, move last one in the array to the slot removed. 
         * Get random using time O(1), but need to make sure that the random number is the key! 
         * 
         * Need to maintain the key from 0 to n continuously in map2 - an array, can be best fit!
         * 
         * Otherwise, need to look up and see if it is in map1 or not; if not, generate a new one again.                    
         */
        public bool remove(int val) {
            if (!map1.ContainsKey(val))
                return false; 
            
            int index = map1[val];
            int lastPos = map2.Count - 1; // map2 
 
            //remove the entry from both maps
            map1.Remove(val);
            map2.Remove(index);
 
            if(map1.Count == 0){
                return true;
            }
 
            //if last is deleted, do nothing 
            if(index == map1.Count){
                return true;
            }    
 
            //update the last element's index     
            int keyForMap1 = map2[lastPos]; 
            
            map1[keyForMap1] = index;  // need to update in map1

            move(map2, lastPos, index); 
           
            return true;
        }

        /*
         * Design API - move an entry from the dictionary from one location 
         * to another location
         * 
         * assume that dictionay contains the entry of from
         * assume that to position is available in the dictionary
         * 
         * Time complexity: O(1) 
         * two position are available. 
         *
         */
        public bool move(Dictionary<Int32, Int32> dict, int from, int to)
        {
            if (dict == null || 
                !dict.ContainsKey(from) || 
                dict.ContainsKey(to))
                return false;

            int val = dict[from];

            dict.Remove(from);
            dict.Add(to, val);

            return true; 
        }

        /**
         * 
         * Get a random element from the set. 
         * 
         * Since the key value in map2 is from 0 to n - array's length, 
         * so any value from 0 to n will be in the map2 definitely. 
         * 
         * So, generate one randome number from 0 to n, and then, return value as key. 
         * 
         * Usually, the hashmap value key can be any number depending hashing function. 
         * 
         * Time complexity: O(1)
        */
        public int getRandom() {
            if(map1.Count == 0){
                return -1; 
            }
 
            if(map1.Count == 1){
                return map2[0];    
            }    
 
            return map2[new Random().Next(map1.Count)];            
        }
    }
}

Highlights of practice:

1. read the blog, http://www.guoting.org/leetcode/leetcode-380-insert-delete-getrandom-o1/, and then, understand challenge of Leetcode 380.
   Hashmap can achieve O(1) in insertion/delete, but cannot achieve getRandom() in O(1).
2. Start to understand second container - array like data structure, maintain the key value from 0 to n without any missing number. Prepare to get random number from 0 to n in O(1).
3. Add comments for all function add/ remove/ getRandom to add time complexity.