Struktur data: masukkan, hapus, isi, dapatkan elemen acak, semuanya di O (1)

Saya diberi masalah ini dalam sebuah wawancara. Bagaimana Anda akan menjawabnya?

Rancang struktur data yang menawarkan operasi berikut dalam waktu O (1):

• memasukkan
• menghapus
• mengandung
• dapatkan elemen acak

Pertimbangkan struktur data yang terdiri dari hashtable H dan array A. Kunci hashtable adalah elemen dalam struktur data, dan nilainya adalah posisinya dalam array.

1. masukkan (nilai): tambahkan nilai ke array dan biarkan i menjadi indeksnya di A. Set H [nilai] = i.
2. hapus (nilai): Kami akan mengganti sel yang berisi nilai di A dengan elemen terakhir di A. biarkan d menjadi elemen terakhir dalam larik A pada indeks m. biarkan saya menjadi H [nilai], indeks dalam array nilai yang akan dihapus. Set A [i] = d, H [d] = i, kurangi ukuran array satu, dan hapus nilai dari H.
3. berisi (nilai): mengembalikan H. berisi (nilai)
4. getRandomElement (): misalkan r = random (ukuran A saat ini). mengembalikan A [r].

karena array perlu bertambah besar secara otomatis, itu akan diamortisasi O (1) untuk menambahkan elemen, tapi saya rasa tidak apa-apa.

Pencarian O (1) menyiratkan struktur data berciri .

Dengan perbandingan:

• O (1) sisipkan / hapus dengan O (N) pencarian menyiratkan daftar tertaut.
• O (1) insert, O (N) delete, dan O (N) lookup menyiratkan daftar yang didukung array
• O (logN) menyisipkan / menghapus / pencarian menyiratkan pohon atau tumpukan.

Anda mungkin tidak menyukai ini, karena mereka mungkin mencari solusi yang cerdas, tetapi kadang-kadang membayar untuk tetap berpegang pada keinginan Anda ... Tabel hash sudah memenuhi persyaratan - mungkin secara keseluruhan lebih baik daripada yang lain (meskipun jelas dalam konstanta diamortisasi waktu, dan dengan kompromi yang berbeda dengan solusi lain).

Persyaratan yang rumit adalah pemilihan "elemen acak": dalam tabel hash, Anda perlu memindai atau menyelidiki elemen semacam itu.

Untuk pencirian tertutup / pengalamatan terbuka, kemungkinan setiap bucket ditempati adalah size() / capacity(), tetapi yang terpenting ini biasanya disimpan dalam kisaran perkalian konstan dengan implementasi tabel hash (misalnya tabel dapat disimpan lebih besar dari isinya saat ini dengan katakanlah 1.2x hingga ~ 10x tergantung pada kinerja / penyetelan memori). Ini berarti rata-rata kami dapat mencari 1,2 hingga 10 ember - benar-benar tidak tergantung pada ukuran total wadah; diamortisasi O (1).

Saya bisa membayangkan dua pendekatan sederhana (dan lebih banyak lagi pendekatan fiddly):

• telusuri secara linier dari keranjang acak

  • pertimbangkan keranjang kosong / penahan nilai ala "--AC ----- B - D": Anda dapat mengatakan bahwa pilihan "acak" pertama adil meskipun memilih B, karena B tidak memiliki kemungkinan lebih disukai daripada elemen lainnya, tetapi jika Anda melakukan pemilihan "acak" berulang menggunakan nilai yang sama maka secara jelas memilih B berulang kali mungkin tidak diinginkan (meskipun pertanyaan tidak menuntut bahkan probabilitas)

• coba keranjang acak berulang kali sampai Anda menemukan yang terisi

  • "hanya" kapasitas () / ukuran () keranjang rata-rata yang dikunjungi (seperti di atas) - tetapi dalam istilah praktis lebih mahal karena pembuatan bilangan acak relatif mahal, dan sangat buruk jika perilaku kasus terburuknya sangat mustahil ...
    • kompromi yang lebih cepat adalah menggunakan daftar offset acak yang dibuat sebelumnya dari keranjang awal yang dipilih secara acak,% memasukkannya ke dalam jumlah keranjang

