Struktura danych: wstaw, usuń, zawiera, pobierz element losowy, wszystko w O (1)

Przedstawiono mi ten problem w wywiadzie. Jak byś odpowiedział?

Zaprojektuj strukturę danych, która oferuje następujące operacje w czasie O (1):

• wstawić
• usunąć
• zawiera
• uzyskać element losowy

Rozważmy strukturę danych składającą się z tablicy hashy H i tablicy A. Klucze tablicy hashy to elementy struktury danych, a wartości to ich pozycje w tablicy.

1. insert (wartość): dołącz wartość do tablicy i niech i będzie jej indeksem w A. Ustaw H [wartość] = i.
2. remove (value): Zamierzamy zastąpić komórkę zawierającą wartość w A ostatnim elementem z A. niech d będzie ostatnim elementem tablicy A pod indeksem m. niech będę H [wartość], indeks w tablicy wartości do usunięcia. Ustaw A [i] = d, H [d] = i, zmniejsz rozmiar tablicy o jeden i usuń wartość z H.
3. zawiera (wartość): zwraca H.contains (wartość)
4. getRandomElement (): let r = random (aktualny rozmiar A). powrót A [r].

ponieważ tablica musi automatycznie zwiększyć rozmiar, będzie amortyzowana O (1), aby dodać element, ale myślę, że to jest OK.

Wyszukiwanie O (1) implikuje zakodowaną strukturę danych .

W stosunku:

• O (1) wstawianie / usuwanie za pomocą wyszukiwania O (N) implikuje połączoną listę.
• O (1) wstawianie, O (N) usuwanie i wyszukiwanie O (N) implikuje listę opartą na tablicy
• O (logN) wstawianie / usuwanie / wyszukiwanie oznacza drzewo lub stertę.

Może ci się to nie podobać, ponieważ prawdopodobnie szukają sprytnego rozwiązania, ale czasami opłaca się trzymać się swoich pistoletów ... Tabela haszująca już spełnia wymagania - prawdopodobnie ogólnie lepiej niż cokolwiek innego (choć oczywiście w stałej amortyzowanej czas iz różnymi kompromisami do innych rozwiązań).

Podchwytliwym wymaganiem jest wybór „elementu losowego”: w tablicy haszującej musiałbyś przeskanować lub sondować taki element.

W przypadku adresowania zamkniętego / otwartego prawdopodobieństwo zajętości dowolnego zasobnika jest size() / capacity(), ale co najważniejsze, jest to zazwyczaj utrzymywane w stałym zakresie mnożenia przez implementację tablicy mieszającej (np. Tabela może być utrzymywana jako większa niż jej obecna zawartość, powiedzmy 1,2x do ~ 10x w zależności od wydajności / dostrojenia pamięci). Oznacza to, że średnio możemy spodziewać się przeszukiwania od 1,2 do 10 wiader - całkowicie niezależnie od całkowitej wielkości kontenera; amortyzowane O (1).

Mogę sobie wyobrazić dwa proste podejścia (i wiele bardziej skomplikowanych):

• szukaj liniowo z losowego zasobnika

  • rozważyć pusty / wartość trzymając wiadra ala „--AC ----- B - D”: Państwo może powiedzieć, że pierwszy „random” wybór jest sprawiedliwy, chociaż preferuje B, B, ponieważ nie miał więcej prawdopodobieństwo zostania uprzywilejowanych niż inne elementy, ale jeśli wykonujesz powtarzające się „losowe” wybory przy użyciu tych samych wartości, to jednoznaczne wielokrotne faworyzowanie B może być niepożądane (nic w pytaniu nie wymaga jednak nawet prawdopodobieństwa)

• wypróbuj losowe zasobniki wielokrotnie, aż znajdziesz wypełniony

  • „tylko” pojemność () / rozmiar () przeciętne odwiedzone segmenty (jak wyżej) - ale w praktyce droższe, ponieważ generowanie liczb losowych jest stosunkowo drogie i nieskończenie złe, jeśli nieskończenie nieprawdopodobne najgorsze zachowanie ...
    • szybszym kompromisem byłoby użycie listy wstępnie wygenerowanych losowych przesunięć z początkowego losowo wybranego segmentu,% -owanie ich w liczbie segmentów

