g**u
发帖数: 583 | 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没处理完，但是第一个分析道一半，汗。。。
面的很玄
求祝福 |
g**e
发帖数: 6127 | 2 环状网哪题没看懂，是要求啥？
最后一题也没看懂……
bless
tier
cache
的query，比如说可否
order的sequence就可以了，注意需要用extra的buffer来暂存结果，还得注意可能有非
法输入（2 3）,自己只code完了第2个function，而且还有corner case没处理完，但是
第一个分析道一半，汗。。。
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
d***e
发帖数: 4864 | |
H**d
发帖数: 152 | |
g*******g
发帖数: 1416 | |
c*****l
发帖数: 879 | |
R********s
发帖数: 3420 | 7 bless ...
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
w**********u
发帖数: 172 | |
B****o
发帖数: 8307 | 9 Bless
★ Sent from iPhone App: iReader Mitbbs 6.88 - iPhone Lite |
s******s
发帖数: 3694 | 10 C 的话， function params, reference 很少用或者基本不用。 有些编译器支持， 有些不支持， 你这个问题应该是失分比较多。 C++ 的话， 就随便搞了。
bst 这个指明需要找到数第二个而不是 kth， 用两个临时指针交换就可以了， 这个基本没有得分， 应该
cache 的这实际应用可能比较多一些， 客户端的 cache 应该也是很重要一部分， I/O 和 serialization 应该对性能会有帮助 , 服务器端的话， 就需要经验了， 可能需要内存，文件映射或者数据库的高手回答了
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
|
|
b******n
发帖数: 4509 | 11
这个题可以 find_max, remove_max, find_max (the result), insert_max
O(logn)...
add a linked list, and each hast table entry has a pointer to the node of
corresponding node)
only one loop is enough, just use a marker
tier
cache
node* is enough, no reference needed
的query，比如说可否
不需要建立 binary tree, use two stack to get the post fix expression
order的sequence就可以了，注意需要用extra的buffer来暂存结果，还得注意可能有非
法输入（2 3）,自己只code完了第2个function，而且还有corner case没处理完，但是
第一个分析道一半，汗。。。
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
s*i
发帖数: 388 | |
s*i
发帖数: 388 | |
l****6
发帖数: 1180 | |
f*****w
发帖数: 2602 | 15 环状那个没很明白要干嘛
bless
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
f*****w
发帖数: 2602 | 16 最后一个表达式如果没有特别准备的话 还是很难写对的 pat |
r******r
发帖数: 700 | 17 "然后是要在hash table中实现一个function可以按照插入的顺序打印出来；"
这个是用 queue 保存按顺序插入的 key 吗？ key 还不行，应该是 key 的 hashcode?
但是如果有 collosion, 一个 hashcode 对应多个 key, 咋办呢
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
R*******d
发帖数: 13640 | |
h*******8
发帖数: 1280 | |
l****a
发帖数: 2361 | 20
bless
【在 g**u 的大作中提到】
: 今天刚面的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间的
|
|
|
a***y
发帖数: 117 | |
g**u
发帖数: 583 | 22
可以想象现在有一个 circular array， 里面的每个cell都有唯一的id，但是现在每个
cell只能向下一个cell发消息，只能从上一个cell接收消息，然后tail的下一个是开头
（成为一个环）。 现在是所有的cell可以类比为网络中的host，利用提供的api选出
leader，分析算法的复杂度（需要send多少message）。
最后一题是如何 evaluate如下的表达式：
3 - foo* bar/5+4
其中假设我们有时symbal table查询foo和bar的值。
表达式已经tokenlize了， listexpression，上面的例子里面就有7个string
， 分别是 “3”，“-”，“foo”,“*”, "bar","/", "5"
【在 g**e 的大作中提到】
: 环状网哪题没看懂，是要求啥？
: 最后一题也没看懂……
: bless
:
: tier
: cache
: 的query，比如说可否
: order的sequence就可以了，注意需要用extra的buffer来暂存结果，还得注意可能有非
: 法输入（2 3）,自己只code完了第2个function，而且还有corner case没处理完，但是
: 第一个分析道一半，汗。。。
|
g**u
发帖数: 583 | 23
有些不支持， 你这个问题应该是失分比较多。 C++ 的话， 就随便搞了。
基本没有得分， 应该
/O 和 serialization 应该对性能会有帮助 , 服务器端的话， 就需要经验了， 可能
需要内存，文件映射或者数据库的高手回答了
这个肯定是C++，C里面没有refference支持的。
至于找第二大的节点， 可否提供sample code。 比如说下面这个情况：
5
\
16
/
13
\14
怎么找到14呢？
【在 s******s 的大作中提到】
: C 的话， function params, reference 很少用或者基本不用。 有些编译器支持， 有些不支持， 你这个问题应该是失分比较多。 C++ 的话， 就随便搞了。
: bst 这个指明需要找到数第二个而不是 kth， 用两个临时指针交换就可以了， 这个基本没有得分， 应该
: cache 的这实际应用可能比较多一些， 客户端的 cache 应该也是很重要一部分， I/O 和 serialization 应该对性能会有帮助 , 服务器端的话， 就需要经验了， 可能需要内存，文件映射或者数据库的高手回答了
|
g**u
发帖数: 583 | 24
见上的解释
【在 f*****w 的大作中提到】
: 环状那个没很明白要干嘛
: bless
|
g**u
发帖数: 583 | 25
面试完了就想到其实我们需要的是一个从 infix expression-->postfix expression的
预处理，但是等到自己想到这一步的时候，这个时候就需要合适的数据结构来实现这种
转变，binary tree就可以了，但是那时候时间快没了...
【在 f*****w 的大作中提到】
: 最后一个表达式如果没有特别准备的话 还是很难写对的 pat
|
g**u
发帖数: 583 | 26
hashcode?
不用在用额外的存储空间。提示一下，你的每个key里面可以不仅仅村里想要的value，
还可以存其他的信息的。。。
【在 r******r 的大作中提到】
: "然后是要在hash table中实现一个function可以按照插入的顺序打印出来；"
: 这个是用 queue 保存按顺序插入的 key 吗？ key 还不行，应该是 key 的 hashcode?
: 但是如果有 collosion, 一个 hashcode 对应多个 key, 咋办呢
|
R***i
发帖数: 78 | 27 bless!
我最近也拿到A家offer,要是过了联系我 |
g**e
发帖数: 6127 | 28 find the max node, then find its immediate in-order precessor, which is a
classic problem.
if it has left node, then find the right most node in its left sub tree;
otherwise, find the first parent node that is smaller than the max node.
，
I
【在 g**u 的大作中提到】
:
: hashcode?
: 不用在用额外的存储空间。提示一下，你的每个key里面可以不仅仅村里想要的value，
: 还可以存其他的信息的。。。
|
L*******r
发帖数: 8961 | |