Bukan solusi yang hebat, tetapi mungkin masih merupakan kompromi keseluruhan yang lebih baik daripada overhead memori dan kinerja untuk mempertahankan array indeks kedua setiap saat.

Solusi terbaik mungkin adalah tabel hash + array, ini sangat cepat dan deterministik.

Tetapi jawaban dengan peringkat terendah (cukup gunakan tabel hash!) Sebenarnya bagus juga!

• tabel hash dengan hashing ulang, atau pilihan keranjang baru (yaitu satu elemen per keranjang, tidak ada daftar tertaut)
• getRandom () berulang kali mencoba memilih keranjang acak hingga kosong.
• sebagai pengaman dari kegagalan, mungkin getRandom (), setelah N (jumlah elemen) percobaan yang gagal, mengambil indeks acak i di [0, N-1] dan kemudian menelusuri tabel hash secara linier dan mengambil elemen ke-i .

Orang-orang mungkin tidak menyukai ini karena "kemungkinan putaran tak terbatas", dan saya telah melihat orang yang sangat pintar mengalami reaksi ini juga, tapi itu salah! Peristiwa yang sangat tidak mungkin tidak terjadi begitu saja.

Dengan asumsi perilaku baik dari sumber pseudo-random Anda - yang tidak sulit dibuat untuk perilaku khusus ini - dan tabel hash selalu setidaknya 20% penuh, mudah untuk melihat bahwa:

Tidak akan pernah terjadi jika getRandom () harus mencoba lebih dari 1000 kali. Tidak pernah . Memang, kemungkinan kejadian seperti itu adalah 0,8 ^ 1000, yaitu 10 ^ -97 - jadi kita harus mengulanginya 10 ^ 88 kali agar satu peluang dari satu miliar kejadian itu pernah terjadi sekali. Bahkan jika program ini berjalan penuh waktu di semua komputer manusia sampai Matahari mati, ini tidak akan pernah terjadi.

Untuk Pertanyaan ini saya akan menggunakan dua Struktur Data

• HashMap
• ArrayList / Array / Double LinkedList.

Langkah :-

1. Penyisipan: - Periksa apakah X sudah ada di HashMap --Kompleksitas waktu O (1). jika tidak Hadir Kemudian Tambahkan di akhir ArrayList - Kompleksitas waktu O (1). tambahkan di HashMap juga x sebagai kunci dan Indeks terakhir sebagai nilai - Kompleksitas waktu O (1).
2. Hapus: - Periksa apakah X ada di HashMap --Kompleksitas waktu O (1). Jika ada, temukan indeksnya dan hapus dari HashMap --Kompleksitas waktu O (1). tukar elemen ini dengan elemen terakhir di ArrayList dan hapus elemen terakhir --Kompleksitas waktu O (1). Perbarui indeks Elemen terakhir di HashMap --Kompleksitas waktu O (1).
3. GetRandom: - Menghasilkan nomor acak dari 0 hingga indeks terakhir ArrayList. mengembalikan elemen ArrayList pada indeks acak yang dihasilkan --Kompleksitas waktu O (1).
4. Cari: - Lihat di HashMap untuk x sebagai kunci. --Kompleksitas waktu O (1).

Kode: -

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;


public class JavaApplication1 {

    public static void main(String args[]){
       Scanner sc = new Scanner(System.in);
        ArrayList<Integer> al =new ArrayList<Integer>();
        HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();  
        while(true){
            System.out.println("**menu**");
            System.out.println("1.insert");
            System.out.println("2.remove");
            System.out.println("3.search");
            System.out.println("4.rendom");
            int ch = sc.nextInt();
            switch(ch){
                case 1 : System.out.println("Enter the Element ");
                        int a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println("Element is already present ");
                        }
                        else{
                            al.add(a);
                            mp.put(a, al.size()-1);

                        }
                        break;
                case 2 : System.out.println("Enter the Element Which u want to remove");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){

                            int size = al.size();
                            int index = mp.get(a);

                            int last = al.get(size-1);
                            Collections.swap(al, index,  size-1);

                            al.remove(size-1);
                            mp.put(last, index);

                            System.out.println("Data Deleted");

                        }
                        else{
                            System.out.println("Data Not found");
                        }
                        break;
                case 3 : System.out.println("Enter the Element to Search");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println(mp.get(a));
                        }
                        else{
                            System.out.println("Data Not Found");
                        }
                        break;
                case 4 : Random rm = new Random();
                        int index = rm.nextInt(al.size());
                        System.out.println(al.get(index));
                        break;

            }
        }
    }

}

