Mock Interview: Facebook #2

2699 ワード


Range Sum Query

class NumArray {

    int[] nums;
    
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += this.nums[i];
        }
        
        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */
Runtime: 62 ms, faster than 22.42% of Java online submissions for Range Sum Query - Immutable.
Memory Usage: 41.5 MB, less than 94.40% of Java online submissions for Range Sum Query - Immutable.
private int[] sum;

public NumArray(int[] nums) {
    sum = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }
}

public int sumRange(int i, int j) {
    return sum[j + 1] - sum[i];
}
caching~~~

Read N Characters Given Read4

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf4);
 */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    public int read(char[] buf, int n) {
        char[] four = new char[4];
        int read = 0;
        int copy = 0;
        
        while (read < n && copy < n / 4) {
            four = read4(four);
        }
        if (n >= buf.length) {
            return buf.length;
        } else {
            return (int) n; 
        }
        
    }
}
Wrong Answer
問題が何なのか分からないが...
public class Solution extends Reader4 {
    public int read(char[] buf, int n) {
        int copiedChars = 0, readChars = 4;
        char[] buf4 = new char[4];
        
        while (copiedChars < n && readChars == 4) {
            readChars = read4(buf4);
            
            for (int i = 0; i < readChars; ++i) {
                if (copiedChars == n)
                    return copiedChars;
                buf[copiedChars] = buf4[i];
                ++copiedChars;    
            }    
        }
        return copiedChars;
    }
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Read N Characters Given Read4.
Memory Usage: 36.6 MB, less than 97.22% of Java online submissions for Read N Characters Given Read4.