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

/*

Au moment où j'écris ceci, toutes les solutions sur cette page doubleront (ou plus) la quantité d'espace nécessaire pour stocker le tableau. La solution suivante réduit la quantité d'espace gaspillé de Ω(n) à θ(n/w), où w est le nombre de bits dans un "mot" d'ordinateur. Sur ma machine, c'est 64.

La prose de cette réponse est en commentaires C, vous pouvez copier-coller cette réponse intégralement et la compiler avec votre compilateur C.

*/

#include 
#include 
#include 
#include 

/*

Le problème est de soutenir la lecture et l'écriture de valeurs dans un tableau en temps O(1) en même temps que des écritures en bloc où toutes les valeurs du tableau sont écrites en même temps en temps O(1). C'est possible en utilisant une technique inventée par Aho, Hopcroft et Ullman, autant que je sache. Je vais présenter une version due à Gonzalo Navarro, "Initialisation des tableaux en temps constant dans un petit espace".

L'idée est de garder trois tableaux de métadonnées avec le tableau de données. Nous gardons également deux entiers: unset, qui est la dernière valeur utilisée dans une opération d'écriture en bloc, et size, une approximation pour le nombre de valeurs qui ont été définies depuis la dernière écriture en bloc. En tout temps, le nombre de valeurs distinctes écrites depuis la dernière écriture en bloc est entre size et w * size.

Les trois tableaux de métadonnées décrivent des informations sur des blocs de w valeurs dans le tableau de données. Ils sont:

• nth: nth[i] est le ième bloc unique à écrire depuis la dernière écriture en bloc

• inverse_nth: inverse_nth[i] est l'ordre dans lequel le ième bloc du tableau a été écrit, en comptant à partir de 0 à la dernière écriture en bloc.

• bitset: Le j-ième bit de bitset[i] est 1 lorsque la cellule de tableau numérotée 64*i + j a été écrite depuis la dernière écriture en bloc.

bitset[i] et inverse_nth[i] sont autorisés à être invalides si i n'est pas un membre de l'ensemble {nth[0], nth[1], ... , nth[size-1]}. En d'autres termes, inverse_nth[i] et bitset[i] sont valides si et seulement si inverse_nth[i] < size et nth[inverse_nth[i]] == i.

Au lieu de stocker trois tableaux séparés de même longueur, j'ai choisi de stocker un seul tableau, is_set, avec trois champs.

*/

typedef struct {
  int nth_;
  int inverse_nth_;
  uint64_t bitset_;
} IsSetCell;

typedef struct {
  int unset_;
  int size_;
  IsSetCell is_set_[];
} IsSetArray;

typedef struct {
  IsSetArray * metadata_;
  int payload_[];
} ResettableArray;

/*

Pour construire un tableau, nous avons besoin d'une valeur par défaut à retourner lorsque l'on lit une valeur qui n'a jamais été écrite.

*/

ResettableArray * ConstructResettableArray(int n, int unset) {
  ResettableArray* result =
      malloc(offsetof(ResettableArray, payload_) + n * sizeof(int));
  if (!result) return NULL;
  n = (n + 63) / 64;
  result->metadata_ =
      malloc(offsetof(IsSetArray, is_set_) + n * sizeof(IsSetCell));
  if (!result->metadata_) {
    free(result);
    return NULL;
  }
  result->metadata_->size_ = 0;
  result->metadata_->unset_ = unset;
  return result;
}

void DestructResettableArray(ResettableArray * a) {
  if (a) free(a->metadata_);
  free(a);
}

/*

Le cœur de l'algorithme réside dans l'écriture et la lecture des métadonnées. Après IsSet() et Set() sont définis (ci-dessous), lire et écrire dans les tableaux est simple.

*/

bool IsSet(const IsSetArray * a, int i);
void Set(IsSetArray * a, int i);

int GetValue(const ResettableArray * a, int i) {
  if (!IsSet(a->metadata_, i)) return a->metadata_->unset_;
  return a->payload_[i];
}

void SetValue(ResettableArray * a, int i, int v) {
  a->payload_[i] = v;
  Set(a->metadata_, i);
}

void SetAllValues(ResettableArray * a, int v) {
  a->metadata_->unset_ = v;
}

/*

La partie complexe de la lecture et de l'écriture est la relation bidirectionnelle entre inverse_nth et nth. S'ils se pointent mutuellement à l'emplacement i (is_set[is_set[i].inverse_nth].nth == i) alors l'emplacement i contient des données valides qui ont été écrites après la dernière écriture en bloc, tant que is_set[i].inverse_nth < size.

*/

uint64_t OneBit(int i) {
  return UINT64_C(1) << i;
}

bool IsSet(const IsSetArray * a, int i) {
  const int cell = i/64, offset = i & 63;
  const int inverse_nth = a->is_set_[cell].inverse_nth_;
  return inverse_nth < a->size_ && a->is_set_[inverse_nth].nth_ == cell &&
         a->is_set_[cell].bitset_ & OneBit(offset);
}

