Bir röportajda bu sorunun verildi. Nasıl cevap verir miydin?

O(1) süre: aşağıdaki işlemleri sunan bir veri yapısı tasarımı

• Ekle
• Kaldır
• içerir
• rastgele bir eleman olsun

Veri yapısı karma tablo bir H oluşan ve karma tablo anahtarları veri yapısındaki elemanları bir dizi A. düşünün, ve değerleri dizideki konumları.

1. Ekle(değer): diziye değer eklemek ve ben A. Set H[değer]=ı. endeks olalım
2. Kaldır(Değer): Değer endeksi de A. d son elemanı dizinin son elemanı olarak ile Bir m. içeren hücreyi değiştirmek için gidiyoruz H[değer], kaldırılacak değeri dizideki endeksi de buna izin verdim. Bir dizi[i]=d, H[d]=ben, bir dizinin boyutunu azaltmak ve H. değer çıkarın
3. (değer) içerir: iade H. içerir(değer)
4. () getRandomElement: r=random(mevcut boyut). [r] dönüş.

dizi otomatik artış boyutu gerekir, çünkü, O(1) bir öğe eklemek için amorti olacak, ama bu sorun değil sanırım.