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

ধরুন আমাদের একটি স্ন্যাপশট অ্যারে প্রয়োগ করতে হবে যা নিম্নলিখিত ইন্টারফেসগুলিকে সমর্থন করে -

• SnapshotArray(int length) এটি প্রদত্ত দৈর্ঘ্যের সাথে অ্যারের মতো ডেটা স্ট্রাকচার শুরু করবে। প্রাথমিকভাবে, প্রতিটি উপাদান সমান 0।

• set(index, val) এটি প্রদত্ত সূচকে উপাদানটিকে val এর সমান সেট করবে।

• snap() অ্যারের একটি স্ন্যাপশট নেবে এবং snap_id প্রদান করবে:মোট কতবার আমরা snap() মাইনাস 1 বলেছি।

• get(index, snap_id) এটি প্রদত্ত সূচীতে মান ফিরিয়ে দেবে, যখন আমরা প্রদত্ত snap_id দিয়ে স্ন্যাপশট নিয়েছিলাম

সুতরাং যদি অ্যারের আকার 2 হয়, এটি [0, 5] ব্যবহার করে সেট করা হয়, তারপরে আমরা একটি স্ন্যাপ নিই, এটি 0 রিটার্ন করবে, তারপর [0, 6] ব্যবহার করে সেট করুন এবং get(0, 0), এটি ফিরে আসবে। ৫.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আরম্ভ করার পদ্ধতিটি হবে −

  এর মত

• বর্তমান :=0

• arr :=দৈর্ঘ্যের একটি অ্যারে + 2d অ্যারের 1 সংখ্যা [[0, 0]]

• সেট() পদ্ধতি −

  এর মত হবে

• temp :=arr[index]

  এর শেষ উপাদান

• যদি temp[0] =বর্তমান, তাহলে arr[index] এর শেষ উপাদান থেকে সূচক 1 এর উপাদান :=val

• অন্যথায় arr[index]

  -এ [current, val] ঢোকান

• snap() পদ্ধতিটি হবে like−

• কারেন্ট 1 দ্বারা বাড়ান, গণনার চেয়ে কম ফেরত দিন

• get() পদ্ধতি −

  এর মত হবে

• temp :=arr[index], low :=0, high :=temp-এর দৈর্ঘ্য - 1

• যখন কম <উচ্চ

  • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2

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

• রিটার্ন টেম্প[লো, 1]

উদাহরণ(পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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]
      #print(temp)
      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))

ইনপুট

Initialize the array using 3, then call set(0,5), snap(), set(0,6), get(0, 0)

আউটপুট

0
5