Python, Straightforward with Explanation


  • 21
    class LogSystem(object):
        def __init__(self):
            self.logs = []
    
        def put(self, tid, timestamp):
            self.logs.append((tid, 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 sorted(tid for tid, timestamp in self.logs
                          if start <= timestamp[:index] <= end)
    

    Because the number of operations is very small, we do not need a complicated structure to store the logs: a simple list will do.

    Let's focus on the retrieve function. For each granularity, we should consider all timestamps to be truncated to that granularity. For example, if the granularity is 'Day', we should truncate the timestamp '2017:07:02:08:30:12' to be '2017:07:02'. Now for each log, if the truncated timetuple cur is between start and end, then we should add the id of that log into our answer.


  • 0
    P

    Great solution! I used the same idea of truncating/pruning the timestamp as per granularity, but converted the timestamp to a tuple by splitting at : before storing/comparing so thinking of which index to prune the tuple as it was simple to think of. (For Year, prune the timestamp tuple from index 1 and onwards, for Month prune from index 2 and onwards...). Here's the accepted code:

    # Map of granularity to index at which the timestamp should be pruned for respective granularity
    gmap = { 'Year': 1, 'Month': 2, 'Day': 3, 'Hour': 4, 'Minute': 5, 'Second': 6 }
    
    class LogSystem:
        def __init__(self):
            self.d = {}
            
        def put(self, id, timestamp):
            t = tuple(timestamp.split(':'))
            self.d[t] = id
    
        def retrieve(self, s, e, gra):
            idx = gmap[gra]     # Prune from this index onwards
            s = tuple(s.split(':')[:idx])
            e = tuple(e.split(':')[:idx])
    
            ans = []
            for t in self.d.keys():
                if s <= t[:idx] <= e:
                    ans.append(self.d[t])
            return ans
    

    It is important to think that the lexicographic comparison of elements in the tuple will work as intended because year/month/... are all padded to the same length in the given input. And since each of year/month/day, etc have the same length we could even directly slice the string without converting to tuple which brings us to back to your solution. :)


  • 0
    S

    Thanks for sharing this brilliant solution. Intuitively, we tend to first convert the time stamp into a tuple of integers for comparison. However, your solution inspires that the string of an integer in a 0 padding form can be used for comparison directly, which is much more concise.
    Following is the translation of your idea in C++.

    #include <unordered_map>
    #include <vector>
    #include <string>
    class LogSystem {
    private:
        std::unordered_map<std::string, int> map{{"Year",4},{"Month",7},{"Day",10},{"Hour",13},{"Minute",16},{"Second",19}};
        std::vector<std::string> logs;
        std::vector<int> ids;
    public:
        LogSystem() {
            
        }
        
        void put(int id, string timestamp) {
            ids.push_back(id);
            logs.push_back(timestamp);
        }
        
        vector<int> retrieve(string s, string e, string gra) {
            int n = map[gra];
            auto ss = s.substr(0, n);
            auto se = e.substr(0, n);
            std::vector<int> r;
            for (int i = 0; i < logs.size(); i++){
                auto s = logs[i].substr(0, n);
                if (s >= ss && s <= se){
                    r.push_back(ids[i]);
                }
            }
            return r;
        }
    };

  • 0
    L

    How is the sorting working exactly? Why do you need to sort?


  • 1
    P

    @livelearn Sorting is not really needed (not explicitly mentioned in the question). Leetcode accepts the result even without sorting. E.g. If retrieve method in @awice's solution is changed to the following, it would still get accepted:

        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 ]
    

  • 0
    I

    is there a python version of tree map?


  • 0
    S
            index = {'Year': 5, 'Month': 8, 'Day': 11, 
                     'Hour': 14, 'Minute': 17, 'Second': 20}[gra]
    

    I think you're including ':' too for cumulative effect in applying granularity, so Month granularity will simply bey "Year:Month:" while Hour granularity be "Year:Month:Day:Hour:". So ":" is deliberately included for ease in string comparison?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.