# Custom DS Design

## 经典题目

[*380 Insert Delete GetRandom O(1)* ](https://leetcode.com/problems/insert-delete-getrandom-o1/description/)

* *Follow up, what if duplicates are allowed.* [*LC 381*](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/)

{% tabs %}
{% tab title="380 Sol" %}

```java
// HashMap + ArrayList
// 有个 corner case 需要 handle，就是调用 remove 操作时，
// list 中 只有一个元素 和 有多个元素 的情况，需要区分开来。

class RandomizedSet {
    Map<Integer, Integer> map;
    List<Integer> list;
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<Integer, Integer>();
        list = new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            map.put(val, list.size());
            list.add(val);
            return true;
        }
        return false;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int index = map.get(val);
            // put the last element in the list to index
            if (index == list.size() - 1) {
                list.remove(list.size() - 1);
                map.remove(val);
            } else {
                int tailValue = list.get(list.size() - 1);
                list.set(index, tailValue);
                // remove the last element
                list.remove(list.size() - 1);
                map.remove(val);
                map.put(tailValue, index);
            }
            return true;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        return list.get(random.nextInt(list.size()));
    }
}
```

{% endtab %}

{% tab title="381 Follow up --- Duplicates Allowed" %}

```java
// Follow up 多了 duplicates
// 因为所有操作需要做到 O(1)，并且 getRandom() 跟比重有关
// 所以这里需要一个 Map<Integer, Set<Integer>> ，记录不同值的所有index
// Remove() 的策略还是跟之前一样，取一个index，然后和list 最后一个index交换
// 注意，交换之后，必须确保所有变量的物理意义不变。
class RandomizedCollection {
    List<Integer> list;
    // key : unique value
    // value: list of indexes respectively
    Map<Integer, Set<Integer>> map;
    Random rd;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rd = new Random();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        list.add(val);
        if (map.containsKey(val)) {
            map.get(val).add(list.size() - 1);
            return false;
        } else {
            Set<Integer> indexes = new HashSet<>();
            indexes.add(list.size() - 1);
            map.put(val, indexes);
            return true;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            Set<Integer> indexes = map.get(val);
            Iterator<Integer> itr = indexes.iterator();
            if (itr.hasNext()) {
                int valIndex = itr.next();              
                // Condition 1: valIndex is the last index of list
                // Then, we just need to remove it from list and map.
                if (valIndex == list.size() - 1) {
                    indexes.remove(valIndex);
                    list.remove(list.size() - 1);
                } else {
                    // Condition 2: valIndex is not the last index of list
                    // Then, swap it with the last element of list.
                    // Remove the index record in map
                    // Update the index records of swapped element in map
                    // Remove the last element of list
                                        
                    // remove index
                    indexes.remove(valIndex);                  
                    int tailVal = list.get(list.size() - 1);
                    Set<Integer> tailIndexes = map.get(tailVal);
                    // swap valIndex and last element
                    list.set(valIndex, tailVal);
                    // delete the last element in list
                    list.remove(list.size() - 1);
                    // update index
                    tailIndexes.remove(list.size());
                    tailIndexes.add(valIndex);
                }
                return true;
            } else {
                map.remove(val);
                return false;
            }
        } 
        return false;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        int index = rd.nextInt(list.size());
        return list.get(index);
    }
}
```

{% endtab %}
{% endtabs %}

[ *895. Maximum Frequency Stack*](https://leetcode.com/problems/maximum-frequency-stack/description/)

```java
class FreqStack {
	/*
		Method 1: HashMap of Stack.
		
		levelMap: {frequency: stack of numbers}
		freqMap: {number: frequency}
		
		For example:
		5 -> 1 -> 5 -> 2 -> 5 -> 1 -> 4
		
		levelMap: {
			1 : {5, 1, 2, 4}
			2 : {5, 1}
			3 : {5}
		}
		freqMap: {
			1:2
			2:1
			4:1
			5:3
		}
	*/
	
    private int maxFreq = 0;
    private Map<Integer, Deque<Integer>> levelMap; 
    private Map<Integer, Integer> freqMap;
    
    public FreqStack() {
        freqMap = new HashMap<>();
        levelMap = new HashMap<>();
    }
    
    public void push(int x) {
        int newFreq = freqMap.getOrDefault(x, 0) + 1;
        freqMap.put(x, newFreq);
        maxFreq = Math.max(maxFreq, newFreq);
        
        Deque<Integer> stack = levelMap.get(newFreq);
        if (stack == null) {
            stack = new LinkedList<>();
        }
        stack.offerLast(x);
        levelMap.put(newFreq, stack);
    }
    
    public int pop() {
        int res = levelMap.get(maxFreq).pollLast();
        freqMap.put(res, maxFreq - 1);
        if (levelMap.get(maxFreq).size() == 0) {
            maxFreq -= 1;
        }
        return res;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/data-structure/custom-ds-design.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.