一面 一道题，但有followup
四二六 变体，普通的binary tree，没有sort， 楼主用了 recursion 解法，interviewer 问的很细致，需要跑 case 解释代码
中间问了很多 case （楼主也主动提出了一些 corner case， 比如 highly skewed， 向左向右skew， 只有一个 node 等等） 代码是否正确 和相关问题，
比如 recursion 有啥问题没 （回答了可能会 stack overflow，以及可以手工用 stack 来模拟递归的 implicit stack）
followup 是 反过来 从circular doubly linkedlist 转 binary tree，
这个楼主解释了如何用 recursion 去做，中间卡住了一会儿又改用 iteration，
最后还是没写完，只能看运气求过了。
二面 两题
二面是老印interviewer，开始有些担心会出难和怪的题， 不过人还是很nice，
一开始就说明两道题，需要不停的 talk，不要 silence。中间有几秒钟停顿了我还以为电话质量不好，赶紧确认，他回应了才继续。
虽然他介绍自己工作的时候有些话听的不是很明白，但面试还是蛮顺利，不知道不会让过。
第一题：valid number 稍微简化的，没有 逗号和 指数处理之类的，但有正负和首位0之类的处理。明确说明考察 edge case 处理
# str: "12345" --- absolutely any string -> int32: 12345
其实一开始很纠结， 这是道 hard 题 用 state machine 做法，有很多 states 要处理，
后来和 interviewer 不断沟通输入输出才确定不需要考虑很复杂的。
我自己给了一些例子比如：
1,233, 456 这个他说不用考虑这么复杂
0123 -> 123
-12 34 -> -1234
1a23 -> invalid （自定义输出指，楼主用的 Python 就输出了 None）
楼主解法是逐个反向 iterate 每个字符，转成 int 再乘 10 累加
大概是这么写的：
def convert_number(s):
no= 0
fori, c in enumerate(s):
try:
c_i = int(c) # interviewer 说单个字符可以用 int 转，如果不行，其实可以用 ord(c) - ord('0')
except :
pass
if c_i == 0:
continue
if i == 0:
no += c_i
else:
no += c_i * 10 ** (i - 1)
return -no if s[0] == '-' else no
第二题：First Bad Version 变体，看起来简单的二分查找，其实考察点非常细，而且页非常注重 testcase 和 communication
题目：看到interviewer 走了把题copy出来了（不会有啥问题吧），
17 <-- good
18
19
20
21
22 <-- bad
# Given. Takes 11 hours to run.
def is_good(svn_version) -> bool:
first_bad(good=3, bad=6) -> 5
is_good(3) -> True
is_good(4) -> True
is_good(5) -> False
is_good(6) -> False
# Implement this one
def first_bad(good, bad) -> int:
沟通真的很重要，确认输入输出含义，怎么转化成二分查找。其中最重要的是如何找testcase以及优化 (注意 call 一次 is_good 要花费很长时间)
说他nice 是因为写完了基本的binary search 他会带着跑一些case (楼主想先自己跑来着，他就直接开始了)，并且给出可能的优化点
楼主的做法：
def first_bad(good, bad) -> int:
while good < bad:
mid = (good + bad) // 2
if is_good(mid):
good = mid + 1
else:
bad = mid
# 注意以下两行，一开始放在了mid之前，被带着跑 testcase 发现有问题，后来放这里了，稍微检查了一下（时间不够了）
if bad - good <= 1:
return bad
return good
下面是几个 testcase (其实最好自己能提出来，不够 interverer 好像也不是很介意)
我解释了奇偶数目的case，不过interverer 很关心 is_good 的 call 次数，反复举例子可以优化
标 * 表示 bad version
# *
# 3, 4, 5, 6
# *
# 3, 4, 5
# *
# 3, 4, 5, 6
# *
# 3, 4, 5
# *
# 3, 4
总的体验很好，感觉基本功和熟练度非常重要而且会考察的很细致， 就算是面经题，变化无穷，基本功扎实才能灵活应对。
基本的tree，bfs，dfs，recursion，stack，binary search 不仅要深入理解而且非常灵活去运用(举个例子：recursion stack 何时返回，
linkedlist pointer 如何操作保证不出错，binary search 的边界条件怎么去根据具体问题优化等等)。
说白了需要多刷题，多总结 （比如自己提出变种练习以加强深入理解算法和数据结构），再多刷几遍题及刷变种（增加熟练度）
楼主过了真是的运气好，因为个人感觉熟练度不太够，部分算法和基本数据结构也深入理解不够，说白了还是题刷了不够多， 集中准备了一个月目前才刷了面经题130道，有些还不是很熟，没有做到four passes。
没过也很正常，当作一次面试练习吧，最大的感受是最好把刷题 workload 均摊到平时（比如每天一两道刷透，总结到位）来准备明年找全职的工作，
因为这一个月楼主白天需要忙学校的两个research project，还每周开会，只能晚上几个小时熬夜刷题，均摊到平时应该会好很多。