ڈیٹا سٹرکچر ڈیزائننگ


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون DBOI فیس بک فانٹکس فورکائٹس
ڈیٹا سٹرکچر کی تھیوری اور

ڈیٹا سٹرکچر ڈیزائننگ کی سماعت ، بہت سارے لوگ خود ہی عنوان دیکھ کر بھاگنا چاہتے ہیں۔ جو لوگ مجھے جانتے ہیں وہ جانتے ہیں کہ میں اس وقت تک نہیں جا رہا جب تک میں مکمل طور پر اس تصور کی وضاحت نہیں کرتا ہوں۔ آج کے راستے میں ایک مسئلہ اور کچھ نظریات سیکھنے کے لئے سفر کے ساتھ میرے ساتھ سفر کریں!

ہم میں سے بہت سے لوگوں نے اس اصطلاح پر چھید کر دی ہو گی “CRUD ”۔ان لوگوں کے لئے جو اسے نہیں جانتے ، CRUD کا مطلب تخلیق پڑھنے کی تازہ کاری کو حذف کرنا ہے۔

مثال کے طور پر

آپ تخلیق کر رہے ہیں a ڈیٹا بیس آپ کے تمام پسندیدہ فنکاروں کی

سی بنائیں

  • ہم کہتے ہیں کہ آپ نے ایک نیا فنکار دریافت کیا ہے اور اسے ڈیٹا بیس میں رکھنا چاہتے ہیں۔ آپ اندراج پیدا کریں گے۔

آر ریڈ

  • آپ کسی پرانے فنکار کو سننا چاہتے ہیں۔ اس طرح ، آپ ڈیٹا بیس سے باہر ڈیٹا انٹری پڑھ رہے ہوں گے۔

انڈر اپڈیٹ

  • آپ نے غلطی سے آر اینڈ بی کی بجائے ریحانہ کو پاپ کے نیچے ڈال دیا اور اپنی غلطی کو درست کرنے کی ضرورت ہے۔ اس طرح ، آپ تازہ کاری کریں گے۔

ڈی - ڈیلیٹ کریں

  • آپ کو اب ٹوری کیلی سننا پسند نہیں ہے۔ اس طرح آپ اندراج کو حذف کردیتے ہیں۔

آج کے مسئلے میں ، ہم ہیں "ڈیٹا کا ڈھانچہ ڈیزائن کریں" جو داخل ، حذف کریں ، اور گیٹ رینڈم کے طریقے انجام دیتا ہے۔

داخل کرنا:

موجودہ ڈیٹا ڈھانچے میں عنصر شامل کرنا

ہٹانا:

چونکہ ہم ڈیٹا سٹرکچر کو ڈیزائن کر رہے ہیں ، ہم عنصر کو ہٹا رہے ہیں صرف اس صورت میں جب یہ موجود ہے۔

گیٹ رینڈم:

میں ایک بے ترتیب عنصر کو واپس کر رہا ہوں اس پر غور کر کے کہ موجودہ خصوصیات میں سے کسی کو منتخب کرنے کا امکان ایک جیسا ہے۔

ڈیٹا ڈھانچہ جو استعمال کیا جاسکتا ہے

کارروائیوں کو انجام دینے کے طریقے کے بارے میں سوچنے کی کوشش کرتے ہوئے اعداد و شمار کے بہت سارے ڈھانچے پر غور کیا جاسکتا ہے۔ ہم عناصر کو موثر انداز میں شامل کرنے کے لئے ارے یا لنکڈ لسٹ کا استعمال کرسکتے ہیں۔ تاہم ، لنکڈ لسٹ اور اریز دونوں او (1) وقت میں ہٹانے کی کارروائی کرنے سے قاصر ہیں جو ہمیں ڈیٹا کے دوسرے ڈھانچے کی طرف لے جاتا ہے۔ ہیش نقشہ جات

جبکہ ہیش نقشہ جات اعداد و شمار کو شامل کرسکتے ہیں اور انڈیکس کے مطابق بے ترتیب ڈیٹا حاصل کرنا ایک ہوا کا جھونکا بن جائے گا۔ تاہم ، کچھ اقدار کے ساتھ ڈیٹا پوائنٹس کو ہٹانے کی کوشش کرنا ایک خاص کام بن جائے گا۔

ضرورت ایجاد کی ماں ہے اور ہمارے حالات ہمیں ایک نئے ہائبرڈ کی طرف لے جاتے ہیں

دیئے گئے نقطہ نظر میں ہم ایک ہائبرڈ لیتے ہیں

