Mock Interview: Google

278. First Bad Version

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        //binary search
        int start = 1;
        int end = n;
        while (start < end) {
            int mid = start + ((end - start) / 2);
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
            
        }
        
        return start;
    }
}

Runtime: 12 ms, faster than 98.31% of Java online submissions for First Bad Version.
Memory Usage: 35.9 MB, less than 31.99% of Java online submissions for First Bad Version.

binary search를 써서 풀었읍니다~
근데 계속 overflow 에러가 나서
mid = (start + end) / 2로 한거를
mid = start + (end - start) / 2 로 바꾸니 통과됐다는점..
overflow 조심~

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int i = 0;
        while (! isBadVersion(i)) {
            i++;
        }
        
        return i;
    }
}

11 / 22 test cases passed.

binary search로 안풀려서 혹시나..^^하는 마음에 이렇게도 풀었읍니다
당근 Time Limit Exceeded 떴다는점~

1146. Snapshot Array

class SnapshotArray {
    int[] pictures;
    int snap_id;

    Map<Integer, int[]> snapshots = new TreeMap<Integer, int[]>(); 
    public SnapshotArray(int length) {
        pictures = new int[length];
        snap_id = 0;
    }
    
    public void set(int index, int val) {
        this.pictures[index] = val;
    }
    
    public int snap() {
        snapshots.put(snap_id, this.pictures.clone());
        snap_id++;
        return snap_id - 1;
    }
    
    public int get(int index, int snap_id) {
        int[] result = snapshots.get(snap_id);
        return result[index];
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

69 / 71 test cases passed.
Memory Limit Exceeded

처음에는 pictures를 clone 안하고 그냥 넣어서
값이 안바껴야 하는데 바뀌는..불상사가 있었지만
고쳤는데 이번에는 memory limit exceeded가 떳다는점~

루션이

class SnapshotArray {
    TreeMap<Integer, Integer>[] A;
    int snap_id = 0;
    public SnapshotArray(int length) {
        A = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            A[i] = new TreeMap<Integer, Integer>();
            A[i].put(0, 0);
        }
    }

    public void set(int index, int val) {
        A[index].put(snap_id, val);
    }

    public int snap() {
        return snap_id++;
    }

    public int get(int index, int snap_id) {
        return A[index].floorEntry(snap_id).getValue();
    }
}

Runtime: 38 ms, faster than 63.98% of Java online submissions for Snapshot Array.
Memory Usage: 88.7 MB, less than 20.74% of Java online submissions for Snapshot Array.

[] of treemap
저번에도 나왔는데 또 나왔네요..

앞으로 Map<Integer, int[]> 쓸 일 있으면 무조건 treemap이로 대신해보겠읍니다

** TreeMap을 쓸 때 알아두면 좋은

.floorEntry :
The floorEntry(K key) method is used to return a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.