Introduction

1.Time Complexity in Coding interview

• O(1) 极少

• O(logn) 几乎都是二分法，比O(n)更优的时间复杂度几乎只能是O(logn)的二分法

• O(√n) 几乎是分解质因数

• O(n) 高频

• O(nlogn) 一般都可能要排序

• O(n2) 数组，枚举，动态规划

• O(n3) 数组，枚举，动态规划

• O(2n) 与组合有关的搜索

• O(n!) 与排列有关的搜索

2.面试中是否使用 Recursion 的几个判断条件

面试官是否要求了不使用 Recursion （如果你不确定，就向面试官询问）
不用 Recursion 是否会造成实现变得很复杂
Recursion 的深度是否会很深
题目的考点是 Recursion vs Non-Recursion 还是就是考你是否会Recursion？

• 记住：不要自己下判断，要跟面试官讨论！

3.经典二分搜索模板

start + 1 < end （不会陷入死循环）

start + (end - start) / 2

A[mid] ==, <, >

A[start] A[end] ? target

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

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

        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }