data structures شرح مقابلة المقابلة: هيكل البيانات لتعيين جميع القيم في O(1)




data structures شرح (9)

بالنظر إلى أسئلة المقابلة على الإنترنت ، واجهت السؤال التالي.

وصف بنية البيانات التي لها getValue (int index) و setValue (int index و int value) و setAllValues ​​(int value) كلها O (1).

على الرغم من أن الصفيف جيد بما فيه الكفاية للعمليات الأولى والثانية التي يجب إجراؤها في O (1) ، ما الذي يمكن اقتراحه للثالث (setAllValues)؟


ماذا عن array من tuples {timestamp, value} ، مع {timestamp, value} تسمى all . نظرًا لأنك لا تهتم إلا بالوقت النسبي للإدراج ، يمكنك استخدام id متزايد بمرور الوقت لقيم الطابع الزمني:

type Entry {
  int timestamp, 
  int value
}

type structure {
    int     id
    Entry   all
    Entry[] array
}

تهيئة جميع الحقول إلى 0. ثم يجب أن يعمل ما يلي:

  • setValue (index i، value v):

    array[i] = {id++, value}
    
  • قيمة getValue (مؤشر ط)

    if(all.timestamp > array[i].timestamp) return all.value
    else return array[i].value
    
  • setAll (القيمة v)

    all = {id++, value}
    

تكمن المشكلة في هذا الأسلوب في أنه ستنفد في النهاية من معرفات للطابع الزمني ، وقد تلتف حولها. إذا اخترت قيمة 64 بت لتخزين الطوابع الزمنية ، فهذا يمنحك 18،446،744،073،709،551،616 إدخال أو setAlls قبل حدوث ذلك. اعتمادًا على الاستخدام المتوقع لبنية البيانات ، قد تكون مرحلة تنظيف O (n) مناسبة ، أو يمكنك فقط طرح استثناء.

مسألة أخرى قد تحتاج إلى النظر فيها هي متعددة الخيوط. ثلاث مشاكل واضحة:

  • إذا كانت id++ غير ذرية واثنين من مؤشرات الترابط الحصول على id جديد في نفس الوقت ثم يمكنك الحصول على إدخالين بنفس معرف.
  • إذا لم تكن الزيادة في رقم التعريف وتخصيص الصف المبني معًا ذريًا (قد لا يكونان على الأرجح) وكان هناك إدخالان متزامنان ، فيمكنك الحصول على حالة سباق حيث يفوز المعرّف القديم.
  • إذا كان تعيين الصف ليس ذريًا ، وكان هناك insert() في نفس وقت get() فقد ينتهي بك الأمر في وضع حيث يمكنك قول {new_id, old_value} في المصفوفة ، مما يسبب قيمة خاطئة ليتم إرجاعها.

إذا كان أي من هذه المشاكل ، الحل الأسهل المطلق لهذا هو وضع "غير آمن موضوع" في الوثائق (الغش). بدلاً من ذلك ، إذا لم تتمكن من تنفيذ الأساليب بشكل اختياري بلغتك المفضلة ، فستحتاج إلى وضع نوع من أقفال المزامنة من حولها.


هذه هي إجابتي في Java (لست متأكدًا تمامًا من الصيغة). لقد قمت بمزامنة الوظائف المتزامنة من أجل تجنب وضع يكون فيه changeT و defChangeT متساويين.

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;
  }
}

ماذا عن مجموعة من المؤشرات لقيمة واحدة مشتركة؟ قم بتعيين القيمة ، وستشير جميع المراجع إلى القيمة التي تم تغييرها في O (1) ..


فيما يتعلق بإجابة تيموثي جون:

تكمن المشكلة في هذا الأسلوب في أنه ستنفد في النهاية من معرفات للطابع الزمني ، وقد تلتف حولها. إذا اخترت قيمة 64 بت لتخزين الطوابع الزمنية ، فهذا يمنحك 18،446،744،073،709،551،616 إدخال أو setAlls قبل حدوث ذلك. اعتمادًا على الاستخدام المتوقع لبنية البيانات ، قد تكون مرحلة تنظيف O (n) مناسبة ، أو يمكنك فقط طرح استثناء.

هذا هو بالضبط السيناريو الأسوأ الذي يجعل هذا الحل O (n) أيضًا ، وليس O (1). هذا التزاوج ، على الرغم من أنه يوفر الكثير من عمليات الإدراج المحتملة لـ O (n) ، لا يزال في كفاءة O (n).


/*

في الوقت الذي أكتب فيه هذا ، ستضاعف جميع الحلول في هذه الصفحة (أو أكثر) مقدار المساحة المطلوبة لتخزين الصفيف. يقلل الحل التالي من مقدار المساحة المهدورة من Ω (n) إلى θ (n / w) ، حيث w هو عدد البتات في "كلمة" الكمبيوتر. على جهازي ، هذا هو 64.

هذا النثر في هذه الإجابة هو في التعليقات C ، حتى تتمكن من نسخ ولصق هذه الإجابة حرفيا وتجميعها مع مترجم C الخاص بك.

*/

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

