堂妹来美国短期旅游，我可以给她办张我的信用卡副卡么？# Money - 海外理财
f*d
1 楼
补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
===============================================
Oct.19th ，东部时间1:30， 一面，印度a3
1，为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了，他表示赞同
2，分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤，他push我快快快，我一紧张，递归函数没有写好， 写出来之后
说用主定理，再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
3， 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque， 他表示赞同， 但是我始终没有到NlogN, 只
到了N^2, 其实以前做过，也学过，紧张了就是没有想起来
他说先做下一道吧
4, 给一个很长的bit array， reverse， 说bit array存在byte array中， bytes数
很大，强调百万规模， 硬是设了个大套给我。。。
我说先reverse byte array， 再reverse 每一个byte，我写了一个例子 （感觉在
拖延我的时间），他同意，让我写代码，
我不敢写那个O(1) 的reverse一个byte的算法，就一位一位对调的， 写完他说一
个byte最多有多少可能reverse， 我马上反应过了，说可以用个table， 他说是的，
然后我说这个方法很好。。。
5， 只有5分钟了， 说还有一个算法题给我做， 其实还有10来分钟，不算最后问他问
题的时间， 他吓我的，给n个点在平面上， 找一对点，连接成直线， 把剩下的点等分
在两个半平面中。这时候我有点不敢张口就来了， 想了30秒，他说 暴力 怎么搞， 我
缓过来了， 说O(N^3)的暴力算法，然后他说怎么优化， 我没有想出来，他说O（N^2）
可以，我说给点提示，他说其实暴力算法本质上的复杂度其实是O(N^2)的， 跟我解释
我始终没有听懂，装了一下懂。最后跟我说有有much much faster的算法， 又不说复
杂度， 我就开始想预处理排序， 猜测分x 或者 y坐标排序， 就是没有想到按极坐标
排序。计算几何问题完全没有准备，都搞dp字符串，树，甚至是图了，是按电面的标准
准备的，不觉得会考计算几何的。哎，还是准备不够充分。。。
最后回到第2题， 他说有两个算法，
Mul(vector Big1, Big2, int size)
{
res = Mul(Big1, ( first half of Big2) )* 10 ^ (size / 2) + Mul(Big1* (
second half of Big2);
}
X = Ax + B
m=A*A
n=B*B
p=(A+B)*(A+B) 其实应该是(A*B)
我表示赞同，他一说我就反应出来了，我说跟那个矩阵相乘的8变7很相似，我说是的，
他问我还记得那个算法名字不，我记不得了，就说记得中文名字，不记得英文怎么说了
，他大笑，。。。他说第二个方法用FFT， 我说恩，是的， 确实知道这个算法， 多项
式相乘
没啦， 计算几何题目让我回去想。。。
=======================================================
一个半小时后二面， 口音应该是老中，不过有时候真的有点听不懂
1， sorted 数组转平衡的bst
分析，写代码， 面试官表示同意
2， bst 给一个数，找出在bst中离这个数最近的节点
分析，没让我写代码，面试官表示同意
3， bst，分层打印各层最大的节点数值
反应用bfs， 分层打印的思路， 似乎不是他想要的， 但是这个也是O(n)的啊， 他还
能更块？ 或许空间更好， 我想，即使是便利，一般来说 空间至少也要O(h)吧， 就算
递归，递归栈也是O(h)， 当然了， bfs要用队列， 空间复杂度是O(w), 这些我都没有
说， 不敢顶嘴！ 就struggle， 他说只有20分钟了， 说就按照你的思路写吧， 那我
就只能写了， 中间有个bug他打住我了，应该存指针，我抽筋写成存节点值了， 他说
为了避免错的厉害， 先给我指出来了， 我马上改了，所以一直觉得他应该是会帮我的
。 最后终于写完了，他也表示赞同了。聊天。。。完。。。
几天后一大早接到电话说偶挂了。。。其他的我也没有多问了。。。
第三题后来在别人的指教下发现了更加精简的代码， O(n)的，类似于遍历~
包子！
===============================================
Oct.19th ，东部时间1:30， 一面，印度a3
1，为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了，他表示赞同
2，分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤，他push我快快快，我一紧张，递归函数没有写好， 写出来之后
说用主定理，再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
3， 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque， 他表示赞同， 但是我始终没有到NlogN, 只
到了N^2, 其实以前做过，也学过，紧张了就是没有想起来
他说先做下一道吧
4, 给一个很长的bit array， reverse， 说bit array存在byte array中， bytes数
很大，强调百万规模， 硬是设了个大套给我。。。
我说先reverse byte array， 再reverse 每一个byte，我写了一个例子 （感觉在
拖延我的时间），他同意，让我写代码，
我不敢写那个O(1) 的reverse一个byte的算法，就一位一位对调的， 写完他说一
个byte最多有多少可能reverse， 我马上反应过了，说可以用个table， 他说是的，
然后我说这个方法很好。。。
5， 只有5分钟了， 说还有一个算法题给我做， 其实还有10来分钟，不算最后问他问
题的时间， 他吓我的，给n个点在平面上， 找一对点，连接成直线， 把剩下的点等分
在两个半平面中。这时候我有点不敢张口就来了， 想了30秒，他说 暴力 怎么搞， 我
缓过来了， 说O(N^3)的暴力算法，然后他说怎么优化， 我没有想出来，他说O（N^2）
可以，我说给点提示，他说其实暴力算法本质上的复杂度其实是O(N^2)的， 跟我解释
我始终没有听懂，装了一下懂。最后跟我说有有much much faster的算法， 又不说复
杂度， 我就开始想预处理排序， 猜测分x 或者 y坐标排序， 就是没有想到按极坐标
排序。计算几何问题完全没有准备，都搞dp字符串，树，甚至是图了，是按电面的标准
准备的，不觉得会考计算几何的。哎，还是准备不够充分。。。
最后回到第2题， 他说有两个算法，
Mul(vector
{
res = Mul(Big1, ( first half of Big2) )* 10 ^ (size / 2) + Mul(Big1* (
second half of Big2);
}
X = Ax + B
m=A*A
n=B*B
p=(A+B)*(A+B) 其实应该是(A*B)
我表示赞同，他一说我就反应出来了，我说跟那个矩阵相乘的8变7很相似，我说是的，
他问我还记得那个算法名字不，我记不得了，就说记得中文名字，不记得英文怎么说了
，他大笑，。。。他说第二个方法用FFT， 我说恩，是的， 确实知道这个算法， 多项
式相乘
没啦， 计算几何题目让我回去想。。。
=======================================================
一个半小时后二面， 口音应该是老中，不过有时候真的有点听不懂
1， sorted 数组转平衡的bst
分析，写代码， 面试官表示同意
2， bst 给一个数，找出在bst中离这个数最近的节点
分析，没让我写代码，面试官表示同意
3， bst，分层打印各层最大的节点数值
反应用bfs， 分层打印的思路， 似乎不是他想要的， 但是这个也是O(n)的啊， 他还
能更块？ 或许空间更好， 我想，即使是便利，一般来说 空间至少也要O(h)吧， 就算
递归，递归栈也是O(h)， 当然了， bfs要用队列， 空间复杂度是O(w), 这些我都没有
说， 不敢顶嘴！ 就struggle， 他说只有20分钟了， 说就按照你的思路写吧， 那我
就只能写了， 中间有个bug他打住我了，应该存指针，我抽筋写成存节点值了， 他说
为了避免错的厉害， 先给我指出来了， 我马上改了，所以一直觉得他应该是会帮我的
。 最后终于写完了，他也表示赞同了。聊天。。。完。。。
几天后一大早接到电话说偶挂了。。。其他的我也没有多问了。。。
第三题后来在别人的指教下发现了更加精简的代码， O(n)的，类似于遍历~
