Question d'entretien : structure de données pour définir toutes les valeurs en O(1)

Question

J'ai rencontré la question d'entrevue suivante sur Internet.

Décrivez une structure de données pour laquelle getValue(int index), setValue(int index, int value) et setAllValues(int value) sont tous en O(1).

Bien que le tableau soit suffisant pour que les première et deuxième opérations soient effectuées en O(1), que peut-on proposer pour la troisième (setAllValues)?

Answer 1

Eh bien, je l'ai fait en fonction des événements. Vérifiez-le.

internal class Program
{
     public static void Main(string[] args)
     {
          SomeUsefullDataStructure ds = new SomeUsefullDataStructure();

          ds.SetValue(1, "11");
          ds.SetValue(2, "22");
          var result = ds.GetValue(2);
          ds.SetAllValues("haha");

          Console.ReadKey();
      }
}

public class SomeUsefullDataStructure
{
    private delegate void SetValueDelegate(string newValue);
    private event SetValueDelegate SetValueEventFired;
    private Dictionary dict = new Dictionary();

    public string GetValue(int key)
    {
        if (dict.ContainsKey(key))
        {
            return dict[key].StringValue;
        }

        throw new ArgumentException("aucune clé de ce type");
    }

    public void SetValue(int key, string value)
    {
        if (dict.ContainsKey(key))
        {
            dict[key].UpdateValue(value);
        }
        else
        {
           StringDataEntry stringDataEntry = new StringDataEntry(value);
           SetValueEventFired += stringDataEntry.UpdateValue;
           dict.Add(key, stringDataEntry);
       }
    }

    public void SetAllValues(string value)
    {
        SetValueEventFired(value);
    }
}

public class StringDataEntry
{
    public string StringValue { get; private set; }

    public StringDataEntry(string value)
    {
        StringValue = value;
    }

    public void UpdateValue(string newValue)
    {
        StringValue = newValue;
    }
}

Answer 2

Ma solution Python. Testée. Pas thread-safe. Veuillez me faire savoir si vous trouvez un problème :)

class NodeStampedTemps:
    def __init__(self, timestamp, val):
        self.timestamp = timestamp
        self.val = val

class EnsembleTousDS:
    def __init__(self):
        self.items = []
        self.timestamp = 0
        self.all_joker= NodeStampedTemps(self.timestamp, 0)

    def getValue(self, index):
        try:
            item=self.items[index]
        except IndexError:
            return None
        if item.timestamp=len(self.items): #
        #     raise IndexError("Index invalide\n")
        self.timestamp += 1
        self.items[index]=NodeStampedTemps(self.timestamp, val)

    def setAllValues(self, val):
        self.timestamp+=1
        self.all_joker=NodeStampedTemps(self.timestamp, val)

Answer 3

Beaucoup de solutions sont excellentes, mais Aucune d'entre elles n'a mentionné la dernière innovation.

Elle a une complexité de temps pire de O(1) pour les opérations remplir(v), lire(i), écrire(i, v)
(appeler remplir(v) met toutes les valeurs du tableau à v, et lire/écrire sont explicites),
tout en prenant seulement 1 bit d'espace supplémentaire en plus du tableau. Oui.

Donc un tableau int32_t de taille 1 000 000 prendra O(1) de temps au pire pour être initialisé (et rempli),
et ne prendra que 32 000 001 bits de mémoire.

Elle est mentionnée dans l'article Des tableaux initialisables sur place,
et expliquée dans un Article que j'ai écrit sur le sujet.

J'ai écrit une bibliothèque en C++ en-tête seulement appelée Farray qui propose le Farray Remplissable,
qui est une implémentation modélisée sur le papier mentionné ci-dessus.