Nie jest to świetne rozwiązanie, ale nadal może być lepszym ogólnym kompromisem niż narzuty dotyczące pamięci i wydajności związane z utrzymywaniem przez cały czas drugiej tablicy indeksów.

Najlepszym rozwiązaniem jest prawdopodobnie tablica mieszająca + tablica, jest to naprawdę szybkie i deterministyczne.

Ale najniżej oceniona odpowiedź (po prostu użyj tabeli skrótów!) Jest w rzeczywistości świetna!

• tabela mieszająca z ponownym haszowaniem lub nowym wyborem zasobnika (tj. jeden element na zasobnik, brak połączonych list)
• getRandom () wielokrotnie próbuje wybrać losowy zasobnik, dopóki nie zostanie on pusty.
• jako fail-safe, być może getRandom (), po N (liczba elementów) nieudanych próbach, wybiera losowy indeks i w [0, N-1], a następnie przechodzi liniowo przez tablicę haszującą i wybiera # i-ty element .

Ludziom może się to nie podobać z powodu „możliwych nieskończonych pętli” i widziałem, jak bardzo mądrzy ludzie też mają taką reakcję, ale to źle! Nieskończenie nieprawdopodobne wydarzenia po prostu się nie zdarzają.

Zakładając dobre zachowanie twojego pseudolosowego źródła - co nie jest trudne do ustalenia dla tego konkretnego zachowania - i że tabele skrótów są zawsze zapełnione w co najmniej 20%, łatwo zauważyć, że:

Nigdy się nie zdarzy, że getRandom () będzie musiało wykonać więcej niż 1000 razy. Po prostu nigdy . Rzeczywiście, prawdopodobieństwo takiego zdarzenia wynosi 0,8 ^ 1000, czyli 10 ^ -97 - więc musielibyśmy powtórzyć je 10 ^ 88 razy, aby mieć jedną szansę na miliard, że kiedykolwiek się wydarzy. Nawet jeśli ten program działał w pełnym wymiarze godzin na wszystkich komputerach ludzkości aż do śmierci Słońca, to się nigdy nie wydarzy.

W tym pytaniu użyję dwóch struktur danych

• HashMap
• ArrayList / Array / Double LinkedList.

Kroki :-

1. Wstawianie: - Sprawdź, czy X jest już obecny w HashMap - Złożoność czasu O (1). jeśli nie jest obecny Następnie dodaj na końcu ArrayList - złożoność czasowa O (1). dodaj go w HashMap również x jako klucz i ostatni indeks jako wartość - Złożoność czasowa O (1).
2. Usuń: - Sprawdź, czy X jest obecny w HashMap - złożoność czasu O (1). Jeśli jest obecny, znajdź jego indeks i usuń go z HashMap - złożoność czasu O (1). zamień ten element na ostatni element w ArrayList i usuń ostatni element --Time złożoność O (1). Zaktualizuj indeks ostatniego elementu w HashMap - złożoność czasu O (1).
3. GetRandom: - Generuj liczbę losową od 0 do ostatniego indeksu ArrayList. zwraca element ArrayList w wygenerowanym losowym indeksie - złożoność czasu O (1).
4. Szukaj: - Zobacz w HashMap dla x jako klucz. - Złożoność czasowa O (1).

Kod :-

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;

            }
        }
    }

}

- Złożoność czasowa O (1). - Złożoność przestrzeni O (N).

Oto rozwiązanie C # tego problemu, które wymyśliłem jakiś czas temu, gdy zadałem to samo pytanie. Implementuje Add, Remove, Contains i Random wraz z innymi standardowymi interfejsami .NET. Nie żebyś kiedykolwiek musiał wdrażać to tak szczegółowo podczas rozmowy kwalifikacyjnej, ale miło jest mieć konkretne rozwiązanie, na które warto spojrzeć ...

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;

        }
    }
}

