Amazon Mock Interview

Find Words That Can Be Formed By Characters

class Solution {
    
    String chars;
    int[] c;
    public int countCharacters(String[] words, String chars) {
        //dp
        
        this.chars = chars; 
        this.c = new int[26];
        
        for (int i = 0; i < chars.length(); i++) {
            this.c[chars.charAt(i) - 'a']++;
        }
        
        int[] comp = new int[26];
        int result = 0; 
        
        for (String w : words) {
            comp = c.clone();
            if (isSame(w, comp)) {
                result += w.length(); 
            }
        }
        
        return result; 
    }
    
    private boolean isSame(String word, int[] comp) {
        if (word.length() > this.chars.length()) {
            return false;
        }
        
        for (int i = 0; i < word.length(); i++) {
            if (comp[word.charAt(i) - 'a'] == 0) {
                return false; 
            } else {
                comp[word.charAt(i) - 'a']--;
            }
        }
        
        return true; 
    }
}

Runtime: 4 ms, faster than 96.40% of Java online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 39.5 MB, less than 69.59% of Java online submissions for Find Words That Can Be Formed by Characters.

Number of DIce Rolls with Target Sum

class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        if (d > target) { //너무 num이 작을때
            return 0; 
        }
        
        if (d * f < target) { //너ㅜ num이 클 때 
            return 0; 
        }
        
        
        int num = 0;
        int pos = (target - d) / f; //평균 느낌
        
        for (int i = 0; i < pos; i++) {
            num += probability(i, d, f, target);
        }
        
        return num;
        
    }
    
    public int probability(int i, int d, int f, int target) {
        int result = 1; 
        if (i % 2 == 1) {
            result = result * -1; 
        }
        
        int first = factorial(d) / (factorial(i) * factorial(d - i));
        int second = factorial(target - f * i - 1) / (factorial(d - 1) * factorial(target - f * i - d));
        
        return result * first * second; 
    }
    
    public int factorial(int n) {
        
        if (n == 1) {
            return 1;
        }
        
        return n * factorial(n-1);
        
    }
}

0 / 65 test cases passed.

https://mathworld.wolfram.com/Dice.html

이쫘식들...

class Solution:
    def numRollsToTarget(self, d, f, t):
        dp = {}
        def r_roll(dice, target):
            if target>f*dice:
                dp[dice, target] = 0
                return 0
            if dice == 0: return target==0
            if target <0: return 0
            if (dice, target) in dp: return dp[dice, target]
            ways = 0
            for num in range(1, f+1):
                ways+=r_roll(dice-1, target-num)
            dp[dice, target] = ways
            return ways
        return r_roll(d, t)%(10**9+7)

python
Runtime: 204 ms, faster than 82.60% of Python3 online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 15.3 MB, less than 52.79% of Python3 online submissions for Number of Dice Rolls With Target Sum.

class Solution {
    int MOD = 1000000000 + 7;
    Map<String, Integer> memo = new HashMap<>();
    public int numRollsToTarget(int d, int f, int target) {
        if (d == 0 && target == 0) {
            return 1;
        }
        if (target > d * f || d > target) {
            return 0;
        }
        String str = d + " " + target;
        if (memo.containsKey(str)) {
            return memo.get(str);
        }
        int res = 0;
        for (int i = 1; i <= f; i++) {
            if (target >= i) {
                res = (res + numRollsToTarget(d - 1, f, target - i)) % MOD;
            } else {
                break;
            }
        }
        memo.put(str, res);
        return res;
    }
}

Runtime: 45 ms, faster than 35.99% of Java online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 40.1 MB, less than 22.16% of Java online submissions for Number of Dice Rolls With Target Sum.