Estrutura de dados: inserir, remover, conter, obter elemento aleatório, tudo em O (1)

Esse problema me foi dado em uma entrevista. Como você responderia?

Projete uma estrutura de dados que ofereça as seguintes operações em tempo O (1):

• inserir
• remover
• contém
• obter elemento aleatório

Considere uma estrutura de dados composta de uma hashtable H e um array A. As chaves hashtable são os elementos na estrutura de dados e os valores são suas posições no array.

1. insert (value): acrescenta o valor ao array e seja i seu índice em A. Defina H [value] = i.
2. remove (valor): Vamos substituir a célula que contém o valor em A pelo último elemento em A. seja d o último elemento no array A no índice m. seja i H [valor], o índice na matriz do valor a ser removido. Defina A [i] = d, H [d] = i, diminua o tamanho da matriz em um e remova o valor de H.
3. contém (valor): retorna H.contém (valor)
4. getRandomElement (): deixe r = random (tamanho atual de A). retornar A [r].

como a matriz precisa aumentar automaticamente de tamanho, será amortizado O (1) para adicionar um elemento, mas acho que está tudo bem.

O (1) lookup implica uma estrutura de dados hash .

Por comparação:

• O (1) inserir / excluir com O (N) pesquisa implica em uma lista vinculada.
• O (1) inserção, O (N) exclusão e O (N) pesquisa implica em uma lista baseada em matriz
• Inserir / excluir / consultar O (logN) implica uma árvore ou heap.

Você pode não gostar disso, porque eles provavelmente estão procurando por uma solução inteligente, mas às vezes vale a pena se ater a suas armas ... Uma tabela hash já satisfaz os requisitos - provavelmente melhor do que qualquer outra coisa (embora obviamente em constante amortizada tempo, e com compromissos diferentes para outras soluções).

O requisito que é complicado é a seleção de "elemento aleatório": em uma tabela hash, você precisaria fazer a varredura ou sondar esse elemento.

Para hashing fechado / endereçamento aberto, a chance de qualquer depósito ser ocupado é size() / capacity(), mas crucialmente isso é normalmente mantido em um intervalo multiplicativo constante por uma implementação de tabela hash (por exemplo, a tabela pode ser mantida maior do que seu conteúdo atual, digamos 1,2x para ~ 10x dependendo do desempenho / ajuste de memória). Isso significa que, em média, podemos esperar pesquisar 1,2 a 10 baldes - totalmente independente do tamanho total do contêiner; amortizado O (1).

Posso imaginar duas abordagens simples (e muitas outras muito mais complicadas):

• pesquisar linearmente de um balde aleatório

  • considere baldes vazios / retentores de valor ala "--AC ----- B - D": você pode dizer que a primeira seleção "aleatória" é justa mesmo que favoreça B, porque B não tinha mais probabilidade de ser favorecido do que os outros elementos, mas se você estiver fazendo seleções "aleatórias" repetidas usando os mesmos valores, então claramente ter B repetidamente favorecido pode ser indesejável (nada na questão exige nem mesmo probabilidades)

• tente baldes aleatórios repetidamente até encontrar um preenchido

  • "apenas" capacidade () / tamanho () intervalos médios visitados (como acima) - mas em termos práticos mais caros porque a geração de números aleatórios é relativamente cara e infinitamente ruim, se o pior caso de comportamento infinitamente improvável ...
    • um compromisso mais rápido seria usar uma lista de deslocamentos aleatórios pré-gerados a partir do intervalo inicial selecionado aleatoriamente,% -ing-os na contagem do intervalo

Não é uma ótima solução, mas ainda pode ser um compromisso geral melhor do que as sobrecargas de memória e desempenho de manter um segundo array de índice o tempo todo.

A melhor solução é provavelmente o hash table + array, é bem rápido e determinístico.

Mas a resposta com a pontuação mais baixa (apenas use uma tabela hash!) Também é ótima!

• tabela de hash com re-hashing ou nova seleção de balde (ou seja, um elemento por balde, sem listas vinculadas)
• getRandom () tenta repetidamente escolher um balde aleatório até que esteja vazio.
• como um fail-safe, talvez getRandom (), após N (número de elementos) tentativas malsucedidas, escolhe um índice aleatório i em [0, N-1] e, em seguida, passa pela tabela hash linearmente e escolhe o # i-ésimo elemento .

As pessoas podem não gostar disso por causa de "possíveis loops infinitos", e eu já vi pessoas muito inteligentes terem essa reação também, mas é errado! Eventos infinitamente improváveis ​​simplesmente não acontecem.

Presumindo o bom comportamento de sua fonte pseudo-aleatória - o que não é difícil de estabelecer para este comportamento específico - e que as tabelas hash estão sempre pelo menos 20% cheias, é fácil ver que:

