我看了面经觉得Tree考的很多，follow up多是如何优化
写了个BST,从后往前打印。recursive/iterative
-
给一个sorted array， 和一个target，如果target在array里就返回index，否则返回target在这个array的插入位置 -> binary search
-
LC 977
-
判断一个数是不是fibonacci number，我没想到什么好办法就一个个生成数列直到超过给的数。他问如果这个函数会被调用的很频繁比如一天一百万次怎么办？我说在每次计算的时候可以把生成的fibonacci number存下来，再记录一个目前存着的最大的fibonacci number，这样下次我们看给的数小于这个max的话就查一下存下来的数里有没有就行；如果大于它我们再生成。他说你implement一下吧，我就用hashset去写了一下。写完以后又让想一些test case和edge case。
事后查一下发现有方法直接判断一个数字是不是fibonacci number，可以自己去google一下。但是感觉这种属于看过才知道，不看过不可能想出来的。不知道面试官问这种题的时候的expectation是什么样的呢？ -
写一个class，用来计算polynomial。就是给好了系数a[0] - a[N-1]，然后每次给一个输入x计算出结果。具体来说就是a[0] + a[1]*x + a[2]*x^2 + … + a[N-1]*x^(N-1)。说要efficient和考虑performance，但我除了在计算时在每次的x项后直接再乘一个x而不是用pow(x,n)来计算以外，也没想到有什么能优化的。求点拨。写完以后也是让写一些test case，负数、0都要考虑到，为了确定程序是对的。
同学hint(vectorization??) -
上来让实现一个支持template的stack
-
3sum
-
lru cache
-
int to str
-
reverse bits. 没什么太多，follow up问了一个，如果是个3 byte number我该怎么办，我有点懵逼没明白他想干什么，就问他再具体点说说，那边沉默了一下，我补上说如果byte比较多，可以弄个map来cache一下，然后又问了一遍能否提示一下3个byte有什么特殊的，结果他特么就这么略过了，就开始问下一个题。
-
construct tree from inorder and preorder traversal. 做题没什么问题。我觉得我做法挺普通的(就是lc大众做法)，结果他特么居然没明白，我最后举了三套例子，从头到尾说了一下怎么build。做题十分钟，举例子居然十分钟。 后来说了一下一个地方可以用个map优化成const time，过了。
-
constant space complexity traverse tree。 我说这是个morris traversal，每次改in order predecessor 的right pointer，然后再改回来。
-
Given a list of buy/sell transactions (e.g [(‘buy’, quantity: 100, price: 15), ( ‘sell’, quantity:10, price: 10), etc], calculate the final loss/profit
sell quantity <= buy quantity， don’t worry about sell exceeds buy amount cases. -
写一个class，有add和get的功能，add的输入是一个(time,price)的pair，get的输入是time，如果正好是已经add过的就返回对应的price值，否则返回<time的最近time对应的price值。存储有一个限制，就是只存time在最近5000以内的，比如如果之前有(1,2.2)，add进一个(5002,1.2)，那(1,2.2)就要删掉，因为小于5002-5000。
-
先是一道code， 给一个n x n distance矩阵A, Aij 代表行人i距离自行车j有多远，每个行人挑一辆自行车，求一种方法使总距离最小。 我直接用的dfs。
-
两道match， 一道常见的 corr(x,y) = 0.9, corr(y,z) = 0.9 求 corr(x,z)， 用det去做的，但是要怎么才能把corr想象成夹角，用夹角去做啊，求指教。
-
Inetger a = 100；Integer b = 100; Integer c = 1000; Integer d = 1000;
a==b, c==d 的结果分别是什么样的。答案是 a==b true, c == d false. 这个有多少人能想到呢。。然后问问什么。 -
然后让deisgn 一个MyInt class， 要能达到
MyInt a = MyInt.valueOf(v);
MyInt b = MyInt.valueOf(v);
a==b is always true;
followup是如何设计让这个class 做到thread safe。 -
假设有一个计算量很大要跑很长时间的function，如何设计cache，让其他有same input的function call 不用重复计算，而且在第一个function with input v运算完成时，其他有 same input的function就算没有算完也可以立刻得到这个结果。
说白了还是考parallel computing。 -
2 multiply/ 3 multiply follow up: 每个数只能用一次）输入是正序的怎么做？ 有负数
-
如果输入不是sparse number，那么输出下一个sparse number， 如果是就输出当前输入
注：sparse number的定义是，如果一个数的二进制表示有连续的1，那么这个数就是sparse number，例如：10110就不是sparse， 101010就是 -
给一个时间为0时刻的board，每个点有三种值：I代表ice，T代表treasure，.代表空地，时间每+1，上下左右四个方向里有一个方向不是ice的ice会融化成空地。treasure只有一个。定义如果treasure可以由某一个边出发访问到（只能走空地，不能走ice），称treasure是accessible的，问经过多少时间treasure可以变的accessible。
-
用给一个有各种括号的字符串，找出有哪些字符串不匹配并且输出这些括号的index。
-
LC 105
-
LC 121
-
LC 19
-
HashMap底层实现
-
写一个sequence 的permutation，没有duplicate的
-
binary tree 转换成 linked list 如下
1
/ \
2 3
/ \ \
4 5 6
1->3->6->2->5->4
先提出一个BFS的作法，说ok，
但问有没有O(1) space的作法
想了一下用two pointers，说明一遍，也说ok