/*

تكمن المشكلة في دعم قيم القراءة والكتابة في صفيف في وقت O (1) مع عمليات الكتابة المجمعة حيث يتم كتابة جميع القيم في الصفيف مرة واحدة في زمن O (1). هذا ممكن باستخدام تقنية اخترعها Aho ، Hopcroft و Ullman ، بقدر ما أعرف. سأقدم نسخة بسبب غونزالو نافارو ، "التهيئة لصف الوقت الثابت في الفضاء الصغير" .

الفكرة هي الاحتفاظ بثلاث صفائف بيانات وصفية مع مصفوفة البيانات. نحن أيضًا نحتفظ بعمليتين unset : unset ، وهي القيمة الأخيرة المستخدمة في عملية الكتابة المجمعة ، size ، وتقريبًا لعدد القيم التي تم تعيينها منذ آخر كتابة مجمعة. في جميع الأوقات ، يكون عدد القيم المميزة المكتوبة منذ آخر كتابة مجمعة بين size w *.

تصف صفائف البيانات الوصفية الثلاثة معلومات حول كتل قيم w في مصفوفة البيانات. هم انهم:

  • nth : nth [i] هو المقطع الفريد ith المراد كتابته منذ آخر كتابة مجمعة

  • inverse_nth : inverse_nth [i] هو الترتيب الذي تم فيه كتابة كتلة ith للمصفوفة ، مع احتسابها من 0 في آخر كتابة مجمعة.

  • bitset : بت bitset[i] من bitset[i] هو 1 عندما تمت كتابة الخلية الصفيف المرقمة 64 * i + j إلى منذ آخر كتابة مجمعة.

bitset[i] و inverse_nth[i] إذا لم أكن عضوًا في المجموعة { nth[0] ، nth[1] ، ...، nth[size-1] }. وبعبارة أخرى ، يكون inverse_nth[i] و bitset[i] صالحين فقط إذا كان inverse_nth[i] < size and nth[inverse_nth[i]] == i .

بدلاً من تخزين ثلاث صفائف منفصلة من نفس الطول ، اخترت تخزين صفيف واحد ، is_set ، مع ثلاثة حقول.

*/

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;

/*

لإنشاء صفيف ، نحتاج إلى قيمة افتراضية للعودة عند قراءة قيمة لم تتم كتابتها أبدًا.

*/

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);
}

/*

الجزء الأكبر من الخوارزمية مكتوب وقراءة البيانات الوصفية. بعد IsSet() و Set() (أدناه) ، قراءة و كتابة صفائف مباشرة.

*/

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;
}

/*

الجزء المعقد في القراءة والكتابة هو العلاقة ثنائية الاتجاه بين inverse_nth و nth . إذا أشار كل منهما إلى الآخر في الموقع i ( is_set[is_set[i].inverse_nth].nth == i ) ثم الموقع i يحتوي على بيانات صالحة تمت كتابتها بعد آخر كتابة مجمعة ، طالما كان 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);
}

الحل الصحيح في 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;
    }
}

والاختبار:

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();
}

لقد سُئلت هذا السؤال مؤخراً في مقابلة. توصلت مع تطبيق جدول التجزئة. من شأنه أن يحل مشكلة نفاد قيم الطابع الزمني ولكن يجب تنفيذ ميزة سلامة الخيط (ربما باستخدام تقنيات التهيئة البطيئة)

دعنا نقول في صفنا لدينا متغير _DefaultValue خاص للحفاظ على قيمة افتراضية ولدينا أيضا hashtable الخاص أو القاموس _hashtable . يمكن لـ SetAllValues فقط تعيين _defaultValue يساوي القيمة التي تم تمريرها وتم تهيئة _hashtable / set إلى hashtable جديد وتجاهل أي مرجع لجدول التجزئة القديم. يجب فقط SetValue إضافة قيمة جديدة إلى _hashtable أو تحديث القيمة إذا كان المفتاح (أو الفهرس) موجود بالفعل في _hashtable . يجب أن تحقق GetValue ما إذا كان المفتاح (أو الفهرس) موجودًا في _hashtable ، ثم أعده ، وإلا فأرجع القيمة المخزنة في _defaultValue .

هذا هو جوابي الأول على . أنا كسول قليلا في كتابة التعليمات البرمجية. ربما سوف تعدل الجواب قريبا.

أومأ المحاور بنعم إلى هذا الحل لكنه أصر على تنفيذه دون استخدام حاشية. أعتقد أنه كان يطلب مني أن أعطي مقاربة مماثلة لإجابة تيموثي. ولم أتمكن من الحصول عليه في تلك اللحظة :(. على أي حال ، هتافات!

تحرير: نشر التعليمة البرمجية (في 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;
        }
    }
}

حصلت على نفس السؤال في واحدة من المقابلات الفنية.
هنا هو تطبيق جافا جاهز للاستخدام الكامل بما في ذلك حالات الاختبار.

والفكرة الرئيسية هي الحفاظ على قيمة setAll() في متغير خاص (مثل joker ) ثم تتبع تغيير هذه القيمة بطريقة مناسبة.

للحفاظ على الرمز نظيفًا ، تم إلغاء بعض مفاتيح الوصول.

فئة العقد :

import java.time.LocalDate;

class Node {

    int value;
    LocalDate jokerSetTime;

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

فئة DS :

class DS {

    Node[] arr;

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

فئة 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);
    }
}

الطبقة الرئيسية :

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);
    }
}

تحديث:
تم تحديث الرمز. لم يأخذ التنفيذ السابق في الاعتبار الحالة عند setAll() مرتين في صف بنفس القيمة وتتبعه set(x) ، get(y) ، على سبيل المثال: setAll(100) ، set(3, 1) ، setAll(100) ، set(5, 3) ، get(3) .

تمت إضافة استخدام setAll() الطابع الزمني للسماح بالتمييز بين setAll() مختلفة setAll() متطابقة.

سكرتير خاص هذا التطبيق ليس خيط آمن.


بايثون سبيل المثال

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




data-structures