vhmj1982
BAN USER- 0of 0 votes
AnswersDesign a data structure with the following API:
- vhmj1982 in United States
*get
*add
*getRandom
*delete
All in constant time| Report Duplicate | Flag | PURGE
Yeah, hashmap is a good approach, but somehow complicated, you know calculating the hash, selecting a bucket, handling collisions etc..
I Think it's easier just to wrap up an array into a class and then provide some logic to increment the size of the array when needed, per say use a growRate variable which is calculated something like this:
m_growrate = N/n // N -> number of buckets and n ->number of used buckets
if that is greater than 0.7 (70%) just double the size of the array and copy back all the elements, in that case insert an element will take O(1) time in most cases, and O(n) in the worst case.
Yes I agree, I did precisely that on the interview, After the interviewer told me "you could just wrapped an array into a class and create a growRate method which is going to be responsible of re-sizing the internal array just like the hash map does" Anyways I was just wondering if there is another crazy approach I missed.
- vhmj1982 February 28, 2013What would be the definition of the HashMap ?? , I mean you will have something like this:
public class MyDS
{
private HashMap<K,V> dataStore = new HashMap<K,V>();
......
}
When I was asked this the interviewer told me that hashMap solution is overkiller,
so what would be K,V ??? can u think on something simpler ??
I think doing % and / is not the correct approach to this, the algorithm basically work, but if we consider a number with millions of digits, the datatype should be some sort of linked list containing a single digit peer bucket, in that way the "big" number can grow to million digits, so in my opinion the correct way should be visit from back to beginning the linked list an put each digit into a string buffer then return it.
- vhmj1982 February 07, 2013
That approach will never select the root node of the tree, I would do an inOrder traversal then store it on an array and select a random value from the array, that would guarantee equal random probability for all nodes.
- vhmj1982 March 07, 2013