Leetcode 380 - Insert Delete GetRandom O(1) - practice 2 - Extract a function move from line 170 - 183

Leetcode380_Practice2_B.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/
         * 
         * Write a C# version: 
         * 
         * We can use two hashmaps to solve this problem. One uses value as keys and the other uses index as the keys.
         */
        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>();

            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.
         * 
         * map1 - using value as key
         *   value is the size of map2 - count of numbers in the map 2. 
         * map2 - using number as key, where the number is related to map1's count. 
         *   key value starts from 0, increment one by one when new value is added. 
        */
        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;
        }
 
        /**
         * 
         * Removes a value from the set. Returns true if the set contains
         *  the specified element. 
         *  
         * Tricky part - Julia adds the comment
         * collision may happen - need to remove last one in map2 
         * map2 last value will be written again, since count of map decrements one. 
         * 
         * In order to avoid collision, when the number is removed from map1, map2,  
         * then, need to set last one in the map2 to replace the slot removing, and also
         * add a new entry to map1 as well. 
         * 
         * So many tasks for the function:  
         * 1.remove an entry in two maps
         *  map1 - remove the entry - by val
         *  map2 - remove the entry - by index
         *  
         * 2. map2 last entry should be added into the map2 
         * with key - index, 
         *    also, the entry should be updated in map1 as well. 
         *    put the position of removed item. 
         *    
         * Get into details, step by step: 
         *   lastPos = map2.Count - 1; 
         *   map1
         *      key    value
         *      val    index  <- to be removed
         *   map2
         *      key    value 
         *      index  ?     <- to be removed
         *      
         *  And then, 
         *   map2  <- last entry before removing
         *      key            value
         *      lastPos     map2[lastPos]  <- since lastPos decrements one
         *      
         *   key1 = map2[lastPos]
         *   
         *   fill the removed slot in map1:
         *   map1[key1] = index; 
         *   
         *   map2: 
         *   1. remove last entry
         *     map2.Remove(map2.Count); 
         *   2. map2.Add(index, key1)
         */
        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
         */
        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. 
        */
        public int getRandom() {
            if(map1.Count == 0){
                return -1; 
            }
 
            if(map1.Count == 1){
                return map2[0];    
            }    
 
            return map2[new Random().Next(map1.Count)];            
        }
    }
}