# GetRandom O(1)

## 380. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

* List 儲存 val
* Map 儲存 val, store index
* Remove val in list in constant, so we swap the number with last number in list and then delete the number in last position, it's O(1) operation

```java
class RandomizedSet {
    List<Integer> list;
    Map<Integer, Integer> map;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    /** 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)) return false;
        map.put(val, list.size());
        System.out.println(val);
        list.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;
        int idx = map.get(val);

        // swap the val and last val in list
        if(idx < list.size()-1){
            int lastNum = list.get(list.size()-1);
            list.set(idx, lastNum);
            map.put(lastNum, idx);
        }
        list.remove(list.size()-1);
        map.remove(val);

        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        Random ran = new Random();
        return list.get(ran.nextInt(list.size()));
    }
}
```

## 381. Insert Delete GetRandom O(1) - Duplicates allowed

Same as 380, but with duplicated number

* List store numbers
* Map> indexes to the same numbers

```java
class RandomizedCollection {
    List<Integer> list;
    Map<Integer, Set<Integer>> map;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contain = map.containsKey(val);
        if(!contain) map.put(val, new HashSet<>());
        map.get(val).add(list.size());
        list.add(val);
        return !contain;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;
        int idx = map.get(val).iterator().next();
        map.get(val).remove(idx);
        if(map.get(val).size() == 0) map.remove(val); 

        if(idx < list.size()-1){
            int lastNum = list.get(list.size()-1);
            list.set(idx, lastNum);
            map.get(lastNum).remove(list.size()-1);
            map.get(lastNum).add(idx);
        }
        list.remove(list.size()-1);

        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        Random ran = new Random();
        return list.get(ran.nextInt(list.size()));
    }
}
```


---

# 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://netjimmy.gitbook.io/code-interview-note/simulation/getrandom-o1.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.