学校工程招聘会聊得，跟⼀个天竺哥聊了会就让我填了个时间约第二天面试。
⾯试是另⼀个天竺哥，45分钟，前5分钟吹b套近乎，后⾯出了道hard，我还没做过。
跟这题差不多 https://leetcode.com/problems/max-points-on-a-line/
给⼀个list of 2d points 然后输出⼀个equation ⽐如 y=2x，这个线穿过最多的点。
⼀开始⽐较懵逼，然后写暴力解，之后分析时间复杂度，后来在提示下优化了一下，还是感觉不咋地。
后来在⽹上查了一下，也没啥特别好的解。
⼀周多之后通知约电话⾯面试。让约一小时zoom。
我考了 https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/ 变种
Given a binary string of size N and a positive integer K, calculate the number of operations required to convert this string to zero string by applying the following operation any number of times.
Operation: Let X is the index of first ‘1’ bit from left side, then Flip all the X’th, X+K, X+2K, X+3K… bits of string.
1 <= N <= 10^6
1 <= K <= N
Sample:
Input: 100010010011110, K = 2
Step-1: 001000111001011
Step-2: 000010010011110
Step-3: 000000111001011
Step-4: 000000010011110
Step-5: 000000000110100
Step-6: 000000000011110
Step-7: 000000000001011
Step-8: 000000000000001
Step-9: 000000000000000
Brute force is easy; O(n^2 / k )
Optimization thought
I believe we need to use % operator here since X’th, X+K, X+2K, X+3K… that means x + pK where p= 1,2,3…
that left x as reminder.
Any thought how to solve this?
As per interviwer we can solve it in O(n) time and O(1) space