Mock Interview: Microsoft #5

Fibonacci Number

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        
        if (n == 1) {
            return 1;
        }
        
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        m.put(0, 0);
        m.put(1, 1);
        
        for (int i = 2; i < n; i++) {
            int val = m.get(i - 1) + m.get(i - 2);
            m.put(i, val);
        }
        
        return m.get(n-1) + m.get(n-2);

        
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 35.7 MB, less than 62.87% of Java online submissions for Fibonacci Number.

알고리즘의 1번... 피보나치

루션이 보고 놀라 자빠졌읍니다;
이거 어렵게 풀라면 ㅈㄴ 어렵게 풀 수 있군요..

루션이

class Solution {
    public int fib(int N) {
        int current = 0; // F(0)
        int previous = 1; 
        for (int i = 0; i < N; i++) {
            current = current + previous;
            previous = current - previous;
        }
        return current;
    }
}

하지만 저는 어려운건 패스하고..^^ 뷰티풀한 루션이 하나 들고왔읍니다
사람들 진짜 머리좋아

Distribute Candies

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> s = new HashSet<Integer>();
        int types = 0;
        for (int i = 0; i < candyType.length; i++) {
            if (! s.contains(candyType[i])) {
                s.add(candyType[i]);
                types++;
            }
        }

        return Math.min(types, candyType.length / 2);
    }
}

Runtime: 36 ms, faster than 24.69% of Java online submissions for Distribute Candies.
Memory Usage: 40.6 MB, less than 87.10% of Java online submissions for Distribute Candies.

너무 느려서 파이선으로도 풀어봤읍니다..

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        types = {}
        types = set()
        t = 0
        for c in candyType:
            if c not in types:
                t = t + 1
                types.add(c)
        
        return int(min(t, len(candyType) / 2))
        

Runtime: 876 ms, faster than 13.00% of Python3 online submissions for Distribute Candies.
Memory Usage: 16.4 MB, less than 38.88% of Python3 online submissions for Distribute Candies.

더 느려졌다는 점...^^

루션이

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
       
        return int(min(len(set(candyType)), len(candyType) / 2))
        

Runtime: 776 ms, faster than 87.09% of Python3 online submissions for Distribute Candies.
Memory Usage: 16.3 MB, less than 64.26% of Python3 online submissions for Distribute Candies.
파이선 한줄솔루션
걍 세트에 한방에 넣어버려

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> s = new HashSet<Integer>();
        int types = 0;
        for (int i = 0; i < candyType.length && types < candyType.length / 2; i++) {
            if (! s.contains(candyType[i])) {
                s.add(candyType[i]);
                types++;
            }
        }

        return Math.min(types, candyType.length / 2);
    }
}

Runtime: 22 ms, faster than 91.74% of Java online submissions for Distribute Candies.
Memory Usage: 41.4 MB, less than 12.10% of Java online submissions for Distribute Candies.

types가 candyType.length / 2를 넘어가는 순간 답은 어짜피 candyType.length / 2가 되니깐 거기서 forloop 을 끝내주면 훨씬 빨라짐!!!!