我看了面经觉得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