- Kompleksitas waktu O (1). - Kompleksitas ruang O (N).

Berikut adalah solusi C # untuk masalah yang saya munculkan beberapa waktu lalu ketika ditanya pertanyaan yang sama. Ini mengimplementasikan Tambah, Hapus, Berisi, dan Acak bersama dengan antarmuka .NET standar lainnya. Bukan berarti Anda perlu menerapkannya secara detail selama wawancara tetapi senang memiliki solusi konkret untuk dilihat ...

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

/// <summary>
/// This class represents an unordered bag of items with the
/// the capability to get a random item.  All operations are O(1).
/// </summary>
/// <typeparam name="T">The type of the item.</typeparam>
public class Bag<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable
{
    private Dictionary<T, int> index;
    private List<T> items;
    private Random rand;
    private object syncRoot;

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    public Bag()
        : this(0)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="capacity">The capacity.</param>
    public Bag(int capacity)
    {
        this.index = new Dictionary<T, int>(capacity);
        this.items = new List<T>(capacity);
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="collection">The collection.</param>
    public Bag(IEnumerable<T> collection)
    {
        this.items = new List<T>(collection);
        this.index = this.items
            .Select((value, index) => new { value, index })
            .ToDictionary(pair => pair.value, pair => pair.index);
    }

    /// <summary>
    /// Get random item from bag.
    /// </summary>
    /// <returns>Random item from bag.</returns>
    /// <exception cref="System.InvalidOperationException">
    /// The bag is empty.
    /// </exception>
    public T Random()
    {
        if (this.items.Count == 0)
        {
            throw new InvalidOperationException();
        }

        if (this.rand == null)
        {
            this.rand = new Random();
        }

        int randomIndex = this.rand.Next(0, this.items.Count);
        return this.items[randomIndex];
    }

    /// <summary>
    /// Adds the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    public void Add(T item)
    {
        this.index.Add(item, this.items.Count);
        this.items.Add(item);
    }

    /// <summary>
    /// Removes the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns></returns>
    public bool Remove(T item)
    {
        // Replace index of value to remove with last item in values list
        int keyIndex = this.index[item];
        T lastItem = this.items[this.items.Count - 1];
        this.items[keyIndex] = lastItem;

        // Update index in dictionary for last item that was just moved
        this.index[lastItem] = keyIndex;

        // Remove old value
        this.index.Remove(item);
        this.items.RemoveAt(this.items.Count - 1);

        return true;
    }

    /// <inheritdoc />
    public bool Contains(T item)
    {
        return this.index.ContainsKey(item);
    }

    /// <inheritdoc />
    public void Clear()
    {
        this.index.Clear();
        this.items.Clear();
    }

    /// <inheritdoc />
    public int Count
    {
        get { return this.items.Count; }
    }

    /// <inheritdoc />
    public void CopyTo(T[] array, int arrayIndex)
    {
        this.items.CopyTo(array, arrayIndex);
    }

    /// <inheritdoc />
    public bool IsReadOnly
    {
        get { return false; }
    }

    /// <inheritdoc />
    public IEnumerator<T> GetEnumerator()
    {
        foreach (var value in this.items)
        {
            yield return value;
        }
    }

    /// <inheritdoc />
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    /// <inheritdoc />
    public void CopyTo(Array array, int index)
    {
        this.CopyTo(array as T[], index);
    }

    /// <inheritdoc />
    public bool IsSynchronized
    {
        get { return false; }
    }

    /// <inheritdoc />
    public object SyncRoot
    {
        get
        {
            if (this.syncRoot == null)
            {
                Interlocked.CompareExchange<object>(
                    ref this.syncRoot,
                    new object(),
                    null);
            }

            return this.syncRoot;

        }
    }
}

Kita dapat menggunakan hashing untuk mendukung operasi dalam waktu Θ (1).

insert (x) 1) Periksa apakah x sudah ada dengan melakukan pencarian peta hash. 2) Jika tidak ada, masukkan di akhir larik. 3) Tambahkan juga tabel hash, x ditambahkan sebagai kunci dan indeks array terakhir sebagai indeks.

