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

Question

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

Conception d'une structure de données qui offre la suite des opérations en O(1) heure:

• insérer
• supprimer
• contient
• obtenez de l'élément aléatoire

Answer 1

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

1. insert(valeur): ajouter de la valeur à un tableau et j'ai laisser-être est-ce l'indice en A. Ensemble H[valeur]=i.
2. retirer(valeur): Nous allons remplacer la cellule qui contient la valeur en Un avec le dernier élément de A. soit d le dernier élément du tableau à Un indice m. laissez-je H[valeur], l'index dans le tableau de la valeur à être supprimé. Set A[i]=d, H[j]=i, diminuer la taille de la matrice par un, et de supprimer la valeur de H.
3. contient du(de la valeur): retour H. contient du(de la valeur)
4. getRandomElement(): soit r=random(taille actuelle). de retour d'Un[r].

depuis le tableau doit à l'auto-augmentation de la taille, ça va être amorti O(1) pour ajouter un élément, mais je suppose que c'est OK.

Answer 2

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

Par comparaison:

• O(1) insérer/supprimer des avec O(N) de recherche implique une liste liée.
• O(1) insérer, O(N) supprimer, et O(N) de recherche implique un tableau soutenu la liste
• O(logN) insérer/supprimer/recherche implique un arbre ou d'un segment.

Answer 3

Vous ne pourriez pas comme cela, parce qu'ils sont probablement à la recherche d'une solution intelligente, mais parfois, il paie pour en tenir à vos armes à feu... Une table de hachage déjà satisfait aux exigences de l' - probablement mieux que tout le reste sera (bien évidemment amorti de la constante de temps, et avec différents compromis à d'autres solutions).

L'exigence qui est difficile est le "hasard" elément sélectionné: dans une table de hachage, vous auriez besoin de balayage de la sonde ou d'un tel élément. La chance d'un seau d'être occupés est - size() / capacity(), mais le point crucial c'est habituellement conservées dans une constante multiplicative de la gamme par une table de hachage de mise en œuvre (par exemple, la table peut être maintenue supérieure à celle de son contenu actuel par dire 1.2 x ~10x en fonction de la performance/le paramétrage de la mémoire). Cela signifie en moyenne, on peut s'attendre à la recherche de 1,2 à 10 seaux de façon totalement indépendante de la taille totale du conteneur; amorti O(1).

Je peux imaginer deux approches simples (et un grand nombre de plus incommodes):

• recherche de façon linéaire à partir d'un seau aléatoire

  • envisager de vide/de la valeur de portefeuille des seaux ala "--AC-----B-D": vous pouvez dire que le premier "aléatoire" de la sélection est juste, même si elle privilégie B, car B n'avaient plus de probabilité d'être favorisée que les autres éléments, mais si vous faites répétées "aléatoire" des sélections à l'aide des mêmes valeurs alors clairement B à plusieurs reprises favorisée peut être indésirable (rien dans la question demande même des probabilités)

• essayez aléatoire seaux à plusieurs reprises jusqu'à ce que vous trouver un rempli d'un

  • "seulement" (capacité) / taille() moyenne des seaux visités (comme ci-dessus) -, mais en termes pratiques, plus coûteux en raison de génération de nombre aléatoire est relativement cher, et infiniment mauvais si infiniment improbable pire des cas, les comportements...

Pas une bonne solution, mais peut encore être un meilleur compromis global de la mémoire et de la performance des frais généraux du maintien d'un deuxième indice de tableau à tout moment.

Answer 4

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

Mais le moins bien noté la réponse (il suffit d'utiliser une table de hachage!) est en fait beaucoup trop!

• table de hachage avec re-hachage, ou nouveau seau de sélection (c'est à dire un élément par seau, pas de listes chaînées)
• getRandom() à plusieurs reprises essaie de choisir aléatoirement seau jusqu'à ce qu'elle est vide.
• comme un fail-safe, peut-être getRandom(), après N (nombre d'éléments) tentatives, sélectionne aléatoirement index i dans [0, N-1] et puis s'en va par le biais de la table de hachage linéaire et prend le n ° i-ème élément.

Les gens pourraient ne pas aimer ce à cause de possible "boucle infinie", et j'ai vu des gens très intelligents ont cette réaction trop, mais c'est faux! Infiniment peu probable des événements juste ne pas se produire.

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

Il va jamais arriver que getRandom() a essayer plus de 1000 fois. Juste jamais. En effet, la probabilité d'un tel événement est de 0,8^1000, qui est de 10^-97 -- de sorte que nous aurions à le répéter 10^88 fois pour avoir une chance sur un milliard de jamais il se passe une fois. Même si ce programme était en cours d'exécution à temps plein sur tous les ordinateurs de l'humanité jusqu'à ce que le Soleil meurt, ce sera de ne jamais arriver.

Answer 5

Ici C# solution à ce problème je suis venu avec un peu de temps en arrière quand on a posé la même question. Elle met en œuvre d'Ajouter, de Supprimer, de les Contient, et au Hasard le long de avec d'autres standards .NET interfaces. Ce que vous ne pourriez jamais besoin de mettre en œuvre dans de tels détails, lors d'une interview, mais c'est agréable 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;

        }
    }
}