Mock Interview: Adobe #1

1-bit and 2-bit Characters

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int l = bits.length;
        
        int i = 0;
        while (i < l - 2) {
        	//requires 2 bits
            if (bits[i] == 1) {
                i +=2;
            } else {
                i++;
            }
        }
        
        if (i == l - 2 && bits[l - 2] == 1) {
            return false;
        } else {
            return true; 
        }
        
    }
}

처음에는 문제가 뭔소린지 이해가 안되서 2번으로 넘어갔읍니다^^
0부터 bits.length - 2까지 만약에 1이 나온다면 무조건 2bit이니깐 +2를 해주고, 그게 아니라면 +1을 해줌
그렇게 마지막에서 2번째까지 가면

1) 1-bit 0이 2개가 남음 (true)
2) 2-bit이 마지막 2번째를 써서 1개밖에 안남음 (true)
3) 마지막이 2-bit임 (false)

이걸 기억해서 이대로 리턴해주면 됨~

Runtime: 0 ms, faster than 100.00% of Java online submissions for 1-bit and 2-bit Characters.
Memory Usage: 40.3 MB, less than 5.64% of Java online submissions for 1-bit and 2-bit Characters.

루션이

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.length - 1) {
            i += bits[i] + 1;
        }
        return i == bits.length - 1;
    }
}

루션이는 끝까지 가네요
이게 더 심플한듯
하지만 저는 제 코드가 더 이해하기 편하네요..^^

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = bits.length - 2;
        while (i >= 0 && bits[i] > 0) i--;
        return (bits.length - i) % 2 == 0;
    }
}

이건 greedy
근데 이건 이해가 잘 안됩니다....^^
이것저것 읽어봤는데도 안된다는 점~~!

Kth Largest Element in a Stream

class KthLargest {
    PriorityQueue<Integer> pq;
    int k;

    public KthLargest(int k, int[] nums) {
        pq = new PriorityQueue<Integer>((n1, n2) -> n1 - n2); //minheap
        this.k = k;
        
        for (int i = 0; i < nums.length; i++) {
            pq.offer(nums[i]);
            
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
    }
    
    public int add(int val) {
        pq.offer(val);
        
        if (pq.size() > k) {
            pq.poll();
        }
        
        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

Runtime: 19 ms, faster than 27.35% of Java online submissions for Kth Largest Element in a Stream.
Memory Usage: 49.9 MB, less than 5.27% of Java online submissions for Kth Largest Element in a Stream.

오랜만의 저의 친구 PriorityQueue의 컴백~~~!

뒤에 더하든 말든 상관 없으니 앞에 있는 놈들만 조진다는 느낌으로~ minheap을 만들어 뒀읍니다
그래서 k개만 기억하고 더하고 새로운 가장 큰 놈을 엎앤 후 마지막 숫자를 return~

좀 느려서 루션이를 찾아보려고 했는데 루션이가 없고;;;; discussion은 대충 비슷한 것 같네여