[Solution]Problem 41: Create your own Datastructure with O(1) Time complexity (Dropbox)
Data structures, Logic, Object Oriented Programming
Problem
This problem was asked by Dropbox.
Create a data structure that performs all the following operations in O(1)
time:
plus
: Add a key with value1
. If the key already exists, increment its value by one.minus
: Decrement the value of a key. If the key's value is currently1
, remove it.get_max
: Return a key with the highest value.get_min
: Return a key with the lowest value.
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Thanks to the guaranteed refund policy, there is no risk to you -
Step 1: The Xs and Os
Problems like this are hard for a variety of reasons. Obviously, there will be some challenges in implementing the O(1) time operations. So it makes sense to go for the lower-hanging fruit first. Luckily, the get_min/max functions are easy to reach.
Typically, if we want to return the min/max value, we will track just them using variables. You might be tempted to do so, however that approach has one drawback. Let’s look at the requirements of our DS once more.
plus: Add a key with value 1. If the key already exists, increment its value by one.
minus: Decrement the value of a key. If the key's value is currently 1, remove it.
Both these functions tweak our DS in a major way. Notice that for an instance of our DS, there is a chance that our minimum and max values will change if these functions are called a bunch of times on keys. Clearly, we will need to track more than just the max and min value at the current time. For any given key, it thus becomes important to keep track of both the keys with lower and higher counts than it. Fortunately, we have a DS perfectly developed for this bi-directionality.
Step 2: Doubly Linked List
Doubly Linked-Lists are like the big brothers of LinkedLists. They don’t show up as frequently as LLs, but they do have a very important role in software engineering. When we have relationships where bi-directionality is important, you can implement them.
To meet the needs, we would a sorted collection of keys. We store these keys as a doubly-linked list. For a given node, the previous node will contain keys with the next lowest value, and the next node will contain keys with the next highest value. If we maintain a pointer to the head and tail of this list, we will always be able to access a key with the lowest and highest value, respectively in constant time.
Before we start implementing the DLL, we need to develop the Node Class. Most of it is relatively straightforward. Take a look below.
class Node(object):
def __init__(self):
self.key_set = set()
self.prev, self.nxt = None, None
def add_key(self, key):
self.key_set.add(key)
def remove_key(self, key):
self.key_set.remove(key)
def get_any_key(self):
if self.key_set:
result = self.key_set.pop()
self.add_key(result)
return result
else:
return None
def is_empty(self):
return len(self.key_set) == 0
We a set() instead of dict/hash-map because uniqueness matters in our final solution. Remember, each node will track all the keys with the same count. With our node done, let’s create our DLL.
Step 3: Creating The Doubly Linked List
We can code up the doubly linked list class, which will allow us to chain together nodes. The logic of each method here hopefully should not have any surprises. In addition to maintaining head
and tail
pointers, we define insertion and removal methods that run in O(1)
time.
class DoubleLinkedList(object):
def __init__(self):
self.head_node, self.tail_node = Node(), Node()
self.head_node.nxt, self.tail_node.prev = self.tail_node, self.head_node
def insert_after(self, x):
node, temp = Node(), x.nxt
x.nxt, node.prev = node, x
node.nxt, temp.prev = temp, node
return node
def insert_before(self, x):
return self.insert_after(x.prev)
def insert_after_head(self):
return self.insert_after(self.head_node)
def remove(self, x):
prev_node = x.prev
prev_node.nxt, x.nxt.prev = x.nxt, prev_node
def get_head(self):
return self.head_node.nxt
def get_tail(self):
return self.tail_node.prev
The DLL is implemented using the idea of sentinel nodes, i.e. we have two dummy nodes to represent head and tail. Initially head.next points to tail and tail.prev points to head. Using two dummy nodes dramatically simplifies the implementation. We will cover this in Math Mondays soon.
Now that we have finished laying the foundation, it’s time to actually implement the problems that will allow us to create our solution.
Step 4: Sketching up the algorithms
We know that a node in the doubly linked list represents a bucket containing a bag of words with a certain frequency. The DLL is maintained in sorted order with the head node containing words with the least frequency and the tail node containing words with maximum frequency.
The DLL, allows us to implement get_max/min
in O(1) by returning any word contained in the tail and head respectively. Next we need 2 dicts to increment or decrement frequency of a key in O(1) and to map the count for every bucket node in the linked list respectively. This is not too hard.
If we can maintain the sorted order of the linked list in O(1) while performing the increment and decrement operations, we would have a working solution. Yippee!!!
So now, let’s figure out the increment/decrement of key counts. Believe it or not, we are very close to fixing everything. We have all the pieces together (mostly). We just have to arrange them properly.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.