Skip to content

Randomized Algorithms

Table of Contents

398. Random Pick Index

382. Linked List Random Node

384. Shuffle an Array

470. Implement Rand10() Using Rand7()

  • LeetCode | LeetCode CH (Medium)

  • Tags: math, rejection sampling, randomized, probability and statistics

528. Random Pick with Weight

710. Random Pick with Blacklist

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, hash table, math, binary search, sorting, randomized

478. Generate Random Point in a Circle

497. Random Point in Non-overlapping Rectangles

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, math, binary search, reservoir sampling, prefix sum, ordered set, randomized

519. Random Flip Matrix

380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1) - Python Solution
import random


class RandomizedSet:
    def __init__(self):
        self.dict = {}
        self.list = []

    def insert(self, val: int) -> bool:
        if val in self.dict:
            return False
        self.dict[val] = len(self.list)
        self.list.append(val)

        return True

    def remove(self, val: int) -> bool:
        if val not in self.dict:
            return False
        last_element = self.list[-1]
        idx = self.dict[val]
        self.list[idx] = last_element
        self.dict[last_element] = idx
        self.list.pop()
        del self.dict[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)


obj = RandomizedSet()
print(obj.insert(1))  # True
print(obj.remove(2))  # False
print(obj.insert(2))  # True
print(obj.getRandom())  # 1 or 2
print(obj.remove(1))  # True

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

1515. Best Position for a Service Centre

1968. Array With Elements Not Equal to Average of Neighbors

Comments