Amazon Interview Question SDE-2s
Country: United States
I dont think this is correct, I think a remove from an array is always O(n). How do you 'decrease the array by one'? Only be getting new memory and copying to it. Anything else will not free that memory so it still claimed. It maybe an acceptable solution but you going to be wasting memory.
Consider a similar solution, a hashtable and linkedList. Remove in a linked listed when given a pointer to the element is O(1). To remove a random element you can use the hashtable to lookup the pointer to that element so the remove is O(1).
@Anon:
It is correct. Replace array with vector (which can be made worst case O(1) and not just amortized).
As for remove, a neat trick of swapping with the last element is being used (please read the description).
Every operation is indeed O(1).
btw, this problem has appeared multiple times, with getRandom instead of remove random, there might be some other explanation which will help you better understand. I suggest you try searching for it.
I understand it, I just don't think "decrease the size of the array by one" is a valid operation in any real programming language. "Replace array with vector" means a hashtable and vector is a valid answer but the terms array and vector are not interchangable.
@Anon.
Decrease size of array is just decrementing a variable called, err, size. You don't actually go and try to deallocate the memory for the last byte. To make it easier for you, 'reduce the count by 1'.
Replace array with vector means hashtable? What? You lost me there.
I suggest (again) you search for previous answers. Maybe those will help.
This answer is good. Your dismissal of this answer is your loss.
@Anon
Decreasing the size of an array isn't just decreasing a size variable
Often we want to shrink the array by half when it is below 1/4 full
Think before you talk please
@Anon: You really have no clue, do you?
I said use a vector, which does all that for you (shrinking/growing at the right time etc). I also said it can be made worst case O(1) rather than amortized O(1). Do you even understand that?
You are free to be a stubborn bonehead. No more explanation for you, idiot.
The basic understanding of HashMap / HashTable is violated
The value as such calculated for the ELEM inserted is hashCode of the ELEMENT, and two ELEMENTS can have same hashCode. So the algo has problems firstly it does not store ELEMENTS with same hashCode and other
@Mike Nope its not even case of duplicate. Two elements can have same hashcode and hence they lie in same bucket.
hmm i just see the exact solution posted on stackover flow 2 years ago. the issue is, you forgot to mention that, in order to keep a vector of keys (or arraylist, which is recommended), you might encounter insertion worse case O(n) (which should be fine)
The remove(T) operation is hash table is not O(1) as it needs to iterate thru the sub Entries to findout the target element to remove
Hashtable+vector are good choice only in synchronized context.
Vector behind the scene is dynamic resizable array , so reduce by one is same as in array.
So it seems best approach is Hashmap+ doublyLinkedList.
hashmap can be used for deleting random o(1). and adding & removing is O(1) in list
This is my C++ version using two hashmaps. All operations are O(1).
#include <iostream>
#include <unordered_map>
#include <ctime>
template <typename T>
class rand_set {
public:
rand_set() : elem2pos_map_(), pos2elem_map_(), next_slot_(0) {
srand(time(NULL));
}
void add(T elem) {
// Map element -> slot
elem2pos_map_[elem] = next_slot_;
// Map slot -> element
pos2elem_map_[next_slot_] = elem;
// Increase slot
next_slot_++;
}
void remove(T elem) {
// Find element
auto it = elem2pos_map_.find(elem);
if (it != elem2pos_map_.end()) {
// Delete element
elem2pos_map_.erase(it);
size_t pos = it->second;
pos2elem_map_.erase(pos);
}
}
T removeRandom() {
if (pos2elem_map_.empty())
throw std::runtime_error("No elements found");
// Find random element. Must be within 0 and next_slot_
T elem;
size_t pos = rand() % next_slot_;
auto it = pos2elem_map_.find(pos);
if (it != pos2elem_map_.end()) {
elem = it->second;
} else {
elem = pos2elem_map_.begin()->second;
pos = elem2pos_map_.at(elem);
}
elem2pos_map_.erase(elem);
pos2elem_map_.erase(pos);
return elem;
}
private:
typedef std::unordered_map<T, size_t> elem2pos_map;
typedef std::unordered_map<size_t, T> pos2elem_map;
elem2pos_map elem2pos_map_;
pos2elem_map pos2elem_map_;
size_t next_slot_;
};
int main() {
rand_set<int> rset;
for (size_t i = 0; i < 10000; i++)
rset.add(i);
int rand = rset.removeRandom();
std::cout << rand << std::endl;
return 0;
}
public class CustomSet <TVal>
where TVal : IComparable<TVal>
{
// Use ConcurrentDictionary?
private readonly HashSet<TVal> m_HashSet = new HashSet<TVal>(/*Pre-set size if known*/);
public void Add(TVal item)
{
m_HashSet.Add(item);
}
public void Remove(TVal item)
{
m_HashSet.Remove(item);
}
public void RemoveRandom(TVal item)
{
//...
}
}
Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.
- blackfever November 20, 20131.insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
2.remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
3.getRandomElement(): let r=random(current size of A). return A[r].