Mock Interview: Microsoft #4

Majority Element II

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        
        
        for (int i = 0; i < nums.length; i++) {
            m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
            
            if (m.get(nums[i]) > nums.length / 3) {
                result.add(nums[i]);
                m.remove(nums[i]);
            }
        }
        
        return result;
    }
}

Wrong Answer
80/82 test cases passed

처음에는 맵을 쓰고 없애는 방식을 쓰려고 했으나... 꼼수가 안통했다는점^^

• Storage가 O(1)이 아님

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        int i = 0;
        
        Arrays.sort(nums);
        int cur = nums[0];
        int count = 0; 
        while (i < nums.length) {
            cur = nums[i];
            while (i < nums.length && nums[i] == cur) {
                count++;
                i++;
            }
            
            if (count > nums.length / 3) {
                result.add(cur);
            }
            count = 0;
        }
        
        return result; 
    }
    
}

Runtime: 5 ms, faster than 41.36% of Java online submissions for Majority Element II.
Memory Usage: 46.3 MB, less than 11.05% of Java online submissions for Majority Element II.

O(1)

여기서 1/3로 한줄만 바꿔주면

while (i < nums.length - nums.length / 3)

Runtime: 3 ms, faster than 51.67% of Java online submissions for Majority Element II.
Memory Usage: 46.7 MB, less than 5.11% of Java online submissions for Majority Element II.

조금 올라가네여

+++ 루션이를 본 후기

정말 제가 작아지네요~^^

Boyer-Moore Voting Algorithm

class Solution {
    public List < Integer > majorityElement(int[] nums) {

        // 1st pass
        int count1 = 0;
        int count2 = 0;

        Integer candidate1 = null;
        Integer candidate2 = null;

        for (int n: nums) {
            if (candidate1 != null && candidate1 == n) {
                count1++;
            } else if (candidate2 != null && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1++;
            } else if (count2 == 0) {
                candidate2 = n;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }

        // 2nd pass
        List result = new ArrayList <> ();

        count1 = 0;
        count2 = 0;

        for (int n: nums) {
            if (candidate1 != null && n == candidate1) count1++;
            if (candidate2 != null && n == candidate2) count2++;
        }

        int n = nums.length;
        if (count1 > n/3) result.add(candidate1);
        if (count2 > n/3) result.add(candidate2);

        return result;
    }
}

1/3 이상이니깐 candidate이 최대 2개라는 점을 이용해서
만약 top 2 majority와 같은 값이 나온다면 그 값의 count는 올리고, 다른 것은 그대로. 만약 둘 다가 아닌 것이 나온다면 둘 다 1씩 빼고 그러다가 0이 되면 다음 나오는 값으로 대체한다. 끝에 남아있는 2 값을 가지고 이게 진짜 majority가 맞는지 한번 더 확인해서 arraylist에 넣어주면 됨... 진짜 천재 아닌지?

Rotate String

//여러개가 같을 수도 있음...ㅠㅠㅠㅠㅠ
class Solution {
    public boolean rotateString(String A, String B) {
        
        if (A.length() == 0 || B.length() == 0) {
            return A.equals(B); 
        }
        char start = A.charAt(0);
        int diff = 0;
        
        for (int i = 0; i < B.length(); i++) {
            if (B.substring(i).equals(A.substring(0, A.length() - i))) {
                diff = i; 
                break; 
            }
        }
        
        String newB = B.substring(diff) + B.substring(0, diff);
        
        return A.equals(newB);
    }
}

Runtime: 1 ms, faster than 35.17% of Java online submissions for Rotate String.
Memory Usage: 38.8 MB, less than 12.66% of Java online submissions for Rotate String.

뒤쪽에 남은 substring이 같은 지점을 찾아서 앞쪽도 같은지 보는 방식~

+++ 루션이

class Solution {
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A + A).contains(B);
    }
}

이게 좀 이해도 가고 제 머리에서 그나마 나올만한 방식 같네요..^^