Insert Delete GetRandom O(1) - Duplicates allowed (Hard)
Problem is here (#424 solved in my list): https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
The approach will be the following:
Design a data structure that supports all following operations in averageO(1) time.
Note: Duplicate elements are allowed.insert(val): Inserts an item val to the collection.remove(val): Removes an item val from the collection if present.getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:
// Init an empty collection. RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3. collection.getRandom(); // Removes 1 from the collection, returns true. Collection now contains [1,2]. collection.remove(1); // getRandom should return 1 and 2 both equally likely. collection.getRandom();So to solve this problem I'll make use of some C# data types and assume that some of its inner operations are on average constant time (right thing to do would be to research it and make sure that this is the case - that's left as an exercise).
The approach will be the following:
- Keep the elements in a linked-list. Allow dupes
- Whenever you add an element, have a hash table pointing to the node in the list that's just been added
- To delete an element, use the hash table to get the node, and delete from the list using the built-in list function Delete which accepts a node as input
- To randomize, use the ElementAt built-in function from the list (also the count, which would be easy to implement natively)
I have scratched the solution on a (Whole Foods) paper, as you can see below. Code is down here, cheers, ACC.
public class RandomizedCollection
{
private LinkedList<LinkedListNode<int>> list = null;
private Hashtable valToNode = null;
private Random rd = null;
/** Initialize your data structure here. */
public RandomizedCollection()
{
list = new LinkedList<LinkedListNode<int>>();
valToNode = new Hashtable();
rd = new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public bool Insert(int val)
{
LinkedListNode<int> node = new LinkedListNode<int>(val);
list.AddLast(node);
bool retVal = false;
if (!valToNode.ContainsKey(val))
{
LinkedList<LinkedListNode<int>> index = new LinkedList<LinkedListNode<int>>();
index.AddLast(node);
valToNode.Add(val, index);
retVal = true;
}
else
{
LinkedList<LinkedListNode<int>> index = (LinkedList<LinkedListNode<int>>)valToNode[val];
index.AddLast(node);
retVal = false;
}
return retVal;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public bool Remove(int val)
{
if (!valToNode.ContainsKey(val)) return false;
LinkedList<LinkedListNode<int>> index = (LinkedList<LinkedListNode<int>>)valToNode[val];
LinkedListNode<int> firstNode = index.First.Value;
list.Remove(firstNode);
index.RemoveFirst();
if (index.Count == 0)
{
valToNode.Remove(val);
}
return true;
}
/** Get a random element from the collection. */
public int GetRandom()
{
int randIndex = rd.Next(0, list.Count);
return list.ElementAt<LinkedListNode<int>>(randIndex).Value;
}
}
{
private LinkedList<LinkedListNode<int>> list = null;
private Hashtable valToNode = null;
private Random rd = null;
/** Initialize your data structure here. */
public RandomizedCollection()
{
list = new LinkedList<LinkedListNode<int>>();
valToNode = new Hashtable();
rd = new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public bool Insert(int val)
{
LinkedListNode<int> node = new LinkedListNode<int>(val);
list.AddLast(node);
bool retVal = false;
if (!valToNode.ContainsKey(val))
{
LinkedList<LinkedListNode<int>> index = new LinkedList<LinkedListNode<int>>();
index.AddLast(node);
valToNode.Add(val, index);
retVal = true;
}
else
{
LinkedList<LinkedListNode<int>> index = (LinkedList<LinkedListNode<int>>)valToNode[val];
index.AddLast(node);
retVal = false;
}
return retVal;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public bool Remove(int val)
{
if (!valToNode.ContainsKey(val)) return false;
LinkedList<LinkedListNode<int>> index = (LinkedList<LinkedListNode<int>>)valToNode[val];
LinkedListNode<int> firstNode = index.First.Value;
list.Remove(firstNode);
index.RemoveFirst();
if (index.Count == 0)
{
valToNode.Remove(val);
}
return true;
}
/** Get a random element from the collection. */
public int GetRandom()
{
int randIndex = rd.Next(0, list.Count);
return list.ElementAt<LinkedListNode<int>>(randIndex).Value;
}
}
Comments
Looks great, although I think the complexity of GetRandom is not O(1), since ElementAt's complexity is linear with respect to the number of elements. I'm using vector (aka ArrayList) to get constant complexity:
Reply Deleteclass RandomizedCollection {
private:
vector values;
unordered_map> indices;
public:
bool insert(int val) {
auto& val_indices = indices[val];
val_indices.insert(values.size());
values.push_back(val);
return val_indices.size() == 1;
}
bool remove(int val) {
auto found = indices.find(val);
if (found == indices.cend() || found->second.empty()) {
return false;
}
auto& to_remove_indices = found->second;
auto to_remove_idx = *to_remove_indices.begin();
to_remove_indices.erase(to_remove_idx);
int to_insert = values.back();
values[to_remove_idx] = to_insert;
found = indices.find(to_insert);
if (found != indices.cend() && !found->second.empty()) {
indices[to_insert].erase(values.size()-1);
indices[to_insert].insert(to_remove_idx);
}
values.pop_back();
return true;
}
int getRandom() {
return values[rand() % values.size()];
}
};
Post a Comment
[γγ¬γΌγ ]