Accepted problems

gouthampradhan · gouthampradhan · commit d3d503a0eda9 · 2018-05-04T17:45:01.000+02:00
diff --git a/README.md b/README.md
@@ -38,6 +38,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Minimum Moves to Equal Array Elements II](problems/src/array/MinimumMovesToEqualArray.java) (Median)
 - [Image Smoother](problems/src/array/ImageSmoother.java) (Easy)
 - [Minimum Index Sum of Two Lists](problems/src/array/MinimumIndexSumOfTwoLists.java) (Easy)
+- [Card Flipping Game](problems/src/array/CardFilipGame.java) (Medium)
 
 #### [Backtracking](problems/src/backtracking)
 
@@ -168,6 +169,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Palindrome Pairs](problems/src/dynamic_programming/PalindromePairs.java) (Hard)
 - [Cherry Pickup](problems/src/dynamic_programming/CherryPickup.java) (Hard)
 - [Knight Probability in Chessboard](problems/src/dynamic_programming/KnightProbabilityInChessboard.java) (Medium)
+- [Largest Sum of Averages](problems/src/dynamic_programming/LargestSumOfAverages.java) (Medium)
 
 
 #### [Greedy](problems/src/greedy)
@@ -195,6 +197,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Brick Wall](problems/src/hashing/BrickWall.java) (Medium)
 - [Partition Labels](problems/src/hashing/PartitionLabels.java) (Medium)
 - [Custom Sort String](problems/src/hashing/CustomSortString.java) (Medium)
+- [Short Encoding of Words](problems/src/hashing/ShortEncodingOfWords.java) (Medium)
 
 #### [Heap](problems/src/heap)
 
diff --git a/problems/src/array/CardFilipGame.java b/problems/src/array/CardFilipGame.java
@@ -0,0 +1,65 @@
+package array;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Created by gouthamvidyapradhan on 04/05/2018.
+ *
+ * On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).
+
+ We flip any number of cards, and after we choose one card.
+
+ If the number X on the back of the chosen card is not on the front of any card, then this number X is good.
+
+ What is the smallest number that is good?  If no number is good, output 0.
+
+ Here, fronts[i] and backs[i] represent the number on the front and back of card i.
+
+ A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.
+
+ Example:
+
+ Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
+ Output: 2
+ Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3].
+ We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.
+
+
+ Note:
+
+ 1 <= fronts.length == backs.length <= 1000.
+ 1 <= fronts[i] <= 2000.
+ 1 <= backs[i] <= 2000.
+
+ */
+public class CardFilipGame {
+
+    public static void main(String[] args) {
+
+    }
+
+    public int flipgame(int[] fronts, int[] backs) {
+        List<Integer> numbers = new ArrayList<>();
+        for(int i = 0; i < fronts.length; i ++){
+            numbers.add(fronts[i]);
+            numbers.add(backs[i]);
+        }
+        Collections.sort(numbers);
+        for(int n : numbers){
+            boolean success = true;
+            for(int i = 0; i < fronts.length; i ++){
+                if(n == fronts[i] && n == backs[i]){
+                    success = false;
+                    break;
+                }
+            }
+            if(success){
+                return n;
+            }
+        }
+        return 0;
+    }
+
+}
diff --git a/problems/src/dynamic_programming/LargestSumOfAverages.java b/problems/src/dynamic_programming/LargestSumOfAverages.java
@@ -0,0 +1,65 @@
+package dynamic_programming;
+/**
+ * Created by gouthamvidyapradhan on 04/05/2018.
+ * We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?
+
+ Note that our partition must use every number in A, and that scores are not necessarily integers.
+
+ Example:
+ Input:
+ A = [9,1,2,3,9]
+ K = 3
+ Output: 20
+ Explanation:
+ The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
+ We could have also partitioned A into [9, 1], [2], [3, 9], for example.
+ That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
+
+
+ Note:
+
+ 1 <= A.length <= 100.
+ 1 <= A[i] <= 10000.
+ 1 <= K <= A.length.
+ Answers within 10^-6 of the correct answer will be accepted as correct.
+
+ Solution: O(N x N x K): Calculate average for each sub-array starting from the right.
+ */
+
+public class LargestSumOfAverages {
+
+    public static void main(String[] args) {
+        int[] A = {9,1,2,3,9};
+        System.out.println(new LargestSumOfAverages().largestSumOfAverages(A, 3));
+    }
+
+    public double largestSumOfAverages(int[] A, int K) {
+        double[][] dp = new double[K][A.length];
+        for(int i = dp[0].length - 1; i >= 0; i --){
+            dp[0][i] = A[i];
+            if(i + 1 < dp[0].length){
+                dp[0][i] += dp[0][i + 1];
+            }
+        }
+
+        for(int i = dp[0].length - 1, j = 1; i >= 0; i --, j++){
+            dp[0][i] = dp[0][i] / j;
+        }
+
+        for(int i = dp[0].length - 1; i >= 0; i --){
+            for(int j = 1; j < dp.length; j ++){
+                double sum = 0.0D;
+                for(int k = i, c = 1; k < dp[0].length; k ++, c++){
+                    sum += A[k];
+                    if(k + 1 < dp[0].length){
+                        double avg = sum / c;
+                        avg += dp[j - 1][k + 1];
+                        dp[j][i] = Math.max(dp[j][i], avg);
+                    }
+                }
+            }
+        }
+        return dp[K-1][0];
+    }
+
+}
diff --git a/problems/src/hashing/ShortEncodingOfWords.java b/problems/src/hashing/ShortEncodingOfWords.java
@@ -0,0 +1,64 @@
+package hashing;
+
+import java.util.*;
+
+/**
+ * Created by gouthamvidyapradhan on 04/05/2018.
+ * Given a list of words, we may encode it by writing a reference string S and a list of indexes A.
+
+ For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0,
+ 2, 5].
+
+ Then for each index, we will recover the word by reading from the reference string from that index until  we reach a
+ "#" character.
+
+ What is the length of the shortest reference string S possible that encodes the given words?
+
+ Example:
+
+ Input: words = ["time", "me", "bell"]
+ Output: 10
+ Explanation: S = "time#bell#" and indexes = [0, 2, 5].
+ Note:
+
+ 1 <= words.length <= 2000.
+ 1 <= words[i].length <= 7.
+ Each word has only lowercase letters.
+
+ Solution: Sort the words by length and then use a hashmap to map each substring of a string with its position.
+ */
+public class ShortEncodingOfWords {
+    class Node {
+        String s;
+        int l;
+        Node(String s, int l){
+            this.s = s;
+            this.l = l;
+        }
+    }
+
+    public static void main(String[] args) {
+        String[] A = {"memo", "me", "mo"};
+        System.out.println(new ShortEncodingOfWords().minimumLengthEncoding(A));
+    }
+
+    public int minimumLengthEncoding(String[] words) {
+        List<Node> list = new ArrayList<>();
+        for(String w : words){
+            list.add(new Node(w, w.length()));
+        }
+        Collections.sort(list, (o1, o2) -> Integer.compare(o2.l, o1.l));
+        Map<String, Integer> map = new HashMap<>();
+        int count = 0;
+        for(Node node : list){
+            String str = node.s;
+            if(!map.containsKey(str)){
+                for(int i = 0, l = str.length(); i < l; i++){
+                    map.put(str.substring(i, l), count + i);
+                }
+                count += (str.length() + 1);
+            }
+        }
+        return count;
+    }
+}
