Added 5 solutions

varunu28 · varunu28 · commit 22d63e2c37b6 · 2019-08-24T18:56:48.000-07:00
diff --git a/Easy/Largest Triangle Area.java b/Easy/Largest Triangle Area.java
@@ -0,0 +1,20 @@
+class Solution {
+    public double largestTriangleArea(int[][] points) {
+        int n = points.length;
+        double maxArea = 0;
+        for (int i = 0; i < n; i++) {
+            for (int j = i + 1; j < n; j++) {
+                for (int k = j + 1; k < n; k++) {
+                    maxArea = Math.max(maxArea, getArea(points[i], points[j], points[k]));
+                }
+            }
+        }
+        
+        return maxArea;
+    }
+    
+    private double getArea(int[] P, int[] Q, int[] R) {
+        return 0.5 * Math.abs(P[0] * Q[1] + Q[0] * R[1] + R[0] * P[1]
+                             -P[1] * Q[0] - Q[1] * R[0] - R[1] * P[0]);
+    }
+}
diff --git a/Easy/Single-Row Keyboard.java b/Easy/Single-Row Keyboard.java
@@ -0,0 +1,17 @@
+class Solution {
+    public int calculateTime(String keyboard, String word) {
+        Map<Character, Integer> map = new HashMap<>();
+        for (int i = 0; i < keyboard.length(); i++) {
+            map.put(keyboard.charAt(i), i);
+        }
+        
+        int currPos = 0;
+        int totalTime = 0;
+        for (char c : word.toCharArray()) {
+            totalTime += Math.abs(currPos - map.get(c));
+            currPos = map.get(c);
+        }
+        
+        return totalTime;
+    }
+}
diff --git a/Medium/Design File System.java b/Medium/Design File System.java
@@ -0,0 +1,30 @@
+class FileSystem {
+
+    Map<String, Integer> map;
+    public FileSystem() {
+        map = new HashMap<>();
+    }
+    
+    public boolean create(String path, int value) {
+        if (map.containsKey(path)) {
+            return false;
+        }
+        int lastIdx = path.lastIndexOf('/');
+        if (lastIdx != 0 && !map.containsKey(path.substring(0, lastIdx))) {
+            return false;
+        }    
+        map.put(path, value);
+        return true;
+    }
+    
+    public int get(String path) {
+        return map.getOrDefault(path, -1);
+    }
+}
+
+/**
+ * Your FileSystem object will be instantiated and called as such:
+ * FileSystem obj = new FileSystem();
+ * boolean param_1 = obj.create(path,value);
+ * int param_2 = obj.get(path);
+ */
diff --git a/Medium/Number of Dice Rolls With Target Sum.java b/Medium/Number of Dice Rolls With Target Sum.java
@@ -0,0 +1,23 @@
+class Solution {
+    int MOD = 1000000007;
+    public int numRollsToTarget(int d, int f, int target) {
+        Integer[][] dp = new Integer[d + 1][target + 1];
+        return helper(d, f, target, dp);
+    }
+    
+    private int helper(int d, int f, int target, Integer[][] dp) {
+        if (d == 0 || target <= 0) {
+            return d == target ? 1 : 0;
+        }
+        if (dp[d][target] != null) {
+            return dp[d][target];
+        }
+        
+        dp[d][target] = 0;
+        for (int i = 1; i <= f; i++) {
+            dp[d][target] = (dp[d][target] + helper(d - 1, f, target - i, dp)) % MOD; 
+        }
+        
+        return dp[d][target];
+    }
+}
diff --git a/Medium/Online Election.java b/Medium/Online Election.java
@@ -0,0 +1,63 @@
+class TopVotedCandidate {
+
+    Map<Integer, Integer> voteCount;
+    Map<Integer, Integer> timeCount;
+    int currLeaderCount;
+    List<Winner> winners;
+
+    public TopVotedCandidate(int[] persons, int[] times) {
+        voteCount = new HashMap<>();
+        timeCount = new HashMap<>();
+        currLeaderCount = 0;
+        winners = new ArrayList<>();
+        
+        for (int i = 0; i < persons.length; i++) {
+            boolean isPresent = voteCount.containsKey(persons[i]);
+            voteCount.put(persons[i], voteCount.getOrDefault(persons[i], 0) + 1);
+            timeCount.put(persons[i], times[i]);
+            if (voteCount.get(persons[i]) >= currLeaderCount) {
+                winners.add(new Winner(persons[i], times[i]));
+                currLeaderCount = Math.max(currLeaderCount, voteCount.get(persons[i]));
+            }
+        }
+    }
+
+    public int q(int t) {
+        return winners.get(binarySearchHelper(winners, 0, winners.size() - 1, t)).val;
+    }
+
+    private int binarySearchHelper(List<Winner> winners, int left, int right, int target) {
+        int idx = winners.size();
+        while (left <= right) {
+            int mid = (left + right) / 2;
+            if (winners.get(mid).time == target) {
+                idx = mid;
+                break;
+            }
+            else if (winners.get(mid).time < target) {
+                idx = mid;
+                left = mid + 1;
+            }
+            else {
+                right = mid - 1;
+            }
+        }
+        
+        return idx == winners.size() ? 0 : idx;
+    }
+}
+
+class Winner {
+    int val;
+    int time;
+
+    public Winner(int val, int time) {
+        this.val = val;
+        this.time = time;
+    }
+}
+/**
+ * Your TopVotedCandidate object will be instantiated and called as such:
+ * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
+ * int param_1 = obj.q(t);
+ */
