Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Insert Delete GetRandom O(1) – Duplicates allowed

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

Insert Delete GetRandom O(1) – Duplicates allowed



Similar Problems:

  • Max Stack
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #oodesign, #random

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

Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

Github: code.dennyzhang.com

Credits To: leetcode.com

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


  • Solution: hashmap with set as value
// https://code.dennyzhang.com/insert-delete-getrandom-o1-duplicates-allowed
// Basic Ideas: hashmap + array
//
// Complexity: Time O(1), Space O(n)
import "math/rand"
type RandomizedCollection struct {
    // value to positions
    positions map[int]map[int]bool
    values []int
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
    return RandomizedCollection{positions:map[int]map[int]bool{}, values:[]int{}}
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
func (this *RandomizedCollection) Insert(val int) bool {
    res := false
    if _, ok := this.positions[val]; !ok {
        this.positions[val] = map[int]bool{}
        res = true
    }
    this.positions[val][len(this.values)] = true
    this.values = append(this.values, val)
    return res
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
    // not found
    _, ok := this.positions[val]
    if !ok || len(this.positions[val]) == 0 {
        return false
    }
    // get one random position for the value of val
    pos := -1
    for k, _ := range this.positions[val] {
        pos = k
        delete(this.positions[val], pos)
        break
    }
    // move last_element to val
    last_element := this.values[len(this.values)-1]
    this.values[pos] = last_element

    this.positions[last_element][pos] = true
    delete(this.positions[last_element], len(this.values)-1)

    // shorten array
    this.values = this.values[0:len(this.values)-1]
    return true
}

/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
    index := rand.Intn(len(this.values))
    return this.values[index]
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
linkedin
github
slack

Post Views: 5
Posted in HardTagged #inspiring, oodesign, random, redo

Post navigation

LeetCode: Longest Continuous Increasing Subsequence
LeetCode: Search Insert Position

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.