All O`one Data Structure

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

from collections import defaultdict
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 count(self):
        return len(self.key_set)

    def is_empty(self):
        return len(self.key_set) == 0


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
        return

    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 remove(self, x):
        prev_node = x.prev
        prev_node.nxt, x.nxt.prev = x.nxt, prev_node
        return

    def get_head(self):
        return self.head_node.nxt
    
    def get_tail(self):
        return self.tail_node.prev

    def get_sentinel_head(self):
        return self.head_node

    def get_sentinel_tail(self):
        return self.tail_node
    
class AllOne(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dll, self.key_counter = DoubleLinkedList(), defaultdict(int)
        self.node_freq = {0:self.dll.get_sentinel_head()}

    def _rmv_key_pf_node(self, pf, key):
        node = self.node_freq[pf]
        node.remove_key(key)
        if node.is_empty():
            self.dll.remove(node)
            self.node_freq.pop(pf)
        return

    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: void
        """
        self.key_counter[key] += 1
        cf, pf = self.key_counter[key], self.key_counter[key]-1
        if cf not in self.node_freq:
            # No need to test if pf = 0 since frequency zero points to sentinel node
            self.node_freq[cf] = self.dll.insert_after(self.node_freq[pf])
        self.node_freq[cf].add_key(key)
        if pf > 0:
            self._rmv_key_pf_node(pf, key)

    def dec(self, key):
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        :type key: str
        :rtype: void
        """
        if key in self.key_counter:
            self.key_counter[key] -= 1
            cf, pf = self.key_counter[key], self.key_counter[key]+1
            if self.key_counter[key] == 0:
                self.key_counter.pop(key)
            if cf != 0:
                if cf not in self.node_freq:
                    self.node_freq[cf] = self.dll.insert_before(self.node_freq[pf])
                self.node_freq[cf].add_key(key)
            self._rmv_key_pf_node(pf, key)

    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        return self.dll.get_tail().get_any_key() if self.dll.get_tail().count() > 0 else ""

    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        return self.dll.get_head().get_any_key() if self.dll.get_tail().count() > 0 else ""

Identifying Problem Isomorphism

“All O’one Data Structure” requires the implementation of a data structure that can support insert, delete, getMax and getMin operations all in O(1) time complexity. It needs a solid understanding of data structures and algorithms to design an efficient solution.

A similar problem that also involves design and implementation of a data structure is “LRU Cache”. It’s a more straightforward problem because it only requires maintaining the Least Recently Used (LRU) ordering with insert and get operations.

On the more complex end of the spectrum, we have “LFU Cache”. Here, the data structure design involves maintaining the Least Frequently Used (LFU) order. This adds a new dimension of complexity because frequency can change dynamically with each operation, and yet, it needs to support all operations in O(1) time.

The reasoning behind this selection:

  • “LRU Cache” introduces the concept of a specialized data structure where insertion and retrieval operations affect the state of the data structure. It’s a great starting point for understanding “All O’one Data Structure”.
  • “All O’one Data Structure” adds a layer of complexity by requiring all operations to be performed in constant time.
  • “LFU Cache” is the most complex of these problems. It requires the same O(1) time complexity as the “All O’one Data Structure” but introduces the challenge of dynamically changing frequencies.

So, in increasing order of complexity:

  1. “LRU Cache”
  2. “All O’one Data Structure”
  3. “LFU Cache”

These mappings are approximate, as perceived difficulty can vary based on individual familiarity with the concepts. But all these problems share the underlying theme of designing specialized data structures that require certain operation time complexities.

The problem “432. All O’one Data Structure” is a design problem where one needs to design a data structure that can support operations like inc(key), dec(key), getMaxKey(), and getMinKey(), all in constant time complexity. Here are 10 problems of lesser complexity that you can solve to prepare for this:

  1. “155. Min Stack”: Teaches you how to design a stack that supports retrieving the minimum element in constant time.

  2. “232. Implement Queue using Stacks”: Lets you understand how to use one data structure to implement another.

  3. “146. LRU Cache”: Introduces the concept of designing a data structure with both O(1) access and removal.

  4. “380. Insert Delete GetRandom O(1)”: A problem where you need to support insert, delete, and getRandom operations, all in average O(1) time.

  5. “706. Design HashMap”: A basic problem to understand how to design a HashMap.

  6. “208. Implement Trie (Prefix Tree)”: While not directly relevant, understanding Trie can broaden your perspective on data structures.

  7. “384. Shuffle an Array”: Helps you understand how to maintain properties (in this case, randomness) under certain operations.

  8. “295. Find Median from Data Stream”: Teaches you how to maintain a data structure under continuous input.

  9. “355. Design Twitter”: Helps you to understand a complex data structure design that involves maintaining multiple kinds of information.

  10. “173. Binary Search Tree Iterator”: Helps to understand how to build a data structure that can smoothly iterate over another data structure.

These problems provide a good foundation for understanding data structure design and constant time operations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class AllOne:
    def __init__(self):
        self.mem = dict()
        self.prev_max = None
        self.prev_min = None

    def inc(self, key: str) -> None:
        self.prev_max, self.prev_min = None, None

        if key not in self.mem:
            self.mem[key] = 1
        else:
            self.mem[key] += 1

    def dec(self, key: str) -> None:
        self.prev_max, self.prev_min = None, None

        if self.mem[key] == 1:
            self.mem.pop(key)
        else:
            self.mem[key] -= 1

    def getMaxKey(self) -> str:
        if len(self.mem) == 0:
            return ""
        else:
            if self.prev_max != None:
                return self.prev_max
            
            output = sorted(self.mem.items(), key=lambda x:x[1])[-1][0]
            self.prev_max = output

            return output

    def getMinKey(self) -> str:
        if len(self.mem) == 0:
            return ""
        else:
            if self.prev_min != None:
                return self.prev_min
            output = sorted(self.mem.items(), key=lambda x:x[1])[0][0]
            self.prev_min = output
            return output

This problem requires designing a data structure that supports operations in constant time. This is a Data Structure Design Problem.

Language Agnostic Coding Drills

This is an implementation of a data structure that maintains a dictionary of key-value pairs while also tracking the maximum and minimum keys. It provides the ability to increment and decrement the values associated with keys, and it can return the key with the maximum or minimum value.

Let’s break down the problem-solving approach and list the coding concepts used, without writing any code:

  1. Concept: Basic Data Types and Structures - Understanding of basic data types and structures is crucial in the given problem. For example, the usage of a dictionary (dict in Python) is essential to store the keys and their corresponding values.

  2. Concept: Object-Oriented Programming (OOP) - Understanding the concept of classes and objects is key. The ‘AllOne’ class is created with methods to increment and decrement the value associated with a key and to get the maximum and minimum key based on the values.

  3. Concept: Conditional Statements - The use of if-else statements allows the code to handle different conditions. These conditions include whether a key is present in the dictionary, and whether the previous maximum or minimum keys are stored.

  4. Concept: Functions and Method Definitions - Understanding how to define and use methods within a class is crucial. This includes knowing how to access and manipulate the class’s attributes within these methods.

  5. Concept: Sorting - The use of the sorted function allows for sorting the dictionary items based on their values. Understanding how to use a lambda function as the key argument to sort by the value of the dictionary items is also important.

  6. Concept: Dictionary Manipulation - It is important to understand dictionary operations, such as adding, updating, and removing key-value pairs, as well as accessing values by keys.

Problem Solving Approach:

  1. Begin by defining the ‘AllOne’ class and initializing the dictionary (mem) and variables to keep track of the previous maximum and minimum keys.

  2. Define the inc method to increment the value of a key. If the key is not present, it is added with a value of 1. If it is present, its value is incremented. The previous max and min values are reset.

  3. Define the dec method to decrement the value of a key. If the value becomes 0, the key is removed from the dictionary. If it is present, its value is decremented. The previous max and min values are reset.

  4. Define the getMaxKey method to return the key with the maximum value. If a previous maximum is stored, it returns that. Otherwise, it sorts the dictionary items based on their values in ascending order and returns the key of the last item (i.e., the key with the highest value).

  5. Define the getMinKey method to return the key with the minimum value in a similar way. It sorts the items and returns the key of the first item (i.e., the key with the smallest value).

  6. The entire class works as a system maintaining a dictionary while tracking the maximum and minimum keys effectively.

Targeted Drills in Python

  1. Drill 1: Basic Data Types and Structures - Create a dictionary and perform simple operations such as adding, updating, and deleting key-value pairs.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Define the dictionary
my_dict = {}

# Add key-value pairs
my_dict["apple"] = 1
my_dict["banana"] = 2
print(my_dict)

# Update a value
my_dict["apple"] = 3
print(my_dict)

# Delete a key-value pair
del my_dict["banana"]
print(my_dict)
  1. Drill 2: Object-Oriented Programming (OOP) - Define a simple class with a constructor and a method.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class MyClass:
    def __init__(self, value):
        self.value = value

    def getValue(self):
        return self.value

# Create an instance of the class and call its method
my_obj = MyClass(5)
print(my_obj.getValue())
  1. Drill 3: Conditional Statements - Write an if-else statement that checks if a variable is greater than a certain value.
1
2
3
4
5
6
7
8

# Define the variable
x = 10

# Write the if-else statement
if x > 5:
    print("x is greater than 5")
else:
    print("x is not greater than 5")
  1. Drill 4: Functions and Method Definitions - Define a function that calculates the square of a number.
1
2
3
4
5

def square(num):
    return num * num

# Call the function
print(square(5))
  1. Drill 5: Sorting - Sort a list of tuples based on the second element of each tuple.
1
2
3
4
5
6
7

# Define the list of tuples
my_list = [(1, 2), (3, 1), (2, 3)]

# Sort the list
my_list.sort(key=lambda x: x[1])

print(my_list)
  1. Drill 6: Dictionary Manipulation - Create a dictionary and perform some basic manipulations.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Create the dictionary
my_dict = {"a": 1, "b": 2, "c": 3}

# Update a value
my_dict["a"] = 10
print(my_dict)

# Remove a key-value pair
del my_dict["b"]
print(my_dict)
  1. Problem Specific Drill: Define a class with methods for adding a key-value pair, incrementing and decrementing the value of a key, and retrieving the maximum and minimum keys.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class KeyValues:
    def __init__(self):
        self.mem = {}

    def add_key(self, key, value):
        self.mem[key] = value

    def increment(self, key):
        if key in self.mem:
            self.mem[key] += 1

    def decrement(self, key):
        if key in self.mem:
            self.mem[key] -= 1
            if self.mem[key] == 0:
                del self.mem[key]

    def get_max_key(self):
        return max(self.mem, key=self.mem.get)

    def get_min_key(self):
        return min(self.mem, key=self.mem.get)

# Test the class
kv = KeyValues()
kv.add_key('a', 1)
kv.add_key('b', 2)
kv.increment('a')
kv.decrement('b')
print(kv.get_max_key())  # Output: 'a'
print(kv.get_min_key())  # Output: 'b'