BST solution....


  • 0
    D
    class TreeNode(object):
        def __init__(self, id, timestamp):
            self.id = id
            self.timestamp = timestamp
            self.left = None
            self.right = None
            
    class LogSystem(object):
    
        def __init__(self):
            self.root = TreeNode(0,'2009:06:15:12:30:30')
            
        def put(self, id, timestamp):
            tmp = self.root
            tempNode = TreeNode(id,timestamp)
            self.root = self.insert(self.root,tempNode)
            
            
        
        def insert(self, root, node):
            if not root:
                return node
            if self.compare(root.timestamp,node.timestamp,6)>=0:
                root.left = self.insert(root.left,node)
            else:
                root.right = self.insert(root.right,node)
            return root
            """
            :type id: int
            :type timestamp: str
            :rtype: void
            """
            
    
        def retrieve(self, s, e, gra):
            res = []
            
            if gra == 'Year':
                g =1
            elif gra == 'Month':
                g = 2
            elif gra == 'Day':
                g = 3
            elif gra == 'Hour':
                g = 4
            elif gra == 'Minute':
                g = 5
            else:
                g = 6
            self.helper(s,e,res,self.root,g)
            return res
        
        def helper(self,start,end,res,root,g):
            
            if not root:
                return
            
            if self.compare(start,root.timestamp,g)<=0 and self.compare(end,root.timestamp,g)>=0:
                if root.id!=0:
                    res.append(root.id)
                self.helper(start,end,res,root.left,g)
                self.helper(start,end ,res, root.right,g)
            elif self.compare(start,root.timestamp,g)>=0 and self.compare(end,root.timestamp,g)>=0:
                self.helper(start,end, res, root.right,g)
            elif self.compare(start,root.timestamp,g)<=0 and self.compare(end,root.timestamp,g)<=0:
                self.helper(start,end,res,root.left,g)
                
        def compare(self,a,b,g):
            a = a.split(':')
            b = b.split(':')
            
            for i in range(g):
                if int(a[i])>int(b[i]):
                    return 1
                elif int(a[i])<int(b[i]):
                    return -1
                else:
                    continue
            return 0
    

    The logic is simple. I created a dummy root node (whose id is 0 and the timestamp is the average values of the year , month , day and so on).

    for each given id and timestamp ,I create a new BST node and insert it based upon the timestamp. Time complexity: Avg case - O(logn). Worst Case - O(n)

    Retrival is done based upon the timestamp (don't forget to include the granularity). Time complexity: Avg case - O(logn). Worst Case - O(n)


Log in to reply
 

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