Cho các log, mỗi log có id duy nhất và timestamp dạng Year:Month:Day:Hour:Minute:Second (ví dụ: 2019:01:01:23:59:59). Cần thiết kế hệ thống lưu trữ log với 2 hàm:
Put(int id, string timestamp): lưu log.Retrieve(String start, String end, String granularity): trả về id các log có timestamp trong khoảng[start, end]theo độ chi tiếtgranularity(Year, Month, Day, Hour, Minute, Second).
Ví dụ: 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 với granularity "Year" trả về [1,2,3], với "Hour" trả về [1,2].
Giải pháp: lưu danh sách (id, timestamp). Khi retrieve, xác độ dài prefix theo granularity (Year:5, Month:8, Day:11, Hour:14, Minute:17, Second:20), so sánh prefix của timestamp.
Ví dụ triển khai
class LogSystem(object):
def __init__(self):
self.logs = []
def put(self, id, timestamp):
self.logs.append((id, timestamp))
def retrieve(self, s, e, gra):
index = {'Year':5, 'Month':8, 'Day':11, 'Hour':14, 'Minute':17, 'Second':20}[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")))
print(list(ob.retrieve("2018:01:01:01:01:01","2019:01:01:23:00:00","Hour")))
Đầu vào
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") ob.retrieve("2018:01:01:01:01:01","2019:01:01:23:00:00","Year") ob.retrieve("2018:01:01:01:01:01","2019:01:01:23:00:00","Hour")
Đầu ra
[1, 2, 3] [1, 2]