Mock Interview: Adobe #1

3167 ワード


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からbitslength-2までに1が現れると必ず2 bitなので+2、そうでなければ+1
では最後から2番目です.
1)残り2個1-bit 0(true)
2)2-bitは最後の2個を書いて1個しか残っていません(true)
3)最後は2ビット(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;
    }
}
これは欲張りだ
でもこれはよくわかりません…^^
何度も読んだけどやっぱりダメ~~!

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個しか覚えていないし、新しい最大のやつを加えて、最後の数字に戻ります~
ちょっと遅いので、露を探してみましたが、ありません;;;討論はあまり悪くないようだ.