data-structures - unam - tipos de entrevista pdf
Pregunta de la entrevista: estructura de datos para establecer todos los valores en O(1) (11)
¿Qué tal una serie de indicadores para un solo valor común? Establezca el valor, y todas las referencias apuntarán al único valor modificado en O (1) ..
Al mirar las preguntas de la entrevista en Internet, me encontré con la siguiente.
Describa una estructura de datos para la cual getValue (int index), setValue (int index, int value) y setAllValues (int value) son todos O (1).
Aunque la matriz es lo suficientemente buena para que la primera y la segunda operación se realicen en O (1), ¿qué se puede proponer para la tercera (setAllValues)?
Ejemplo de Python
class d:
def __init__(self, l):
self.len = l
self.g_p = [i for i in range(self.len)]
self.g_v = [0 for i in range(self.len)]
self.g_s = self.len - 1
self.g_c = 0
def getVal(self, i):
if (i < 0 or i >= self.len):
return
if (self.g_p[i] <= self.g_s):
return self.g_v[self.g_p[i]]
return self.g_c
def setVal(self, i, v):
if (i < 0 or i >= self.len):
return
if (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]
self.g_v[self.g_p[i]] = v
def setAll(self, v):
self.g_c = v
self.g_s = -1
En cuanto a la respuesta de Timothy Jone:
Un problema con este enfoque es que eventualmente se quedará sin identificadores para la marca de tiempo, y puede que se ajuste. Si elige un valor de 64 bits para almacenar marcas de tiempo, entonces esto le brinda 18,446,744,073,709,551,616 inserciones o setAlls antes de que esto suceda. Dependiendo del uso esperado de la estructura de datos, una fase de limpieza de O (n) podría ser apropiada, o podría lanzar una excepción.
Este es exactamente el peor escenario que hace que esta solución O (n) también, y no O (1). Esta estructura, aunque ahorra una gran cantidad de potencial O (n) inserción de la operación, todavía está en O (n) eficiencia.
Esta es mi respuesta en Java (no estoy completamente seguro de la sintaxis). Hice las funciones de set sincronizadas para evitar una situación donde changeT y defChangeT son iguales.
Struct ValueSt{
int value;
Timestamp changeT;
}
Class MyDS{
int default;
Timestamp defChangeT;
HashMap map;
public MyDS(){
map = new HashMap<int, ValueSt>();
}
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;
}
}
La solución correcta en C #:
public sealed class SpecialDictionary<T, V>
{
private Dictionary<T, Tuple<DateTime, V>> innerData;
private Tuple<DateTime, V> setAllValue;
private DateTime prevTime;
public SpecialDictionary()
{
innerData = new Dictionary<T, Tuple<DateTime, V>>();
}
public void Set(T key, V value) => innerData[key] = new Tuple<DateTime, V>(GetTime(), value);
public void SetAll(V value) => setAllValue = new Tuple<DateTime, V>(GetTime(), value);
public V Get(T key)
{
Tuple<DateTime, V> 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;
}
}
Y la prueba:
static void Main(string[] args)
{
SpecialDictionary<string, int> dict = new SpecialDictionary<string, int>();
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();
}
Me acaban de hacer esta pregunta muy recientemente en una entrevista. Se me ocurrió una implementación de tabla hash. Resolvería el problema de quedarse sin los valores de marca de tiempo pero la característica de seguridad de subprocesos debe implementarse (probablemente usando técnicas de inicialización perezosas)
Digamos en nuestra clase que tenemos una variable privada _defaultValue para mantener un valor predeterminado y también tenemos una tabla hash privada o un diccionario _hashtable . SetAllValues podría simplemente configurar _defaultValue igual al valor pasado y _hashtable initialized / set a una nueva tabla hash y descartar cualquier referencia a la antigua tabla hash. SetValue solo debe agregar un nuevo valor a _hashtable o actualizar el valor si la clave (o índice) ya está presente en _hashtable . GetValue debería verificar si la clave (o índice) está presente en _hashtable , luego devolverlo, de lo contrario, devolver el valor almacenado en _defaultValue .
Esta es mi primera respuesta en . Soy un poco flojo al escribir el código. Probablemente editará la respuesta pronto.
El entrevistador asintió con la cabeza a esta solución, pero insistió en implementarla sin usar una tabla hash. Supongo que me estaba pidiendo que diera un enfoque similar a la respuesta de Timothy. Y no pude obtenerlo en ese momento :(. De todos modos, ¡Salud!
EDITAR: Publicar el código (en C #)
class MyDataStruct
{
private int _defaultValue;
private Dictionary<int,int> _hashtable;
public MyDataStruct()
{
_defaultValue = 0; // initialize default with some value
_hashtable = new Dictionary<int, int>();
}
public void SetAllValues(int val)
{
_defaultValue = val;
_hashtable = new Dictionary<int, int>();
}
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;
}
}
}
Podemos tener una variable V que almacena un int y una matriz que contiene Tuple como {Value, id} ..
Y una variable int global G (que actuará como identidad en SQL y cada vez que se establece un conjunto o setToda operación se incrementa su valor en 1)
Inicial todos los valores de Ids y V serán por defecto nulo.
so V = null All Tuple = {null, null}
set(index i, val v) -> G = G+1, arr[i].Val = v, arr[i].Id = G
get(index i) -> if V.Id > arr[i].Id return V.Val else return arr[i]
set-all(val v) -> G= G+1, V.Id= G, V.Val = v
Tengo la misma pregunta en una de las entrevistas técnicas.
Aquí está mi completa implementación de Java lista para usar, incluidos los casos de prueba.
La idea clave es mantener el valor de setAll() en una variable especial (por ejemplo, joker ) y luego rastrear el cambio de este valor de una manera adecuada.
Para mantener el código limpio, algunos modificadores de acceso han sido abolidos.
Clase de nodo :
import java.time.LocalDate;
class Node {
int value;
LocalDate jokerSetTime;
Node(int val, LocalDate jokSetTime) {
value = val;
jokerSetTime = jokSetTime;
}
}
Clase DS :
class DS {
Node[] arr;
DS(int len) {
arr = new Node[len];
}
}
Clase 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() has been just called
if (isJokerChanged) {
return joker;
}
if (myDS.arr[i] == null) {
// setAll() has been previously called
if (joker != null) {
result = joker;
} else {
result = null;
}
} else if (myDS.arr[i].jokerSetTime == jokerSetTime) {
// cell value has been overridden after setAll() call
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);
}
}
Clase principal :
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);
}
}
Actualizar:
El código ha sido actualizado. La implementación anterior no tuvo en cuenta el caso cuando se llama a setAll() dos veces seguidas con el mismo valor y es seguido por set(x) , get(y) , por ejemplo: setAll(100) , set(3, 1) , setAll(100) , set(5, 3) , get(3) .
Se ha agregado el uso del enfoque de marca de tiempo para permitir distinguir entre diferentes llamadas setAll() con valores idénticos.
PD: esta implementación no es segura para subprocesos.
Todas las respuestas existentes usan una marca de tiempo que se incrementa en cada operación setVal . Esto no es necesario. De hecho, solo es necesario incrementar la marca de tiempo en setAll . Otro problema que algunos plantearon fue el desbordamiento aritmético. Esto se puede manejar sin romper los límites de tiempo constantes actualizando una sola celda en cada setAll y realizando la comparación de tiempo cuidadosamente.
Cómo funciona
El concepto básico es esencialmente similar al de las otras respuestas, pero con un giro.
Lo que hacen: almacena el valor utilizado para la última operación setAll separado, y realiza un seguimiento de la hora en que se realizó la operación. Cada vez que realizan un setVal , almacenan la hora actual junto con el valor dado en el conjunto. Cada vez que realizan un getVal , comparan el tiempo en la ubicación dada con el momento en que ocurrió el último setAll , y luego eligen el valor en la ubicación o el valor setAll dependiendo de cuál sea mayor.
Por qué esto puede ser un problema: supongamos que la hora actual se desborda y una operación setAll ocurre poco después. setAll que la mayoría de los valores de matriz almacenados son más nuevos que el valor setAll , cuando en realidad son más antiguos.
La solución: deje de imaginar que estamos haciendo un seguimiento de la cantidad total de tiempo que ha pasado desde la inicialización de la estructura de datos. Imagine un reloj gigante con una "manecilla de segundos" que no gire 60 veces alrededor del círculo sino más bien 2 ^ n veces alrededor del círculo. La posición de la manecilla de los segundos representa el tiempo de la operación setAll más reciente. Cada operación setVal almacena esta vez junto con un valor. Entonces, si realizamos un setAll cuando el "reloj" está en 45, y luego realizamos seis operaciones setVal en diferentes elementos, el setAll hora y las horas en las seis ubicaciones serán las mismas. Queremos mantener la siguiente invariante:
El tiempo en la ubicación de un elemento determinado es igual a
setAlltime si y solo si ese elemento se estableció consetValmás recientemente que la última operaciónsetAll.
Claramente, el procedimiento descrito anteriormente asegura automáticamente que si el elemento se configuró recientemente, entonces su tiempo será igual a setAll time. El desafío es hacer que la implicación inversa también se mantenga.
Continuará ....
El código
He escrito esto en Haskell porque ese es el idioma que mejor conozco, pero no es exactamente el lenguaje más natural para el trabajo.
{-# 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
-- The Int in the MutVar is the refresh pointer
data RepArr s a = RepArr (MutVar s (Word, a, Int)) (MVector s (Word,a))
-- Create a fancy array of a given length, initially filled with a given value
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)
Para evitar posibles (raras) pausas de recolección de basura, en realidad es necesario desempaquetar los valores de Int y Word , así como usar vectores sin caja en lugar de los polimórficos, pero no estoy realmente de humor y esta es una tarea bastante mecánica.
Aquí hay una versión en C (completamente no probada):
#include <malloc.h>
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; i<n; i++) {
struct Pair foo = {0,val};
q->vec[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;
}
¿Qué tal un array de tuplas {timestamp, value} , con {timestamp, value} adicional llamado all . Como solo le importa el tiempo relativo de las inserciones, puede usar una id monótonamente creciente para los valores de la marca de tiempo:
type Entry {
int timestamp,
int value
}
type structure {
int id
Entry all
Entry[] array
}
Inicialice todos los campos en 0. Entonces, lo siguiente debería funcionar para usted:
setValue (índice i, valor v):
array[i] = {id++, value}valor getValue (índice i)
if(all.timestamp > array[i].timestamp) return all.value else return array[i].valuesetAll (valor v)
all = {id++, value}
Un problema con este enfoque es que eventualmente se quedará sin identificadores para la marca de tiempo, y puede que se ajuste. Si elige un valor de 64 bits para almacenar marcas de tiempo, entonces esto le brinda 18,446,744,073,709,551,616 inserciones o setAlls antes de que esto suceda. Dependiendo del uso esperado de la estructura de datos, una fase de limpieza de O (n) podría ser apropiada, o podría lanzar una excepción.
Otro problema que podría ser necesario considerar es el multi-threading. Tres problemas obvios:
- si
id++no es atómico y dos subprocesos obtuvieron una nuevaidal mismo tiempo, entonces podría obtener dos entradas con la misma identificación. - si el incremento de id y la asignación de la tupla creada no son atómicas juntas (probablemente no lo sean) y hubo dos insertos simultáneos, entonces podrías obtener una condición de carrera donde gana la identificación anterior.
- si la asignación de la tupla no es atómica, y hay una
insert()al mismo tiempo que unget()entonces podrías terminar en una posición donde tienes decir{new_id, old_value}en la matriz, causando el valor incorrecto para ser devuelto
Si alguno de estos es un problema, la solución más fácil para esto es poner "no a prueba de hilos" en la documentación (hacer trampa). Alternativamente, si no puede implementar los métodos atómicamente en el idioma de su elección, deberá colocar algún tipo de bloqueos de sincronización a su alrededor.
/*
En el momento en que escribo esto, todas las soluciones en esta página duplicarán (o más) la cantidad de espacio requerido para almacenar la matriz. La siguiente solución reduce la cantidad de espacio desperdiciado de Ω (n) a θ (n / w), donde w es el número de bits en una computadora "palabra". En mi máquina, eso es 64.
Esta prosa en esta respuesta está en C comentarios, por lo que puede copiar y pegar esta respuesta textualmente y compilarla con su compilador de C.
*/
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
/*
El problema es admitir valores de lectura y escritura en una matriz en tiempo O (1) junto con escrituras masivas en las que todos los valores de la matriz se escriben a la vez en O (1) tiempo. Esto es posible usando una técnica inventada por Aho, Hopcroft y Ullman, hasta donde yo sé. Presentaré una versión de Gonzalo Navarro, "Inicialización de matriz de tiempo constante en Little Space" .
La idea es mantener tres matrices de metadatos junto con la matriz de datos. También guardamos dos enteros: unset , que es el último valor utilizado en una operación de escritura masiva, y size , una aproximación para el número de valores que se han establecido desde la última escritura masiva. En todo momento, la cantidad de valores distintos escritos desde la última escritura masiva está entre size y w * size .
Las tres matrices de metadatos describen información sobre bloques de valores w en la matriz de datos. Son:
nth: nth [i] es el i-ésimo bloque en el que se escribirá desde la última escritura masivainverse_nth: inverse_nth [i] es el orden en que se escribió el i-ésimo bloque de la matriz, contando desde 0 en la última escritura masiva.bitset: el j-ésimo bit debitset[i]es 1 cuando la celda de la matriz numerada 64 * i + j ha sido escrita desde la última escritura masiva.
bitset[i] e inverse_nth[i] pueden ser inválidos si no soy miembro del conjunto { nth[0] , nth[1] , ..., nth[size-1] }. En otras palabras, inverse_nth[i] y bitset[i] son válidos si y solo si inverse_nth[i] < size y nth[inverse_nth[i]] == i .
En lugar de almacenar tres matrices separadas de la misma longitud, elegí almacenar una matriz, is_set , con tres campos.
*/
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;
/*
Para construir una matriz, necesitamos un valor predeterminado para devolver cuando se lee un valor que nunca se ha escrito.
*/
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);
}
/*
La mayor parte del algoritmo está en escribir y leer los metadatos. Después de IsSet() y Set() (abajo), leer y escribir las matrices es sencillo.
*/
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 parte compleja de leer y escribir es la relación bidireccional entre inverse_nth y nth . Si apuntan el uno al otro en la ubicación i ( is_set[is_set[i].inverse_nth].nth == i ), entonces la ubicación i contiene datos válidos que se escribieron después de la última escritura masiva, siempre 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);
}