O(1) ekleme, silme ve rastgele eleman

Problem

Tamsayılar için bir küme sınıfı yaz:

• insert(val): değer yoksa ekler ve true döner; varsa false.
• remove(val): değer varsa siler ve true döner; yoksa false.
• getRandom(): kümedeki elemanlardan birini eşit olasılıkla döndürür (çağrıldığında küme boş değildir).

Üç işlem de ortalama O(1) olmalı.

insert(5)    -> true
insert(5)    -> false
remove(7)    -> false
getRandom()  -> 5
insert(7)    -> true
remove(5)    -> true
getRandom()  -> 7

Netleştirme soruları

• getRandom boş kümede çağrılabilir mi? (LeetCode'da hayır; production'da exception ya da OptionalInt.)
• "Eşit olasılık" tam olarak uniform mu? Testte rastgeleliği nasıl doğrulayacağız? (Seed enjekte edilebilir olmalı.)
• Tekrar eden değerlere izin var mı? (Hayır; izin olsaydı LeetCode 381 olurdu.)
• Thread-safe olmalı mı?
• O(1) ortalama mı, en kötü durum mu? (Ortalama; HashMap en kötü durumda O(1) değildir.)

İpuçları

Yaklaşım

Neden tek yapı yetmez:

ArrayList + HashMap (seçilen çözüm): Liste elemanları yoğun bir dizide tutar (rastgele indeks için), map her değerin listedeki indeksini tutar (O(1) arama için).

• insert: map'te varsa false; yoksa sona ekle, indeksini map'e yaz.
• remove: indeksi map'ten al. Son elemanı o indekse yaz ve son elemanın map girdisini güncelle (swap-remove). Sonra listenin sonunu sil. Sıra bozulur, ama küme için sıranın önemi yok.
• getRandom: values.get(random.nextInt(size)). Liste boşluksuz olduğu için her eleman eşit olasılıklıdır.

Neden uniform? Liste her zaman tam olarak kümedeki n elemanı, boşluksuz içerir; nextInt(n) her indeksi 1/n olasılıkla seçer. "Silinenleri işaretle, getRandom'da işaretliyse tekrar dene" yaklaşımı da uniformdur ama çok silme sonrası beklenen süre bozulur.

Java çözümü

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;

public final class RandomizedSet {

    private final List<Integer> values = new ArrayList<>();          // rastgele erişim için yoğun dizi
    private final Map<Integer, Integer> indexOf = new HashMap<>();   // değer -> values içindeki indeks
    private final Random random;

    public RandomizedSet() { this(new Random()); }

    RandomizedSet(Random random) { this.random = random; }           // testte seed'li Random

    public boolean insert(int val) {
        if (indexOf.containsKey(val)) return false;
        indexOf.put(val, values.size());
        values.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer idx = indexOf.remove(val);
        if (idx == null) return false;
        int lastIdx = values.size() - 1;
        int last = values.get(lastIdx);
        if (idx != lastIdx) {                             // silineni sonuncuyla değiştir (swap-remove)
            values.set(idx, last);
            indexOf.put(last, idx);
        }
        values.remove(lastIdx);                           // sondan silmek O(1)
        return true;
    }

    public int getRandom() {
        if (values.isEmpty()) throw new NoSuchElementException("set is empty");
        return values.get(random.nextInt(values.size()));
    }
}

Java'ya özgü iki tuzak:

1. List<Integer>.remove(...): values.remove(lastIdx) burada int ile çağrıldığı için indeksle silme yapar (doğru olan). values.remove(val) yazılsaydı val indeks olarak yorumlanırdı; values.remove(Integer.valueOf(val)) ise değeri arayıp O(n)'de silerdi.
2. Integer idx ile int lastIdx karşılaştırması: idx != lastIdx ifadesinde idx unboxing'e uğrar ve değer karşılaştırılır. İki Integer nesnesini != ile karşılaştırmak ise referans karşılaştırmasıdır ve -128..127 aralığı dışında yanlış sonuç verir.

Random'ın constructor ile enjekte edilmesi testte seed vermeyi sağlar. Eşzamanlı kullanımda paylaşılan bir Random contention yaratır; ThreadLocalRandom.current() tercih edilir.

Karmaşıklık

• Zaman: insert amortize O(1) (ArrayList büyümesi + HashMap ortalama), remove ortalama O(1), getRandom O(1).
• Bellek: O(n); liste ve map.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Tekrar ekleme false; olmayanı silme false.
• Tek elemanlı kümede getRandom.
• İlk elemanı silmek (sonuncuyla takas) ve son elemanın kendisini silmek (takas gereksiz; idx == lastIdx dalı).
• Boş kümede getRandom: NoSuchElementException.
• Negatif ve büyük değerler (-3, 1000): indeks/değer karışıklığı yok.
• 20.000 rastgele işlem HashSet referansıyla karşılaştırıldı; getRandom her zaman kümede olan bir değer döndürdü.
• Uniformluk: 8 elemanlı kümede (iki silme sonrası) 800.000 getRandom çağrısında her değerin frekansı beklenen değerin %2'si içinde kaldı.

Rastgele davranışı test etmenin iki yolu: seed sabitleyip deterministik çıktıyı kontrol etmek, ya da çok sayıda örnekle dağılımı istatistiksel toleransla kontrol etmek. İkincisi daha anlamlıdır ama tolerans çok dar seçilirse flaky olur.

Mülakatçı için

Bu soru iki yapıyı birleştirme becerisini ölçer (LRU ile aynı ruhta). Gözlemle: swap-remove fikrine kendisi ulaşıyor mu? Son elemanın map indeksini güncelliyor mu? Silinen eleman zaten sondaysa ne olduğunu düşünüyor mu (sıralama hatası: önce map'i güncelleyip sonra silinen anahtarı map'ten kaldırmak, son eleman kendisiyse onu yanlışlıkla siler)? Java'da remove(int) ile remove(Object) farkını biliyor mu?

İpucu zamanlaması: Aday HashSet ile getRandom'u O(n) yapıp durursa ilk ipucunu ver. Liste fikrine ulaşıp ortadan silmede takılırsa ikinci ipucunu ver. Üçüncü ipucundaki "son eleman kendisiyse" uyarısını vermek yerine testi adaydan iste.

Takip sorusu 1: Tekrar eden değerlere izin ver (multiset); getRandom her kopyayı eşit olasılıkla seçsin. Beklenen: map'in değeri indeks kümesi (Map<Integer, Set<Integer>>); swap-remove sırasında taşınan son elemanın indeks kümesini güncellemek (LeetCode 381).

Takip sorusu 2: Ağırlıklı rastgele seçim: her değerin bir ağırlığı var. Beklenen: statik küme için prefix toplam + binary search, O(log n) (LeetCode 528); dinamik için Fenwick ağacı; O(1) için alias method (ön işleme O(n)).

Takip sorusu 3: Bunu bir A/B test servisinde kullanıcıyı rastgele varyanta atamak için mi kullanırsın? Beklenen: Hayır. Atama deterministik olmalı (aynı kullanıcı her istekte aynı varyantı görmeli); hash(userId + experimentId) % 100 gibi tutarlı hashleme kullanılır. Rastgelelik ile deterministik dağıtım arasındaki farkı görmek senior sinyalidir.

Benzer problemler

• Insert Delete GetRandom O(1) - Duplicates allowed (LeetCode 381)
• Random Pick with Weight (LeetCode 528)
• LRU Cache (LeetCode 146)
• Design HashSet (LeetCode 705)
• Random Pick with Blacklist (LeetCode 710)