w****a
发帖数: 710 | 1 背景：新鲜小硕，申的是2013北美new grads，SDE
地点：都柏林office
没签nda，直接放送了。坐等拒信，明年再来。
第一轮：
写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
需要描述详细时空复杂度，最好情况最坏情况和平均情况。
第二轮：
第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
开始他都没看懂。中间出了一点点小问题，但是改对了。因为我没考虑到1这个情况，4
的0次方是1。太粗心了。然后他让我别用hash_set，用普通方法做一个。我就写了个循
环的方法。循环的方法倒是一次性bug free了。pow4伺候完就开始第二题了。
最短路径那个时间不够了没做完。 不过没做完他倒是没说啥因为开始做这题的时候已
经就剩下10分钟了，他说没做完没事，讲下思路就行。我就没怎么花心思在code上，重
点讲了BFS，画了图给他描述了下。我估计这轮反馈不会很好。
第三轮：
这轮也就1题。很常规的DFS题。给一个board充满了字符，一个cell可以与其八方向连
接，返回整个board所有可能的单词的vector。这个不难写（但是还是出了点小bug啊。
粗心的人果然会与谷哥无缘阿）。然后follow是如果要求每个单词都要在字典里怎么改
。然后是详细询问时空复杂度。然后是详细询问时空复杂度，同样是最好最坏平均。最
后问我怎么优化。我说建trie树，过滤掉前缀不在字典的情况。他说不错，能告诉我大
概能优化多少么？2倍10倍还是100倍。多少倍答的不好，最后他很开心的告诉我是1000
倍。
午饭：
午饭那个小哥告诉我他被G拒了3次才进来的。。。。
第四轮：
这轮比较非主流，感觉在面杀毒软件公司。一开始面试官给我两个C函数，fgets和gets
。并给出函数原形。问我为什么fgets要size变量。我说为了安全。不然会内存越界。
他让我解释下内存越界怎样发生，什么危害。我就解释了比如本来传进来是大小10的
byte数组，结果把他当大小为12的buffer改，这个就越界了。越界后可能会crash。他
追问，你说可能crash，也就是有不会crash的情况咯？我说是，不同机器不同情况不同
场合不同OS遇到内存越界问题是不一样的。有的时候会崩溃，有的时候可能不崩，但是
堆栈帧会被改写，导致do different things。他说崩溃会怎么样。我说比如在windows
环境下，操作系统分配的Heap对象是有个标记检查的(边界检查），当写到别的heap对
象中操作系统会查出越界，抛出WIN32异常，通过__try __catch可以捕获并生成迷你
dump。他然后就让我解释下堆内存，我就说一般有三种内存形式，栈内存，堆内存，全
局或静态。栈内存分配释放快，堆内存分配释放慢(取决于OS)。他说那么我们现在回到
那个问题，我们不说堆内存就说栈空间，假设我现在用gets函数，传入了10字节大小的
栈上的数组，结果我实际写了14字节进去。这将怎样？我说会把下面的堆栈帧改写。导
致要么会crash，要么函数执行完毕后会返回到其他地方去（期间我在白板上花了堆栈
的一般形式，并且跟他解释了一般情况下栈内存是有哪些组成的（局部变量/参数/堆栈
帧））。然后他就问了，假如你现在在做一个web service，用户如何take advantage
of我们刚刚讨论的内容。这个问题我当时没想到，因为不是很理解他这个take
advantage of的意思。他后来就跟我解释了，假如我们现在在做一个输入密码并验证用
户的机制。如果允许用那种不限制size的不安全的C函数，比如gets，hacker怎样跳过
密码验证。我当时就理解他意思了。我就说比如密码固定10位，我传14位，剩下4位是
堆栈帧，传进去把他web service的堆栈帧改写，改到返回函数后直接跳到密码验证成
功的流程。他可算表示满意了。。然后让我想个办法实现堆栈帧的保护。我就说一般在
函数调用末尾写个宏_STACK_FRAME_PROTECTION_之类的，具体实现是在尾堆栈帧上面分
配一定大小的栈空间，然后函数调用结束时验证。他说可以，但是假如你是黑客你怎么
破解？我说假如我是黑客，我就反汇编调试进去，跟着试，试出我stack protection那
块栈内存的大小以及初始值，然后传入的参数的内存尾部搞一个跟他一样的一块数据，
然后再在后面写出我自己想要的堆栈帧。。他表示OK。最后他问我，哪些常用的C函数
有这类隐患。我sprintf之类的都有，所以在新版CRT中有sprintf_s之类的安全版本。
至此第四轮结束。
第五轮：
烙印终于来了。手舞足蹈的跟我搞了40分钟的基。非常欢乐，肢体语言很多。但是明显
不像会给我好feedback的样子，一路拍照。。。他先是问我归并排序的机制，我答了。然
后问我它哪里好。我说归并排序稳定，可以用于外部排序，处理大文件的时候不需要全部
装入内存，是一种分治策略。他说这确实是个有名的问题。然后说现在让你设计一个
interface来做归并排序。你要考虑online stream，fixed memory buffer之类的。然后
我写了个初步版本，然后他立即开始拍照。。我就感觉设计的有点问题，就慢慢在他的
指点下修改。最后给了个他满意的版本。。最终版本其实就是input给出front, move,
end接口，然后output只需要写emit接口。
用了template，然后传入参数的时候要传入函数对象，来执行判断方法。我当时用了
boost::function，他大叫i hate boost。我立马把boost::function改成了
google::function。其实我boost::function也记不住了具体参数是什么了，戒了boost
很久了。。改成了google::他立马开心了。。。然后我又迎合着他说我可以在模板参数
里传allocator，像STL那样。他咧嘴笑。。设计题完事儿后他问了C++的一个细节问题。
#include
int main()
{
std::cout << "Hello World”;
return 0;
}
同样是STL的std命名空间下的，为什么cout要std::，而<<不需要。然后问我
namespace NS
{
class A {};
void f( A *&, int ) {}
}
int main()
{
NS::A *a;
f( a, 0 ); //calls NS::f
}
为什么调用f(a,0)的时候不需要些NS::f(a,0)。说实话这个真不知道。。。他跟我说这
个是ADL机制。然后阴柔一笑：C++ always hurts people’s brain... |
l*********8
发帖数: 4642 | 2 我说怎么会是一个小时前的onsite呢，原来是都柏林office
good luck!
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
P*******b
发帖数: 1001 | 3 heapsort排序稳定吗？
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
w****a
发帖数: 710 | 4 打错了 是归并排序
【在 P*******b 的大作中提到】
: heapsort排序稳定吗？
|
l*********8
发帖数: 4642 | 5 "同样是STL的std命名空间下的，为什么cout要std::，而<<不需要"
这是为什么呢？ 也是ADL机制吗？
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
r*********n
发帖数: 4553 | 6 第三论的问题
起点给定了吗？如果没有给定起点，那么就太多种words了吧，因为每个word可以有不
同的permutation。 |
r*********n
发帖数: 4553 | 7 是啊，std::cout是<< operator的argument，所以ADL
【在 l*********8 的大作中提到】
: "同样是STL的std命名空间下的，为什么cout要std::，而<<不需要"
: 这是为什么呢？ 也是ADL机制吗？
|
w****a
发帖数: 710 | 8 没有起点，任意。
【在 r*********n 的大作中提到】
: 是啊，std::cout是<< operator的argument，所以ADL
|
w****a
发帖数: 710 | 9 其实他核心想问的是trie树优化。
【在 w****a 的大作中提到】
: 没有起点，任意。
|
r*********n
发帖数: 4553 | 10 那就每个点DFS走一次，但是应该走过的就不能再用了（否则无限多个words）
【在 w****a 的大作中提到】
: 没有起点，任意。
|
|
|
r*********n
发帖数: 4553 | 11 恩，不过那个1000倍有理论支持吗？我觉得更像是empirical result。
对了isPow4查表法怎么做哦？Thanks
【在 w****a 的大作中提到】
: 其实他核心想问的是trie树优化。
|
w****a
发帖数: 710 | 12 就hash_set，把int范围内的所有的都放到表里
【在 r*********n 的大作中提到】
: 恩，不过那个1000倍有理论支持吗？我觉得更像是empirical result。
: 对了isPow4查表法怎么做哦？Thanks
|
r*********n
发帖数: 4553 | 13 .....
确实不错，因为不会有很多pow4
【在 w****a 的大作中提到】
: 就hash_set，把int范围内的所有的都放到表里
|
w****a
发帖数: 710 | 14 是啊，面试管好像挺喜欢的，它当时有点吃惊。。。不过是不是可以用bit shift来做？
【在 r*********n 的大作中提到】
: .....
: 确实不错，因为不会有很多pow4
|
g*****o
发帖数: 1637 | 15 m
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l**b
发帖数: 457 | 16 我靠，这个很NB啊！bless，然后我觉得9成希望拿offer！ |
j*****y
发帖数: 1071 | 17 bless
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
w****a
发帖数: 710 | 18 多谢！！lanb你过几天A家onsite好运啊！
【在 l**b 的大作中提到】
: 我靠，这个很NB啊！bless，然后我觉得9成希望拿offer！
|
w****a
发帖数: 710 | 19 Thanks！！
【在 j*****y 的大作中提到】
: bless
|
f*******t
发帖数: 7549 | |
|
|
l*********8
发帖数: 4642 | 21 isPow4是什么意思？
问一个数字是不是4的幂？ 还是问一个数字是不是另一个数字的4次方？
做？
【在 w****a 的大作中提到】
: 是啊，面试管好像挺喜欢的，它当时有点吃惊。。。不过是不是可以用bit shift来做？
|
l*********8
发帖数: 4642 | 22 isPow4是什么意思？
问一个数字是不是4的幂？ 还是问一个数字是不是另一个数字的4次方？
做？
【在 w****a 的大作中提到】
: 是啊，面试管好像挺喜欢的，它当时有点吃惊。。。不过是不是可以用bit shift来做？
|
w****a
发帖数: 710 | 23 是不是4的幂。
【在 l*********8 的大作中提到】
: isPow4是什么意思？
: 问一个数字是不是4的幂？ 还是问一个数字是不是另一个数字的4次方？
:
: 做？
|
o****d
发帖数: 2835 | |
l*********8
发帖数: 4642 | 25 bit operation的话，可以这样做：
bool isPow4(int x) {
return !(x & 0xAAAAAAAA) && !(x & (x-1));
}
【在 w****a 的大作中提到】
: 是不是4的幂。
|
j*****y
发帖数: 1071 | 26 nice
【在 l*********8 的大作中提到】
: bit operation的话，可以这样做：
: bool isPow4(int x) {
: return !(x & 0xAAAAAAAA) && !(x & (x-1));
: }
|
w****a
发帖数: 710 | 27 嗯，当时就没敢往上面想。已经实现了两种方法了，万一bit搞错了不值，就索性不跟
他说这个了。。
【在 l*********8 的大作中提到】
: bit operation的话，可以这样做：
: bool isPow4(int x) {
: return !(x & 0xAAAAAAAA) && !(x & (x-1));
: }
|
l*********8
发帖数: 4642 | 28 面试官可能没想到过hashset的方法，expecting bit operations, 你的回答给了他惊
喜。效果还不错。
【在 w****a 的大作中提到】
: 嗯，当时就没敢往上面想。已经实现了两种方法了，万一bit搞错了不值，就索性不跟
: 他说这个了。。
|
j*****s
发帖数: 189 | 29 午饭那个小哥让我对人生又燃起了希望。
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l*********8
发帖数: 4642 | 30 "要求包含查找最小的节点的方法。并利用这个函数实现findNext()"
不是太明白， 怎么用findMin()来实现findNext()?
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
|
|
w****a
发帖数: 710 | 31 如果1个节点有右子树，他的next就是右子树的findMin
【在 l*********8 的大作中提到】
: "要求包含查找最小的节点的方法。并利用这个函数实现findNext()"
: 不是太明白， 怎么用findMin()来实现findNext()?
|
c********t
发帖数: 5706 | 32 bless, lz很强，坐等offer吧！
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
c********t
发帖数: 5706 | 33 你这个行吗？ 111？
这样可以吗？ return (x & 0xAAAAAAAA) == x || x==1;
【在 l*********8 的大作中提到】
: bit operation的话，可以这样做：
: bool isPow4(int x) {
: return !(x & 0xAAAAAAAA) && !(x & (x-1));
: }
|
c********t
发帖数: 5706 | 34 查找最小的节点的方法。并利用这个函数实现findNext()
how to use findLeftMostNode() to get findNext()? 有parent指针吗？
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l**b
发帖数: 457 | 35 可以吧，后面半段保证必须是power of 2. 111显然不是。
你那个的话，10101就通过了吧？
【在 c********t 的大作中提到】
: 你这个行吗？ 111？
: 这样可以吗？ return (x & 0xAAAAAAAA) == x || x==1;
|
w****a
发帖数: 710 | 36 给parent指针了。
【在 c********t 的大作中提到】
: 查找最小的节点的方法。并利用这个函数实现findNext()
: how to use findLeftMostNode() to get findNext()? 有parent指针吗？
|
l**b
发帖数: 457 | 37 再膜拜一下，第4轮太NB了，虽然我已经膜拜很久了。
【在 w****a 的大作中提到】
: 给parent指针了。
|
T********e
发帖数: 363 | |
w****a
发帖数: 710 | |
c********t
发帖数: 5706 | 40 嗯，明了，多谢！
【在 l**b 的大作中提到】
: 可以吧，后面半段保证必须是power of 2. 111显然不是。
: 你那个的话，10101就通过了吧？
|
|
|
c********t
发帖数: 5706 | 41 多谢！被你的第四轮震惊了。
【在 w****a 的大作中提到】
: 给parent指针了。
|
b***k
发帖数: 77 | 42 Buffer overflow attack:
http://en.wikipedia.org/wiki/Buffer_overflow
【在 c********t 的大作中提到】
: 多谢！被你的第四轮震惊了。
|
w****a
发帖数: 710 | 43 好文章！
【在 b***k 的大作中提到】
: Buffer overflow attack:
: http://en.wikipedia.org/wiki/Buffer_overflow
|
h****n
发帖数: 1093 | 44 bless 感觉很扣细节啊，拿到offer发包子吧
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l********5
发帖数: 230 | |
j********o
发帖数: 8 | 46 好多语言底层的问题，lz有这方面的背景么？bless |
p*****2
发帖数: 21240 | 47
貌似我就第四轮懂
【在 c********t 的大作中提到】
: 多谢！被你的第四轮震惊了。
|
p*****2
发帖数: 21240 | |
w****a
发帖数: 710 | 49 我在爱尔兰，就在本地面的。offer真不知道有没有。玄之又玄。
多谢二爷高看！
【在 p*****2 的大作中提到】
: LZ是在英国吗？估计offer跑不掉了
|
l*********8
发帖数: 4642 | 50 面得不错，bless!
【在 w****a 的大作中提到】
: 我在爱尔兰，就在本地面的。offer真不知道有没有。玄之又玄。
: 多谢二爷高看！
|
|
|
g****g
发帖数: 221 | |
f*******w
发帖数: 1243 | |
w****a
发帖数: 710 | 53 阴柔一笑快弄死我了。。
【在 f*******w 的大作中提到】
: 牛，bless
: 赞阴柔一笑
|
s****r
发帖数: 125 | 54 最后c++的那个叫 Koenig's name lookup, http://en.wikipedia.org/wiki/Argument-dependent_name_lookup.
Stephan T. Lavavej 的core c++的讲座里有讲到。
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
m*****k
发帖数: 731 | 55 findNext() is 'same' as inorder, parent pointer is not needed.
【在 l*********8 的大作中提到】
: "要求包含查找最小的节点的方法。并利用这个函数实现findNext()"
: 不是太明白， 怎么用findMin()来实现findNext()?
|
w****a
发帖数: 710 | 56 yep, 用stack也行。但是题目给了parent,不用白不用啦。
【在 m*****k 的大作中提到】
: findNext() is 'same' as inorder, parent pointer is not needed.
|
Z**********4
发帖数: 528 | |
w****a
发帖数: 710 | 58 背景：新鲜小硕，申的是2013北美new grads，SDE
地点：都柏林office
没签nda，直接放送了。坐等拒信，明年再来。
第一轮：
写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
需要描述详细时空复杂度，最好情况最坏情况和平均情况。
第二轮：
第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
开始他都没看懂。中间出了一点点小问题，但是改对了。因为我没考虑到1这个情况，4
的0次方是1。太粗心了。然后他让我别用hash_set，用普通方法做一个。我就写了个循
环的方法。循环的方法倒是一次性bug free了。pow4伺候完就开始第二题了。
最短路径那个时间不够了没做完。 不过没做完他倒是没说啥因为开始做这题的时候已
经就剩下10分钟了，他说没做完没事，讲下思路就行。我就没怎么花心思在code上，重
点讲了BFS，画了图给他描述了下。我估计这轮反馈不会很好。
第三轮：
这轮也就1题。很常规的DFS题。给一个board充满了字符，一个cell可以与其八方向连
接，返回整个board所有可能的单词的vector。这个不难写（但是还是出了点小bug啊。
粗心的人果然会与谷哥无缘阿）。然后follow是如果要求每个单词都要在字典里怎么改
。然后是详细询问时空复杂度。然后是详细询问时空复杂度，同样是最好最坏平均。最
后问我怎么优化。我说建trie树，过滤掉前缀不在字典的情况。他说不错，能告诉我大
概能优化多少么？2倍10倍还是100倍。多少倍答的不好，最后他很开心的告诉我是1000
倍。
午饭：
午饭那个小哥告诉我他被G拒了3次才进来的。。。。
第四轮：
这轮比较非主流，感觉在面杀毒软件公司。一开始面试官给我两个C函数，fgets和gets
。并给出函数原形。问我为什么fgets要size变量。我说为了安全。不然会内存越界。
他让我解释下内存越界怎样发生，什么危害。我就解释了比如本来传进来是大小10的
byte数组，结果把他当大小为12的buffer改，这个就越界了。越界后可能会crash。他
追问，你说可能crash，也就是有不会crash的情况咯？我说是，不同机器不同情况不同
场合不同OS遇到内存越界问题是不一样的。有的时候会崩溃，有的时候可能不崩，但是
堆栈帧会被改写，导致do different things。他说崩溃会怎么样。我说比如在windows
环境下，操作系统分配的Heap对象是有个标记检查的(边界检查），当写到别的heap对
象中操作系统会查出越界，抛出WIN32异常，通过__try __catch可以捕获并生成迷你
dump。他然后就让我解释下堆内存，我就说一般有三种内存形式，栈内存，堆内存，全
局或静态。栈内存分配释放快，堆内存分配释放慢(取决于OS)。他说那么我们现在回到
那个问题，我们不说堆内存就说栈空间，假设我现在用gets函数，传入了10字节大小的
栈上的数组，结果我实际写了14字节进去。这将怎样？我说会把下面的堆栈帧改写。导
致要么会crash，要么函数执行完毕后会返回到其他地方去（期间我在白板上花了堆栈
的一般形式，并且跟他解释了一般情况下栈内存是有哪些组成的（局部变量/参数/堆栈
帧））。然后他就问了，假如你现在在做一个web service，用户如何take advantage
of我们刚刚讨论的内容。这个问题我当时没想到，因为不是很理解他这个take
advantage of的意思。他后来就跟我解释了，假如我们现在在做一个输入密码并验证用
户的机制。如果允许用那种不限制size的不安全的C函数，比如gets，hacker怎样跳过
密码验证。我当时就理解他意思了。我就说比如密码固定10位，我传14位，剩下4位是
堆栈帧，传进去把他web service的堆栈帧改写，改到返回函数后直接跳到密码验证成
功的流程。他可算表示满意了。。然后让我想个办法实现堆栈帧的保护。我就说一般在
函数调用末尾写个宏_STACK_FRAME_PROTECTION_之类的，具体实现是在尾堆栈帧上面分
配一定大小的栈空间，然后函数调用结束时验证。他说可以，但是假如你是黑客你怎么
破解？我说假如我是黑客，我就反汇编调试进去，跟着试，试出我stack protection那
块栈内存的大小以及初始值，然后传入的参数的内存尾部搞一个跟他一样的一块数据，
然后再在后面写出我自己想要的堆栈帧。。他表示OK。最后他问我，哪些常用的C函数
有这类隐患。我sprintf之类的都有，所以在新版CRT中有sprintf_s之类的安全版本。
至此第四轮结束。
第五轮：
烙印终于来了。手舞足蹈的跟我搞了40分钟的基。非常欢乐，肢体语言很多。但是明显
不像会给我好feedback的样子，一路拍照。。。他先是问我归并排序的机制，我答了。然
后问我它哪里好。我说归并排序稳定，可以用于外部排序，处理大文件的时候不需要全部
装入内存，是一种分治策略。他说这确实是个有名的问题。然后说现在让你设计一个
interface来做归并排序。你要考虑online stream，fixed memory buffer之类的。然后
我写了个初步版本，然后他立即开始拍照。。我就感觉设计的有点问题，就慢慢在他的
指点下修改。最后给了个他满意的版本。。最终版本其实就是input给出front, move,
end接口，然后output只需要写emit接口。
用了template，然后传入参数的时候要传入函数对象，来执行判断方法。我当时用了
boost::function，他大叫i hate boost。我立马把boost::function改成了
google::function。其实我boost::function也记不住了具体参数是什么了，戒了boost
很久了。。改成了google::他立马开心了。。。然后我又迎合着他说我可以在模板参数
里传allocator，像STL那样。他咧嘴笑。。设计题完事儿后他问了C++的一个细节问题。
#include
int main()
{
std::cout << "Hello World”;
return 0;
}
同样是STL的std命名空间下的，为什么cout要std::，而<<不需要。然后问我
namespace NS
{
class A {};
void f( A *&, int ) {}
}
int main()
{
NS::A *a;
f( a, 0 ); //calls NS::f
}
为什么调用f(a,0)的时候不需要些NS::f(a,0)。说实话这个真不知道。。。他跟我说这
个是ADL机制。然后阴柔一笑：C++ always hurts people’s brain... |
l*********8
发帖数: 4642 | 59 我说怎么会是一个小时前的onsite呢，原来是都柏林office
good luck!
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
P*******b
发帖数: 1001 | 60 heapsort排序稳定吗？
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
|
|
w****a
发帖数: 710 | 61 打错了 是归并排序
【在 P*******b 的大作中提到】
: heapsort排序稳定吗？
|
l*********8
发帖数: 4642 | 62 "同样是STL的std命名空间下的，为什么cout要std::，而<<不需要"
这是为什么呢？ 也是ADL机制吗？
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
r*********n
发帖数: 4553 | 63 第三论的问题
起点给定了吗？如果没有给定起点，那么就太多种words了吧，因为每个word可以有不
同的permutation。 |
r*********n
发帖数: 4553 | 64 是啊，std::cout是<< operator的argument，所以ADL
【在 l*********8 的大作中提到】
: "同样是STL的std命名空间下的，为什么cout要std::，而<<不需要"
: 这是为什么呢？ 也是ADL机制吗？
|
w****a
发帖数: 710 | 65 没有起点，任意。
【在 r*********n 的大作中提到】
: 是啊，std::cout是<< operator的argument，所以ADL
|
w****a
发帖数: 710 | 66 其实他核心想问的是trie树优化。
【在 w****a 的大作中提到】
: 没有起点，任意。
|
r*********n
发帖数: 4553 | 67 那就每个点DFS走一次，但是应该走过的就不能再用了（否则无限多个words）
【在 w****a 的大作中提到】
: 没有起点，任意。
|
r*********n
发帖数: 4553 | 68 恩，不过那个1000倍有理论支持吗？我觉得更像是empirical result。
对了isPow4查表法怎么做哦？Thanks
【在 w****a 的大作中提到】
: 其实他核心想问的是trie树优化。
|
w****a
发帖数: 710 | 69 就hash_set，把int范围内的所有的都放到表里
【在 r*********n 的大作中提到】
: 恩，不过那个1000倍有理论支持吗？我觉得更像是empirical result。
: 对了isPow4查表法怎么做哦？Thanks
|
r*********n
发帖数: 4553 | 70 .....
确实不错，因为不会有很多pow4
【在 w****a 的大作中提到】
: 就hash_set，把int范围内的所有的都放到表里
|
|
|
w****a
发帖数: 710 | 71 是啊，面试管好像挺喜欢的，它当时有点吃惊。。。不过是不是可以用bit shift来做？
【在 r*********n 的大作中提到】
: .....
: 确实不错，因为不会有很多pow4
|
g*****o
发帖数: 1637 | 72 m
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l**b
发帖数: 457 | 73 我靠，这个很NB啊！bless，然后我觉得9成希望拿offer！ |
j*****y
发帖数: 1071 | 74 bless
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
w****a
发帖数: 710 | 75 多谢！！lanb你过几天A家onsite好运啊！
【在 l**b 的大作中提到】
: 我靠，这个很NB啊！bless，然后我觉得9成希望拿offer！
|
w****a
发帖数: 710 | 76 Thanks！！
【在 j*****y 的大作中提到】
: bless
|
f*******t
发帖数: 7549 | |
l*********8
发帖数: 4642 | 78 isPow4是什么意思？
问一个数字是不是4的幂？ 还是问一个数字是不是另一个数字的4次方？
做？
【在 w****a 的大作中提到】
: 是啊，面试管好像挺喜欢的，它当时有点吃惊。。。不过是不是可以用bit shift来做？
|
l*********8
发帖数: 4642 | 79 isPow4是什么意思？
问一个数字是不是4的幂？ 还是问一个数字是不是另一个数字的4次方？
做？
【在 w****a 的大作中提到】
: 是啊，面试管好像挺喜欢的，它当时有点吃惊。。。不过是不是可以用bit shift来做？
|
w****a
发帖数: 710 | 80 是不是4的幂。
【在 l*********8 的大作中提到】
: isPow4是什么意思？
: 问一个数字是不是4的幂？ 还是问一个数字是不是另一个数字的4次方？
:
: 做？
|
|
|
o****d
发帖数: 2835 | |
l*********8
发帖数: 4642 | 82 bit operation的话，可以这样做：
bool isPow4(int x) {
return !(x & 0xAAAAAAAA) && !(x & (x-1));
}
【在 w****a 的大作中提到】
: 是不是4的幂。
|
j*****y
发帖数: 1071 | 83 nice
【在 l*********8 的大作中提到】
: bit operation的话，可以这样做：
: bool isPow4(int x) {
: return !(x & 0xAAAAAAAA) && !(x & (x-1));
: }
|
w****a
发帖数: 710 | 84 嗯，当时就没敢往上面想。已经实现了两种方法了，万一bit搞错了不值，就索性不跟
他说这个了。。
【在 l*********8 的大作中提到】
: bit operation的话，可以这样做：
: bool isPow4(int x) {
: return !(x & 0xAAAAAAAA) && !(x & (x-1));
: }
|
l*********8
发帖数: 4642 | 85 面试官可能没想到过hashset的方法，expecting bit operations, 你的回答给了他惊
喜。效果还不错。
【在 w****a 的大作中提到】
: 嗯，当时就没敢往上面想。已经实现了两种方法了，万一bit搞错了不值，就索性不跟
: 他说这个了。。
|
j*****s
发帖数: 189 | 86 午饭那个小哥让我对人生又燃起了希望。
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l*********8
发帖数: 4642 | 87 "要求包含查找最小的节点的方法。并利用这个函数实现findNext()"
不是太明白， 怎么用findMin()来实现findNext()?
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
w****a
发帖数: 710 | 88 如果1个节点有右子树，他的next就是右子树的findMin
【在 l*********8 的大作中提到】
: "要求包含查找最小的节点的方法。并利用这个函数实现findNext()"
: 不是太明白， 怎么用findMin()来实现findNext()?
|
c********t
发帖数: 5706 | 89 bless, lz很强，坐等offer吧！
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
c********t
发帖数: 5706 | 90 你这个行吗？ 111？
这样可以吗？ return (x & 0xAAAAAAAA) == x || x==1;
【在 l*********8 的大作中提到】
: bit operation的话，可以这样做：
: bool isPow4(int x) {
: return !(x & 0xAAAAAAAA) && !(x & (x-1));
: }
|
|
|
c********t
发帖数: 5706 | 91 查找最小的节点的方法。并利用这个函数实现findNext()
how to use findLeftMostNode() to get findNext()? 有parent指针吗？
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l**b
发帖数: 457 | 92 可以吧，后面半段保证必须是power of 2. 111显然不是。
你那个的话，10101就通过了吧？
【在 c********t 的大作中提到】
: 你这个行吗？ 111？
: 这样可以吗？ return (x & 0xAAAAAAAA) == x || x==1;
|
w****a
发帖数: 710 | 93 给parent指针了。
【在 c********t 的大作中提到】
: 查找最小的节点的方法。并利用这个函数实现findNext()
: how to use findLeftMostNode() to get findNext()? 有parent指针吗？
|
l**b
发帖数: 457 | 94 再膜拜一下，第4轮太NB了，虽然我已经膜拜很久了。
【在 w****a 的大作中提到】
: 给parent指针了。
|
T********e
发帖数: 363 | |
w****a
发帖数: 710 | |
c********t
发帖数: 5706 | 97 嗯，明了，多谢！
【在 l**b 的大作中提到】
: 可以吧，后面半段保证必须是power of 2. 111显然不是。
: 你那个的话，10101就通过了吧？
|
c********t
发帖数: 5706 | 98 多谢！被你的第四轮震惊了。
【在 w****a 的大作中提到】
: 给parent指针了。
|
b***k
发帖数: 77 | 99 Buffer overflow attack:
http://en.wikipedia.org/wiki/Buffer_overflow
【在 c********t 的大作中提到】
: 多谢！被你的第四轮震惊了。
|
w****a
发帖数: 710 | 100 好文章！
【在 b***k 的大作中提到】
: Buffer overflow attack:
: http://en.wikipedia.org/wiki/Buffer_overflow
|
|
|
h****n
发帖数: 1093 | 101 bless 感觉很扣细节啊，拿到offer发包子吧
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
l********5
发帖数: 230 | |
j********o
发帖数: 8 | 103 好多语言底层的问题，lz有这方面的背景么？bless |
p*****2
发帖数: 21240 | 104
貌似我就第四轮懂
【在 c********t 的大作中提到】
: 多谢！被你的第四轮震惊了。
|
p*****2
发帖数: 21240 | |
w****a
发帖数: 710 | 106 我在爱尔兰，就在本地面的。offer真不知道有没有。玄之又玄。
多谢二爷高看！
【在 p*****2 的大作中提到】
: LZ是在英国吗？估计offer跑不掉了
|
l*********8
发帖数: 4642 | 107 面得不错，bless!
【在 w****a 的大作中提到】
: 我在爱尔兰，就在本地面的。offer真不知道有没有。玄之又玄。
: 多谢二爷高看！
|
g****g
发帖数: 221 | |
f*******w
发帖数: 1243 | |
w****a
发帖数: 710 | 110 阴柔一笑快弄死我了。。
【在 f*******w 的大作中提到】
: 牛，bless
: 赞阴柔一笑
|
|
|
s****r
发帖数: 125 | 111 最后c++的那个叫 Koenig's name lookup, http://en.wikipedia.org/wiki/Argument-dependent_name_lookup.
Stephan T. Lavavej 的core c++的讲座里有讲到。
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
m*****k
发帖数: 731 | 112 findNext() is 'same' as inorder, parent pointer is not needed.
【在 l*********8 的大作中提到】
: "要求包含查找最小的节点的方法。并利用这个函数实现findNext()"
: 不是太明白， 怎么用findMin()来实现findNext()?
|
w****a
发帖数: 710 | 113 yep, 用stack也行。但是题目给了parent,不用白不用啦。
【在 m*****k 的大作中提到】
: findNext() is 'same' as inorder, parent pointer is not needed.
|
Z**********4
发帖数: 528 | |
j********x
发帖数: 2330 | |
j********x
发帖数: 2330 | |
M****6
发帖数: 36 | |
c***f
发帖数: 40 | 118
请教下关于楼主的面试内容：
楼主会不会感觉 google onsite 问的某些问题会跟你的简历背景有比较大的关系呢？
比如说，楼主的遇到第四面问题的原因，是不是因为楼主在简历上有过关于security
的project等经历呢
或者是其他一些事算法问题，会不会或多或少的跟楼主在简历上的某些project/背景有
些关系呢
【在 w****a 的大作中提到】
: 背景：新鲜小硕，申的是2013北美new grads，SDE
: 地点：都柏林office
: 没签nda，直接放送了。坐等拒信，明年再来。
: 第一轮：
: 写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
: 最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
: 需要描述详细时空复杂度，最好情况最坏情况和平均情况。
: 第二轮：
: 第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
: 的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
|
c***f
发帖数: 40 | 119 不好意思，忘了表示谢谢了！！
祝福楼主在今后面试一切顺利! |
