Added 7 solutions

varunu28 · varunu28 · commit 1ff38ef130ae · 2018-10-02T09:14:33.000-07:00
diff --git a/Easy/Flip Game.java b/Easy/Flip Game.java
@@ -0,0 +1,30 @@
+class Solution {
+    public static List<String> generatePossibleNextMoves(String s) {
+        List<String> ans = new ArrayList<>();
+
+        if (s.length() < 2) {
+            return ans;
+        }
+
+        if (s.equals("--")) {
+            return ans;
+        }
+
+        int i = 0;
+        while (i < s.length()-1) {
+            if (s.charAt(i) == s.charAt(i+1) && s.charAt(i) == '+') {
+                StringBuilder sb = new StringBuilder();
+                sb.append(s.substring(0, i));
+                sb.append('-');
+                sb.append('-');
+                sb.append(s.substring(i+2));
+
+                ans.add(sb.toString());
+            }
+
+            i++;
+        }
+
+        return ans;
+    }
+}
diff --git a/Easy/Logger Rate Limiter.java b/Easy/Logger Rate Limiter.java
@@ -0,0 +1,28 @@
+class Logger {
+
+    /** Initialize your data structure here. */
+    Map<String, Integer> map;
+    public Logger() {
+        map = new HashMap<>();
+    }
+
+    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
+     If this method returns false, the message will not be printed.
+     The timestamp is in seconds granularity. */
+    public boolean shouldPrintMessage(int timestamp, String message) {
+
+        if (map.containsKey(message) && timestamp - map.get(message) < 10) {
+            return false;
+        }
+
+        map.put(message, timestamp);
+
+        return true;
+    }
+}
+
+/**
+ * Your Logger object will be instantiated and called as such:
+ * Logger obj = new Logger();
+ * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
+ */
diff --git a/Easy/Meeting Rooms.java b/Easy/Meeting Rooms.java
@@ -0,0 +1,30 @@
+/**
+ * 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 static boolean canAttendMeetings(Interval[] intervals) {
+        Arrays.sort(intervals, new Comparator<Interval>() {
+            @Override
+            public int compare(Interval o1, Interval o2) {
+                return o1.start - o2.start;
+            }
+        });
+
+        int i=0;
+        while (i < intervals.length - 1) {
+            if (intervals[i].end > intervals[i+1].start) {
+                return false;
+            }
+
+            i++;
+        }
+
+        return true;
+    }
+}
diff --git a/Easy/Moving Average from Data Stream.java b/Easy/Moving Average from Data Stream.java
@@ -0,0 +1,29 @@
+class MovingAverage {
+
+    /** Initialize your data structure here. */
+    Queue<Integer> queue;
+    int capacity;
+    int sum = 0;
+    public MovingAverage(int size) {
+        capacity = size;
+        queue = new LinkedList<>();
+    }
+
+    public double next(int val) {
+        if (queue.size() == capacity) {
+            sum -= queue.remove();
+        }
+
+        queue.add(val);
+        sum += val;
+
+        double avg = (double) sum / queue.size();
+
+        return avg;
+    }
+}
+/**
+ * Your MovingAverage object will be instantiated and called as such:
+ * MovingAverage obj = new MovingAverage(size);
+ * double param_1 = obj.next(val);
+ */
diff --git a/Easy/Palindrome Permutation.java b/Easy/Palindrome Permutation.java
@@ -0,0 +1,24 @@
+class Solution {
+    public static boolean canPermutePalindrome(String s) {
+        Map<Character, Integer> map = new HashMap<>();
+        char[] chars = s.toCharArray();
+        
+        for (char c : chars) {
+            map.put(c, map.getOrDefault(c, 0) + 1);
+        }
+        
+        int oddVal = 0;
+        
+        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
+            if (entry.getValue()%2 != 0) {
+                oddVal++;
+            }
+            
+            if (oddVal == 2) {
+                return false;
+            }
+        }
+        
+        return true;
+    }
+}
diff --git a/Medium/Design Hit Counter.java b/Medium/Design Hit Counter.java
@@ -0,0 +1,31 @@
+class HitCounter {
+
+    /** Initialize your data structure here. */
+    Queue<Integer> queue;
+    public HitCounter() {
+        queue = new LinkedList<>();
+    }
+
+    /** Record a hit.
+     @param timestamp - The current timestamp (in seconds granularity). */
+    public void hit(int timestamp) {
+        queue.add(timestamp);
+    }
+
+    /** Return the number of hits in the past 5 minutes.
+     @param timestamp - The current timestamp (in seconds granularity). */
+    public int getHits(int timestamp) {
+        while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
+            queue.remove();
+        }
+
+        return queue.size();
+    }
+}
+
+/**
+ * Your HitCounter object will be instantiated and called as such:
+ * HitCounter obj = new HitCounter();
+ * obj.hit(timestamp);
+ * int param_2 = obj.getHits(timestamp);
+ */
diff --git a/Medium/Meeting Rooms II.java b/Medium/Meeting Rooms II.java
@@ -0,0 +1,80 @@
+/**
+ * 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 static int minMeetingRooms(Interval[] intervals) {
+
+        if (intervals.length == 0) {
+            return 0;
+        }
+
+        int[] start = new int[intervals.length];
+        int[] end = new int[intervals.length];
+
+        int i = 0;
+
+        for (Interval interval : intervals) {
+            start[i] = interval.start;
+            end[i] = interval.end;
+
+            i++;
+        }
+
+        Arrays.sort(start);
+        Arrays.sort(end);
+
+        int slow = 0;
+        int fast = 0;
+        int count = 0;
+
+        while (slow < intervals.length) {
+            if (start[slow] >= end[fast]) {
+                count--;
+                fast++;
+            }
+
+            count++;
+            slow++;
+        }
+
+        return count;
+    }
+    
+    public static int minMeetingRoomsQueue(Interval[] intervals) {
+        if (intervals.length == 0) {
+            return 0;
+        }
+
+        PriorityQueue<Integer> endTimes = new PriorityQueue<>(intervals.length, new Comparator<Integer>() {
+            @Override
+            public int compare(Integer o1, Integer o2) {
+                return o1 - o2;
+            }
+        });
+
+        Arrays.sort(intervals, new Comparator<Interval>() {
+            @Override
+            public int compare(Interval o1, Interval o2) {
+                return o1.start - o2.start;
+            }
+        });
+
+        endTimes.add(intervals[0].end);
+
+        for (int i=1; i<intervals.length; i++) {
+            if (intervals[i].start >= endTimes.peek()) {
+                endTimes.poll();
+            }
+
+            endTimes.add(intervals[i].end);
+        }
+
+        return endTimes.size();
+    }
+}
