Skip to main content

380. Insert Delete GetRandom O(1)

mediumAsked at DoorDash

Design a data structure that supports insert, remove, and getRandom each in O(1) average. DoorDash uses this for backend rounds — they want the swap-with-last-then-pop trick that combines a hash map and an array.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite this as a recurring data-structure design question.
  • Blind (2025-12)— DoorDash backend SDE reports note the swap-with-last trick as the actual interview signal.

Problem

Implement the RandomizedSet class: RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. You must implement the functions of the class such that each function works in average O(1) time complexity.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

Examples

Example 1

Input
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
Output
[null,true,false,true,2,true,false,2]

Approaches

1. Hash map (value -> index) + array

Array stores values for O(1) random access. Hash map maps value to its index in the array. On remove, swap with the last element, then pop.

Time
O(1) avg per op
Space
O(n)
class RandomizedSet {
  constructor() {
    this.values = [];
    this.idx = new Map();
  }
  insert(val) {
    if (this.idx.has(val)) return false;
    this.idx.set(val, this.values.length);
    this.values.push(val);
    return true;
  }
  remove(val) {
    if (!this.idx.has(val)) return false;
    const i = this.idx.get(val);
    const last = this.values[this.values.length - 1];
    this.values[i] = last;
    this.idx.set(last, i);
    this.values.pop();
    this.idx.delete(val);
    return true;
  }
  getRandom() {
    const i = Math.floor(Math.random() * this.values.length);
    return this.values[i];
  }
}

Tradeoff: DoorDash's expected answer. The swap-with-last trick is the heart of the problem — without it, remove is O(n) due to array shift.

2. Set + Array (broken getRandom)

Use a Set for O(1) insert/remove. But getRandom on a Set is O(n) without an index — fails the constraint.

Time
Set ops O(1), getRandom O(n)
Space
O(n)
class RandomizedSetBroken {
  constructor() { this.set = new Set(); }
  insert(val) { if (this.set.has(val)) return false; this.set.add(val); return true; }
  remove(val) { if (!this.set.has(val)) return false; this.set.delete(val); return true; }
  getRandom() {
    const arr = [...this.set];
    return arr[Math.floor(Math.random() * arr.length)];
  }
}

Tradeoff: Fails the O(1) getRandom constraint because materializing the array is O(n). Mention as the naive approach that misses the constraint.

DoorDash-specific tips

DoorDash interviewers grade specifically on the SWAP-WITH-LAST trick. State 'I'll use an array for O(1) random access plus a hash map for O(1) lookup; on remove, swap with last so the array stays compact' BEFORE coding. That sentence proves you spotted the constraint.

Common mistakes

  • Removing from the middle of the array without the swap — O(n) shift breaks the constraint.
  • Forgetting to update the hash map for the swapped element.
  • Computing random over a set-like structure — Set has no O(1) random.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Insert Delete GetRandom O(1) - Duplicates Allowed (LC 381) — value -> set of indices.
  • LRU Cache (LC 146) — similar 'multiple structures for O(1)' pattern.
  • LFU Cache (LC 460) — same pattern, more complex bookkeeping.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why swap with last?

Removing from the middle requires shifting all later elements — O(n). Swapping with the last element preserves O(1) by only touching two slots.

What if we needed duplicates?

LC 381. The hash map becomes value -> Set of indices. On remove, swap the LAST occurrence with the global last.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Insert Delete GetRandom O(1) and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →