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

Concernant la réponse de Timothy Jone :

Un problème avec cette approche est qu'à un moment donné, vous risquez de manquer d'identifiants pour les horodatages et il se peut que vous fassiez une boucle. Si vous choisissez une valeur de 64 bits pour stocker les horodatages, cela vous donne 18 446 744 073 709 551 616 insertions ou setAlls avant que cela se produise. En fonction de l'utilisation attendue de la structure de données, une phase de nettoyage en O(n) pourrait être appropriée, ou vous pourriez simplement lever une exception.

C'est exactement le pire des cas qui rend cette solution aussi en O(n) et non en O(1). Cette structure, bien qu'elle économise beaucoup d'opérations d'insertion potentielles en O(n), reste en efficacité O(n).

Answer 2

Ceci est ma réponse en Java (je ne suis pas totalement sûr de la syntaxe). J'ai synchronisé les fonctions set afin d'éviter une situation où changeT et defChangeT sont égaux.

Struct ValueSt{ 
  int value;
  Timestamp changeT;
}

Class MyDS{
  int default;
  Timestamp defChangeT;
  HashMap map;

  public MyDS(){
    map = new HashMap();
  }

  public synchronized void mySet(Int key, int value){
    ValueSt vs = new ValueSt(value, Timestamp(System.current));
    map.put(key, vs);
  }

  public synchronized void setAll(int value){
    default = value;
    defChangeT = Timestamp(System.current));
  }

  public int myGet(int key){
    ValueSt vs = map.get(key);
    if(vs != null){
      if(vs.changeT > defChangeT)
        return vs.value;
      else
        return default;
    }
    return null;
  }
}

Answer 3

J'ai récemment été confronté à une question similaire. La structure de données que j'ai utilisée est une combinaison d'une hashmap et d'un hashset.

1) setValue(String key, String value) Dans cette méthode, j' insère directement la paire dans la hashmap. Nous insérons également la clé dans le hashset

2) setAllValue (String Value) Dans cette méthode, je réinitialise la hashmap. Cela supprime toutes les paires puis ajoute une clé disons <"god"> et la valeur. Le hashset maintient l'ensemble de clés à travers toutes les versions de la hashmap.

3) getValue (String key) Dans cette méthode, je maintiens plusieurs conditions if/else pour retourner la valeur.

1. Je vérifie la conditionnelle si la clé est présente dans la hashmap alors je retourne la valeur de cette clé. Cela peut se produire si soit il n'y a pas encore de clé "god" présente et que chaque clé conserve sa valeur d'origine, soit une clé "god" est là mais la valeur a été remplacée pour cette clé.
2. Une condition else/if pour vérifier si la clé n'était pas présente dans le hashset alors retourner null car cette clé n'a jamais été présente dans la hashmap ou dans toute instance précédente de la map.
3. Enfin une autre condition else dans laquelle je retourne la valeur de la clé <"god"> parce que ce else signifie que la clé existait dans une certaine version de la hashmap et n'a pas encore été remplacée.

class OptimisedMap {

Map mymap = new HashMap();
Set myset = new HashSet<>();
public void setValue (String key, String value) {
    mymap.put(key, value);
    myset.add(key);
}

public void setAllValue (String value) {
    mymap = new HashMap<>();
    mymap.put("god", value);
}

public String getValue (String key) {
    if (mymap.containsKey(key)) {
        return mymap.get(key);
    } else if (!myset.contains(key)) {
        return null;
    } else {
        return mymap.get(key);
    }
}

public static void main (String args[]) {

    OptimisedMap opmap = new OptimisedMap();
    String value = opmap.getValue("hey");
    if (value == null) {
        System.out.println("Clé non présente");
    }
    opmap.setValue("hey", "there");
    opmap.setValue("ho", "there");
    System.out.println(opmap.getValue("hey")); // affichera there
    opmap.setAllValue("whatsup");
    System.out.println(opmap.getValue("hey")); // affichera whatsup
    System.out.println(opmap.getValue("ho")); // affichera whatsup
    opmap.setValue("hey", "there");
    System.out.println(opmap.getValue("hey")); // affichera there
    System.out.println(opmap.getValue("ho")); // affichera whatsup
}

}

Answer 4

Un autre exemple en Python :

    class SetAll:
    def __init__(self):
        self.mapping = {}
        self.is_all_same = True
        self.all_value = None
        self.set_all_ran = False

    def set(self, index, value):
        if self.is_all_same:
            if value == self.all_value:
                return
            else:
                self.is_all_same = False
                self.mapping[index] = value
        else:
            self.mapping[index] = value

    def get(self, index):
        if self.mapping.get(index, None):
            return self.mapping[index]
        else:
            if self.is_all_same:
                return self.all_value
            else:
                if self.set_all_ran:
                    return self.all_value
        return

    def set_all(self, value):
        self.mapping = {}
        self.is_all_same = True
        self.set_all_ran = True
        self.all_value = value

Answer 5

Mon implémentation en c# pour ce problème :

   public class MyStruct
    {
    public MyStruct(int val)
    {
        this.value = val;
        this.currentTime = 0;
    }
    public int value { get; set; }
    public int currentTime { get; set; }
}

public class Struct
{
    public List array = new List();
    public MyStruct all = new MyStruct(0);

    public int GetValue(int index)
    {
        if(all.currentTime >= array[index].currentTime)
        {
            return all.value;
        }
        else
        {
            return array[index].value;
        }
    }

    public void Set(int index, int value)
    {
        if(array.Count <= index)
        {
            array.Add(new MyStruct(value));
        }
        else
        {
            array[index].value = value;
        }
        array[index].currentTime = all.currentTime +1;
    }

    public void SetAll(int value)
    {
        all.value = value;
        all.currentTime++;
    }

    public void Delete(int index)
    {
        array[index].currentTime = 0;
        array[index].value = -1;
    }
}

Chen Lugasi