পাইথনে O(1) এ Insert, Delete, GetRandom ইম্প্লিমেন্টেশন

মনে করুন আমাদের একটি ডেটা স্ট্রাকচার তৈরি করতে হবে যা নিচের সকল অপারেশন গড়ে O(1) টাইমে সাপোর্ট করবে:

insert(val) — যদি val সেটে না থাকে তবে ইনসার্ট করবে।
remove(val) — যদি val সেটে থাকে তবে রিমুভ করবে।
getRandom() — বর্তমান সেটের এলিমেন্টগুলোর মধ্যে থেকে যেকোনো একটি র‍্যান্ডমলি রিটার্ন করবে। প্রতিটি এলিমেন্টের সমান প্রোবাবিলিটি থাকবে।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (হ্যাশ ম্যাপ + ডাইনামিক অ্যারে):

ইনিশিয়ালাইজেশনে: parent ম্যাপ এবং elements অ্যারে ডিফাইন করুন।
insert() ফাংশন val নেবে:
- যদি val parent-এ না থাকে বা parent[val] == 0, তবে elements-এ অ্যাপেন্ড করুন, parent[val] := 1, এবং true রিটার্ন করুন।
false রিটার্ন করুন।
remove() মেথড val নেবে:
- যদি val parent-এ না থাকে বা parent[val] == 0, তবে false রিটার্ন করুন।
- parent[val] := 0
- index := elements-এ val-এর ইনডেক্স
- যদি index != len(elements) - 1:
  - temp := elements[-1]
  - elements[-1] := val
  - elements[index] := temp
- elements.pop() (লাস্ট এলিমেন্ট ডিলিট)
getRandom() মেথড elements অ্যারেতে থাকা যেকোনো র‍্যান্ডম ভ্যালু রিটার্ন করবে।

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

import random

class RandomizedSet(object):
    def __init__(self):
        self.present = {}
        self.elements = []

    def insert(self, val):
        if val not in self.present or self.present[val] == 0:
            self.elements.append(val)
            self.present[val] = 1
            return True
        return False

    def remove(self, val):
        if val not in self.present or self.present[val] == 0:
            return False
        self.present[val] = 0
        index = self.elements.index(val)
        if index != len(self.elements) - 1:
            temp = self.elements[-1]
            self.elements[-1] = val
            self.elements[index] = temp
        self.elements.pop()
        return True

    def getRandom(self):
        return random.choice(self.elements)

ob = RandomizedSet()
print(ob.insert(1))
print(ob.remove(2))
print(ob.insert(2))
print(ob.getRandom())
print(ob.remove(1))
print(ob.insert(2))
print(ob.getRandom())

ইনপুট

ক্লাস ইনিশিয়ালাইজ করুন, তারপর insert(), remove(), getRandom() ফাংশন কল করুন। ইমপ্লিমেন্টেশন দেখুন।

আউটপুট

True
False
True
2
True
False
2