Mock Interview: Bloomberg

1480. Running Sum of 1d Array

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = []
        
        total = 0
        
        for i in nums:
            total = total + i
            result.append(total)
        
        
        return result

Runtime: 40 ms, faster than 64.89% of Python3 online submissions for Running Sum of 1d Array.
Memory Usage: 14.5 MB, less than 10.24% of Python3 online submissions for Running Sum of 1d Array.

최고의 문제~^^

1297. Maximum Number of Occurrences of a Substring

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int[] chars = new int[26];
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            chars[s.charAt(i) - 'a']++;
        }
        
        for (int j = minSize; j <= maxSize; j++) {
            int n = factorial(j);
            int bottom = 1;
            
            for (int k = 0; k < 26; k++) {
                if (chars[k] != 0) {
                    bottom = bottom * factorial(chars[k]);
                }
            }
            
            result += n / bottom;
            
        }
        
        return result;
    }
    
    private int factorial(int x) {
        int result = 1;
        for (int i = 1; i <= x; i++) {
            result = result * i;
        }
        
        return result;
    }
}

어디서부터 잘못됐을까..

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cnt = Counter()
        for size in range(minSize, maxSize+1):
            for i in range(len(s)-size+1):
                ss = s[i:i+size]
                if len(set(ss)) <= maxLetters:
                    cnt[ss]+=1
        return max(cnt.values()) if cnt else 0

Runtime: 2628 ms, faster than 12.91% of Python3 online submissions for Maximum Number of Occurrences of a Substring.
Memory Usage: 125.2 MB, less than 23.04% of Python3 online submissions for Maximum Number of Occurrences of a Substring.

문제가 이해가 안가요^^

1274. Number of Ships in a Rectangle

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *     public boolean hasShips(int[] topRight, int[] bottomLeft);
 * }
 */

class Solution {
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        int count = 0;
        if (! sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        for (int[] s : sea) {
            if (s[0] < topRight[0] && s[0] > bottomLeft[0] && s[1] < topRight[1] && s[1] > bottomLeft[1]) {
                count++;
            }
        }
        
        return count;
    }
}

이렇게 될거라는 희망이 있었어요..ㅎ

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *     public boolean hasShips(int[] topRight, int[] bottomLeft);
 * }
 */

class Solution {
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        int count = 0;
        if (! sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        
        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) {
            return 1;
        }
        
        int newx = (topRight[0] + bottomLeft[0]) / 2;
        int newy = (topRight[1] + bottomLeft[1]) / 2;
        
        return countShips(sea, new int[]{newx, newy}, bottomLeft)
            + countShips(sea, topRight, new int[]{newx + 1, newy + 1})
            + countShips(sea, new int[]{newx, topRight[1]}, new int[]{bottomLeft[0], newy + 1}) + countShips(sea, new int[]{topRight[0], newy}, new int[]{newx + 1, bottomLeft[1]});

    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Number of Ships in a Rectangle.
Memory Usage: 36.8 MB, less than 39.02% of Java online submissions for Number of Ships in a Rectangle.

아래에 있는 hint를 참고했읍니다..
4분할로 나눠서 재귀를 돌리는 방식