hapus (x) 1) Periksa apakah x ada dengan melakukan pencarian peta hash. 2) Jika ada, temukan indeksnya dan hapus dari peta hash. 3) Tukar elemen terakhir dengan elemen ini dalam array dan hapus elemen terakhir. Swapping dilakukan karena elemen terakhir dapat dihilangkan dalam waktu O (1). 4) Perbarui indeks elemen terakhir di peta hash.

getRandom () 1) Menghasilkan nomor acak dari 0 hingga indeks terakhir. 2) Kembalikan elemen array pada indeks yang dibuat secara acak.

search (x) Lakukan pencarian untuk x di peta hash.

Meskipun ini jauh lebih tua, tetapi karena tidak ada jawaban di C ++, inilah dua sen saya.

#include <vector>
#include <unordered_map>
#include <stdlib.h>

template <typename T> class bucket{
    int size;
    std::vector<T> v;
    std::unordered_map<T, int> m;
public:
    bucket(){
        size = 0;
        std::vector<T>* v = new std::vector<T>();
        std::unordered_map<T, int>* m = new std::unordered_map<T, int>();
    }
    void insert(const T& item){
        //prevent insertion of duplicates
        if(m.find(item) != m.end()){
            exit(-1);
        }
        v.push_back(item);
        m.emplace(item, size);
        size++;

    }
    void remove(const T& item){
        //exits if the item is not present in the list
        if(m[item] == -1){
            exit(-1);
        }else if(m.find(item) == m.end()){
            exit(-1);
        }

        int idx = m[item];
        m[v.back()] = idx;
        T itm = v[idx];
        v.insert(v.begin()+idx, v.back());
        v.erase(v.begin()+idx+1);
        v.insert(v.begin()+size, itm);
        v.erase(v.begin()+size);
        m[item] = -1;
        v.pop_back();
        size--;

    }

     T& getRandom(){
      int idx = rand()%size;
      return v[idx];

     }

     bool lookup(const T& item){
       if(m.find(item) == m.end()) return false;
       return true;

     }
    //method to check that remove has worked
    void print(){
        for(auto it = v.begin(); it != v.end(); it++){
            std::cout<<*it<<" ";
        }
    }
};

Berikut adalah kode klien untuk menguji solusinya.

int main() {

    bucket<char>* b = new bucket<char>();
    b->insert('d');
    b->insert('k');
    b->insert('l');
    b->insert('h');
    b->insert('j');
    b->insert('z');
    b->insert('p');

    std::cout<<b->random()<<std::endl;
    b->print();
    std::cout<<std::endl;
    b->remove('h');
    b->print();

    return 0;
}

Di C # 3.0 + .NET Framework 4, generik Dictionary<TKey,TValue>bahkan lebih baik daripada Hashtable karena Anda dapat menggunakan System.Linqmetode ekstensi ElementAt()untuk mengindeks ke dalam array dinamis yang mendasari tempat KeyValuePair<TKey,TValue>elemen disimpan:

using System.Linq;

Random _generator = new Random((int)DateTime.Now.Ticks);

Dictionary<string,object> _elements = new Dictionary<string,object>();

....

Public object GetRandom()
{
     return _elements.ElementAt(_generator.Next(_elements.Count)).Value;
}

Namun, sejauh yang saya tahu, Hashtable (atau keturunan Dictionary-nya) bukanlah solusi nyata untuk masalah ini karena Put () hanya dapat diamortisasi O (1), bukan O (1) yang sebenarnya, karena itu adalah O (N) ) di batas pengubahan ukuran dinamis.

