Formatted question description: https://leetcode.ca/all/635.html

635. Design Log Storage System

Level

Medium

Description

You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Design a log storage system to implement the following functions:

void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system.

int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.

Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:

There will be at most 300 operations of Put or Retrieve.
Year ranges from [2000,2017]. Hour ranges from [00,23].
Output for Retrieve has no order required.

Solution

Use a tree map to store each log’s timestamp and id, where the entries are sorted according to the timestamps.

For put, add an entry into the tree map where timestamp is the key and id is the value.

For retrieve, first change s and e to the needed formats according to granularity, and increase the changed e by 1, and then obtain all the entries from the tree map, and finally add all the ids to a list and return.

treeMap.tailMap(start);

class LogSystem {
    List<String> granularityList;
    TreeMap<String, Integer> treeMap;

    public LogSystem() {
        granularityList = new ArrayList<String>(Arrays.asList("Year", "Month", "Day", "Hour", "Minute", "Second"));
        treeMap = new TreeMap<String, Integer>();
    }
    
    public void put(int id, String timestamp) {
        treeMap.put(timestamp, id);
    }
    
    public List<Integer> retrieve(String s, String e, String gra) {
        List<Integer> retrieveList = new ArrayList<Integer>();
        int index = granularityList.indexOf(gra);
        String[] sArrayStr = s.split(":");
        String[] eArrayStr = e.split(":");
        int length = sArrayStr.length;
        int[] sArray = new int[length];
        int[] eArray = new int[length];
        for (int i = 0; i < length; i++) {
            sArray[i] = Integer.parseInt(sArrayStr[i]);
            eArray[i] = Integer.parseInt(eArrayStr[i]);
        }
        eArray[index]++;
        update(eArray);
        StringBuffer sSB = new StringBuffer();
        StringBuffer eSB = new StringBuffer();
        for (int i = 0; i <= index; i++) {
            if (i > 0) {
                sSB.append(':');
                eSB.append(':');
            }
            sSB.append(String.format("%02d", sArray[i]));
            eSB.append(String.format("%02d", eArray[i]));
        }
        String start = sSB.toString();
        String end = eSB.toString();
        Map<String, Integer> sortedMap = treeMap.tailMap(start);
        Set<String> keySet = sortedMap.keySet();
        for (String timestamp : keySet) {
            if (timestamp.compareTo(end) < 0)
                retrieveList.add(sortedMap.get(timestamp));
        }
        return retrieveList;
    }

    public void update(int[] eArray) {
        if (eArray[5] >= 60) {
            eArray[5] -= 60;
            eArray[4]++;
        }
        if (eArray[4] >= 60) {
            eArray[4] -= 60;
            eArray[3]++;
        }
        if (eArray[3] >= 24) {
            eArray[3] -= 24;
            eArray[2]++;
        }
        int month = eArray[1];
        if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) {
            if (eArray[2] > 31) {
                eArray[2] -= 31;
                eArray[1]++;
            }
        } else if (month == 4 || month == 6 || month == 9 || month == 11) {
            if (eArray[2] > 30) {
                eArray[2] -= 30;
                eArray[1]++;
            }
        } else if (month == 2) {
            int year = eArray[0];
            boolean isLeap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
            int maxDate = isLeap ? 29 : 28;
            if (eArray[1] > maxDate) {
                eArray[2] -= maxDate;
                eArray[1]++;
            }
        }
        if (eArray[1] > 12) {
            eArray[1] -= 12;
            eArray[0]++;
        }
    }
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * List<Integer> param_2 = obj.retrieve(s,e,gra);
 */

############

class LogSystem {
    private List<Log> logs = new ArrayList<>();
    private Map<String, Integer> d = new HashMap<>();

    public LogSystem() {
        d.put("Year", 4);
        d.put("Month", 7);
        d.put("Day", 10);
        d.put("Hour", 13);
        d.put("Minute", 16);
        d.put("Second", 19);
    }

    public void put(int id, String timestamp) {
        logs.add(new Log(id, timestamp));
    }

    public List<Integer> retrieve(String start, String end, String granularity) {
        List<Integer> ans = new ArrayList<>();
        int i = d.get(granularity);
        String s = start.substring(0, i);
        String e = end.substring(0, i);
        for (var log : logs) {
            String t = log.ts.substring(0, i);
            if (s.compareTo(t) <= 0 && t.compareTo(e) <= 0) {
                ans.add(log.id);
            }
        }
        return ans;
    }
}

class Log {
    int id;
    String ts;

    Log(int id, String ts) {
        this.id = id;
        this.ts = ts;
    }
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * List<Integer> param_2 = obj.retrieve(start,end,granularity);
 */

class LogSystem:
    def __init__(self):
        self.logs = []
        self.d = {
            "Year": 4,
            "Month": 7,
            "Day": 10,
            "Hour": 13,
            "Minute": 16,
            "Second": 19,
        }

    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((id, timestamp))

    def retrieve(self, start: str, end: str, granularity: str) -> List[int]:
        i = self.d[granularity]
        return [id for id, ts in self.logs if start[:i] <= ts[:i] <= end[:i]]


# Your LogSystem object will be instantiated and called as such:
# obj = LogSystem()
# obj.put(id,timestamp)
# param_2 = obj.retrieve(start,end,granularity)

class LogSystem {
public:
    LogSystem() {
        d["Year"] = 4;
        d["Month"] = 7;
        d["Day"] = 10;
        d["Hour"] = 13;
        d["Minute"] = 16;
        d["Second"] = 19;
    }

    void put(int id, string timestamp) {
        logs.push_back({id, timestamp});
    }

