Updated 3 solutions

varunu28 · varunu28 · commit da5774a22f39 · 2019-06-26T13:00:53.000-07:00
diff --git a/Easy/Strobogrammatic Number.java b/Easy/Strobogrammatic Number.java
@@ -1,26 +1,18 @@
 class Solution {
     public boolean isStrobogrammatic(String num) {
-        Set<String> set = new HashSet<>();
-        set.add("0");
-        set.add("1");
-        set.add("8");
-        set.add("00");
-        set.add("11");
-        set.add("88");
-        set.add("69");
-        set.add("96");
-                
-        int start = 0;
-        int end = num.length()-1;
-        
-        while (start <= end) {
-            if (!set.contains(num.charAt(start) + "" + num.charAt(end))) {
+        StringBuilder sb = new StringBuilder();
+        for (char c : num.toCharArray()) {
+            if (c == '0' || c == '1' || c == '8') {
+                sb.append(c);
+            }
+            else if (c == '6' || c == '9') {
+                sb.append(c == '6' ? '9' : '6');
+            }
+            else {
                 return false;
             }
-            start++;
-            end--;
         }
         
-        return true;
+        return sb.reverse().toString().equals(num);
     }
 }
diff --git a/Hard/Insert Delete GetRandom O(1) - Duplicates Allowed.java b/Hard/Insert Delete GetRandom O(1) - Duplicates Allowed.java
@@ -1,60 +1,44 @@
 class RandomizedCollection {
 
     /** Initialize your data structure here. */
-    List<Integer> list;
     Map<Integer, Set<Integer>> map;
+    List<Integer> list;
 
     public RandomizedCollection() {
-        list = new ArrayList<>();
         map = new HashMap<>();
+        list = new ArrayList<>();
     }
 
     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
     public boolean insert(int val) {
-        boolean returnVal = map.containsKey(val);
-
-        Set<Integer> indexes = returnVal ? map.get(val) : new HashSet<>();
-        indexes.add(list.size());
+        map.computeIfAbsent(val, k -> new LinkedHashSet<>()).add(list.size());
         list.add(val);
-        map.put(val, indexes);
-
-        return !returnVal;
+        return map.get(val).size() == 1;
     }
 
     /** Removes a value from the collection. Returns true if the collection contained the specified element. */
     public boolean remove(int val) {
-        if (!map.containsKey(val)) {
+        if (!map.containsKey(val) || map.get(val).size() == 0) {
             return false;
         }
 
-        Set<Integer> indexes = map.get(val);
-        int index = indexes.iterator().next();
-        indexes.remove(index);
+        int idxToRemove = map.get(val).iterator().next();
+        map.get(val).remove(idxToRemove);
+        int lastVal = list.get(list.size() - 1);
+        list.set(idxToRemove, lastVal);
+        map.get(lastVal).add(idxToRemove);
+        map.get(lastVal).remove(list.size() - 1);
+        list.remove(list.size() - 1);
         
-        if (indexes.size() == 0) {
-            map.remove(val);
-        }
-
-        if (index != list.size()-1) {
-            int lastVal = list.get(list.size()-1);
-            Set<Integer> lastValIndexes = map.get(lastVal);
-            list.set(index, lastVal);
-            lastValIndexes.remove(list.size()-1);
-            lastValIndexes.add(index);
-        }
-
-        list.remove(list.size()-1);
-
         return true;
     }
 
     /** Get a random element from the collection. */
     public int getRandom() {
-        return list.get((int)(Math.random() * list.size()));
+        return list.get(new java.util.Random().nextInt(list.size()));
     }
 }
 
-
 /**
  * Your RandomizedCollection object will be instantiated and called as such:
  * RandomizedCollection obj = new RandomizedCollection();
diff --git a/Medium/Task Scheduler.java b/Medium/Task Scheduler.java
@@ -1,28 +1,45 @@
 class Solution {
     public int leastInterval(char[] tasks, int n) {
-        int[] map = new int[26];
-        int time = 0;
-        
-        for (char c : tasks) {
-            map[c - 'A']++;
+        Map<Character, Integer> map = new HashMap<>();
+        for (char task : tasks) {
+            map.put(task, map.getOrDefault(task, 0) + 1);
         }
-        
-        Arrays.sort(map);
-        
-        while(map[25] > 0) {
-            int i = 0;
-            while (i <= n) {
-                if (map[25] == 0) break;
-                if (i < 26 && map[25-i] > 0) {
-                    map[25 - i]--;
+
+        PriorityQueue<Character> pq = new PriorityQueue<>((o1, o2) -> {
+            int c = map.get(o2).compareTo(map.get(o1));
+            if (c != 0) {
+                return c;
+            }
+
+            return o1 - o2;
+        });
+        pq.addAll(map.keySet());
+
+        int count = 0;
+        while (!pq.isEmpty()) {
+            int jump = n + 1;
+            List<Character> temp = new ArrayList<>();
+            while (jump > 0 && !pq.isEmpty()) {
+                Character polled = pq.poll();
+                map.put(polled, map.get(polled) - 1);
+                temp.add(polled);
+                jump--;
+                count++;
+            }
+
+            for (Character executedTask : temp) {
+                if (map.get(executedTask) > 0) {
+                    pq.add(executedTask);
                 }
-                i++;
-                time++;
             }
-            
-            Arrays.sort(map);
+
+            if (pq.isEmpty()) {
+                break;
+            }
+
+            count += jump;
         }
-        
-        return time;
+
+        return count;
     }
 }
