Added 2 solutions & modified 2 solutions

varunu28 · varunu28 · commit 56cb3fd9f3e2 · 2019-07-16T14:13:44.000-07:00
diff --git a/Hard/Employee Free Time.java b/Hard/Employee Free Time.java
@@ -0,0 +1,32 @@
+/**
+ * Definition for an interval.
+ * public class Interval {
+ *     int start;
+ *     int end;
+ *     Interval() { start = 0; end = 0; }
+ *     Interval(int s, int e) { start = s; end = e; }
+ * }
+ */
+/*
+*/
+class Solution {
+    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
+        List<Interval> ans = new ArrayList<>();
+        PriorityQueue<Interval> pq = new PriorityQueue<>((a,b) -> a.start - b.start);
+        schedule.forEach(e -> pq.addAll(e));    
+    
+        Interval temp = pq.poll();
+        while (!pq.isEmpty()) {
+            if (temp.end < pq.peek().start) {
+                ans.add(new Interval(temp.end, pq.peek().start));
+                temp = pq.poll();
+            }
+            else {
+                temp = temp.end < pq.peek().end ? pq.peek() : temp;
+                pq.poll();
+            }
+        }
+        
+        return ans;
+    }   
+}
diff --git a/Medium/Evaluate Division.java b/Medium/Evaluate Division.java
@@ -0,0 +1,73 @@
+class Solution {
+    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
+        double[] ans = new double[queries.size()];
+
+        Map<String, Set<String>> map = new HashMap<>();
+        Map<String, Double> resMap = new HashMap<>();
+
+        for (int i = 0; i < equations.size(); i++) {
+            String operand1 = equations.get(i).get(0);
+            String operand2 = equations.get(i).get(1);
+
+            map.computeIfAbsent(operand1, k -> new HashSet<>()).add(operand2);
+            map.computeIfAbsent(operand2, k -> new HashSet<>()).add(operand1);
+
+            resMap.put(operand1 + "|" + operand2, values[i]);
+        }
+
+        for (int i = 0; i < queries.size(); i++) {
+            String operand1 = queries.get(i).get(0);
+            String operand2 = queries.get(i).get(1);
+
+            if (!map.containsKey(operand1) || !map.containsKey(operand2)) {
+                ans[i] = -1.0;
+            }
+            else if (operand1.equals(operand2)) {
+                ans[i] = 1.0;
+            }
+            else if (map.get(operand1).contains(operand2)) {
+                ans[i] = getSimpleDivisionVal(resMap, operand1, operand2);
+            }
+            else if (operand2.contains(operand1)) {
+                ans[i] = getSimpleDivisionVal(resMap, operand2, operand1);
+            }
+            else {
+                ans[i] = dfs(map, resMap, operand1, operand2, 1.0, new HashSet<>());
+            }
+        }
+
+        return ans;
+    }
+
+    private double dfs (Map<String, Set<String>> map, Map<String, Double> resMap, String operand1, String operand2,
+                        double base, Set<String> visited) {
+        if (visited.contains(operand1)) {
+            return -1.0;
+        }
+        if (map.get(operand1).contains(operand2)) {
+            return base * getSimpleDivisionVal(resMap, operand1, operand2);
+        }
+
+        visited.add(operand1);
+
+        double ans = -1.0;
+        Iterator<String> children = map.get(operand1).iterator();
+
+        while (children.hasNext()) {
+            String child = children.next();
+            if (!visited.contains(child)) {
+                ans = Math.max(ans, dfs(map, resMap, child, operand2, base * getSimpleDivisionVal(resMap, operand1, child), visited));
+            }
+        }
+
+        return ans;
+    }
+
+    private double getSimpleDivisionVal (Map<String, Double> resMap, String operand1, String operand2) {
+        if (resMap.containsKey(operand1 + "|" + operand2)) {
+            return resMap.get(operand1 + "|" + operand2);
+        }
+
+        return 1 / resMap.get(operand2 + "|" + operand1);
+    }
+}
diff --git a/Medium/Exclusive Time of Functions.java b/Medium/Exclusive Time of Functions.java
@@ -1,42 +1,28 @@
 class Solution {
     public int[] exclusiveTime(int n, List<String> logs) {
-        int[] time = new int[n];
-
-        Stack<Task> tasks = new Stack<>();
+        int[] timer = new int[n];
+        Stack<Integer> stack = new Stack<>();
+        int lastTime = 0;;
 
         for (String log : logs) {
-            Task task = new Task(log);
+            String[] strs = log.split(":");
+            int id = Integer.parseInt(strs[0]);
+            String status = strs[1];
+            int time = Integer.parseInt(strs[2]);
 
-            if (task.status == Status.Start) {
-                tasks.push(task);
+            if (!stack.isEmpty()) {
+                timer[stack.peek()] += time - lastTime;
+            }
+            lastTime = time;
+            if (status.equals("start")) {
+                stack.push(id);
             }
             else {
-                Task top = tasks.pop();
-                time[top.num] += task.time - top.time + 1;
-
-                if (!tasks.isEmpty()) {
-                    time[tasks.peek().num] -= task.time - top.time + 1;
-                }
+                timer[stack.pop()]++;
+                lastTime++;
             }
         }
 
-        return time;
+        return timer;
     }
 }
-
-class Task {
-    public int num;
-    public int time;
-    public Status status;
-
-    public Task(String log) {
-        String[] strs = log.split(":");
-        this.num = Integer.parseInt(strs[0]);
-        this.time = Integer.parseInt(strs[2]);
-        this.status = strs[1].equals("start") ? Status.Start : Status.End;
-    }
-}
-
-enum Status {
-    Start, End;
-}
diff --git a/Medium/Print Binary Tree.java b/Medium/Print Binary Tree.java
@@ -8,45 +8,43 @@
  * }
  */
 class Solution {
-
-    List<List<String>> ans = new ArrayList<>();
-        
     public List<List<String>> printTree(TreeNode root) {
-        int row = height(root);
-        int col = (int)(Math.pow(2, row) - 1);
-        
-        List<String> oneRow = new ArrayList<>();
-        
-        for (int i=0;i<col;i++) {
-            oneRow.add("");
-        }
-        
-        for (int i=0;i<row;i++) {
-            ans.add(new ArrayList<>(oneRow));
+        int height = getHeight(root);
+        int numOfNodes = (int) Math.pow(2, height) - 1;
+
+        List<List<String>> ans = new ArrayList<>();
+
+        for (int i = 0; i < height; i++) {
+            List<String> temp = new ArrayList<>();
+            for (int j = 0; j < numOfNodes; j++) {
+                temp.add("");
+            }
+
+            ans.add(temp);
         }
-        
-        helper(0, 0, col, root);
-        
+
+        updateList(ans, root, 0, 0, numOfNodes);
+
         return ans;
     }
-    
-    public void helper(int rowNum, int start, int end, TreeNode root) {
-    
-        if (root == null) return;
-        
-        int mid = (start + end)/2;
-        
-        List<String> temp = ans.get(rowNum);
-        temp.set(mid, String.valueOf(root.val));
-        
-        ans.set(rowNum, temp);
-        
-        helper(rowNum+1, start, mid-1, root.left);
-        helper(rowNum+1, mid+1, end, root.right);
+
+    private void updateList (List<List<String>> ans, TreeNode root, int idx, int start, int end) {
+        if (root == null) {
+            return;
+        }
+
+        int mid = (start + end) / 2;
+
+        ans.get(idx).set(mid, String.valueOf(root.val));
+        updateList(ans, root.left, idx + 1, start, mid - 1);
+        updateList(ans, root.right, idx + 1, mid + 1, end);
     }
-    
-    public int height(TreeNode root) {
-        if (root == null) return 0;
-        return 1 + Math.max(height(root.left), height(root.right));
+
+    private int getHeight (TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+
+        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
     }
 }
