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