ہش میپ + ارے لسٹ (کوئی بھی لچکدار ذخیرہ فریم ورک استعمال کیا جاسکتا ہے یعنی سیٹ ، ویکٹر وغیرہ)

مجھے تمام طریقوں کا خلاصہ پیش کرنے دو اور ہم ان حالات کو پورا کرنے کے لئے کس طرح ان کا ڈیزائن تیار کرسکتے ہیں

طریقہ داخل کریں

  • ہم اپنی اقدار کو صف اور ہش میپ دونوں میں داخل کرتے ہیں
  • اگر قیمت پہلے سے موجود ہے تو ہم غلط کو واپس کرتے ہیں

طریقہ کو ہٹا دیں

  • یہ وہ جگہ ہے جہاں ارای لسٹ ہمیں حقیقی مدد فراہم کرتی ہے
    • ہم حاصل کرنے کے طریقہ کار کے ذریعہ ارے لسٹ سے عنصر کی پوزیشن حاصل کرتے ہیں
    • ارے لسٹ میں عنصر کو آخری پوزیشن پر سیٹ کرنے کے ساتھ
    • آخری سے عنصر کو ہٹانے والے عنصر کی پوزیشن پر ڈالا جاتا ہے
    • اس کے بعد عنصر کو ہیش میپ اور ارا لسٹ دونوں سے ہٹا دیا جاتا ہے
    •  سائز کم ہوا ہے
  • اگر عنصر موجود نہیں ہے تو ہم غلط کو لوٹاتے ہیں

گیٹ رینڈم کا طریقہ

  • ہم جاوا اور C ++ میں ان بلٹ بے ترتیب طریقہ استعمال کرتے ہیں تاکہ بے ترتیب نمبر تیار کیا جاسکے
  • ہم عنصر کو اس پوزیشن پر لوٹاتے ہیں
ڈیٹا سٹرکچر ڈیزائننگ
ہائبرڈ ڈیٹا کا ڈھانچہ جس مسئلے کے لئے ڈیزائن کیا گیا ہے

دیئے گئے ڈیٹا سٹرکچر کے لئے جاوا کوڈ

class RandomizedSet
{

    /** Initialize your data structure here. */
    HashMap<Integer,Integer>hash;
    ArrayList<Integer>store;
    java.util.Random rand=new java.util.Random();
    public RandomizedSet()
    {
     hash=new HashMap<Integer,Integer>();
     store=new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) 
    {
        if(hash.containsKey(val))
            return false;
        else
        {
        hash.put(val,store.size());
        store.add(val);   
        }
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) 
    {
       if(!hash.containsKey(val))
           return false;
        else
        {
        int cur_pos=store.get(val);
        int last=store.get(store.size()-1);
        store.set(cur_pos,last);
        hash.put(last,cur_pos);
        store.remove(val);
        hash.remove(store.size()-1);   
        }
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() 
    {
       return store.get(rand.nextInt(store.size())); 
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

دیئے گئے ڈیٹا سٹرکچر کے لئے C ++ کوڈ

#include<time.h>
class RandomizedSet {
public:
    /** Initialize your data structure here. */
    map<int,int>hash;
    vector<int>store;
    int size=0;
    RandomizedSet() {
        size=0;
        srand(time(0));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(hash.find(val)!=hash.end())
            return false;
        if (store.size() == size)
            store.push_back(val);
        else
        store[size]=val;
        hash.insert({val,size});
        size++;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        auto srch=hash.find(val);
        if(hash.find(val)==hash.end())
            return false;
        int ele=(*srch).second;
        if(size>1)
        {
            store[ele]=store[size-1];
            (*hash.find(store[size-1])).second=ele;
        }
        size--;
        hash.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        if(size==1)
            return store[0];
        return store[rand()%size];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
[null,true,false,true,2,true,false,2]

دیئے گئے ڈیٹا سٹرکچر کے لئے وقت کی پیچیدگیاں

داخل کریں: O (1) ہش میپ اور ارے لسٹ دونوں کے لئے O (1)

گیٹ رینڈم: O (1) .ایسا ہیش میپ کو ڈیٹا واپس کرنے میں O (1) وقت لگتا ہے

حذف کریں: O (n)

ہم O (1) وقت میں ہیش میپ سے ڈیٹا کو حذف کردیتے ہیں تاہم او (N) وقت کیلئے پیشگی کارروائیوں کا مطالبہ کرتا ہے۔ چونکہ کسی ارا لسٹ میں انڈیکس حاصل کرنے کا آپریشن O (n) ہے۔

حوالہ جات