Common Coding Interview Questions O(1) Data Structure

HappyCerberus

11.8K views

GitHub

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

$O (1)$ data structure

An exercise in understanding performance characteristics of different data structures.

Implement a class with the following methods, all with $O (1)$ time complexity:

class Constant {
public:
	// Insert new key with value 1, or if key is already present, increase it by 1.
	void inc(const string& key);
	// Decrease the value of a key by 1. If the value is already 1, remove it from the data structure.
	void dec(const string& key);
	// Return one of the keys with maximum value. Return "" if datastructure is empty.
	string getMaxKey() const;
	// Return one of the keys with minimum value. Return "" if datastructure is empty.
	string getMinKey() const;
};

In this article, we will go through the deconstruction of this problem and build up the solution step by step.

Trivial $O (n)$ "solution"

Let's establish some baseline of what we can definitely do (ignoring $O (1)$ time complexity requirement for now).

Fetching the maximum and minimum out of an unsorted sequence requires $O (n)$ complexity.

Increasing and decreasing the value for a key can be done in $O (1)$ if we store this information in a hash map.

// {
class Constant {
    unordered_map<string, unsigned> _values;
public:
    void inc(const string& key);
    void dec(const string& key);
    string getMaxKey() const;
    string getMinKey() const;
};
void Constant::inc(const string& key) {
    _values[key]++;
}
void Constant::dec(const string& key) {
    _values[key]--;
    if (_values[key] == 0) {
        _values.erase(key);
    }
}
string Constant::getMaxKey() const {
    unsigned max = 0;
    string key = "";
    for (auto v : _values) {
        if (v.second > max) {
            key = v.first;
            max = v.second;
        }
    }
    return key;
}
string Constant::getMinKey() const {
    unsigned min = numeric_limits<unsigned>::max();
    string key = "";
    for (auto v : _values) {
        if (v.second < min) {
            key = v.first;
            min = v.second;
        }
    }
    return key;
}

This solution is obviously extremely inefficient. We could improve it drastically by simply caching the result of min and max and only updating it when needed. However that wouldn't give us the desired $O (1)$ complexity.

Solving the maximum in $O (1)$

Our previous trivial implementation would work even if the values for the keys could change arbitrarily. Can we exploit the fact that a key can only change by one?

Let's have a look at what can happen to the maximum if we increase or decrease the value for a key.

if the key was not the maximum, the maximum will not change
increasing a maximum key will increase the maximum
decreasing a maximum key can have two results:
1. if this was the only key at the value, the maximum decreases
2. if there are other keys with the value, the maximum does not change

Looking at this, the only information we are missing is how many keys are at a given value. We can maintain this information in $O (1)$ using a hash map. Since we need to return the maximum key (not the maximum value) we will also need to store the keys at a given value, hash set will work fine for this purpose.

// {
class Constant {
    unordered_map<string, unsigned> _values;
    unordered_map<unsigned, unordered_set<string>> _buckets;
    unsigned max = 0;
public:
    void inc(const string& key);
    void dec(const string& key);
    string getMaxKey() const;
    string getMinKey() const;
};
void Constant::inc(const string& key) {
    if (max == _values[key]) {
        max++;
    }
    _values[key]++;
    if (_values[key] > 1) {
        _buckets[_values[key]-1].erase(key);
    }
    _buckets[_values[key]].insert(key);
}
void Constant::dec(const string& key) {
    if (max == _values[key] && _buckets[_values[key]].size() == 1) {
        max--;
    }
    _values[key]--;
    _buckets[_values[key]+1].erase(key);
    if (_values[key] != 0) {
        _buckets[_values[key]].insert(key);
    } else {
        _values.erase(key);
    }
}
string Constant::getMaxKey() const {
    auto it = _buckets.find(max);
    if (it == _buckets.end()) return string("");
    return *it->second.begin();
}
string Constant::getMinKey() const {
    unsigned min = numeric_limits<unsigned>::max();

Solving minimum in $O (1)$

At first glance, we might be able to use the same approach for minimum. That will unfortunately not work. Maximum always changes smoothly, at most by one. Minimum can however change by an arbitrary amount if the minimum key has the value $1$ and we decrement it.

The pathological example would be to have the following keys in our datastructure:

{ a: 1, b: 2, c: 3, d: 4, ....}

If we always decrement the minimum key until it drops out of the datastructure, we will need to repeatedly determine the 2nd lowest key.

The only way to do this in $O (1)$ is to somehow maintain our keys in a sorted way during the increments and decrements.

Keeping the keys sorted

Let's step back and think about what operations we actually need to do in $O (1)$ to keep our keys sorted.

when incrementing a key that is not yet present in our datastructure, we need to insert the key at the front or back of sorted sequence
when decrementing a key that has a value of 1, we need to remove the key from (the back or the front of) the sorted sequence

So, we need $O (1)$ inserts and removals from the tail or head of the sequence.

Let's have a look at what can happen to a key if it's not in one of the already mentioned corner cases.

if we are increasing or decreasing a key and there are no other keys at either the old and the new value, we don't change the keys position in the sorted sequence
if we are increasing or decreasing a key and there are other keys at the old value but no other keys at the new value, we will need to insert a new element into the sequence one position away from the keys previous value
if we are increasing or decreasing a key and there are no other keys at the old value, but there are keys at the new value, we will need to remove an element from the sequence, from the keys previous value
if there are other keys at both the old and new values, the sequence will not change, however we need to move the key from one element of the sequence to another

So, we need the following operations in $O (1)$ :

local removals (remove element before or after a given element)
local inserts (add element before or after a given element)
stable iterators, so we can jump from a key to it's position in the sorted sequence

Yes, the datastructure we want is actually the rarely used linked list.

// {
class Constant {
private:
    // Appart from value we also store the iterator to the corresponding current bucket.
    struct Value {
        unsigned int value;
        list<pair<unsigned int, unordered_set<string>>>::iterator bucket;
    };
    // List of buckets: value + set of keys with this value.
    // We keep this list sorted by value.
    list<pair<unsigned int, unordered_set<string>>> _buckets;
    // Map from value to count of keys with that value.
    unordered_map<unsigned int, unsigned int> _counts;
    // Map from key to Value.
    unordered_map<string, Value> _values;
public:
    void create_element(const string& key) {
        if (_buckets.size() == 0 || _buckets.front().first != 1) {
            _buckets.push_front(make_pair(1, unordered_set<string>{key}));
        } else {
            _buckets.front().second.insert(key);
        }
        
        auto it = _buckets.begin();
        
        _values.insert(make_pair(key, Value{1, it}));
        _counts[1]++;
    }
    
    void delete_element(unordered_map<string, Value>::iterator it) {
        _counts[1]--;
        
        if (_counts[1] == 0) {
            _buckets.pop_front();
        } else {
            _buckets.front().second.erase(it->first);
        }
        
        _values.erase(it);
    }
                       
    // Adjust element by +1/-1
    void adjust_element(unordered_map<string, Value>::iterator it, int adj) {
        unsigned current = it->second.value;