f*********d
发帖数: 140 | 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)的，类似于遍历~ |
m****t
发帖数: 2329 | |
p*****2
发帖数: 21240 | |
d**e
发帖数: 6098 | 4 电面问了五道题？
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
d**********x
发帖数: 4083 | 5 我觉得是第一面的问题吧
最后那个题目不应该，冷静下来分析其实不难，而且是个典型题
不过面g怎么不紧张，对我也是个大问题。。
，
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
s*****2
发帖数: 68 | |
k****r
发帖数: 807 | |
l**b
发帖数: 457 | 8 潜水很久，发个帖子 ，支持楼主，A3可恶啊。
不是fresh的也这样考吗？学CS还是学数学啊？ |
d*********g
发帖数: 154 | 9
同问
【在 l**b 的大作中提到】
: 潜水很久，发个帖子 ，支持楼主，A3可恶啊。
: 不是fresh的也这样考吗？学CS还是学数学啊？
|
Q*******e
发帖数: 939 | 10 阿三明显不想让楼主过啊
一般电面是一个编程
多个概念就足够了吧 |
|
|
p*****2
发帖数: 21240 | |
e******o
发帖数: 757 | 12 第五题，可以先sort找到最低的一个点，然后对剩余的点算想对于x 轴的写率，sort邪
率。找中间的那个点。O(nlogn). |
l***i
发帖数: 1309 | 13 The first 4 problems of interviewer1 is in Dasgupta's textbook Algorithms. |
d**********x
发帖数: 4083 | 14 这不就是lz说的极坐标嘛。。。
【在 e******o 的大作中提到】
: 第五题，可以先sort找到最低的一个点，然后对剩余的点算想对于x 轴的写率，sort邪
: 率。找中间的那个点。O(nlogn).
|
e******o
发帖数: 757 | 15 是啊。丢人了。
【在 d**********x 的大作中提到】
: 这不就是lz说的极坐标嘛。。。
|
c********r
发帖数: 286 | |
p*****2
发帖数: 21240 | 17 3， bst，分层打印各层最大的节点数值
只是打印每一层最大的节点数值？那不都是最右边的吗？ |
l*****a
发帖数: 14598 | 18 对
我几个小时前也想问来得
【在 p*****2 的大作中提到】
: 3， bst，分层打印各层最大的节点数值
: 只是打印每一层最大的节点数值？那不都是最右边的吗？
|
d**********x
发帖数: 4083 | 19 不是满的啊，是存在的节点里面最右边的
【在 l*****a 的大作中提到】
: 对
: 我几个小时前也想问来得
|
l*****a
发帖数: 14598 | 20 咱们说的一样啊。似乎用按层打印的queue或者同层链接sibling 的方法都可以啊
【在 d**********x 的大作中提到】
: 不是满的啊，是存在的节点里面最右边的
|
|
|
d**********x
发帖数: 4083 | 21 按层打印就是lz说的bfs啊。。。
【在 l*****a 的大作中提到】
: 咱们说的一样啊。似乎用按层打印的queue或者同层链接sibling 的方法都可以啊
|
p*****2
发帖数: 21240 | 22
所以说这题算是简单题。如果没有更优的解。
【在 d**********x 的大作中提到】
: 按层打印就是lz说的bfs啊。。。
|
P******r
发帖数: 842 | 23 我觉得你应该要求再来一次店面。第一面太难为人了。而且你水平不错听起来。你应该
有理有据和recruiter说下第一面出了什么题，多少题，难度，多少时间。摆事实，讲
道理，争取一下。并且表示你的自信。反正死马当活马医。 |
A****e
发帖数: 310 | 24 老印的问题相当之彪悍。。。
老中的最后一道，用bfs不满意，那应该用什么啊？ |
p*****2
发帖数: 21240 | 25 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)
总的来说这题做错了
这道题没看明白。上边说分析复杂度，怎么又说递归没写好？ |
p*****2
发帖数: 21240 | 26
刚看了面试官不喜欢这个。
【在 p*****2 的大作中提到】
: 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)
: 总的来说这题做错了
: 这道题没看明白。上边说分析复杂度，怎么又说递归没写好？
|
p*****2
发帖数: 21240 | 27
说不定面试官想的是一个满数呢。
【在 d**********x 的大作中提到】
: 不是满的啊，是存在的节点里面最右边的
|
l*****a
发帖数: 14598 | 28 不是有一个用dummy结点，解决那个链接同层sibling的题目吗
是不是可以借鉴? 空间constant instead of a Queue
【在 A****e 的大作中提到】
: 老印的问题相当之彪悍。。。
: 老中的最后一道，用bfs不满意，那应该用什么啊？
|
p*****2
发帖数: 21240 | 29
你说的这个有next吧？
【在 l*****a 的大作中提到】
: 不是有一个用dummy结点，解决那个链接同层sibling的题目吗
: 是不是可以借鉴? 空间constant instead of a Queue
|
d**********x
发帖数: 4083 | 30 恩，我想了一下，主要是靠灵感，要是灵错了请指出。。
直接按照问题定义来，是可以做到时间O(n)空间O(1)的
具体就是使劲往右边走，然后输出，记录当前输出的最后一层层数 -- 当且仅当当前层
数大于记录的层数时输出。
当没有right child的时候，就往parent方向走，找到第一个具有left child的(注意区
分返回时是从right返回还是left返回)，然后继续重复以上算法
这样可以保证遍历的时候每层总是这一层的最右边节点先被访问到
没有parent指针的话可以利用child指针，不碍事。
【在 l*****a 的大作中提到】
: 不是有一个用dummy结点，解决那个链接同层sibling的题目吗
: 是不是可以借鉴? 空间constant instead of a Queue
|
|
|
p*****2
发帖数: 21240 | 31
你说的就是dfs一遍吧？
【在 d**********x 的大作中提到】
: 恩，我想了一下，主要是靠灵感，要是灵错了请指出。。
: 直接按照问题定义来，是可以做到时间O(n)空间O(1)的
: 具体就是使劲往右边走，然后输出，记录当前输出的最后一层层数 -- 当且仅当当前层
: 数大于记录的层数时输出。
: 当没有right child的时候，就往parent方向走，找到第一个具有left child的(注意区
: 分返回时是从right返回还是left返回)，然后继续重复以上算法
: 这样可以保证遍历的时候每层总是这一层的最右边节点先被访问到
: 没有parent指针的话可以利用child指针，不碍事。
|
d**********x
发帖数: 4083 | 32 对的，但是一般dfs需要递归，要O(h)空间。我说的是那个只用一个指针遍历的算法
【在 p*****2 的大作中提到】
:
: 你说的就是dfs一遍吧？
|
p*****2
发帖数: 21240 | 33
你的意思是，你的算法实现O(n), O(1)的tree的traversal？
【在 d**********x 的大作中提到】
: 对的，但是一般dfs需要递归，要O(h)空间。我说的是那个只用一个指针遍历的算法
|
d**********x
发帖数: 4083 | 34 是啊。
还记得CLRS的课后习题吗
【在 p*****2 的大作中提到】
:
: 你的意思是，你的算法实现O(n), O(1)的tree的traversal？
|
p*****2
发帖数: 21240 | 35
靠。没学过。这个很牛呀。能不能写个code看看。
【在 d**********x 的大作中提到】
: 是啊。
: 还记得CLRS的课后习题吗
|
d**********x
发帖数: 4083 | |
d**********x
发帖数: 4083 | 37 这个假设了不能修改树，我记得可以修改树的话是不用parent指针的
【在 d**********x 的大作中提到】
: http://blog.csdn.net/mishifangxiangdefeng/article/details/77084
: 刚加完班，你看看这个
|
p*****2
发帖数: 21240 | 38
这个code好说。主要是没有parent的话，如果可以修改树能达到O(n)的时间复杂度吗？
感觉是NlogN的复杂度。
【在 d**********x 的大作中提到】
: 这个假设了不能修改树，我记得可以修改树的话是不用parent指针的
|
d**********x
发帖数: 4083 | 39 应该可以的，进入子树时把父亲节点指向当前子树的指针指向爷爷，然后记录当前节电
备用
【在 p*****2 的大作中提到】
:
: 这个code好说。主要是没有parent的话，如果可以修改树能达到O(n)的时间复杂度吗？
: 感觉是NlogN的复杂度。
|
f*********d
发帖数: 140 | 40 多谢安慰！
我的记性哪里有那么好，
之前面完了就作了记录。。。
【在 m****t 的大作中提到】
: 你的记性真好。
: 安慰一下，然后以后机会还多呢。
|
|
|
f*********d
发帖数: 140 | 41 CS fresh MS 美国普通大学， 很多人眼里就是烂校吧。。。
国内本科学校，非211
【在 p*****2 的大作中提到】
: LZ什么背景，怎么被问了这么多题？
|
f*********d
发帖数: 140 | 42 嗯， 是5道，第1题很快就过了，所以就算四道吧:)
【在 d**e 的大作中提到】
: 电面问了五道题？
|
f*********d
发帖数: 140 | 43 嗯，是第一面的问题， 最后那题，已经思路不清晰了。碰到计算几何有点慌了，之前
没有准备。。。g店面来得快了点。。。
还有，面试前休息好很重要:)
【在 d**********x 的大作中提到】
: 我觉得是第一面的问题吧
: 最后那个题目不应该，冷静下来分析其实不难，而且是个典型题
: 不过面g怎么不紧张，对我也是个大问题。。
:
: ，
|
f*********d
发帖数: 140 | 44 CS
【在 d*********g 的大作中提到】
:
: 同问
|
f*********d
发帖数: 140 | 45 大牛，我基本功不够扎实， 您没有问题的！
【在 p*****2 的大作中提到】
: LZ的面试经历看的我很怕
|
f*********d
发帖数: 140 | 46 嗯，就是打印最右边的，BST可以做，不过代码显得有些臃肿， 我上一个dfs的吧， 别
人告诉我写的！估计面试官是想要这个。。。
void GetLevelMax(vector &ret, Node* root, int &curLevel, int &
visitedLevel)
{
if(!root) return;
if(curLevel > visitedLevel) {
ret.push_back(root->val);
visitedLevel++;
//always find the first current level that great than visited level
}
curLevel++;
//always find the first current level that great than visited level
GetLevelMax(ret, root->right, curLevel, visitedLevel);
GetLevelMax(ret, root->left, curLevel, visitedLevel);
curLevel--; // curLevel is always currently level...
}
CALL
GetLevelMax(ret, root, 1, 0)
【在 p*****2 的大作中提到】
: 3， bst，分层打印各层最大的节点数值
: 只是打印每一层最大的节点数值？那不都是最右边的吗？
|
f*********d
发帖数: 140 | 47 感谢大牛的支持！
想再准备准备了明年再试试，不知道6个月后可以再面不，有的说要一年。。。
【在 P******r 的大作中提到】
: 我觉得你应该要求再来一次店面。第一面太难为人了。而且你水平不错听起来。你应该
: 有理有据和recruiter说下第一面出了什么题，多少题，难度，多少时间。摆事实，讲
: 道理，争取一下。并且表示你的自信。反正死马当活马医。
|
f*********d
发帖数: 140 | 48 一紧张， 递归方程都写错了，
这个题他一直催我，说应该一看就知道复杂度
1 我还没有达到一看就知道复杂度的层次
2 求稳起见，写递归方程用主定理给复杂度，可惜我不争气，方程写出了个typo，被他
揪出来了，后面用主定理再次出错，a 和 b弄反了。
总之，还是自己不争气吧
【在 p*****2 的大作中提到】
: 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)
: 总的来说这题做错了
: 这道题没看明白。上边说分析复杂度，怎么又说递归没写好？
|
f*********d
发帖数: 140 | 49 O(n)时间 O(1)空间的遍历是morris遍历吧，而且只能是inorder的吧？
有O(n)时间 O(1)空间的 前序后续遍历算法吗？ 有的话请教教我撒，先谢谢了~~
【在 d**********x 的大作中提到】
: 是啊。
: 还记得CLRS的课后习题吗
|
l*****a
发帖数: 14598 | |
|
|
l*****a
发帖数: 14598 | 51 第一题题目都有问题吧
insertion/selection/bubble都是O(n2) ah
他们不是基于比较？
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
f*********d
发帖数: 140 | 52 谢谢大牛指出
应该是：
基于比较的排序问题复杂度下界为什么是O(nlogn)
【在 l*****a 的大作中提到】
: 第一题题目都有问题吧
: insertion/selection/bubble都是O(n2) ah
: 他们不是基于比较？
|
l*****a
发帖数: 14598 | 53 这个。。
你怎么回答的？
【在 f*********d 的大作中提到】
: 谢谢大牛指出
: 应该是：
: 基于比较的排序问题复杂度下界为什么是O(nlogn)
|
f*********d
发帖数: 140 | 54 额，我是这么回答的。。。
一组数的permutation的规模是 N!, 基于比较，每次最多去掉一半不合法的，所以问题
复杂度下界是 O(logN!) = O(nlogn)
【在 l*****a 的大作中提到】
: 这个。。
: 你怎么回答的？
|
l*****a
发帖数: 14598 | 55 从数学的角度看，这个对吗？
n! n^n
O(logN!) = O(nlogn)
【在 f*********d 的大作中提到】
: 额，我是这么回答的。。。
: 一组数的permutation的规模是 N!, 基于比较，每次最多去掉一半不合法的，所以问题
: 复杂度下界是 O(logN!) = O(nlogn)
|
m******s
发帖数: 165 | 56 两轮是intern？
第一轮题目略尴尬，是不是你简历里强调了自己算法基础很好。。。
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
j******2
发帖数: 362 | |
d**********x
发帖数: 4083 | 58 有啊，看我上面的叙述。
另外我发现leetcode上就有。
http://www.leetcode.com/2010/10/binary-tree-post-order-traversa
【在 f*********d 的大作中提到】
: O(n)时间 O(1)空间的遍历是morris遍历吧，而且只能是inorder的吧？
: 有O(n)时间 O(1)空间的 前序后续遍历算法吗？ 有的话请教教我撒，先谢谢了~~
|
f*********d
发帖数: 140 | 59 Cannot type Chinese for a moment...
NOT intern,
Didn't emphasis that...
【在 m******s 的大作中提到】
: 两轮是intern？
: 第一轮题目略尴尬，是不是你简历里强调了自己算法基础很好。。。
|
f*********d
发帖数: 140 | 60 Sorry, I don't know :)
just SDE
【在 j******2 的大作中提到】
: 请问一下楼主，是什么组阿？
|
|
|
f*********d
发帖数: 140 | 61 Cannot type Chinese for a moment.
I think stack take some space, so i don't think it is O(1) space complexity.
Or what i thought is totally wrong?
【在 d**********x 的大作中提到】
: 有啊，看我上面的叙述。
: 另外我发现leetcode上就有。
: http://www.leetcode.com/2010/10/binary-tree-post-order-traversa
|
d**********x
发帖数: 4083 | 62 但是我想我说的那个不是post-order，而是倒过来的in-order
no stack.
just iteration.
OH... i just googled it and didn't check the solution on leetcode
what i hit was just the comments:
gt said on March 14, 2011 Reply
There is something called MORRIS inorder traversal which does not require
any stack usage to perform the traversal… it uses a tree-transformation
technique to get the traversal done iteratively … not sure if we could
tweak it for post or pre-order traversal … i vaguely recollect it is not
possible for some reason … although i am not sure myself …
why cant we try and come up with an approach that doesnt involve usage of
stack per se ? … because if we do, we are merely mimicking the recursive
approach….
complexity.
【在 f*********d 的大作中提到】
: Cannot type Chinese for a moment.
: I think stack take some space, so i don't think it is O(1) space complexity.
: Or what i thought is totally wrong?
|
f*********d
发帖数: 140 | 63 对的对的!明白你的意思了 修改一下morris就完了嘛! 多谢大牛指教!
【在 d**********x 的大作中提到】
: 但是我想我说的那个不是post-order，而是倒过来的in-order
: no stack.
: just iteration.
: OH... i just googled it and didn't check the solution on leetcode
: what i hit was just the comments:
: gt said on March 14, 2011 Reply
: There is something called MORRIS inorder traversal which does not require
: any stack usage to perform the traversal… it uses a tree-transformation
: technique to get the traversal done iteratively … not sure if we could
: tweak it for post or pre-order traversal … i vaguely recollect it is not
|
p*****2
发帖数: 21240 | 64
morris是O(n)的吗？我怎么感觉是O(nlogn）呀？
【在 f*********d 的大作中提到】
: 对的对的!明白你的意思了 修改一下morris就完了嘛! 多谢大牛指教!
|
f*********d
发帖数: 140 | 65 二爷 morris 是 O(n)的！
【在 p*****2 的大作中提到】
:
: morris是O(n)的吗？我怎么感觉是O(nlogn）呀？
|
k**8
发帖数: 186 | |
f*********d
发帖数: 140 | 67 有些都是补的, 比如g的就是补的,面了都快两个月了...
当时g电面来得太快了点...
【在 k**8 的大作中提到】
: LZ好像最近几天面了好多家。。。 NB
|
k****n
发帖数: 1334 | 68 楼主题目偏难，很不公平
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
p*****2
发帖数: 21240 | 69
这个应该怎么算？每一个node都要找到他的prev那个node，感觉找这个不是logn的时间
吗？
【在 f*********d 的大作中提到】
: 有些都是补的, 比如g的就是补的,面了都快两个月了...
: 当时g电面来得太快了点...
|
f*********d
发帖数: 140 | 70 回二爷， 我是这么理解的，不知道能解释通否
观察每个节点被访问了多少次。 这个算法看起来貌似是2次，也有可能是3次或者4次，
但应该是常数。所以是O（n）的。。。
不过我想在面试中应该没有人期望我们写这个算法吧， 如果没有见过，能现场中想出
来，那是大神中的大神了:)
【在 p*****2 的大作中提到】
:
: 这个应该怎么算？每一个node都要找到他的prev那个node，感觉找这个不是logn的时间
: 吗？
|
|
|
p*****2
发帖数: 21240 | 71
我刚才画了画，确实像你说的这样。应该是O(n)。不过我那个角度我还没想太清楚。感
觉叶子都不会有重复访问，而且只是root需要logn, 所以那么算应该不太对
【在 f*********d 的大作中提到】
: 回二爷， 我是这么理解的，不知道能解释通否
: 观察每个节点被访问了多少次。 这个算法看起来貌似是2次，也有可能是3次或者4次，
: 但应该是常数。所以是O（n）的。。。
: 不过我想在面试中应该没有人期望我们写这个算法吧， 如果没有见过，能现场中想出
: 来，那是大神中的大神了:)
|
s*******n
发帖数: 97 | 72 这些算法都不好写，简单一点就是用一个O(h)的数组，便利一次就好了，比BFS clean.
【在 f*********d 的大作中提到】
: 对的对的!明白你的意思了 修改一下morris就完了嘛! 多谢大牛指教!
|
d**********x
发帖数: 4083 | 73 最多三次
下来的时候一次，右子树返回一次，左子树返回一次，以后就一直往上了
时间
【在 f*********d 的大作中提到】
: 回二爷， 我是这么理解的，不知道能解释通否
: 观察每个节点被访问了多少次。 这个算法看起来貌似是2次，也有可能是3次或者4次，
: 但应该是常数。所以是O（n）的。。。
: 不过我想在面试中应该没有人期望我们写这个算法吧， 如果没有见过，能现场中想出
: 来，那是大神中的大神了:)
|
f*********d
发帖数: 140 | 74 牛！ 学习了~
【在 d**********x 的大作中提到】
: 最多三次
: 下来的时候一次，右子树返回一次，左子树返回一次，以后就一直往上了
:
: 时间
|
f*********d
发帖数: 140 | 75 嗯， 是的， 多谢大牛指点！
前面我上了一个递归的dfs的代码，也是其他大牛指教的， 递归栈的深度应该就是O(h)
的~
clean.
【在 s*******n 的大作中提到】
: 这些算法都不好写，简单一点就是用一个O(h)的数组，便利一次就好了，比BFS clean.
|
t*********h
发帖数: 941 | 76 第五题怎么回事 有人说说马
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
e****e
发帖数: 418 | 77 DFS approach. My code is lousy, the point is to show the DFS approach.
Thanks.
public int[] dFS(TreeNode root ) {
int depth = depth( root );
int[] r = new int[depth];
boolean[] m = new boolean[depth];
if ( root == null )
return r;
dFSCore( root, new MutableInt(0), r, m );
return r;
}
private void dFSCore( TreeNode node, MutableInt level, int[] r, boolean[
] m ) {
if ( node == null )
return;
if ( m[level.val] == false ) {
m[level.val] = true;
r[level.val] = node.val;
}
level.val++;
dFSCore( node.right, level, r, m );
level.val--;
level.val++;
dFSCore( node.left, level, r, m );
level.val--;
}
private int depth( TreeNode node ) {
if ( node == null )
return 0;
return Math.max( depth( node.left ), depth( node.right ) ) + 1;
}
class MutableInt {
int val;
public MutableInt(int v) {
val = v;
}
} |
f*********d
发帖数: 140 | 78 eswine，请问是在做哪个问题啊？
【在 e****e 的大作中提到】
: DFS approach. My code is lousy, the point is to show the DFS approach.
: Thanks.
: public int[] dFS(TreeNode root ) {
: int depth = depth( root );
: int[] r = new int[depth];
: boolean[] m = new boolean[depth];
:
: if ( root == null )
: return r;
:
|
e****e
发帖数: 418 | 79 3， bst，分层打印各层最大的节点数值
【在 f*********d 的大作中提到】
: eswine，请问是在做哪个问题啊？
|
f*********d
发帖数: 140 | 80 前面有个简单点的，可以参考一下:)
【在 e****e 的大作中提到】
: 3， bst，分层打印各层最大的节点数值
|
|
|
f*********d
发帖数: 140 | 81 从数学角度，是不对的，
我们说的是从复杂度角度看，
O(logN!) = O(nlogn) 其实不够严谨
应该写 \omega(logN!) = \omega(NlogN), 即同阶:) 不知道你是不是这个意思？！
【在 l*****a 的大作中提到】
: 从数学的角度看，这个对吗？
: n! n^n
: O(logN!) = O(nlogn)
|
f*********d
发帖数: 140 | 82 k-selection, O(n)可解:) 可惜我没有从极角的角度思考。。。太紧张了:)
【在 e******o 的大作中提到】
: 第五题，可以先sort找到最低的一个点，然后对剩余的点算想对于x 轴的写率，sort邪
: 率。找中间的那个点。O(nlogn).
|
e****e
发帖数: 418 | 83 I didn't read the dfs code on previous post. Thank you for telling me. dfs
is the way to go.
【在 f*********d 的大作中提到】
: 前面有个简单点的，可以参考一下:)
|
b***u
发帖数: 61 | 84 算法书上讲的
h >= lg(n!)
>=lg((n/e)^n)
=nlg(n) - nlg(e)
=omega(nlgn)
所以对于任何一个基于比较的排序算法run time至少是nlgn |
f*********m
发帖数: 726 | 85 连接最低的点和斜率为中间值的点就能找到这条线吗？请问怎么解释？
谢谢。
【在 e******o 的大作中提到】
: 第五题，可以先sort找到最低的一个点，然后对剩余的点算想对于x 轴的写率，sort邪
: 率。找中间的那个点。O(nlogn).
|
l*****a
发帖数: 14598 | 86 no need to be the lowest
u can pick any point as a[0], then u have n-1 line as a[0]a[1],a[0]a[2]..a[0
]a[n-1]
considering the angel between the line and x axis.
sort them, pick the middle one
【在 f*********m 的大作中提到】
: 连接最低的点和斜率为中间值的点就能找到这条线吗？请问怎么解释？
: 谢谢。
|
f*********m
发帖数: 726 | 87 多谢大牛:)
[0
【在 l*****a 的大作中提到】
: no need to be the lowest
: u can pick any point as a[0], then u have n-1 line as a[0]a[1],a[0]a[2]..a[0
: ]a[n-1]
: considering the angel between the line and x axis.
: sort them, pick the middle one
|
l*****a
发帖数: 14598 | 88 不牛，见过而已
【在 f*********m 的大作中提到】
: 多谢大牛:)
:
: [0
|
j*****y
发帖数: 1071 | 89 一面的第三题一般是可以做到 n^(log3) 吧？
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的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)的，类似于遍历~
【在 f*********d 的大作中提到】
: 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
: 包子！
: ===============================================
: Oct.19th ，东部时间1:30， 一面，印度a3
: 1，为什么基于比较的排序问题复杂度下界是O(nlogn)
: 回答出来了，他表示赞同
: 2，分析下面递归算法的复杂度
: Alg(array, size)
: split -> A1, A2, A3.... O(n)
: Alg(A1, size/3)
|
w****x
发帖数: 2483 | |
|
|
w****x
发帖数: 2483 | 91 那个烙印这些题根本就是想灭你嘛， 楼主不要自责。
中国人最后那题可能是要这个解法：
void inner_get_rightmost(NODE* pNode, vector& vec, int nLev)
{
if (NULL == pNode)
return;
if (nLev >= vec.size())
vec.push_back(pNode);
inner_get_rightmost(pNode->pRgt, vec, nLev+1);
inner_get_rightmost(pNode->pLft, vec, nLev+1);
}
vector getRightMost(NODE* pRoot)
{
vector vec;
inner_get_rightmost(pRoot, vec, 0);
return vec;
} |
d**********n
发帖数: 132 | 92 大数平方该怎么做呀？这个跟大数乘法是一样样的吗？ |
w****x
发帖数: 2483 | 93
那个公式我怎么看怎么不是nlogn
【在 d**********n 的大作中提到】
: 大数平方该怎么做呀？这个跟大数乘法是一样样的吗？
|
l*****i
发帖数: 136 | 94 第一面问的真是多啊，FFT都出来了，要我估计也是挂
LZ能做到这样已经很不错了 |
