Mock Interview: Microsoft #8

Rotate String

class Solution {
    public boolean rotateString(String A, String B) {
        
        if (A.length() != B.length()) {
            return false;
        } 
        return helper(A, B, 0);
    }
    
    private boolean helper(String A, String B, int times) {
        if (A.equals(B)) {
            return true;
        }
        
        if (times >= A.length()) {
            return false; 
        }
        
        String newA = A.substring(1) + A.substring(0, 1);
        
        return helper(newA, B, times + 1);
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate String.
Memory Usage: 37.4 MB, less than 23.53% of Java online submissions for Rotate String.

루션이는 분명 한줄이었는데... RG?^^

소름돋는 이야기

저 interview에다가는 시간이 촉박해서

class Solution {
    public boolean rotateString(String A, String B) {
        
        if (A.length() != B.length()) {
            return false;
        } 
        
        if (A.length() == 0) {
            return true; 
        }
        return helper(A, B, 0);
    }
    
    private boolean helper(String A, String B, int times) {
        if (times >= A.length()) {
            return false; 
        }
        
        if (A.equals(B)) {
            return true;
        }
        
        String newA = A.substring(1) + A.substring(0, 1);
        
        return helper(newA, B, times + 1);
    }
}

이렇게 넣었거든요?

근데 제출하고 보니깐 A.equals(B)가 먼저 오면 A.length() == 0가 없어도 된다는 것을 깨달아서 런타임도 더럽게 느린데 바꿔봤거든요???
그랬더니 30%에서 100%됨;

충격소름실화입니다.

런타임: O(n^2)

루션이

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

O(n^2)
^^

KMP ALGORITHM

class Solution {
    private int[] getLPS(String a){
        int i = 1, j = 0;
        int n = a.length();
        int[] lps = new int[n];
        while(i < n){
            if(a.charAt(j) == a.charAt(i)){
                lps[i] = j + 1;
                i++;
                j++;
            }
            else{
                if(j == 0)lps[i++] = 0;
                else j = lps[j-1];
            }
        }
        return lps;
    }
    private boolean contains(String a, String b){
        int[] lps = getLPS(b);
        int i = 0, j = 0;
        int n = a.length(), m = b.length();
        while(i < n && j < m){
            if(a.charAt(i) == b.charAt(j)){
                i++;
                j++;
            }
            else{
                if(j == 0) i++;
                else j = lps[j-1];
            }
        }
        return j == m;
    }
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && contains(A+A, B);
    }
}

Majority Element 2

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        //아 이거 한칸 띄우기 어쩌구 있었는데
        //at max 2 majority element!!
        
        List<Integer> result = new ArrayList<Integer>();
        
        int maj1 = nums[0];
        int count1 = 1;
        while (count1 < nums.length && nums[count1] == maj1) {
            count1++;
        }
        
        if (count1 == nums.length) {
            result.add(maj1);
            return result; 
        }
        
        int maj2 = nums[count1];
        int count2 = 1;
        
        for (int i = count1 + 1; i < nums.length; i++) {
            if (nums[i] == maj1) {
                count1++;
            } else if (nums[i] == maj2) {
                count2++;
            } else if (count2 <= 0) {
                maj2 = nums[i];
                count2 = 1;
            } else if (count1 <= 0) {
                maj1 = nums[i];
                count1 = 1; 
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == maj1) {
                count1++;
            } else if (nums[j] == maj2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(maj1);
        }
        
        if (count2 > nums.length / 3) {
            result.add(maj2); 
        }
        
        return result; 

    }
}

Runtime: 1 ms, faster than 99.82% of Java online submissions for Majority Element II.
Memory Usage: 43.2 MB, less than 21.76% of Java online submissions for Majority Element II.

이 루션이 충격적이었던 기억이 나서 풀었읍니다^^
1/3이상 갈 수 있는 수가 최대 2개니깐 그 점을 이용해서 빼고 더하는 방식~

루션이

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;
    }
}

찐 루션이가 조금 더 깔끔하네요
저는 후보를 정하고 시작했는데 루션이는 후보를 안정하고 one pass로 돌릴 수 있다는 점~

런타임: O(N)