Binary Search Tree

  1. BinarySearch 所施加的对象是sorted吗？ it depends 但是是连续的

  2. 一定是Array吗？也可以是binary search tree

  3. 数据类型是什么？

本质：reduce half of current size, 所以时间是log(n)

BinarySearch是连续的黑或连续的白找分界线

Q1 L278 First Bad Version

1 1 1 1 0 0 0 0

public int firstBadVersion(int n){
    if(n <= 0) return n;
    if(n == 1) return isBadVersion(n)? 1 : 0;
    
    int left = 0, right = n;
    while(left + 1 < right){
        int mid = left+(right-left)/2;
        if(isBadVersion(mid)){
            right = mid;
        }else{
            left = mid;
        }
    }
    return isBadVersion(left)?left:right;
    
}

Q2 L374 Guess Number

note: -1 is target < mid

public int guessNumber(int n){
    if(n == 0) return n;
    int left = 1, right = n;
    while(left+1 < right){
        int mid = left + (right - left)/2;
        if(guess(mid) < 0){
            right = mid;
        }else{
            left = mid;
        }
    }
    return guess(left) == 0? left : right;
}

Q3 Classical Binary Search Template

left + right /2: integer overflow. left是integer所取的最大值减去1000， right是最大值减去10 --> 990/2 + left. integer可以装得下

corner case 顺序不能换

  • TC: log(n),因为每次取mid把n变成1/2 n,

  • SC: log(n)个mid，o(1)的话因为编译器的garbage collection机制

S1：找target: left <= right -> left = mid + 1, right = mid - 1;

S3：找分界线

public int binarySearch(int[] arr, int target){
    //corner case
    if(arr == null ||arr.length == 0) return -1;
    int left = 0;
    int right = arr.length-1;
    while(left < right + 1){
        int mid = left + (right-left)/2;
        if(arr[mid] == target){
            return mid;
        }
        if(arr[mid] < target){
            left = mid;
        }else{
            right = mid;
        }
    }
    if(arr[left] == target) return left;
    if(arr[right] == target) return right;
    return -1;

}

onsite面经：

  • ads amazon：

  • do sth risk; 坚持自己

  • OOD: video player; playlist design

  • most challenge project

  • OOD: design a delivery system with core objects like warehouse, customer address

  • negative feedback from customer

  • 背包问题，return maximum weight

  • BQ：miss deadline

  • Leetcode 39： combination sum --> DFS

  • BQ轮：backend position, why amazon, sth to reach

Q4 Start & Last position of Target

  • 4.2 first position of Target

    • find the 分界线, 并不是找到target就return

public int firstPosition(int[] arr, int target){
    if(arr == null || arr.length == 0) return -1;
    int left = 0, right = arr.length-1;
    while(left + 1 < right){
        int mid = left + (right - left)/2;
        if(arr[mid] < target){
            left = mid;
        }else{
            right = mid;
        }
    }
    if(arr[left] == target) return left;
    if(arr[right] == target) return right;
    return -1;
}

  • 4.3

    • check arr[right] first

    • arr[mid] <= target, left = mid

public int lastPosition(int[] arr, int target){
    if(arr == null || arr.length == 0) return -1;
    
    int left = 0, right = arr.length-1;
    while(left + 1 < right){
        int mid = left + (right - left)/2;
        if(arr[mid] <= target){
            left = mid;
        }else{
            right = mid;
        }
    }
    if(arr[right] == target) return right;
    if(arr[left] == target) return left;
    return -1;
}

  • 4.0 Start & Last

    • option1：两次binary search

    • option2：find the first position, then make the right at left position, ++, until the right position != target. [left, right)

    • which one is better?

      • option 1: TC = logn + logn = O(logn)

      • option 2: TC = logn + k

      • so, if k < logn, option is better; it depends the number of the repetition

    public static void main(String[] args) {
    int[] array = new int[] {1, 2, 3, 3, 3, 3,4,5};
    int target = 3;
    JavaApplication43 app = new JavaApplication43();
    int firstIndex = app.findStartAndLast(array, target);
    int lastIndex = app.findLast(array, firstIndex, target);
    System.out.println(firstIndex);
    System.out.println(lastIndex);
}

public int findStartAndLast(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }

    int left = 0, right = arr.length - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    if (arr[left] == target) {
        return left;
    }
    if (arr[right] == target) {
        return right;
    }
    return -1;

}
public int findLast(int arr[], int firstIndex,int target){
for(int i = firstIndex; i < arr.length; i++){
    if(arr[i] != target){
    return i-1;
    } 
}
return arr.length-1;
}

Q5 Closest Position of Target

  • clarify the one or two answer

  • demo first

  • find the dividing line

  • use S3:

    • option 1, right - target 和 target - left相比

    • option 2, use absolute(defensive / preventive drive / program)