    vector<int> retrieve(string start, string end, string granularity) {
        vector<int> ans;
        int i = d[granularity];
        auto s = start.substr(0, i);
        auto e = end.substr(0, i);
        for (auto& [id, ts] : logs) {
            auto t = ts.substr(0, i);
            if (s <= t && t <= e) {
                ans.emplace_back(id);
            }
        }
        return ans;
    }

private:
    vector<pair<int, string>> logs;
    unordered_map<string, int> d;
};

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem* obj = new LogSystem();
 * obj->put(id,timestamp);
 * vector<int> param_2 = obj->retrieve(start,end,granularity);
 */

type LogSystem struct {
	logs []pair
	d    map[string]int
}

func Constructor() LogSystem {
	d := map[string]int{
		"Year":   4,
		"Month":  7,
		"Day":    10,
		"Hour":   13,
		"Minute": 16,
		"Second": 19,
	}
	return LogSystem{[]pair{}, d}
}

func (this *LogSystem) Put(id int, timestamp string) {
	this.logs = append(this.logs, pair{id, timestamp})
}

func (this *LogSystem) Retrieve(start string, end string, granularity string) (ans []int) {
	i := this.d[granularity]
	s, e := start[:i], end[:i]
	for _, log := range this.logs {
		t := log.ts[:i]
		if s <= t && t <= e {
			ans = append(ans, log.id)
		}
	}
	return
}

type pair struct {
	id int
	ts string
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Put(id,timestamp);
 * param_2 := obj.Retrieve(start,end,granularity);
 */

Another way, is to use a treemap to store the <timestamp,id> pair

class LogSystem {
    TreeMap<String, List<Integer>> timeToIdMap;
    String minTimeStamp;
    String maxTimeStamp;
    Map<String, Integer> graMap;

    public LogSystem() {
        timeToIdMap = new TreeMap<>();
        minTimeStamp = "2000:01:01:00:00:00";
        maxTimeStamp = "2017:12:31:23:59:59";
        graMap = new HashMap<>();
        graMap.put("Year", 4);
        graMap.put("Month", 7);
        graMap.put("Day", 10);
        graMap.put("Hour", 13);
        graMap.put("Minute", 16);
        graMap.put("Second", 19);
    }

    public void put(int id, String timestamp) {
        List<Integer> idList = timeToIdMap.getOrDefault(timestamp, new ArrayList<>());
        idList.add(id);
        timeToIdMap.put(timestamp, idList);
    }

    public List<Integer> retrieve(String s, String e, String gra) {
        List<Integer> ans = new ArrayList<>();
        int graIdx = graMap.get(gra);
        String startTime = s.substring(0, graIdx) + minTimeStamp.substring(graIdx);
        String endTime = e.substring(0, graIdx) + maxTimeStamp.substring(graIdx);

        // get all logs in required time range
        // public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
        NavigableMap<String, List<Integer>> subMap = timeToIdMap.subMap(
            startTime, true, endTime, true);

        for (String timeStamp : subMap.keySet()) {
            ans.addAll(subMap.get(timeStamp));
        }

        return ans;
    }
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * List<Integer> param_2 = obj.retrieve(s,e,gra);
 */

Solution with Trie, every level of Trie tree to store year,month,day…

class LogSystem:
    def __init__(self):
        self.logs = []
        self.d = {
            "Year": 4,
            "Month": 7,
            "Day": 10,
            "Hour": 13,
            "Minute": 16,
            "Second": 19,
        }

    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((id, timestamp))

    def retrieve(self, start: str, end: str, granularity: str) -> List[int]:
        i = self.d[granularity]
        return [id for id, ts in self.logs if start[:i] <= ts[:i] <= end[:i]]


# Your LogSystem object will be instantiated and called as such:
# obj = LogSystem()
# obj.put(id,timestamp)
# param_2 = obj.retrieve(start,end,granularity)

class LogSystem {
public:
    LogSystem() {
        d["Year"] = 4;
        d["Month"] = 7;
        d["Day"] = 10;
        d["Hour"] = 13;
        d["Minute"] = 16;
        d["Second"] = 19;
    }

    void put(int id, string timestamp) {
        logs.push_back({id, timestamp});
    }

    vector<int> retrieve(string start, string end, string granularity) {
        vector<int> ans;
        int i = d[granularity];
        auto s = start.substr(0, i);
        auto e = end.substr(0, i);
        for (auto& [id, ts] : logs) {
            auto t = ts.substr(0, i);
            if (s <= t && t <= e) {
                ans.emplace_back(id);
            }
        }
        return ans;
    }

private:
    vector<pair<int, string>> logs;
    unordered_map<string, int> d;
};

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem* obj = new LogSystem();
 * obj->put(id,timestamp);
 * vector<int> param_2 = obj->retrieve(start,end,granularity);
 */

type LogSystem struct {
	logs []pair
	d    map[string]int
}

func Constructor() LogSystem {
	d := map[string]int{
		"Year":   4,
		"Month":  7,
		"Day":    10,
		"Hour":   13,
		"Minute": 16,
		"Second": 19,
	}
	return LogSystem{[]pair{}, d}
}

func (this *LogSystem) Put(id int, timestamp string) {
	this.logs = append(this.logs, pair{id, timestamp})
}

func (this *LogSystem) Retrieve(start string, end string, granularity string) (ans []int) {
	i := this.d[granularity]
	s, e := start[:i], end[:i]
	for _, log := range this.logs {
		t := log.ts[:i]
		if s <= t && t <= e {
			ans = append(ans, log.id)
		}
	}
	return
}

type pair struct {
	id int
	ts string
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Put(id,timestamp);
 * param_2 := obj.Retrieve(start,end,granularity);
 */

635 - Design Log Storage System

635. Design Log Storage System

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

635. Design Log Storage System

Level

Description

Solution

All Problems

All Solutions