辞書と並びを組み合わせて O(1) で出し入れと無作為な取り出しができる集合を作る｜コーディング面接問題

問題

抽選に使う整数の集合を、クラス RandomSet として作ってください。同じ値は 1 つしか入りません。次の 3 つの操作を、どれも平均 O(1) の時間でこなしてください。

insert(val) は、val がまだ入っていなければ足して真を返します。もう入っていれば何もせず偽を返します
remove(val) は、val が入っていれば取り除いて真を返します。入っていなければ何もせず偽を返します
getRandom() は、いま入っている値から 1 つを選んで返します。どの値も同じ確率で選ばれるようにします

メソッドの名前は、JavaScript は上のまま、Python は get_random のように小文字と下線、Go は Insert、Remove、GetRandom と頭を大文字にします。Go では newRandomSet() で作ります。

入力は、呼ぶ操作の名前の並び ops と、それぞれの引数の並び args で渡します。ops の最初はクラスの名前で、args の最初は空の並びです。出力は操作ごとの戻り値の並びで、作った所は null です。

getRandom は、値が 1 つ以上入っているときだけ呼びます。答えを 1 つに決めて比べるため、例と確かめでは、値がちょうど 1 つ入っているときだけ呼びます
val は -2147483648 以上 2147483647 以下です
操作の回数は 200000 回以下です

入力と出力の例

例 1

4 は 2 回目の insert では足されません。4 を取り除くと 9 だけが残るので、getRandom は 9 です。

入力

ops = ["RandomSet", "insert",
  "insert", "insert",
  "remove", "getRandom",
  "remove"]
args = [[], [4], [4], [9],
  [4], [], [4]]

出力

[null, true, false, true,
 true, 9, false]

例 2

空の集合から取り除こうとすると偽です。取り除いた値は、もう一度足せます。

入力

ops = ["RandomSet", "remove",
  "insert", "getRandom",
  "remove", "insert"]
args = [[], [1], [-3], [],
  [-3], [-3]]

出力

[null, false, true, -3,
 true, true]

例 3

途中の値を取り除くと、末尾の値がその位置へ移ります。移った値もきちんと取り除けます。

入力

ops = ["RandomSet", "insert",
  "insert", "insert",
  "remove", "remove",
  "getRandom", "insert"]
args = [[], [1], [2], [3],
  [1], [3], [], [3]]

出力

[null, true, true, true,
 true, true, 2, true]

面接での聞かれ方

面接では、抽選や、たくさんの機械から 1 台を無作為に選んで仕事を振る仕組みを例に出して渡されることが多いです。

最初に「集合 (set) を使います」と言うと、「では、集合から同じ確率で 1 つを O(1) で選べますか？」と聞かれます
並びだけで持つと、「途中の値を取り除くのは O(n) ではありませんか？」と指摘されます
書き終えたあとに「同じ値をいくつも入れてよい形に変えるなら、何を持ちますか？」と続きます

辞書は「あるかどうか」に強く、並びは「何番目かで選ぶ」のに強い、と道具の得意を分けて組み合わせられるかが見られています。

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まずは素直に、集合 (辞書) だけで持つ書き方を考えます。insert と remove は平均 O(1) です。ところが集合には番号が無いので、同じ確率で 1 つを選ぶには、全部を並びへ写して乱数の番号で引くことになり、getRandom が O(n) になります。

段 2

並びだけで持つ書き方も考えます。getRandom は乱数の番号で引けば O(1) です。ところが remove は、値を探すのに O(n)、途中を抜いて後ろを詰めるのにも O(n) かかります。

段 3

2 つを組み合わせます。値を並び vals に入れ、辞書 pos で「値から、並びの何番目にあるか」を引けるようにします。insert は、辞書で有無を見て、並びの末尾に足し、番号を辞書に書きます。getRandom は、0 から並びの長さ未満の乱数の番号で引きます。

段 4

remove の芯は、途中に穴を作らないことです。取り除く値の番号 i を辞書で引き、並びの末尾の値をその i の位置へ移し、末尾を取り除きます。移した値の番号を辞書で i に書き直せば、並びは詰まったまま O(1) で済みます。取り除く値がもともと末尾だったときは、移す必要はありません。

解答

Python

