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

Que diriez-vous d'un tableau de tuples {horodatage, valeur}, avec un {horodatage, valeur} supplémentaire appelé all. Puisque vous vous souciez uniquement du temps relatif des insertions, vous pouvez utiliser un id en augmentation monotone pour les valeurs de l'horodatage :

type Entrée {
  int horodatage, 
  int valeur
}

type structure {
    int     id
    Entrée  all
    Entrée[] tableau
}

Initialisez toutes les champs à 0. Ensuite, ce qui suit devrait fonctionner pour vous :

• fixerValeur(index i, valeur v):

  tableau[i] = {id++, valeur}

• valeur obtenirValeur(index i)

  si(all.horodatage > tableau[i].horodatage) return all.valeur
  sinon retourner tableau[i].valeur

• fixerTout(valeur v)

  all = {id++, valeur}

Un problème avec cette approche est qu'à un moment donné vous finirez par manquer d'ids pour l'horodatage, et pourriez faire un tour complet. Si vous choisissez une valeur de 64 bits pour stocker les horodatages, cela vous donne 18,446,744,073,709,551,616 insertions ou mises à jour de tout avant que cela n'arrive. Selon l'utilisation attendue de la structure de données, il pourrait être approprié d'avoir une phase de nettoyage en O(n), ou vous pourriez simplement générer une exception.

Un autre problème qui pourrait nécessiter d'être pris en compte est le multi-threading. Trois problèmes évidents :

• si id++ n'est pas atomique et que deux threads obtiennent un nouvel id en même temps alors vous pourriez obtenir deux entrées avec le même id.
• si l'incrémentation de l'id et l'attribution du tuple créé ne sont pas atomiques ensemble (ils ne le sont probablement pas) et s'il y avait deux insertions simultanées, alors vous pourriez avoir une condition de concurrence où le plus ancien identifiant l'emporte.
• si l'attribution du tuple n'est pas atomique, et qu'il y a une insertion() en même temps qu'un get() alors vous pourriez vous retrouver dans une position où vous avez, disons, {nouvel_id, ancienne_valeur} dans le tableau, ce qui entraîne le retour de la mauvaise valeur.

Si l'un de ces problèmes se présente, la solution la plus simple est de mettre "non thread-safe" dans la documentation (en trichant). Alternativement, si vous ne pouvez pas implémenter les méthodes de manière atomique dans votre langage de choix, vous devriez mettre des verrous de synchronisation autour d'elles.

Answer 2

J'ai eu la même question lors d'un entretien technique.
Voici mon implémentation Java complète prête à l'emploi incluant les cas de test.

L'idée clé est de garder la valeur de setAll() dans une variable spéciale (par exemple joker) et de suivre le changement de cette valeur de manière appropriée.

Afin de garder le code propre, certains modificateurs d'accès ont été supprimés.

Classe Node:

import java.time.LocalDate;

class Node {

    int value;
    LocalDate jokerSetTime;

    Node(int val, LocalDate jokSetTime) {
        value = val;
        jokerSetTime = jokSetTime;
    }
}

Classe DS:

class DS {

    Node[] arr;

    DS(int len) {
        arr = new Node[len];
    }
}

Classe DataStructure:

import java.time.LocalDate;

class DataStructure {

    private boolean isJokerChanged;
    private Integer joker;
    private LocalDate jokerSetTime;
    private DS myDS;

    DataStructure(int len) {
        myDS = new DS(len);
    }

    Integer get(int i) {

        Integer result;

        if (myDS.arr.length < i) {
            return null;
        }

        // setAll() a été appelée juste avant
        if (isJokerChanged) {
            return joker;
        }

        if (myDS.arr[i] == null) {

            // setAll() a été appelée précédemment
            if (joker != null) {
                result = joker;
            } else {
                result = null;

            }

        } else if (myDS.arr[i].jokerSetTime == jokerSetTime) {
            // la valeur de la cellule a été remplacée après l'appel de setAll()
            result = myDS.arr[i].value;
        } else {
            result = joker;
        }

        return result;
    }

    void setAll(int val) {
        isJokerChanged = true;
        joker = val;
        jokerSetTime = LocalDate.now();
    }

    void set(int i, int val) {
        isJokerChanged = false;
        myDS.arr[i] = new Node(val, jokerSetTime);
    }
}

Classe Main:

class Main {

