পাইথনে স্ন্যাপশট অ্যারে ইম্প্লিমেন্টেশন

মনে করুন আমাদের একটি SnapshotArray ইম্প্লিমেন্ট করতে হবে যা নিচের ইন্টারফেসগুলো সমর্থন করে:

• SnapshotArray(int length) — এটি দেওয়া লেন্থের সাথে অ্যারে-লাইক ডেটা স্ট্রাকচার ইনিশিয়ালাইজ করবে। প্রাথমিকভাবে প্রতিটি এলিমেন্ট ০।

• set(index, val) — এটি দিয়ে गये ইনডেক্সের এলিমেন্টকে val সেট করবে।

• snap() — এটি অ্যারেটি একটি স্ন্যাপশট নেবে এবং snap_id রিটার্ন করবে: snap() কল করা হয়েছে সে সংখ্যা মাইনাস ১।

• get(index, snap_id) — এটি দিয়ে गये ইনডেক্সের ভ্যালু রিটার্ন করবে, সেটি সময়ে যখন আমরা দেওয়া snap_id-এর স্ন্যাপশট নেয়েছিলাম।

উদাহরণস্বরূপ, অ্যারে সাইজ ২, set(0, 5) দিয়ে সেট করা হয়, তারপর snap() কল করলে এটি ০ রিটার্ন করবে, তারপর set(0, 6), এবং get(0, 0) কল করলে এটি ৫ রিটার্ন করবে।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব:

• ইনিশিয়ালাইজ মেথড হবে নিচের মতো:

  • current := 0

  • arr := length + 1 সংখ্যক 2D অ্যারে [[0, 0]]

• set() মেথড হবে নিচের মতো:

  • temp := arr[index]-এর লাস্ট এলিমেন্ট

  • যদি temp[0] == current, তবে arr[index]-এর লাস্ট এলিমেন্টের ইনডেক্স ১-এ val সেট করুন

  • অন্যথায় [current, val] আপেন্ড করুন arr[index]-এ।

• snap() মেথড হবে নিচের মতো:

  • current ১ বাড়ান, count - 1 রিটার্ন করুন

• get() মেথড হবে নিচের মতো:

  • temp := arr[index], low := 0, high := len(temp) - 1

  • while low < high

    • mid := low + (high - low) / 2

    • যদি temp[mid][0] <= snap_id, তবে low := mid, অন্যথায় high := mid - 1

  • return temp[low][1]

উদাহরণ (Python)

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

class SnapshotArray(object):
    def __init__(self, length):
        self.current = 0
        self.arr = [[[0,0]] for i in range(length+1)]

    def set(self, index, val):
        temp = self.arr[index][-1]
        if temp[0] == self.current:
            self.arr[index][-1][1] = val
        else:
            self.arr[index].append([self.current, val])

    def snap(self):
        self.current += 1
        return self.current - 1

    def get(self, index, snap_id):
        temp = self.arr[index]
        low = 0
        high = len(temp) - 1
        while low < high:
            mid = low + (high - low + 1) // 2
            if temp[mid][0] <= snap_id:
                low = mid
            else:
                high = mid - 1
        return temp[low][1]

ob = SnapshotArray(3)
ob.set(0, 5)
print(ob.snap())
ob.set(0, 6)
print(ob.get(0, 0))

ইনপুট

অ্যারে ইনিশিয়ালাইজ করুন 3 দিয়ে, তারপর set(0,5), snap(), set(0,6), get(0, 0) কল করুন

আউটপুট

0
5