All O`one Data Structure

All O`one Data Structure is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

- AllOne() Initializes the object of the data structure.

- inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.

- dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.

- getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".

- getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

Example 1:

Input ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []] Output [null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation AllOne allOne = new AllOne(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "hello" allOne.inc("leet"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "leet"

Constraints:

- 1 <= key.length <= 10

- key consists of lowercase English letters.

- It is guaranteed that for each call to dec, key is existing in the data structure.

- At most 5 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

Topics and companies

Topics: Hash Table, Linked List, Design, Doubly-Linked List.

Reported in interviews at Amazon.

How to practise All O`one Data Structure on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) average per operation. Each inc, dec, getMaxKey, and getMinKey runs in O(1) amortized time due to the use of a doubly linked list and hash maps for direct access and updates. time and O(N + M), where N is the number of unique keys and M is the number of unique counts (buckets). Each key is stored in a hash map and a bucket, and each bucket stores a set of keys. space.

Open All O`one Data Structure in the code editor, or read the All O`one Data Structure editorial for a worked solution with its approach and complexity analysis.

Where All O`one Data Structure sits in the DSA pattern sheet

Problems related to All O`one Data Structure

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.