Processing math: 100%

Common Coding Interview Questions O(1) Data Structure

HappyCerberus
3,496 views

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.

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.

  1. if the key was not the maximum, the maximum will not change
  2. increasing a maximum key will increase the maximum
  3. 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.

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.

  1. 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
  2. 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.

  1. 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
  2. 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
  3. 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
  4. 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):

  1. local removals (remove element before or after a given element)
  2. local inserts (add element before or after a given element)
  3. 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.

And that's it. All the operations now run in O(1) time complexity.


Previous: Top k elements and k-th element

Next: Palindromes


CC-BY-SA

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. Šimon Tóth 2020 (kontakt@simontoth.cz)

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content