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...