GetRandom ကိုဖျက်ပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အတည်ပြုပါ အမေဇုံ AppDynamics Apple ဘလွန်းဘာ့ဂ် Citadel Facebook က Google Microsoft က Nvidia က Oracle က Quera တွစ်တာ နှစ်ဦးက Sigma Yandex Zillow
အခင်းအကျင်း ပုံစံ hash

Insert Delete GetRandom ပြproblemနာတွင်အောက်ပါလုပ်ငန်းများအားလုံးကိုထောက်ပံ့သောဒေတာဖွဲ့စည်းပုံကိုဒီဇိုင်းဆွဲရန်လိုအပ်သည် ပျမ်းမျှအား အို (၁) အချိန်။

  1. ထည့်သွင်း (val): မရှိသေးပါလျှင်အစုတစ်ခု item val ထည့်သွင်း။
  2. ဖယ် (Val): ပစ္စုပ္ပန်လျှင်အစုကနေ item ကို Val ဖယ်ရှားပေးသည်။
  3. getRandom: current element တွေထဲက random element တစ်ခုကို return ပြန်ပေးတယ်။ တစ်ခုချင်းစီကိုဒြပ်စင်ရှိရမည် အလားတူဖြစ်နိုင်ခြေ ပြန်လာ၏။

မေးခွန်းသည်အို (၁) တွင်သွင်းခြင်းနှင့်ဖျက်ခြင်းကိုပြုလုပ်ရန်လိုအပ်သောကြောင့်ကျွန်ုပ်တို့မြေပုံလိုအပ်သည်။ getRandom () method အတွက်တော့ index-based data structure ကိုကျွန်တော်တို့ array တစ်ခုလိုပါတယ်။ ဒါကြောင့် index element တစ်ခုကိုကျပန်းကျပန်းရွေးလို့ရပါတယ်။

ထို့ကြောင့်လုပ်ဆောင်ချက်သုံးခုကိုရရှိရန်ကျွန်ုပ်တို့သည်မြေပုံနှင့်ခင်းကျင်းမှုနှစ်ခုလုံးကိုအတူတကွသုံးနိုင်သည်။ ဘယ်လိုကြည့်ရအောင်

အရေးကြီးအချက်များ

  1. အတွက်ထည့်သွင်း အခင်းအကျင်း နောက်ကျောမှာပြုသောအမှုလျှင်အို (1) ဖြစ်ပါတယ်။
  2. ဒြပ်စင်နောက်ကျောကနေဖယ်ရှားလျှင်အခင်းကျင်းအတွက်ဖျက်ပစ် O (1) ဖြစ်ပါတယ်။

ဒေတာဖွဲ့စည်းပုံကိုအသုံးပြုခဲ့သည်

Map M (တန်ဖိုးသိုလှောင်ရန်၊ အညွှန်းကိန်းအတွဲ)

လက်ရှိဒြပ်စင်များသိမ်းဆည်းရန် Vector V

ထည့်သွင်းမှုအတွက် Algorithm

  1. ပေးထားသောဒြပ်စင်သည်မြေပုံတွင်ရှိမရှိစစ်ဆေးပါ။
    • ပစ္စုပ္ပန်လျှင်, မှားယွင်းသောပြန်လာပါ
    • ကျန် -
      • ပေးထားသော element ကို vector V ၏အဆုံးမှာထည့်ပါ
      • ပေးထားသောဒြပ်စင်ကိုထည့်ပါ။ ၎င်းသည် M ကိုညွှန်ပြရန်အညွှန်းဖြစ်သည်
      • ပြန်လာမှန်

ဖျက်မှုအတွက် Algorithm

  1. ပေးထားသောဒြပ်စင်သည်မြေပုံတွင်ရှိမရှိစစ်ဆေးပါ။
    • ရှိလျှင်,
      • ပေးထားသော element နှင့်နောက်ဆုံး element တွင်ရှိသောတန်ဖိုးများကိုလဲပါ (အညွှန်းကိုမြေပုံ M ဖြင့်ရှာနိုင်သည်)
      • မြေပုံကို M [last_element] = M [given_element] အဖြစ်အဆင့်မြှင့်
      • အားနည်းချက်ကို၏နောက်ဆုံးဒြပ်စင်ဖျက်ပစ်ပါ။
      • ပေးထားသောဒြပ်စင်ကိုမြေပုံမှဖျက်ပါ
      • ပြန်လာမှန်
    • အခြားအရာ, မှားယွင်းသောပြန်လာပါ။

getRandom အတွက် Algorithm

  1. ကျပန်းညွှန်းကိန်းများကိုရွေးပါ
  2. vector အားနည်းချက်ကို၏အရွယ်အစား 0 င၏အကွာအဝေး။
  3. အားနည်းချက်ကို V. အတွက်အညွှန်းကိန်းမှာပစ္စုပ္ပန်ပြန်လာဒြပ်စင်

Insert DelR GetRandom အတွက်အကောင်အထည်ဖော်ခြင်း

Insert Delete GetRandom အတွက် C ++ Program

#include<bits/stdc++.h>
using namespace std;

class RandomizedSet {
public:
    vector<int> v;
    map<int,int> m;
    RandomizedSet() {
    }
    
    //function for insertion of given value
    bool insert(int val) {
        if(m.find(val)==m.end()){
            v.push_back(val);
            m.insert({val,v.size()-1});
            return true;
        }
        
        return false;
    }
    
    //function for removal of given value
    bool remove(int val) {
        if(m.find(val)!=m.end()){
            int last = v.back();
            m[last]=m[val];
            v[m[val]]=last;
            v.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    //function to get a random element 
    int getRandom() {
        int ran = rand()%v.size();
        return v[ran];
    }
};

int main()
{
    RandomizedSet* r = new RandomizedSet();
    r->insert(4);
    r->insert(5);
    cout<<r->getRandom()<<" ";
    r->remove(5);
    cout<<r->getRandom()<<" ";
    return 0;
}
5 4

Insert Delete GetRandom အတွက် JAVA အစီအစဉ်

import java.util.*;
public class Main
{
    public static class RandomizedSet {
    
        HashMap<Integer, Integer> m;
        List<Integer> v;
        
        //constructor
        public RandomizedSet() {
            m = new HashMap<>();
            v = new ArrayList<>();
        }
        
        //function for insertion of given value
        public boolean insert(int val) {
            if(m.containsKey(val)) 
                return false;
            v.add(val);
            m.put(val,v.size()-1);
            return true;
        }
        
        //function for removal of given value
        public boolean remove(int val) {
            if(m.containsKey(val)){
                int last = v.get(v.size()-1);
                m.put(last,m.get(val));
                v.set(m.get(val),last);
                v.remove(v.size()-1);
                m.remove(val);
                return true;
            }
            return false;
        }
        
        //function to get a random element 
        public int getRandom() {
            int ran = (int)(Math.random()%v.size());
            return v.get(ran);
        }
    }
  public static void main(String[] args) {
      RandomizedSet obj = new RandomizedSet();
        obj.insert(6);
        obj.insert(5);
        obj.insert(3);
        System.out.print(obj.getRandom()+" ");
        obj.remove(5);
        System.out.print(obj.getRandom()+" ");
        System.out.print(obj.getRandom()+" ");
  }
}
6 6 6

ကိုးကား