void Set(IsSetArray * a, int i) {
  const int cell = i/64, offset = i & 63;
  const int inverse_nth = a->is_set_[cell].inverse_nth_;
  if (inverse_nth >= a->size_ || a->is_set_[inverse_nth].nth_ != cell) {
    a->is_set_[cell].inverse_nth_ = a->size_;
    a->is_set_[cell].bitset_ = 0;
    a->is_set_[a->size_].nth_ = cell;
    ++a->size_;
  }
  a->is_set_[cell].bitset_ |= OneBit(offset);
}

Answer 2

Nous pouvons avoir une variable V qui stocke un entier et un tableau contenant des Tuple comme {Valeur, id}..

Et une variable globale int G (qui agira comme une identité en SQL et chaque fois qu'une opération set ou setAll est effectuée, sa valeur est incrémentée de 1)

Initiallement, tous les Ids et la valeur de V seront par défaut nuls..

ainsi V = null Tous les Tuple = {null, null}
set(index i, val v) -> G = G+1, arr[i].Val = v, arr[i].Id = G

get(index i) -> si V.Id > arr[i].Id retourne V.Val sinon retourne arr[i]

set-all(val v) -> G= G+1, V.Id= G, V.Val = v

Answer 3

La solution correcte en C# :

public sealed class SpecialDictionary
{
    private Dictionary> innerData;
    private Tuple setAllValue;
    private DateTime prevTime;

    public SpecialDictionary()
    {
        innerData = new Dictionary>();
    }
    public void Set(T key, V value) => innerData[key] = new Tuple(GetTime(), value);
    public void SetAll(V value) => setAllValue = new Tuple(GetTime(), value);
    public V Get(T key)
    {
        Tuple tmpValue = innerData[key];
        if (setAllValue?.Item1 > tmpValue.Item1)
        {
            return setAllValue.Item2;
        }
        else
        {
            return tmpValue.Item2;
        }
    }
    private DateTime GetTime()
    {
        if (prevTime == null)
        {
            prevTime = DateTime.Now;

        }
        else
        {
            if (prevTime == DateTime.Now)
            {
                Thread.Sleep(1);
            }
            prevTime = DateTime.Now;
        }
        return prevTime;
    }
}

Et le test :

static void Main(string[] args)
{
    SpecialDictionary dict = new SpecialDictionary();
    dict.Set("testA", 1);
    dict.Set("testB", 2);
    dict.Set("testC", 3);
    Console.WriteLine(dict.Get("testC"));
    dict.SetAll(4);
    dict.Set("testE", 5);
    Console.WriteLine(dict.Get("testC"));
    Console.WriteLine(dict.Get("testE"));
    Console.ReadKey();
}

Answer 4

Ceci est une autre solution python :

from datetime import datetime
from typing import Any, Dict

class ValueNode:
    def __init__(self, value):
        self.value = value
        self.date_updated = datetime.now()

    def set_value(self, value):
        self.value = value
        self.date_updated = datetime.now()

    def get_value(self, value):
        return self.value

class Structure:
    def __init__(self):
        self._structure: Dict[Any, ValueNode] = {}
        self._set_all_node: ValueNode = None

    def get_val(self, index):
        if self._set_all_node and self._structure.get(index) and self._structure.get(index).date_updated < self._set_all_node.date_updated:
            return self._set_all_node.value
        else:
            if index in self._structure:
                return self._structure[index].value
            else:
                return None

    def set_val(self, index, value):
        self._structure[index] = ValueNode(value)

    def set_all(self, value):
        self._set_all_node = ValueNode(value)

s1 = Structure()
s1.set_val(1, 'vert')
s1.set_val(5, 'bleu')
s1.set_val(9, 'jaune')
print(s1.get_val(1))
print(s1.get_val(5))
print(s1.get_val('ValeurInexistante'))
s1.set_all('noir')
print(s1.get_val(1))
print(s1.get_val(5))
print(s1.get_val('ValeurInexistante'))

Answer 5

Exemple Python

classe d:
    def __init__(self, l):
        self.len = l
        self.g_p = [i pour i dans la plage(self.len)]
        self.g_v = [0 pour in dans la plage(self.len)]
        self.g_s = self.len - 1
        self.g_c = 0  

    def getVal(self, i):
        si (i < 0 ou i >= self.len):
            retour

        si (self.g_p[i] <= self.g_s):
            retourner self.g_v[self.g_p[i]]

        retourner self.g_c

    def setVal(self, i, v):
        si (i < 0 ou i >= self.len):
            retour

        si (self.g_p[i] > self.g_s):
            self.g_s += 1

            self.g_p[self.g_s], self.g_p[i] = self.g_p[i], self.g_p[self.g_s]

        auto.g_v[self.g_p[i]] = v

    def setAll(self, v):
        self.g_c = v
        self.g_s = -1