from random import choice


class RandomSet:
    def __init__(self):
        self.pos = {}
        self.vals = []

    def insert(self, val):
        pos = self.pos
        if val in pos:
            return False
        vals = self.vals
        pos[val] = len(vals)
        vals.append(val)
        return True

    def remove(self, val):
        pos = self.pos
        if val not in pos:
            return False
        vals = self.vals
        i = pos.pop(val)
        last = vals.pop()
        if i < len(vals):
            vals[i] = last
            pos[last] = i
        return True

    def get_random(self):
        return choice(self.vals)

JavaScript

class RandomSet {
  constructor() {
    this.pos = new Map();
    this.vals = [];
  }

  insert(val) {
    const pos = this.pos;
    if (pos.has(val)) {
      return false;
    }
    const vals = this.vals;
    pos.set(val, vals.length);
    vals.push(val);
    return true;
  }

  remove(val) {
    const pos = this.pos;
    if (!pos.has(val)) {
      return false;
    }
    const vals = this.vals;
    const i = pos.get(val);
    pos.delete(val);
    const last = vals.pop();
    if (i < vals.length) {
      vals[i] = last;
      pos.set(last, i);
    }
    return true;
  }

  getRandom() {
    const vals = this.vals;
    const n = vals.length;
    const i = Math.floor(
      Math.random() * n
    );
    return vals[i];
  }
}

Go

import "math/rand"

type RandomSet struct {
	pos  map[int]int
	vals []int
}

func newRandomSet() *RandomSet {
	return &RandomSet{
		pos: map[int]int{},
	}
}

func (s *RandomSet) Insert(
	val int,
) bool {
	if _, ok := s.pos[val]; ok {
		return false
	}
	s.pos[val] = len(s.vals)
	s.vals = append(s.vals, val)
	return true
}

func (s *RandomSet) Remove(
	val int,
) bool {
	i, ok := s.pos[val]
	if !ok {
		return false
	}
	delete(s.pos, val)
	n := len(s.vals) - 1
	last := s.vals[n]
	s.vals = s.vals[:n]
	if i < n {
		s.vals[i] = last
		s.pos[last] = i
	}
	return true
}

func (s *RandomSet) GetRandom(
) int {
	i := rand.Intn(len(s.vals))
	return s.vals[i]
}

remove は、取り除く値の番号 i が末尾より前のときだけ、末尾の値を i へ移します。取り除く値がもともと末尾なら、末尾を落とすだけで済み、辞書に書き戻す物はありません。

計算量

時間は、3 つの操作のどれも平均 O(1) です。辞書の出し入れは平均 O(1)、並びの末尾に足す、末尾を取り除く、番号で引く、はどれも O(1) です
使う記憶は、入っている値の数を n として O(n) です。並びと辞書に 1 つずつ持ちます
並びの途中を抜いて詰める書き方だと remove は O(n) です。末尾と入れ替えることで、並びの順を捨てる代わりに O(1) にしています。この集合は順を約束しないので、捨ててかまいません

よくある間違い

末尾を移したあと、移した値の番号を辞書に書き直さない。辞書は古い末尾の番号を指したままになり、その値を次に取り除くとき、並びの外か別の値の位置を消します。例 3 で 3 を取り除くところが壊れます
取り除く値が末尾だったときを考えない。辞書から先に消し、そのあと分けずに「末尾を i へ移して番号を書く」と、末尾の値は取り除く値そのものなので、消したはずの値が辞書に戻ります。次の insert で偽が返り、足せなくなります。末尾より前のときだけ移すか、番号の書き直しを先にして辞書から消すのを後にします
乱数の番号の範囲を 1 つずらす。並びの長さを n として、番号は 0 以上 n 未満です。Math.floor(Math.random() * (n - 1)) のように書くと、末尾の値が選ばれなくなり、確率が同じになりません

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

class RandomSet: def __init__(self): # ここに持つ物を書きます pass def insert(self, val): # ここに書きます pass def remove(self, val): # ここに書きます pass def get_random(self): # ここに書きます pass # 「実行」を押すと、下の行が動きます obj = RandomSet() print(obj.insert(4))

辞書と並びを組み合わせて O(1) で出し入れと無作為な取り出しができる集合を作る

問題