Structure de données: insérer, supprimer, contient, obtenir un élément aléatoire, le tout en O (1)

J'ai eu ce problème dans une interview. Comment auriez-vous répondu?

Concevez une structure de données qui offre les opérations suivantes en temps O (1):

• insérer
• retirer
• contient
• obtenir un élément aléatoire

Considérez une structure de données composée d'une table de hachage H et d'un tableau A. Les clés de table de hachage sont les éléments de la structure de données et les valeurs sont leurs positions dans le tableau.

1. insert (valeur): ajoutez la valeur au tableau et laissez i être son index dans A. Définissez H [valeur] = i.
2. remove (value): Nous allons remplacer la cellule qui contient la valeur dans A par le dernier élément de A. soit d le dernier élément du tableau A à l'index m. Soit i H [valeur], l'indice dans le tableau de la valeur à supprimer. Définissez A [i] = d, H [d] = i, diminuez la taille du tableau de un et supprimez la valeur de H.
3. contient (valeur): retourne H.contains (valeur)
4. getRandomElement (): let r = random (taille actuelle de A). retourne A [r].

puisque le tableau doit augmenter automatiquement en taille, il va être amorti O (1) pour ajouter un élément, mais je suppose que c'est OK.

La recherche O (1) implique une structure de données hachée .

Par comparaison:

• O (1) insérer / supprimer avec O (N) la recherche implique une liste chaînée.
• O (1) insert, O (N) delete et O (N) lookup impliquent une liste sauvegardée sur un tableau
• O (logN) insérer / supprimer / rechercher implique un arbre ou un tas.

Cela ne vous plaira peut-être pas, car ils recherchent probablement une solution intelligente, mais parfois il vaut mieux s'en tenir à vos armes ... Une table de hachage satisfait déjà les exigences - probablement mieux dans l'ensemble que toute autre chose (bien que évidemment en constante amortie temps, et avec différents compromis avec d’autres solutions).

L'exigence qui est délicate est la sélection "d'élément aléatoire": dans une table de hachage, vous auriez besoin de rechercher ou de rechercher un tel élément.

Pour le hachage fermé / l'adressage ouvert, la probabilité qu'un compartiment donné soit occupé est size() / capacity(), mais surtout, cela est généralement maintenu dans une plage multiplicative constante par une implémentation de table de hachage (par exemple, la table peut être maintenue plus grande que son contenu actuel par exemple 1,2x à ~ 10x selon le réglage des performances / de la mémoire). Cela signifie qu'en moyenne, nous pouvons nous attendre à rechercher entre 1,2 et 10 seaux - totalement indépendante de la taille totale du conteneur; amorti O (1).

Je peux imaginer deux approches simples (et bien d'autres plus délicates):

• rechercher linéairement à partir d'un compartiment aléatoire

  • considérez les seaux vides / contenant une valeur ala "--AC ----- B - D": vous pouvez dire que la première sélection "aléatoire" est juste même si elle favorise B, car B n'avait plus de probabilité d'être favorisé que les autres éléments, mais si vous effectuez des sélections «aléatoires» répétées en utilisant les mêmes valeurs, il peut être indésirable d'avoir clairement B favorisé à plusieurs reprises (rien dans la question n'exige même des probabilités)

• essayez plusieurs seaux aléatoires jusqu'à ce que vous en trouviez un rempli

  • "seulement" capacité () / taille () des seaux moyens visités (comme ci-dessus) - mais en termes pratiques plus coûteux car la génération de nombres aléatoires est relativement chère, et infiniment mauvaise si le pire des cas est infiniment improbable ...
    • un compromis plus rapide consisterait à utiliser une liste de décalages aléatoires pré-générés à partir du bucket initial sélectionné au hasard, en les% -ing dans le nombre de bucket

Ce n'est pas une excellente solution, mais cela peut tout de même être un meilleur compromis global que les frais de mémoire et de performances liés à la maintenance d'un deuxième tableau d'index à tout moment.

La meilleure solution est probablement la table de hachage + tableau, c'est vraiment rapide et déterministe.

Mais la réponse la moins bien notée (utilisez simplement une table de hachage!) Est également excellente!