public int binarySearch(int[] arr, int target){
    //corner case
    if(arr == null ||arr.length == 0) return -1;
    int left = 0;
    int right = arr.length-1;
    while(left < right + 1){
        int mid = left + (right-left)/2;
        if(arr[mid] == target){
            return mid;
        }
        if(arr[mid] < target){
            left = mid;
        }else{
            right = mid;
        }
    }
    return(Math.abs(arr[left] - target) < Math.abs(arr[right] - target)) ? left : right; 

}

Q5.1 k Closest position of Target

t = 9, 1 2 3 10 80 90 100

  • 再做一次谁近取谁

  • k需要和arr.length比较

public List<Integer> binarySearch(int[] arr, int target, int k){
    //corner case
    if(arr == null ||arr.length == 0) return -1;
    if(k > arr.length) return -1;
    List<Integer> ans = new ArrayList<>();
    if(k == arr.length){
        ans = Arrays.asList(arr);
    }
    
    int left = 0;
    int right = arr.length-1;
    while(k-- > 0){
        while(left < right + 1){
            int mid = left + (right-left)/2;
            if(arr[mid] == target){
                return mid;
            }
            if(arr[mid] < target){
                left = mid;
            }else{
                right = mid;
            }
        }
        ans.add(Math.abs(arr[left] - target) < Math.abs(arr[right] - target)) ? left : right) 
);
    }
    return ans;
    

}

Q6 Largest smaller Position of Target

  • 约等于first position

  • post-processing 需要注意target是否在最左边

Q7 Smallest larger Position of Target

  • 约等于last position

Q7.1 L35 Search Insert Range

  • given a target, find a position for the target to insert

Ref L34 Search for a Range

1 2 3 3 3 4 5 6

  • 开闭区间 need to be clarified

  • (1.9, 3.1) --> 2 3 3 3 --> int[2]{1,4}; 1, 4 are the index

  • [1.9, 3.1] --> need to equal 1.9 and 3.1

Q8 L162 Find Peak/Valley Element

  • 1 3 5 7 9 8 6 4 2 3 4 5

  • 1 1 1 1 1 0 0 0 1 1 1 1

  • Peak is the Turning point, Valley is the dividing line

  • compare arr[mid] with arr[mid-1] OR arr[mid+1]

  • need to clarify

    • which number is the peak, what about the maximum num

    • how many peaks

Q9 L702 UnknownSize Position of Target --> streaming flow

  • input太大，内存放不下, 放在硬盘里

    • 左边当右边，右边界每次乘二的方式向右扩大，使左右可以包含target

    • probing --> hash collision

    • use S1 since we are looking for a target

public int UnknownSize(MyArray myArray, int target){ //TODO: long
    if(arr == null || arr.length == 0) return -1;
    int left = 0;
    int right = 1;
    while( myArray.get(right) != null && myArray.get[right] < target){
        left = right;
        right *= 2;
    }
    while(left <= right){
        int mid = left + (right - left)/2;
        if(myArray.get(mid) != null && arr[arr[mid] == target) return mid;
        else if(myArray.get(mid) != null && arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    } 
    
    return -1;
    
    
}

9.2 Drop egg

  • 只有一个鸡蛋 --> 一层一层地试

  • 鸡蛋不限，尽量少

9.3 Bond

Q10 Matrix Position of Target

10.1 L74

[ [1, 3, 5, 7], [10, 11, 16, 20], 6 [1][2] [23, 30, 34, 50] ]

  • 可以展开成为一个array

S1: primitive 2 times binary search( logm + logn)

S2: int[][] matrix vs List<List<Integer>>

rows = matrix.length;

cols = matrix[0].length;

matrix[0][0] = 0;

matrix[rows-1][cols-1] --> rows * cols -1

array[mid] --> matrix[mid / cols][mid % cols]

public int[] matrixSearch(int[][] matrix, int target){
    //corner case
    if(matrix  == null || matrix[0].length == 0 || matrix[0] == null|| matirx[0].length == 0) 
    return new int[]{-1, -1};
    int rows = matrix.length;
    int cols = matrix[0].length;
    int start = 0, end = row * col -1;
    
    while(start <= end){
        int mid = start + (end - start) / 2;
        int i = mid / cols;
        int j = mid % cols;
        if(matrix[i][j] == target){
            return new int[]{i, j};
        }else if(matrix[i][j] > target){
            end = mid - 1;
        }else{
            start = mid + 1;
        }
    }
    return new int[]{-1, -1};  

}

TC: log(m*n) = logm + logn

面经：

  • tight time

  • design cache, TC: O(1)

    • clarify what is cache

    • implement a hashmap

  • most challenge project

  • find method

10.2 L240 Search a 2D Matrix || Quadrate Search

  • 不可以展开变成一个array

Q14 天平秤重 （三分法）：

  • 把一堆球分成ABC三份，A和B一样重，那么target 在C里

  • 或者哪边重，target在哪边

Q15 10堆球

（idealsum - sum）/ 0.1

Previous问题NextSort Algorithm

Last updated

Was this helpful?