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

95

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
florim
fonte
Podemos assumir restrições adicionais sobre o tipo de dados? como se não houvesse duplicatas, etc.
Sanjeevakumar Hiremath
Claro, sem duplicatas, você pode até usar estruturas de dados embutidas em uma linguagem como java ou c #.
guilda de
1
Noto que não há especificação referente a: pedido / não pedido
Charles Duffy
7
Eu sei que esta postagem foi respondida, mas para mim faria mais sentido se eles quisessem que você fornecesse o (1) acesso aleatório ao invés de obter um elemento aleatório.
ramsinb
Você encontrou a solução correta para isso?
Balaji Boggaram Ramanarayan

Respostas:

143

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.

r0u1i
fonte
Isso é parecido com o que eu tinha, mas senti falta do uso dos próprios elementos como as chaves ... Eu sabia que estava perto, mas isso realmente acerta na minha cabeça!
guildner de
É interessante que recebi essa pergunta na tela de um telefone do Google e depois de algumas dificuldades, peguei a mesma solução. Estraguei um pouco uma implementação e atribuí a segunda tela do telefone.
Andrey Talnikov
APpend valor ao array: como é O (1)?
Balaji Boggaram Ramanarayan
4
@aamadmi - bem, em Java, acho que deveria. Em pseudo-código, contém deve funcionar perfeitamente :)
r0u1i
4
Por que o array é obrigatório, por que não podemos usar hashmap.
Ankit Zalani
22

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.
Anon
fonte
Isso é um começo, mas e quanto ao último requisito? Você pode obter um elemento aleatório (com probabilidade igual para cada elemento na estrutura de dados) de uma estrutura de dados em hash?
guilda de
1
@ lag1980, acho que você pode:hashtable.get((int)(Math.random()*hashtable.size()));
CMR de
3
Hmmm, não conheço nenhuma tabela de hash que permita obter um elemento como esse e, se houver, não consigo imaginar que seja uma operação de tempo constante. Eu estaria interessado em provar que estou errado em qualquer um dos casos.
guildner de
@ lag1980 ... você poderia facilmente fazer isso em tempo constante da mesma forma que os vetores de Clojure são "tempo constante" - log32 (N) quando os valores possíveis de N são restringidos por seu hardware de modo que o maior valor log32 () possível é ... algo como 7, que é efetivamente um tempo constante.
Charles Duffy
Por "lista apoiada por array" você quer dizer: array?
Hengameh
5

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.

Tony Delroy
fonte
3

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á.

user1147505
fonte
1
Se você escolher continuamente escolher um intervalo aleatório que tenha valor, como diabos é o pior caso, leve a O (1) enquanto você escolhe um elemento aleatório
Balaji Boggaram Ramanarayan
@ user1147505 - onde você conseguiu este número: "0,8 ^ 1000"?
Hengameh
Como você conseguiu isso: "as tabelas de hash estão sempre pelo menos 20% cheias"
Hengameh
Você poderia escrever o método com o qual você pode escolher um balde aleatório?
Hengameh
3

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).

HeadAndTail
fonte
1

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;

        }
    }
}
Scott Lerch
fonte
Não tenho certeza se isso funcionará se você tiver números duplicados.
AlexIIP
Ele não lida com duplicatas, pois @guildner disse para assumir que não há duplicatas nos comentários da questão. Se uma duplicata for adicionada ArgumentExceptioncom a mensagem "Um item com a mesma chave já foi adicionado." será lançado (do Dicionário de índice subjacente).
Scott Lerch
1

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.

Shobhit Raj
fonte
1

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;
}
Antítese
fonte
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.

BaltoStar
fonte
Se você for muito rígido sobre o que é uma tabela hash, então o redimensionamento O (N) é inevitável. No entanto, algumas implementações se comprometem a reduzir o custo de redimensionamento - por exemplo, mantendo a tabela existente enquanto adiciona um segundo do dobro do tamanho, ou tentando redimensionar a tabela existente no local (depois de organizar cuidadosamente o espaço de endereço virtual e os tamanhos das tabelas nos limites da página, para não a cópia é necessária, o que pode exigir mapas de memória em vez de new / malloc mem), em seguida, buscar na nova área maior antes de voltar para a menor (em um modelo no local, modding mais firmemente), com lógica de migração de elemento.
Tony Delroy
0

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.

Ayaskant
fonte
0

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;
}
user1108687
fonte
0
/* 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`
    }
}
Ahmed Taha
fonte
-2

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).

pranay yadav
fonte
-3

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)
Abhinav Jaiswal
fonte
Isso não faz sentido.
innosam