General Advice

1. 理清楚需求，问清楚边界条件，系统限制，异常情况该如何处理。
2. 解释清楚你的算法，必要的话可以画图或者写伪代码来解释。
3. 等面试官认可你的算法之后，用代码去实现你的算法。在写代码过程中，可以写一段然后说一下，自己现在要干什么干什么，确保面试官一直在跟着你的思路。也做好随时回答面试官问题的准备。
4. 写完实现以后，主动写测试案例。通过自己的测试案例找出 bug 其实是加分项。设计好测试案例，测试案例要有代表性。
5. 讲一下自己算法的时间复杂度和空间复杂度，然后等面试官有没有其他问题。

Algorithms

Array

convert every elements to negative to represent this element is already queried

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

  void function(vector<int> &nums) {
    int n = nums.size();
    int dup = -1;
    for (int i = 0; i < n; i++)
    {
        int index = abs(nums[i]) - 1;
        if (nums[index] < 0)
        {
            dup = abs(nums[i]);
        }
        else
        {
            nums[index] *= -1;
        }
    }
  }

Sliding Window

Generally, the sliding window problems have some kind of aggregate, atMost k, largest substring, min substring with k etc. They’re always “given an array or string, find some computed sub problem” value.

Sliding Window ProblemSet

• 992. Subarrays with K Different Integers

Binary Search

1. correctly initialize the boundary variables l and r. Only one rule: set up the boundary to include all possible elements
2. Decide return value.After exiting the while loop, l is the minimal k satisfying the condition function
3. Design the condition function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def binary_search(arr) -> int:
  def condition(value) -> bool:
    pass
  l, r = 0, len(arr)
  while l < r:
    m = l + (r - l) // 2
    if condition(m):
      r = m
    else:
      l = m + 1
  # left insert position
  return l

Binary Search ProblemSet

• Powerful Ultimate Binary Search Template. Solved many problems.