Ele vai não acontecer que getRandom () tem que tentar mais de 1000 vezes. Apenas nunca . Na verdade, a probabilidade de tal evento é 0,8 ^ 1000, que é 10 ^ -97 - então teríamos que repeti-lo 10 ^ 88 vezes para ter uma chance em um bilhão de acontecer uma vez. Mesmo que este programa funcionasse em tempo integral em todos os computadores da humanidade até a morte do Sol, isso nunca acontecerá.

Para esta questão, usarei duas estruturas de dados

• HashMap
• ArrayList / Array / Double LinkedList.

Passos :-

1. Inserção: - Verifique se X já está presente no HashMap --Complexidade de tempo O (1). se não estiver presente, então adicione no final de ArrayList - Complexidade de tempo O (1). adicione-o no HashMap também x como chave e o último índice como valor - Complexidade de tempo O (1).
2. Remover: - Verifique se X está presente no HashMap --Complexidade de tempo O (1). Se estiver presente, encontre seu índice e remova-o do HashMap --Complexidade de tempo O (1). troque este elemento pelo último elemento em ArrayList e remova o último elemento --Complexidade de tempo O (1). Atualize o índice do último elemento no HashMap --Complexidade de tempo O (1).
3. GetRandom: - Gera um número aleatório de 0 ao último índice de ArrayList. retorna o elemento ArrayList no índice aleatório gerado --Complexidade de tempo O (1).
4. Pesquisa: - Veja no HashMap para x como uma chave. --Complexidade de tempo O (1).

Código: -

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;

            }
        }
    }

}

- Complexidade de tempo O (1). - Complexidade do espaço O (N).

Aqui está uma solução em C # para o problema que eu propus há pouco tempo, quando fiz a mesma pergunta. Ele implementa Add, Remove, Contains e Random junto com outras interfaces .NET padrão. Não que você precise implementá-lo com tantos detalhes durante uma entrevista, mas é bom ter uma solução concreta para olhar ...

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;

        }
    }
}

Podemos usar hashing para dar suporte a operações em tempo Θ (1).

insert (x) 1) Verifique se x já está presente fazendo uma pesquisa de mapa hash. 2) Se não estiver presente, insira-o no final da matriz. 3) Adicione também a tabela hash, x é adicionado como chave e o último índice da matriz como índice.

remove (x) 1) Verifique se x está presente fazendo uma pesquisa de mapa hash. 2) Se estiver presente, encontre seu índice e remova-o do mapa hash. 3) Troque o último elemento por este elemento na matriz e remova o último elemento. A troca é feita porque o último elemento pode ser removido no tempo O (1). 4) Atualize o índice do último elemento no mapa hash.

getRandom () 1) Gere um número aleatório de 0 ao último índice. 2) Retorne o elemento da matriz no índice gerado aleatoriamente.

search (x) Faça uma busca por x no mapa hash.

Embora isso seja muito antigo, mas como não há resposta em C ++, aqui estão meus dois centavos.

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

Aqui está uma parte do código do cliente para testar a solução.

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

No C # 3.0 + .NET Framework 4, um genérico Dictionary<TKey,TValue>é ainda melhor do que um Hashtable porque você pode usar o System.Linqmétodo de extensão ElementAt()para indexar na matriz dinâmica subjacente onde os KeyValuePair<TKey,TValue>elementos são armazenados:

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

No entanto, até onde eu sei, uma Hashtable (ou sua progênie de Dicionário) não é uma solução real para este problema porque Put () só pode ser amortizado O (1), não verdadeiro O (1), porque é O (N ) no limite de redimensionamento dinâmico.

Existe uma solução real para este problema? Tudo o que posso pensar é que se você especificar a capacidade inicial de um Dicionário / Hashtable em uma ordem de magnitude além do que você antecipa que vai precisar, então você obtém operações O (1) porque nunca precisa redimensionar.

Eu concordo com Anon. Exceto para o último requisito em que é necessário obter um elemento aleatório com igual justiça, todos os outros requisitos podem ser tratados apenas usando um único DS baseado em Hash. Vou escolher HashSet para isso em Java. O módulo do código hash de um elemento me dará o número do índice da matriz subjacente no tempo O (1). Posso usar isso para adicionar, remover e conter operações.

Não podemos fazer isso usando HashSet de Java? Ele fornece insert, del, search all in O (1) por padrão. Para getRandom, podemos fazer uso do iterador de Set que, de qualquer maneira, fornece comportamento aleatório. Podemos apenas iterar o primeiro elemento do conjunto sem nos preocupar com o resto dos elementos

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

Por que não usamos epoch% arraysize para encontrar o elemento aleatório. Encontrar o tamanho do array é O (n), mas a complexidade amortizada será O (1).

Acho que podemos usar a lista de links duplamente com tabela de hash. a chave será o elemento e seu valor associado será o nó na lista de links dupla.

1. inserir (H, E): inserir nó na lista de links dupla e fazer a entrada como H [E] = nó; O (1)
2. delete (H, E): obtenha o endereço do nó por H (E), vá para anterior deste nó e exclua e torne H (E) como NULL, então O (1)
3. contém (H, E) e getRandom (H) são obviamente O (1)