骨骼清奇Other

LC 849 Maximize Distance to Closest Person
LC 334 Increasing Triplet Subsequence
LC 215 Kth Largest Element in an Array
LC 769 Max Chunks To Make Sorted
LC 31 Next Permutation

[Uber]求n的阶层.F(n) = n(n-1)(n-2)....1; 但是n很大，所以不能整数相乘。我提出写一个helper function, 转换成两个string 相乘(Multiplication LC原题),但是他说一个可以不用转换， 直接用int.
[骨骼清奇]给定一个数组，将其分成两个subgroup使得二者的和相等。follow up： 如果是分成k个group怎么做？

remove ‘a' from char array (move zero 变形）
remove 'a' and replace 'b' with 'bee' from char array 用stringbuilder写完让我inplace O1 写. 扫两遍就行了 第一遍去a不变b，第二遍反着扫加bee. 可以两个pointer，一个start，一个end， start遇到b， end可以move backward with 'eeb' 然后reverse.第一题先从头向后移除‘a'， 同时算 'b'的个数
然后根据b的个数来算一个offset。
再从后向前扩展原子串吧.
利口把伞伞 + helllloooo那道面经
找到一个string的list里Kth most frequent element。bucket sort? 要求平均时间复杂度O(n)，注意是平均。follow up了一个平衡二叉树的查询平均时间复杂度是多少.

LC324

Q: Rearrange a linked list containing a single character per node so that each word is reversed but the overall word order is preserved thus
['h']->['i']->[' ']->['y']->['o']->['u']->null becomes
['i']->['h']->[' ']->['u']->['o']->['y']->null

第一轮题目是给定坐标系中的一堆点，然后求最小的横平竖直的矩形的面积。我只想到了n^3的暴力解法，还因为紧张一开始把复杂度说错了，写代码的时候还卡住了。这一轮表现很差。
第二轮是给定一堆LC标准Tree Node，然后要求判定这些node是否构成唯一合法的二叉树。题比较简单，没有费太大功夫。
第三轮比较奇怪，大概算是OOD题，要求设计一个能够支持模拟魔方的数据结构和后端API。花了很长时间才确定到底怎么做，而且代码量非常大，最后没写完。应该是没戏了。
第四轮是给定一个存有整数的iterator，这个iterator里每两个数字一组，每组的第一个数字表示要重复的次数，第二个数字表示要重复的数字，比如拿到[2, 3]就意味着3这个数字要重复两次。要求实现一个新的iterator，返回进行过重复后的数字（比如前例需要返回的是[3, 3, 3]）。比较简单，但是没能够bug-free，出现了数个bug在test过程中才改正。这一轮表现也不行。

Catalog:
LC 853 Car Fleet
LC 659 Split Array into Consecutive Subsequences

LC八五三（高速路车分cluster）
频率：5
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.
N cars are going to the same destination along a one lane road. The destination is target miles away.
Each car i has a constant speed speed[i] (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?
0 <= position[i] < target
All initial positions are different.

分析：如何判断车A会不会汇入它前面的车队？A到达终点的时间计算出来比车队长，就分别到达！因此我们按照出发地点排序，如果能追上前车，就merge，不能就continue.

class Solution:
    def carFleet(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        time = [float(target - p) / s for p, s in sorted(zip(position, speed))]
        #hour required for car at each position from left to right
        res = cur = 0
        for t in time[::-1]:
            if t > cur: #can not catch the car fleet upfront
                res += 1
                cur = t
        return res

LC 659 Split Array into Consecutive Subsequences [Freq:5]顺子
You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5

Input: [1,2,3,4,4,5]
Output: False