Thoughts about optimal data structure for such problems and Java solution using a Binary Tree


  • 0
    D

    When I first read the problem, I could only think of a solution using Tree data structure. Albeit this is not the fastest solution for the given question. If we increase the year range to a large value and remove the limit on put/retrieve operations, will Tree be a better data structure over an array or an ArrayList?

    '''
    public class LogSystem {

    TreeNode root;
    
    class TreeNode {
        
        class store{
            int id;
            String ts;
            
            store(int id, String ts){
                this.id = id;
                this.ts = ts;
            }
        }
        
        store info;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int id, String ts){
            info = new store(id, ts);
            left = null;
            right = null;
        }
    }
    
    public LogSystem() {
        root = null;
    }
    
    public void put(int id, String timestamp) {
        TreeNode pointer = root;
        
        if(root == null){
            root = new TreeNode(id, timestamp);
            return;
        }
        
        while(pointer != null){
            if(pointer.info.ts.compareTo(timestamp) < 0){
                if(pointer.right == null){
                    pointer.right = new TreeNode(id, timestamp);
                    return;
                }
                pointer = pointer.right;
            }
            else{
                if(pointer.left == null){
                    pointer.left = new TreeNode(id, timestamp);
                    return;
                }
                pointer = pointer.left;
            }
        }
    }
    
    public List<Integer> retrieve(String s, String e, String gra) {
    
        TreeNode pointer = root;
        List<Integer> list = new ArrayList<>();
        
        if(gra.equals("Year"))
            retrieveHelper(s.split(":"), e.split(":"), 0, root, list);
        
        else if(gra.equals("Month"))
            retrieveHelper(s.split(":"), e.split(":"), 1, root, list);
        
        else if(gra.equals("Day"))
            retrieveHelper(s.split(":"), e.split(":"), 2, root, list);
        
        else if(gra.equals("Hour"))
            retrieveHelper(s.split(":"), e.split(":"), 3, root, list);
        
        else if(gra.equals("Minute"))
            retrieveHelper(s.split(":"), e.split(":"), 4, root, list);
        
        else if(gra.equals("Second"))
            retrieveHelper(s.split(":"), e.split(":"), 5, root, list);
        
        return list;
    }
    
    /* Level is the granularity in integer - 0: Year, 1: month, etc,. */
    private void retrieveHelper(String[] start, String[] end, int level, TreeNode root, List<Integer> list){
        if(root == null)
            return;
        
        int cur = 0; /* current level */
        
        String[] strings = root.info.ts.split(":");
        
        boolean moreThanStart = false;
        boolean lessThanEnd = false;
        boolean lessThanStart = false;
        boolean moreThanEnd = false;
        int cmp = 0;
    
        while(cur <= level){
    
            cmp = start[cur].compareTo(strings[cur]);
            if(!lessThanStart && cmp < 0)
                moreThanStart = true;
    
            if(!moreThanStart && cmp > 0)
                lessThanStart = true;
            
            cmp = end[cur].compareTo(strings[cur]);
            if(!moreThanEnd && cmp > 0){
                lessThanEnd = true;
            }
            if(!lessThanEnd && cmp < 0)
                moreThanEnd = true;
    
            cur++;
        }
        
        if(moreThanEnd){
            retrieveHelper(start, end, level, root.left, list);
            return;
        }
    
        if(lessThanStart){
            retrieveHelper(start, end, level, root.right, list);
            return;
        }
    
        list.add(root.info.id);
        retrieveHelper(start, end, level, root.right, list);
        retrieveHelper(start, end, level, root.left, list);
    }
    

    }
    '''


Log in to reply
 

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