Możemy użyć hashowania do obsługi operacji w czasie Θ (1).

insert (x) 1) Sprawdź, czy x jest już obecne, wykonując wyszukiwanie mapy hash. 2) Jeśli nie ma, włóż go na koniec tablicy. 3) Dodaj również tablicę skrótów, x jest dodawany jako klucz i ostatni indeks tablicy jako indeks.

remove (x) 1) Sprawdź, czy x jest obecne, wykonując wyszukiwanie mapy hash. 2) Jeśli jest obecny, znajdź jego indeks i usuń go z mapy skrótów. 3) Zamień ostatni element na ten element w tablicy i usuń ostatni element. Zamiana jest wykonywana, ponieważ ostatni element można usunąć w czasie O (1). 4) Zaktualizuj indeks ostatniego elementu w mapie skrótów.

getRandom () 1) Generuje liczbę losową od 0 do ostatniego indeksu. 2) Zwróć element tablicy do losowo wygenerowanego indeksu.

search (x) Wyszukaj x na mapie skrótów.

Chociaż to już dawno, ale ponieważ nie ma odpowiedzi w C ++, oto moje dwa centy.

#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<<" ";
        }
    }
};

Oto fragment kodu klienta do testowania rozwiązania.

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;
}

W C # 3.0 + .NET Framework 4 generic Dictionary<TKey,TValue>jest nawet lepszy niż Hashtable, ponieważ można użyć System.Linqmetody rozszerzenia ElementAt()do indeksowania podstawowej tablicy dynamicznej, w której KeyValuePair<TKey,TValue>są przechowywane elementy:

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;
}

Jednak, o ile wiem, Hashtable (lub jego potomstwo Dictionary) nie jest prawdziwym rozwiązaniem tego problemu, ponieważ Put () można zamortyzować tylko O ​​(1), a nie O (1), ponieważ jest O (N) ) na granicy dynamicznej zmiany rozmiaru.

Czy istnieje prawdziwe rozwiązanie tego problemu? Wszystko, co przychodzi mi do głowy, to to, że jeśli określisz początkową pojemność Dictionary / Hashtable o rząd wielkości przekraczającą to, czego spodziewasz się kiedykolwiek potrzebować, otrzymasz operacje O (1), ponieważ nigdy nie musisz zmieniać rozmiaru.

Zgadzam się z Anonem. Z wyjątkiem ostatniego wymogu, w którym wymagane jest uzyskanie elementu losowego o jednakowej uczciwości, wszystkie inne wymagania można rozwiązać tylko za pomocą pojedynczego DS opartego na hash. W tym celu wybiorę HashSet w Javie. Modulo kodu skrótu elementu da mi numer indeksu tablicy bazowej w czasie O (1). Mogę tego użyć do operacji dodawania, usuwania i zawierania.

Czy nie możemy tego zrobić za pomocą HashSet of Java? Domyślnie zapewnia insert, del, search all in O (1). Dla getRandom możemy skorzystać z iteratora Set, który i tak daje losowe zachowanie. Możemy po prostu iterować pierwszy element z zestawu, nie martwiąc się o resztę elementów

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`
    }
}

Dlaczego nie użyjemy epoch% arraysize do znalezienia losowego elementu. Znalezienie rozmiaru tablicy to O (n), ale zamortyzowana złożoność wyniesie O (1).

Myślę, że możemy użyć podwójnej listy linków z tabelą skrótów. klucz będzie elementem, a skojarzona z nim wartość będzie węzłem w podwójnej liście dowiązań.

1. insert (H, E): wstaw węzeł na podwójnie linklist i wprowadź jako H [E] = node; O (1)
2. delete (H, E): pobierz adres węzła przez H (E), przejdź do poprzedniego węzła i usuń i ustaw H (E) na NULL, więc O (1)
3. zawiera (H, E) i getRandom (H) są oczywiście O (1)