Leetcode 380 - Insert, delete, getRandom() O(1) time - Practice 4

August 16, 2016

The first 3 practices:


http://juliachencoding.blogspot.ca/2016/08/leetcode-380-insert-delete-getrandom-o1.html

http://juliachencoding.blogspot.ca/2016/08/leetcode-380-insert-delete-getrandom-o1_16.html

http://juliachencoding.blogspot.ca/2016/08/leetcode-380-insert-delete-getrandom-o1_89.html

Read the blog:
http://www.guoting.org/leetcode/leetcode-380-insert-delete-getrandom-o1/

Java code from the above blog:
https://gist.github.com/jianminchen/9561828feda21bac20bc9ba4da0d13c8

4th practice using C#:

https://gist.github.com/jianminchen/7741fabf57413ccbb1080f6f691bb532

Highlights of 4th practice:

1. Thinking problem solving using an array:

 Insertion of array is to append the number at the end of array, O(1);

 Delete a number from the array, for example, at index position i of array with length n, then, all elements from i+1 to n-1 should be shifted to left one position - time complexity is O(n-i) = O(n)

 getRandom() - time complexity is O(1), just get a random number r from 0 to n, and then, return arr[r].
   Array value can be any integer number, and in the range of Int32.min - Int32.max, so given an integer value, it may not be in the array; if it is, to find the index of array to hold the value, we need to look up a hashmap with value/ index of array pair first. 

So, in order to make it O(1) for the deletion, we can use extra space to speed up time to O(1). The idea is to move last number in the array to the position of deleted element.

Extra space - a hashmap to store each number in the array as key, and the value is the position in the array.

4. Introduce new design in the practice? 

arrayDeletionO1 - line 150 API - array deletion, arrayDeletionO1 (Dictionary<Int32, Int32> arr, Dictionary<Int32, Int32> map, int val)

- implement the array deletion in time complexity O(1)

move - line 173 API - array move - move an entry from the dictionary from one location to another location. move(Dictionary<Int32, Int32> dict, int from, int to)

mapUpdateForArrayDeletion - line 129 - hashmap update - mapUpdateForArrayDeletion(Dictionary<Int32, Int32> arr, Dictionary<Int32, Int32> map, int val)

Cons and pros for modified deletion for the array-like data structure:
1. Cons: If the array is sorted, then the order is lost. No longer in the order.
2. Study Array API for C, C++, C#, JavaScript, none of them has API like this. Why?

Array - JavaScript
http://juliachencoding.blogspot.ca/2016/07/javascript-array-mozilla-60-minutes.html

C# array
http://juliachencoding.blogspot.ca/2016/06/array-class-c-c-javascript-java.html

3. For the deletion, update can be done directly instead of first deletion, and then move of the last one to the deleted item's position. line 182, line 183 can be merged to one line - update.

4th practice using C#:
https://gist.github.com/jianminchen/7741fabf57413ccbb1080f6f691bb532

4. JavaScript array is sparse, the array is not contiguous. For Leetcode 380, Julia thought about array deletion design, if the array is leaving as sparse after deletion, then, getRandom() can not be O(1). If the sparse slot is selected by random algorithm, need to select another one.

Related articles:
 1. Uber map article:
http://goo.gl/nmRv18

Google search keyword:
red-black tree - C++ implements the map
http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree

2. Uber algorithm question: 
https://goo.gl/fWq132