পাইথনে লগ স্টোরেজ সিস্টেম ডিজাইন করা

সমস্যা বিবরণ

একটি লগ সিস্টেম ডিজাইন করতে হবে যা প্রতিটি লগের ইউনিক ID এবং টাইমস্ট্যাম্প সংরক্ষণ করবে। টাইমস্ট্যাম্প ফরম্যাট: Year:Month:Day:Hour:Minute:Second (যেমন: 2019:01:01:23:59:59)। দুটি ফাংশন ইমপ্লিমেন্ট করতে হবে:

1. put(id, timestamp) — লগ সংরক্ষণ করুন
2. retrieve(start, end, granularity) — নির্দিষ্ট গ্র্যানুলারিটি (Year, Month, Day, Hour, Minute, Second) অনুযায়ী টাইম রেঞ্জের লগ ID গুলো রিটার্ন করুন

উদাহরণ

put(1, "2019:01:01:23:59:59")
put(2, "2019:01:01:22:59:59")
put(3, "2018:01:01:00:00:00")

retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Year") 
# আউটপুট: [1, 2, 3] (২০১৮ ও ২০১৯ সালের সব লগ)

retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Hour")
# আউটপুট: [1, 2] (লগ ৩ বাদ পড়ে যায়)

সমাধানের কৌশল

গ্র্যানুলারিটি অনুযায়ী টাইমস্ট্যাম্পের প্রিফিক্স দিয়ে তুলনা করা হয়। স্ট্রিং স্লাইসিং ব্যবহার করে সহজে সমাধান করা যায়।

গ্র্যানুলারিটি ম্যাপিং

পাইথন কোড

class LogSystem(object):
    def __init__(self):
        self.logs = []  # (id, timestamp) টাপলের লিস্ট
    
    def put(self, id, timestamp):
        self.logs.append((id, timestamp))
    
    def retrieve(self, s, e, gra):
        # গ্র্যানুলারিটি অনুযায়ী স্লাইস ইনডেক্স
        index_map = {
            'Year': 5, 'Month': 8, 'Day': 11,
            'Hour': 14, 'Minute': 17, 'Second': 20
        }
        index = index_map[gra]
        
        start = s[:index]
        end = e[:index]
        
        # ফিল্টার করুন
        return [tid for tid, timestamp in self.logs 
                if start <= timestamp[:index] <= end]

# টেস্ট
ob = LogSystem()
ob.put(1, "2019:01:01:23:59:59")
ob.put(2, "2019:01:01:22:59:59")
ob.put(3, "2018:01:01:00:00:00")

print(list(ob.retrieve("2018:01:01:01:01:01", 
                       "2019:01:01:23:00:00", "Year")))   # [1, 2, 3]
print(list(ob.retrieve("2018:01:01:01:01:01", 
                       "2019:01:01:23:00:00", "Hour")))   # [1, 2]

জটিলতা বিশ্লেষণ

• Put: O(1) — শুধু অ্যাপেন্ড
• Retrieve: O(N × L) — N = লগ সংখ্যা, L = টাইমস্ট্যাম্প দৈর্ঘ্য
• স্থান জটিলতা: O(N) — লগ সংরক্ষণের জন্য

অপ্টিমাইজেশন সুযোগ

• বড় ডেটাসেটের জন্য ট্রি (BST) বা সর্টেড কন্টেইনার ব্যবহার করলে Retrieve O(log N + K) এ সম্ভব
• টাইমস্ট্যাম্পকে ইন্টিজারে কনভার্ট করে বাইনারি সার্চ করা যাবে

মূল বিষয়বস্তু

• স্ট্রিং স্লাইসিং দিয়ে টাইম কোম্পারিজন
• গ্র্যানুলারিটি ভিত্তিক ফিল্টারিং
• সিম্পল ডিজাইন, রিয়েল-ওয়ার্ল্ড লগ সিস্টেমের ভিত্তি