Increment Key, Decrement Key, Find Max Key, Find Min key in O(1) time

Question

I was asked this question in the interview but could not solve it. Design a data structure which does the following

Inc(Key) -> Takes a key and increment its value by 1. If the key comes first time then make its value as 1.

Dec(Key) -> Takes a key and decrement its value by 1. It is given that its value is minimum 1.

Findmaxkey() -> Returns the key which has the maximum value corresponding to it. If there are multiple such keys then you can output any of them.

Findminkey() -> Returns the key which has the minimum value corresponding to it. If there are multiple such keys then you can output any of them.

You have to do all the operations in O(1) time.

Hint: The interviewer was asking me to use a dictionary(hashmap) with a doubly-linked list.

Answer 1

The data structure could be constructed as follows:

• Store all keys that have the same count in a HashSet keys, and accompany that set with the value for count: let's call this pair of count and keys a "bucket".

• For each count value for which there is at least a key, you'd have such a bucket. Put the buckets in a doubly linked list bucketList, and keep them ordered by count.

• Also create a HashMap bucketsByKey that maps a key to the bucket where that key is currently stored (the key is listed in the bucket's keys set)

The FindMinKey operation is then simple: get the first bucket from bucketList, grab a key from it's keys set (no matter which), and return it. Similar for FindMaxKey.

The Inc(key) operation would perform the following steps:

1. Get the bucket corresponding to key from bucketsByKey
2. If that bucket exists, delete the key from it's keys set.
3. If that set happens to become empty, remove the bucket from bucketList
4. If the next bucket in bucketList has a count that is one more, then add the key to it's set, and update bucketsByKey so that it refers to this bucket for this key.
5. If the next bucket in bucketList has a different count (or there are no more buckets), then create a new bucket with the right count and key and insert it just before the earlier found bucket in bucketList -- or if no next bucket was found, just add the new one at the end.
6. If in step 2 there was no bucket found for this key, then assume its count was 0, and take the first bucket from bucketList and use it as the "next bucket" from step 4 onwards.

The process for Dec(key) is similar except that when the count is found to be already 1, nothing happens.

Here is an interactive snippet in JavaScript which you can run here. It uses the native Map for the HashMap, the native Set for the HashSet, and implements a doubly linked list as a circular one, where the start/end is marked by a "sentinel" node (without data).

You can press the Inc/Dec buttons for a key of your choice and monitor the output of FindMinKey and FindMaxKey, as well as a simple view on the data structure.

class Bucket {
    constructor(count) {
        this.keys = new Set; // keys in this hashset all have the same count:
        this.count = count; // will never change. It's the unique key identifying this bucket
        this.next = this; // next bucket in a doubly linked, circular list
        this.prev = this; // previous bucket in the list
    }
    delete() { // detach this bucket from the list it is in
        this.next.prev = this.prev;
        this.prev.next = this.next;
        this.next = this;
        this.prev = this;
    }
    insertBefore(node) { // inject `this` into the list that `node` is in, right before it
        this.next = node;
        this.prev = node.prev;
        this.prev.next = this;
        this.next.prev = this;
    }
    * nextBuckets() { // iterate all following buckets until the "sentinel" bucket is encountered
        for (let bucket = this.next; bucket.count; bucket = bucket.next) {
            yield bucket;
        }
    }
}

class MinMaxMap {
    constructor() {
        this.bucketsByKey = new Map; // hashmap of key -> bucket
        this.bucketList = new Bucket(0); // a sentinel node of a circular doubly linked list of buckets
    }
    inc(key) {
        this.add(key, 1);
    }
    dec(key) {
        this.add(key, -1);
    }
    add(key, one) {
        let nextBucket, count = 1;
        let bucket = this.bucketsByKey.get(key);
        if (bucket === undefined) {
            nextBucket = this.bucketList.next;
        } else {
            count = bucket.count + one;
            if (count < 1) return;
            bucket.keys.delete(key);
            nextBucket = one === 1 ? bucket.next : bucket.prev;
            if (bucket.keys.size === 0) bucket.delete(); // remove from its list
        }
        if (nextBucket.count !== count) {
            bucket = new Bucket(count);
            bucket.insertBefore(one === 1 ? nextBucket : nextBucket.next);
        } else {
            bucket = nextBucket;
        }
        bucket.keys.add(key);
        this.bucketsByKey.set(key, bucket);
    }
    findMaxKey() {
        if (this.bucketList.prev.count === 0) return null; // the list is empty
        return this.bucketList.prev.keys.values().next().value; // get any key from first bucket
    }
    findMinKey() {
        if (this.bucketList.next.count === 0) return null; // the list is empty
        return this.bucketList.next.keys.values().next().value; // get any key from last bucket
    }
    toString() {
        return JSON.stringify(Array.from(this.bucketList.nextBuckets(), ({count, keys}) => [count, ...keys]))
    }
}

// I/O handling
let inpKey = document.querySelector("input");
let [btnInc, btnDec] = document.querySelectorAll("button");
let [outData, outMin, outMax] = document.querySelectorAll("span");

let minMaxMap = new MinMaxMap;
btnInc.addEventListener("click", function () {
    minMaxMap.inc(inpKey.value);
    refresh();
});
btnDec.addEventListener("click", function () {
    minMaxMap.dec(inpKey.value);
    refresh();
});
function refresh() {
    outData.textContent = minMaxMap.toString();
    outMin.textContent = minMaxMap.findMinKey();
    outMax.textContent = minMaxMap.findMaxKey();
}

key: <input> <button>Inc</button> <button>Dec</button><br>
data structure (linked list): <span></span><br>
findMinKey = <span></span><br>
findMaxKey = <span></span>

Answer 2

The key is the problem only asks for dec(1) or inc(1). Therefore, the algorithm only needs to move a block forward or backward. That's a strong prior and gives a lot of information.

My tested code:

template <typename K, uint32_t N>
struct DumbStructure {
 private:
  const int head_ = 0, tail_ = N - 1;

  std::unordered_map<K, int> dic_;

  int l_[N], r_[N], min_ = -1, max_ = -1;
  std::unordered_set<K> keys_[N];

  void NewKey(const K &key) {
    if (min_ < 0) {
      // nothing on the list
      l_[1] = head_;
      r_[1] = tail_;
      r_[head_] = 1;
      l_[tail_] = 1;

      min_ = max_ = 1;
    } else if (min_ == 1) {
    } else {
      // min_ > 1
      l_[1] = head_;
      r_[1] = min_;
      r_[head_] = 1;
      l_[min_] = 1;

      min_ = 1;
    }
    keys_[1].insert(key);
  }

  void MoveKey(const K &key, int from_value, int to_value) {
    int prev_from_value = l_[from_value];
    int succ_from_value = r_[from_value];

    if (keys_[from_value].size() >= 2) {
    } else {
      r_[prev_from_value] = succ_from_value;
      l_[succ_from_value] = prev_from_value;

      if (min_ == from_value) min_ = succ_from_value;
      if (max_ == from_value) max_ = prev_from_value;
    }
    keys_[from_value].erase(key);

    if (keys_[to_value].size() >= 1) {
    } else {
      if (to_value > from_value) {
        // move forward
        l_[to_value] =
            keys_[from_value].size() > 0 ? from_value : prev_from_value;
        r_[to_value] = succ_from_value;
        r_[l_[to_value]] = to_value;
        l_[r_[to_value]] = to_value;
      } else {
        // move backward
        l_[to_value] = prev_from_value;
        r_[to_value] =
            keys_[from_value].size() > 0 ? from_value : succ_from_value;
        r_[l_[to_value]] = to_value;
        l_[r_[to_value]] = to_value;
      }
    }
    keys_[to_value].insert(key);

    min_ = std::min(min_, to_value);
    max_ = std::max(max_, to_value);
  }

 public:
  DumbStructure() {
    l_[head_] = -1;
    r_[head_] = tail_;
    l_[tail_] = head_;
    r_[tail_] = -1;
  }

  void Inc(const K &key) {
    if (dic_.count(key) == 0) {
      dic_[key] = 1;
      NewKey(key);
    } else {
      MoveKey(key, dic_[key], dic_[key] + 1);
      dic_[key] += 1;
    }
  }

  void Dec(const K &key) {
    if (dic_.count(key) == 0 || dic_[key] == 1) {
      // invalid
      return;
    } else {
      MoveKey(key, dic_[key], dic_[key] - 1);
      dic_[key] -= 1;
    }
  }

  K GetMaxKey() const { return *keys_[max_].begin(); }

  K GetMinKey() const { return *keys_[min_].begin(); }
};

Answer 3

Here is my answer, still I'm not sure that I haven't broken any of the circumstances that your interviewer had in mind.

We will keep a LinkedList where each element has the key and values it's corresponding to, and a pointer to its previous and next element and is always sorted by values. We store a pointer for every key, where it is placed in the LinkedList. Furthermore, for every new number that we see, we add two elements which are supposed to view the start and end element of each number and we will store a pointer to them. Since we are adding these extra elements at most two for each operation, it's still of O(1).

now for every operation (say increment), we can find where the element corresponding to this key is placed in the LinkedList using a dictionary (assuming dictionaries work in time complexity of O(1)) now, we find the last element in the LinkedList which has the same value (we can do it using the element corresponding to the end of that value and come one element backwards) and swap these two's pointers (it's only a simple swap, and this swap does not affect other elements) next we swap this element with it's next one for two times so that it falls in the segment of the next number (we may need to add that number as well), the last things to keep track of, is the value of minimum and maximum which has to be updated if the element which is changing is either the current minimum or maximum and there is no number with the same value (the start and end elements for that value are consecutive in the LinkedList)

Still, I think this approach can be improved.