• table de hachage avec re-hachage ou nouvelle sélection de bucket (c'est-à-dire un élément par bucket, pas de listes liées)
• getRandom () essaie à plusieurs reprises de choisir un compartiment aléatoire jusqu'à ce qu'il soit vide.
• en tant que sécurité intégrée, peut-être getRandom (), après N (nombre d'éléments) essais infructueux, sélectionne un index aléatoire i dans [0, N-1] puis parcourt la table de hachage de manière linéaire et sélectionne l'élément # i-ème .

Les gens n'aimeront peut-être pas ça à cause des "boucles infinies possibles", et j'ai vu des gens très intelligents avoir cette réaction aussi, mais c'est faux! Les événements infiniment improbables ne se produisent tout simplement pas .

En supposant le bon comportement de votre source pseudo-aléatoire - ce qui n'est pas difficile à établir pour ce comportement particulier - et que les tables de hachage sont toujours pleines à au moins 20%, il est facile de voir que:

Il n'arrivera jamais que getRandom () doive essayer plus de 1000 fois. Juste jamais . En effet, la probabilité d'un tel événement est de 0,8 ^ 1000, soit 10 ^ -97 - nous devrions donc le répéter 10 ^ 88 fois pour avoir une chance sur un milliard que cela se produise une fois. Même si ce programme fonctionnait à plein temps sur tous les ordinateurs de l'humanité jusqu'à la mort du Soleil, cela ne se produira jamais .

Pour cette question, j'utiliserai deux structures de données

• HashMap
• ArrayList / Array / Double LinkedList.

Pas :-

1. Insertion: - Vérifier si X est déjà présent dans HashMap - Complexité temporelle O (1). sinon Present Then Add à la fin de ArrayList - Complexité temporelle O (1). ajoutez-le dans HashMap également x comme clé et dernier index comme valeur - Complexité temporelle O (1).
2. Supprimer: - Vérifier si X est présent dans HashMap - Complexité temporelle O (1). S'il est présent, recherchez son index et supprimez-le de HashMap - Complexité temporelle O (1). permutez cet élément avec le dernier élément de ArrayList et supprimez le dernier élément --Complexité temporelle O (1). Mettez à jour l'index du dernier élément dans HashMap - Complexité temporelle O (1).
3. GetRandom: - Génère un nombre aléatoire de 0 au dernier index de ArrayList. renvoie l'élément ArrayList à l'index aléatoire généré --Complexité temporelle O (1).
4. Recherche: - Voir dans HashMap pour x comme une clé. - Complexité temporelle O (1).

Code: -

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;

            }
        }
    }

}

- Complexité temporelle O (1). - Complexité spatiale O (N).

Voici une solution C # à ce problème que j'ai trouvé il y a quelque temps quand on m'a posé la même question. Il implémente Add, Remove, Contains et Random avec d'autres interfaces .NET standard. Non pas que vous ayez jamais besoin de l'implémenter avec autant de détails lors d'une interview, mais c'est bien d'avoir une solution concrète à regarder ...

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;

        }
    }
}

Nous pouvons utiliser le hachage pour prendre en charge les opérations dans le temps Θ (1).

insert (x) 1) Vérifiez si x est déjà présent en effectuant une recherche de carte de hachage. 2) S'il n'est pas présent, insérez-le à la fin du tableau. 3) Ajoutez également la table de hachage, x est ajouté comme clé et le dernier index de tableau comme index.

remove (x) 1) Vérifiez si x est présent en effectuant une recherche de carte de hachage. 2) S'il est présent, recherchez son index et supprimez-le de la carte de hachage. 3) Échangez le dernier élément avec cet élément dans le tableau et supprimez le dernier élément. L'échange est effectué car le dernier élément peut être supprimé en un temps O (1). 4) Mettre à jour l'index du dernier élément de la carte de hachage.

getRandom () 1) Génère un nombre aléatoire de 0 au dernier index. 2) Renvoyez l'élément du tableau à l'index généré aléatoirement.

search (x) Recherchez x dans la carte de hachage.

Bien que ce soit bien vieux, mais comme il n'y a pas de réponse en C ++, voici mes deux cents.

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

Voici un morceau de code client pour tester la solution.

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

Dans C # 3.0 + .NET Framework 4, un générique Dictionary<TKey,TValue>est encore meilleur qu'un Hashtable car vous pouvez utiliser la System.Linqméthode d'extension ElementAt()pour indexer dans le tableau dynamique sous-jacent où les KeyValuePair<TKey,TValue>éléments sont stockés:

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

Cependant, pour autant que je sache, un Hashtable (ou sa progéniture Dictionary) n'est pas une vraie solution à ce problème car Put () ne peut être amorti que O (1), pas vrai O (1), car c'est O (N ) à la limite de redimensionnement dynamique.

Y a-t-il une vraie solution à ce problème? Tout ce que je peux penser, c'est que si vous spécifiez une capacité initiale Dictionary / Hashtable d'un ordre de grandeur au-delà de ce dont vous prévoyez avoir besoin, alors vous obtenez des opérations O (1) car vous n'avez jamais besoin de redimensionner.

Je suis d'accord avec Anon. À l'exception de la dernière exigence où l'obtention d'un élément aléatoire avec une équité égale est requise, toutes les autres exigences ne peuvent être satisfaites qu'à l'aide d'un seul DS basé sur le hachage. Je vais choisir HashSet pour cela en Java. Le modulo du code de hachage d'un élément me donnera le numéro d'index du tableau sous-jacent en temps O (1). Je peux l'utiliser pour ajouter, supprimer et contient des opérations.

Ne pouvons-nous pas faire cela en utilisant HashSet de Java? Il fournit insérer, supprimer, rechercher tout dans O (1) par défaut. Pour getRandom, nous pouvons utiliser l'itérateur de Set qui donne de toute façon un comportement aléatoire. Nous pouvons simplement itérer le premier élément de l'ensemble sans nous soucier du reste des éléments

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

Pourquoi n'utilisons-nous pas epoch% arraysize pour trouver un élément aléatoire. Trouver la taille du tableau est O (n) mais la complexité amortie sera O (1).

Je pense que nous pouvons utiliser une double liste de liens avec une table de hachage. key sera element et sa valeur associée sera node dans doublement linklist.

1. insert (H, E): insérer le nœud dans la liste de liens doublement et faire l'entrée comme H [E] = nœud; O (1)
2. delete (H, E): obtenir l'adresse du nœud par H (E), aller au précédent de ce nœud et supprimer et rendre H (E) comme NULL, donc O (1)
3. contient (H, E) et getRandom (H) sont évidemment O (1)