5寸以下手机有什么推荐# PDA - 掌中宝
w*a
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...
地点：都柏林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...