Apakah ada solusi nyata untuk masalah ini? Yang dapat saya pikirkan adalah jika Anda menentukan kapasitas awal Dictionary / Hashtable urutan besarnya melebihi apa yang Anda antisipasi pernah butuhkan, maka Anda mendapatkan operasi O (1) karena Anda tidak perlu mengubah ukuran.

Saya setuju dengan Anon. Kecuali untuk persyaratan terakhir di mana mendapatkan elemen acak dengan keadilan yang sama diperlukan, semua persyaratan lain dapat ditangani hanya dengan menggunakan DS berbasis Hash tunggal. Saya akan memilih HashSet untuk ini di Jawa. Modulo kode hash suatu elemen akan memberi saya indeks no dari array yang mendasari dalam waktu O (1). Saya dapat menggunakannya untuk menambah, menghapus, dan berisi operasi.

Bisakah kita melakukan ini menggunakan HashSet dari Java? Ini menyediakan insert, del, search all in O (1) secara default. Untuk getRandom kita dapat menggunakan iterator dari Set yang memberikan perilaku acak. Kita bisa mengulang elemen pertama dari set tanpa mengkhawatirkan elemen lainnya

public void getRandom(){
    Iterator<integer> sitr = s.iterator();
    Integer x = sitr.next();    
    return x;
}

/* Java program to design a data structure that support folloiwng operations
   in Theta(n) time
   a) Insert
   b) Delete
   c) Search
   d) getRandom */
import java.util.*;

// class to represent the required data structure
class MyDS
{
   ArrayList<Integer> arr;   // A resizable array

   // A hash where keys are array elements and vlaues are
   // indexes in arr[]
   HashMap<Integer, Integer>  hash;

   // Constructor (creates arr[] and hash)
   public MyDS()
   {
       arr = new ArrayList<Integer>();
       hash = new HashMap<Integer, Integer>();
   }

   // A Theta(1) function to add an element to MyDS
   // data structure
   void add(int x)
   {
      // If ekement is already present, then noting to do
      if (hash.get(x) != null)
          return;

      // Else put element at the end of arr[]
      int s = arr.size();
      arr.add(x);

      // And put in hash also
      hash.put(x, s);
   }

   // A Theta(1) function to remove an element from MyDS
   // data structure
   void remove(int x)
   {
       // Check if element is present
       Integer index = hash.get(x);
       if (index == null)
          return;

       // If present, then remove element from hash
       hash.remove(x);

       // Swap element with last element so that remove from
       // arr[] can be done in O(1) time
       int size = arr.size();
       Integer last = arr.get(size-1);
       Collections.swap(arr, index,  size-1);

       // Remove last element (This is O(1))
       arr.remove(size-1);

       // Update hash table for new index of last element
       hash.put(last, index);
    }

    // Returns a random element from MyDS
    int getRandom()
    {
       // Find a random index from 0 to size - 1
       Random rand = new Random();  // Choose a different seed
       int index = rand.nextInt(arr.size());

       // Return element at randomly picked index
       return arr.get(index);
    }

    // Returns index of element if element is present, otherwise null
    Integer search(int x)
    {
       return hash.get(x);
    }
}

// Driver class
class Main
{
    public static void main (String[] args)
    {
        MyDS ds = new MyDS();
        ds.add(10);
        ds.add(20);
        ds.add(30);
        ds.add(40);
        System.out.println(ds.search(30));
        ds.remove(20);
        ds.add(50);
        System.out.println(ds.search(50));
        System.out.println(ds.getRandom());`enter code here`
    }
}

Mengapa kita tidak menggunakan epoch% arraysize untuk menemukan elemen acak. Menemukan ukuran array adalah O (n) tetapi kompleksitas yang diamortisasi akan menjadi O (1).

Saya pikir kita bisa menggunakan daftar tautan ganda dengan tabel hash. key akan menjadi elemen dan nilai yang terkait akan menjadi node di linklist ganda.

1. masukkan (H, E): masukkan node ke dalam daftar link ganda dan buat entri sebagai H [E] = node; O (1)
2. delete (H, E): dapatkan alamat node dengan H (E), goto sebelumnya dari node ini dan hapus dan buat H (E) sebagai NULL, jadi O (1)
3. berisi (H, E) dan getRandom (H) jelas O (1)