Leetcode 380 - insert delete getRandom in O(1) - 4th practice, thinking using an array, and then solve deletion O(n) to O(1) using extra hashmap.

Leetcode380_insertDeleteGetRandom_P4.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: 
         * 
         * 1. Thinking using a hashmap - cannot work out on getRandom() in O(1) - 
         * 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 
         * 
         * 2. Thinking using an array - work on insertion/ getRandom() in O(1), but problem with deletion in O(1) - using an extra hashmap to store key/value pair for the array 
         *    Make deletion in O(1) 
         *    use last one in the array to replace the deleted one. 
         *
         */
        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 (!arrayDeletionO1(map2, map1, val))
                return false;

            return mapUpdateForArrayDeletion(map2, map1, val); 
        }

        /*
        * The hashmap needs to be update. 
        * 1. Delete the entry 
        * 2. Update the key for last one in the array - remapping
        * after the array is updated with deletion 
        */
        public bool mapUpdateForArrayDeletion(Dictionary<Int32, Int32> arr, Dictionary<Int32, Int32> map, int val)
        {
            if (map == null || !map.ContainsKey(val))
                return false;

            int index = map[val];
            map.Remove(val);

            int key = arr[index];
            map[key] = index; // set up a new position for the key

            return true; 
        }

        /*
         * implement the array deletion in O(1) time 
         * -- find the index position in the array through second container - a hashmap
         *   by looking up by val
         * -- use last value in the array to replace the deleted one
         * instead of shifting all elements, use last one in the array to replace the deleted one in the array
         */
        public bool arrayDeletionO1(Dictionary<Int32, Int32> arr,  Dictionary<Int32, Int32> map, int val)
        {
            if (map == null || !map.ContainsKey(val))
                return false;

            int index = map[val];

            move(arr, arr.Count - 1, 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)];            
        }
    }
}