Amazon on site面试， 攒RP, 求祝福# JobHunting - 待字闺中
g*u
1 楼
今天刚面的Amazon，求祝福
面的题目如下：面的是5个人，第一个是HR， 就聊了些大概的问题，关于Amazon,有关
面试安排， 面试的语言和他们的工作流程之类，略无不表。后面面了4个engineer，把
记住的题目说一下。
每轮面试45 minutes， Interviewer will come to the office.
有个的题目是：如何找到bst中第二大的数；可以用in order visit,然后返回倒数第二
个，但是时间和空间都是O(n)；要求improve，一个方案是寻找最大值（right most
nodes),然后寻找bst中最后一个小于该node的节点（log n)，要求code实现第二个方法
；然后是要在hash table中实现一个function可以按照插入的顺序打印出来；接着是实
现linux下面的count words，用了2个whileloop分别处理当前指针在word中和word间的
空格，要求2种情况一起处理，写了一半没写完（缺少练习啊）
有一个题目是关于C++和Java中的内存分配的；然后问了关于3-tier(UI, middle-tier
manager， back-end db)中，如果现在出现request反应时间很长，问可能的问题；提
供解决方案，讨论可能的软件瓶颈，硬件或者网络的问题；数据库的问题，提供cache
的解决方案，你知道industry用到的cache的tools（memecad?)；然后要求code一个
binary tree的mirror实现，因为习惯了修改指针用node*&, 直接写了个void mirror(
node *&root),interviewer对reference不是很肯定，和面试官员讨论半天到底是*& 还
是*，写了recursive的实现，但是在修改指针的时候，出现一个bug（自乱阵脚了）。
。。
有一个是关于一个环状的网，现在有n个independent nodes在网中，要求从中选出一个
leader。node只有recv（msg）， send(msg)， id()的接口。 所有的node都是独立的
接受和发送msg，而且只能发给它的下一个node，不能群发msg，msg的内容自定，分析
复杂度；然后一个问题是设计restaurant的db schema的设计，设计table来满足特定的query，比如说可否
在某个时间段reserve table，可否提供walk-in service
有一个是实现如下功能
3- foo*bar;
要求实现的函数是：
? parser(list expression)
{
}
double eval(?, mapst)
{
}
其中的？表示你需要设计返回的数据结构
//现在看来，其实就是实现输入一个expression，然后evaluate。
如果有人熟悉的话，其实这是一个infix的expression的问题， 可惜等自己反应过来的
时候， 时间浪费了大半。现在看来需要做的是从infix来建立binary tree，然后再进
行post visit就可以得到post fix expression，然后在eval里面evaluate这个post order的sequence就可以了，注意需要用extra的buffer来暂存结果，还得注意可能有非法输入（2 3）,自己只code完了第2个function，而且还有corner case没处理完，但是第一个分析道一半，汗。。。
面的很玄
求祝福
面的题目如下：面的是5个人，第一个是HR， 就聊了些大概的问题，关于Amazon,有关
面试安排， 面试的语言和他们的工作流程之类，略无不表。后面面了4个engineer，把
记住的题目说一下。
每轮面试45 minutes， Interviewer will come to the office.
有个的题目是：如何找到bst中第二大的数；可以用in order visit,然后返回倒数第二
个，但是时间和空间都是O(n)；要求improve，一个方案是寻找最大值（right most
nodes),然后寻找bst中最后一个小于该node的节点（log n)，要求code实现第二个方法
；然后是要在hash table中实现一个function可以按照插入的顺序打印出来；接着是实
现linux下面的count words，用了2个whileloop分别处理当前指针在word中和word间的
空格，要求2种情况一起处理，写了一半没写完（缺少练习啊）
有一个题目是关于C++和Java中的内存分配的；然后问了关于3-tier(UI, middle-tier
manager， back-end db)中，如果现在出现request反应时间很长，问可能的问题；提
供解决方案，讨论可能的软件瓶颈，硬件或者网络的问题；数据库的问题，提供cache
的解决方案，你知道industry用到的cache的tools（memecad?)；然后要求code一个
binary tree的mirror实现，因为习惯了修改指针用node*&, 直接写了个void mirror(
node *&root),interviewer对reference不是很肯定，和面试官员讨论半天到底是*& 还
是*，写了recursive的实现，但是在修改指针的时候，出现一个bug（自乱阵脚了）。
。。
有一个是关于一个环状的网，现在有n个independent nodes在网中，要求从中选出一个
leader。node只有recv（msg）， send(msg)， id()的接口。 所有的node都是独立的
接受和发送msg，而且只能发给它的下一个node，不能群发msg，msg的内容自定，分析
复杂度；然后一个问题是设计restaurant的db schema的设计，设计table来满足特定的query，比如说可否
在某个时间段reserve table，可否提供walk-in service
有一个是实现如下功能
3- foo*bar;
要求实现的函数是：
? parser(list
{
}
double eval(?, map
{
}
其中的？表示你需要设计返回的数据结构
//现在看来，其实就是实现输入一个expression，然后evaluate。
如果有人熟悉的话，其实这是一个infix的expression的问题， 可惜等自己反应过来的
时候， 时间浪费了大半。现在看来需要做的是从infix来建立binary tree，然后再进
行post visit就可以得到post fix expression，然后在eval里面evaluate这个post order的sequence就可以了，注意需要用extra的buffer来暂存结果，还得注意可能有非法输入（2 3）,自己只code完了第2个function，而且还有corner case没处理完，但是第一个分析道一半，汗。。。
面的很玄
求祝福