    public static void main(String[] args) {

        DataStructure ds = new DataStructure(100);

        Integer res;

        res = ds.get(3);

        ds.set(3, 10);

        res = ds.get(3);

        ds.setAll(6);

        res = ds.get(3);

        res = ds.get(15);

        ds.set(4, 7);

        res = ds.get(4);

        res = ds.get(3);

        ds.setAll(6);

        ds.set(8, 2);

        res = ds.get(3);
    }
}

Mise à jour:
Le code a été mis à jour. L'implémentation précédente ne prenait pas en compte le cas où setAll() est appelée deux fois de suite avec la même valeur et est suivie de set(x), get(y), par exemple : setAll(100), set(3, 1), setAll(100), set(5, 3), get(3).

L'approche du timestamp a été ajoutée pour permettre de faire la distinction entre différentes appels de setAll() avec des valeurs identiques.

P.S. Cette implémentation n'est pas thread-safe.

Answer 3

J'ai été interrogé récemment sur cette question lors d'un entretien. J'ai proposé une implémentation de table de hachage. Cela résoudrait le problème de l'épuisement des valeurs de timestamp, mais la fonctionnalité de sécurité des threads doit être implémentée (probablement en utilisant des techniques d'initialisation paresseuse)

Supposons que dans notre classe nous ayons une variable privée _defaultValue pour contenir une valeur par défaut et que nous ayons également une table de hachage ou un dictionnaire privé _hashtable. SetAllValues pourrait simplement définir _defaultValue égal à la valeur passée et _hashtable initialisé/défini sur une nouvelle table de hachage et ignorer toute référence à l'ancienne table de hachage. SetValue devrait simplement ajouter une nouvelle valeur à _hashtable ou mettre à jour la valeur si la clé (ou l'indice) est déjà présente dans le _hashtable. GetValue devrait vérifier si la clé (ou l'indice) est présente dans _hashtable, puis la renvoyer, sinon renvoyer la valeur stockée dans _defaultValue.

C'est ma première réponse sur StackOverflow. Je suis un peu paresseux pour écrire le code. Je vais probablement éditer la réponse bientôt.

L'intervieweur a acquiescé à cette solution mais a insisté pour l'implémenter sans utiliser de table de hachage. Je suppose qu'il me demandait de donner une approche similaire à la réponse de Timothy. Et je n'ai pas pu le comprendre à ce moment-là :(. En tout cas, Cheers!

EDIT : Publication du code (en C#)

class MyDataStruct
{
    private int _defaultValue;
    private Dictionary _hashtable;

    public MyDataStruct()
    {
        _defaultValue = 0; // initialiser la valeur par défaut avec une certaine valeur
        _hashtable = new Dictionary();
    }

    public void SetAllValues(int val)
    {
        _defaultValue = val;
        _hashtable = new Dictionary();
    }

    public void SetValue(int index, int val)
    {
        if (_hashtable.ContainsKey(index))
        {
            _hashtable.Add(index, val);
        }
        else
        {
            _hashtable[index] = val;
        }
    }

    public int GetValue(int index)
    {
        if (_hashtable.ContainsKey(index))
        {
            return _hashtable[index];
        }
        else
        {
            return _defaultValue;
        }
    }
}

Answer 4

Que diriez-vous d'un tableau de pointeurs vers une seule valeur commune ? Définissez la valeur, et toutes les références pointeront vers la seule valeur modifiée en O(1)...

Answer 5

Toutes les réponses existantes utilisent un horodatage qui est incrémenté à chaque opération setVal. Ce n'est pas nécessaire. En fait, il n'est nécessaire d'incrémenter l'horodatage que sur setAll. Un autre problème soulevé est le débordement arithmétique. Cela peut être géré sans dépasser les limites de temps constant en mettant à jour une seule cellule à chaque setAll et en effectuant la comparaison de temps avec soin.

Comment ça fonctionne

Le concept de base est essentiellement similaire à celui des autres réponses, mais avec une particularité.

Ce qu'ils font : Stockez la valeur utilisée pour la dernière opération setAll séparément et suivez l'heure à laquelle cette opération a été effectuée. Chaque fois qu'ils effectuent un setVal, ils stockent l'heure actuelle avec la valeur donnée dans le tableau. Chaque fois qu'ils effectuent un getVal, ils comparent l'heure dans l'emplacement donné avec l'heure de la dernière occurrence de setAll, puis choisissent soit la valeur à l'emplacement, soit la valeur setAll en fonction de laquelle est la plus grande.

Pourquoi cela peut être un problème : Supposons que l'heure actuelle déborde et qu'une opération setAll se produise peu de temps après. Il semblera que la plupart des valeurs de tableau stockées sont plus récentes que la valeur de setAll, alors qu'en réalité elles sont plus anciennes.

La solution : Arrêter d'imaginer que nous suivons la quantité totale de temps écoulée depuis l'initialisation de la structure de données. Imaginez une horloge géante avec une "aiguille des secondes" qui ne fait pas 60 tours autour du cercle mais plutôt 2^n tours autour du cercle. La position de l'aiguille des secondes représente l'heure de la dernière opération setAll. Chaque opération setVal stocke cette heure avec une valeur. Donc, si nous effectuons un setAll lorsque l'"horloge" est à 45, puis effectuons six opérations setVal sur différents éléments, l'heure de setAll et les heures de tous les six emplacements seront les mêmes. Nous souhaitons maintenir l'invariant suivant :

L'heure à un emplacement donné équivaut à l'heure de setAll si et seulement si cet élément a été réglé avec setVal plus récemment que la dernière opération setAll.

De toute évidence, la procédure décrite ci-dessus garantit automatiquement que si l'élément a été réglé récemment, alors son heure équivaudra à l'heure de setAll. Le défi est de faire en sorte que l'implication inverse soit également vraie.

À suivre ....

Le code

J'ai écrit cela en Haskell car c'est le langage que je connais le mieux, mais ce n'est pas exactement le langage le plus naturel pour ce travail.

{-# LANGUAGE BangPatterns #-}
module RepArr where

import Control.Monad.Primitive
import Data.Primitive.MutVar
import qualified Data.Vector.Mutable as V
import Data.Vector.Mutable (MVector)
import Control.Applicative
import Prelude hiding (replicate)
import Control.Monad.ST
import Data.Word

-- L'Int dans le MutVar est le pointeur de rafraîchissement
data RepArr s a = RepArr (MutVar s (Word, a, Int)) (MVector s (Word,a))

-- Crée un tableau fantaisiste d'une longueur donnée, initialement rempli d'une valeur donnée
replicate :: (PrimMonad m, Applicative m) => Int -> a -> m (RepArr (PrimState m) a)
replicate n a = RepArr <$> newMutVar (0,a,0) <*> V.replicate n (0,a)

getVal :: PrimMonad m => RepArr (PrimState m) a -> Int -> m a
getVal (RepArr allv vec) n = do
  (vectime, vecval) <- V.read vec n
  (alltime, allval, _) <- readMutVar allv
  if (fromIntegral (alltime - vectime) :: Int) > 0
    then return allval
    else return vecval

setVal :: PrimMonad m => RepArr (PrimState m) a -> Int -> a -> m ()
setVal (RepArr allv vec) i v = do
  (!alltime, _, _) <- readMutVar allv
  V.write vec i (alltime, v)

setAll :: PrimMonad m => RepArr (PrimState m) a -> a -> m ()
setAll r@(RepArr allv vec) v = do
  (oldt, _, oldc) <- readMutVar allv
  getVal r oldc >>= setVal r oldc
  let !newc = case oldc+1 of
        op1 | op1 == V.length vec -> 0
            | otherwise -> op1
  let !newt = oldt+1
  writeMutVar allv (newt, v, newc)

Pour éviter les pauses potentielles (rarement) dues à la collecte des déchets, il est en fait nécessaire de déballer les valeurs Int et Word, ainsi que d'utiliser des vecteurs déballés au lieu de ceux polymorphes, mais je ne suis pas vraiment d'humeur et c'est une tâche assez mécanique.

Voici une version en C (complètement non testée) :

#include 

struct Pair {
  unsigned long time;
  void* val;
};

struct RepArr {
  unsigned long allT;
  void* allV;
  long count;
  long length;
  struct Pair vec[];
};

struct RepArr *replicate (long n, void* val) {
  struct RepArr *q = malloc (sizeof (struct RepArr)+n*sizeof (struct Pair));
  q->allT = 1;
  q->allV = val;
  q->count = 0;
  q->length = n;

  int i;
  for (i=0; ivec[i] = foo;
  }
  return q;
}

void* getVal (struct RepArr *q, long i) {
  if ((long)(q->vec[i].time - q->allT) < 0)
    return q->allV;
  else
    return q->vec[i].val;
}

void setVal (struct RepArr *q, long i, void* val) {
  q->vec[i].time = q->allT;
  q->vec[i].val = val;
}

void setAll (struct RepArr *q, void* val) {
  setVal (q, q->count, getVal (q, q->count));
  q->allV = val;
  q->allT++;
  q->count++;
  if (q->count == q->length)
    q->count = 0;
}