Infinidat interview question
(technical interview) Build a data structure that supports the following functions: int alloc() - allocates a new element to a data structure and initializes its value to 0. void inc(key) - Increases the value of the element by one. int get(key) - returns the value of the given key void resetAll() - Initializes the values of all elements to be 0.
Interview Answer
Anonymous
class MyDS { int lastSet=0; unordered_map> map; public: int Alloc(int key) { map[key] = make_pair(0, lastSet); return key; } void Inc(int key) { if (map.find(key) != map.end()) { if (map[key].second < lastSet) { map[key].first = 1; map[key].second = lastSet; } else { map[key].first++; } } } int Get(int key) { if (map.find(key) != map.end()) { if (map[key].second < lastSet) { map[key].second = lastSet; map[key].first = 0; return 0; } else { return map[key].first; } } return -1; } void RestAll() { lastSet++; } };