Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: All O`one Data Structure

Posted on January 31, 2018July 26, 2020 by braindenny

All O`one Data Structure



Similar Problems:

  • Insert Delete GetRandom O(1)
  • LRU Cache
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: oodesign, #lfu

Implement a data structure supporting the following operations:

Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string “”.
GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string “”.

Challenge: Perform all these in O(1) time complexity.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/all-oone-data-structure
## Basic Ideas:
##          hasmap: save key and values
##          How to achieve GetMinKey() with O(1)?
##          double linked list
##
## Complexity: Time O(1), Space O(n)

class DLinkNode:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

class AllOne(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.m = {}
        # head <--> p1 <--> p2 <--> tail
        # head and tail are dummy nodes. And m[p1] <= m[p2]
        self.head = DLinkNode(None)
        self.tail = DLinkNode(None)
        self.head.right = self.tail
        self.tail.left = self.head

    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: void
        """
        if key not in self.m:
            p = DLinkNode(key)
            self.m[key] = [1, p]
            # add to head
            p.right = self.head.right
            p.right.left = p
            p.left = self.head
            self.head.right = p
        else:
            [value, p] = self.m[key]
            self.m[key] = [value+1, p]
            # keep moving to right
            while p.right != self.tail and self.m[p.key][0]>self.m[p.right.key][0]:
                # .. <--> p <--> q <--> ..
                # swap p and q
                q = p.right
                p.right = q.right
                q.left = p.left
                p.right.left = p
                q.left.right = q
                q.right = p
                p.left = q

    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 not in self.m:
            return
        [value, p] = self.m[key]
        if value == 1:
            del self.m[key]
            # remove p, but it may not be the head
            p.left.right = p.right
            p.right.left = p.left
        else:
            self.m[key] = [value-1, p]
            # keep moving to left
            while p.left != self.head and self.m[p.key][0] < self.m[p.left.key][0]:
                # .. <--> q <--> p <--> ..
                q = p.left
                p.left = q.left
                q.right = p.right
                p.left.right = p
                q.right.left = q
                p.right = q
                q.left = p

    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        if self.head.right == self.tail:
            return ""
        else:
            return self.tail.left.key

    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        if self.head.right == self.tail:
            return ""
        else:
            return self.head.right.key

# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()
linkedin
github
slack

Post Views: 3
Posted in HardTagged #inspiring, lfu, oodesign

Post navigation

LeetCode: Word Search II
Review: Hashmap Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.