|
|
此文章由 jacey 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 jacey 所有！转贴必须注明作者、出处和本声明，并保持内容完整
klux 发表于 2014-3-26 23:30 
哪方面的算法？
Amazon面经
Amazon interview questions
some amazon interview algorithm questions
[电话面试] Amazon First Round
同主题阅读：Amazon 电面面经
Phone interview with Amazon. The interviewer said this was just an initial screening and there was lots more to go, if I clear this one. The questions he asked made it seem like he just wanted to know whether I had an idea about these topics rather than interviewing me. The first few questions below are Generic Resume questions. Others relates to my research area which is Distributed Computing.
1. Explain me your failure detector and membership management algorithm that you have implemented and tested on a 960-processor distributed system? (He dint wait for me to expalin the full algorithm, and started asking questions about it in betwwe. Actually it helped)
2. Did you use a Pull based or Push based algorithm?
3. How does each processor send the notification that it is alive?
4. So the main failure detector is centralized?
5. So How did you avoid centralization?
Actually there were quite a lot of questions that followed. Most of them dealt with avoiding centralization and scaling?? He said that the problems I was attacking are quite similar to what they face in Amazon and that he liked my ideas and work and is pretty impressed with it.(This is my third interview, I guess the earlier two had also told me the same thing but about my work, but, they both rejected me after the respective on-site interviews...so i consider all this as Blah Blah)
7. Tell me how a TCP conection is set up?
Explained him the three-way handshake. Forgot what the
6. Given a topological graph ( you know that famous undergraduate courses graph with course prerequisites), how will u tell a student what prerequisites he has to take before taking an advanced course.
I answered using DFS. I remember learning somewhere in school that this can be solved using DFS. But he dint agree. I couldnt think of anything else. Then he answered saying you follow each leaf of the graph thill you reach the course. I was confused, anyways he said forget it.
7. How much time does it take to sort n numbers. Me: Depends on the algorithm you use.
8. whcih algorithm will you use in a general case. Quicksort
7. What is a median. (I was still thinking bout the previous question and answered this one wrong too. He corrected me)
8. How will you calculate median of n numbers: me: sort and the number at the center...will take nlog n time.
9. Can u tell me a O(n) method: me: I cant think of any right now, but i guess you can use quicksort and choosing the right pivot.
10. STL - Heaps, Linked Lists.
11. Virtual Functions: Tell me all you know.
12. What are exceptions..state with an example.
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[电话面试] Amazon First Round
☆─────────────────────────────────────☆
linulysses (夜鱼) 于 �(h 提到:
刚刚放下电话，很新鲜的面经~
一印度同学面的，之前一直在担心印度口音，没想到这位同学英语很好，几乎没有什么
口音，听起来很舒服。整个过程才35分钟，基本上很smooth，除了开始时他把我的名字
念得不像样以至于我以为是wrong number之外。还有一个奇怪的事，他最后没让我问问
题，就说 thanks for your time. 88~ 不知道这是不是不吉之兆。。。大伙有没有碰
到这种情况的？
1. talk about his team and amazon
2. introduce yourself
3. talk about my research
4. what's linked list? how to insert a node into middle?
ans: a data structure only sequential access to its elements allowed. for
each node, it has data field and next pointer field. in general, the
application holds the head pointer of the linked list which allows it to
visit the whole linked list. to insert target node into middle, first, we
find the right position, then, set the target's next as its previous one's
next pointer, then let the previous one's next points to target.
5. how to reverse word in a string?
ans: use a stack. once a word boundary is recognized, put that word into
stack. finally, compose a new string with words by the order of popping.
6. more efficient way?
ans: reverse the string. then, reverse each word in the reversed string.
7. some principles of object-oriented application?
ans: encapsulation, re-usability, and so on. I don't think I answer this
question well><
8. difference between binary search tree and hash table?
ans: search time: BST - average O(log n), worst O(n); hash - Average O(1)
, worst O(n); space usage: BST - more compact, hash - may waste some unused
space, depending on implementation; special issue: hash table has to deal
with collision.
9. some things challenging you previously and what you learned?
ans: talk about some challenges and what I learned from two previous
projects.
10.Why amazon?
感觉是个非典型 amazon 面试：一，没有让code，更不用念code了。我之前还专门练习
过怎么读code；二、印度同学没有口音。之前我还专门练习听印度口音；三、没有问
design 的问题。我还专门把能见到的 design问题如 game card, parking pool,
elevator... 仔细想过；四、时间短。才35分钟，刨掉开头，也就30分钟。不过，经典
的 why amazon还是出现了。。。
最后的时候，他好像说会 get back 啥的，我没听清楚，因为当他说我们今天就面到这
里时，我就在想我该问问题了，结果一走神，就没听清楚他说了啥，但肯定不是让我问
问题，因为，他接着就是 thanks for your time. 88....囧啊
☆─────────────────────────────────────☆
jntl (jntl) 于 (Fri Jun 11 18:12:22 2010, 美东) 提到:
BST还有有序这个优点吧，Hash表没有
☆─────────────────────────────────────☆
freemail165 (BornOn911) 于 (Fri Jun 11 18:21:46 2010, 美东) 提到:
he asked BST or BT?
【 在 linulysses (夜鱼) 的大作中提到: 】
: 刚刚放下电话，很新鲜的面经~
: 一印度同学面的，之前一直在担心印度口音，没想到这位同学英语很好，几乎没有什么
: 口音，听起来很舒服。整个过程才35分钟，基本上很smooth，除了开始时他把我的名字
: 念得不像样以至于我以为是wrong number之外。还有一个奇怪的事，他最后没让我问问
: 题，就说 thanks for your time. 88~ 不知道这是不是不吉之兆。。。大伙有没有碰
: 到这种情况的？
: 1. talk about his team and amazon
: 2. introduce yourself
: 3. talk about my research
: 4. what's linked list? how to insert a node into middle?
: ...................
☆─────────────────────────────────────☆
linulysses (夜鱼) 于 (Fri Jun 11 18:24:39 2010, 美东) 提到:
啊，是的，我当时没想起来。。。这面试官在我答完问题后，一般只吱了一声，就转到
下一题了。。。感觉不是什么好事情。。。
【 在 jntl (jntl) 的大作中提到: 】
: BST还有有序这个优点吧，Hash表没有
☆─────────────────────────────────────☆
linulysses (夜鱼) 于 (Fri Jun 11 18:32:36 2010, 美东) 提到:
sorry for that. he asked binary search tree. I updated my post.
【 在 freemail165 (BornOn911) 的大作中提到: 】
: he asked BST or BT?
☆─────────────────────────────────────☆
freemail165 (BornOn911) 于 (Fri Jun 11 18:38:41 2010, 美东) 提到:
did u say the basic definition of those two DS at first?
【 在 linulysses (夜鱼) 的大作中提到: 】
: sorry for that. he asked binary search tree. I updated my post.
☆─────────────────────────────────────☆
artwork (嘿嘿) 于 (Fri Jun 11 18:39:15 2010, 美东) 提到:
reverse words回答不太好
【 在 linulysses (夜鱼) 的大作中提到: 】
: 刚刚放下电话，很新鲜的面经~
: 一印度同学面的，之前一直在担心印度口音，没想到这位同学英语很好，几乎没有什么
: 口音，听起来很舒服。整个过程才35分钟，基本上很smooth，除了开始时他把我的名字
: 念得不像样以至于我以为是wrong number之外。还有一个奇怪的事，他最后没让我问问
: 题，就说 thanks for your time. 88~ 不知道这是不是不吉之兆。。。大伙有没有碰
: 到这种情况的？
: 1. talk about his team and amazon
: 2. introduce yourself
: 3. talk about my research
: 4. what's linked list? how to insert a node into middle?
: ...................
☆─────────────────────────────────────☆
hunter33 (多年前的梦想) 于 (Sat Jun 12 01:24:06 2010, 美东) 提到:
Bless.
念Code要把每个括符都念出来来么?
你怎么熟悉印度口音啊?找个印度同学狂砍么?
☆─────────────────────────────────────☆
linulysses (夜鱼) 于 (Sun Jun 13 19:36:50 2010, 美东) 提到:
唉。。。没有。。。答题的技巧不足啊，面壁ing...
【 在 freemail165 (BornOn911) 的大作中提到: 】
: did u say the basic definition of those two DS at first?
☆─────────────────────────────────────☆
linulysses (夜鱼) 于 (Sun Jun 13 19:37:58 2010, 美东) 提到:
我以前也念过code，也想听听大家的意见呢~
在网上找些 indian 的视频狂听。。。
【 在 hunter33 (多年前的梦想) 的大作中提到: 】
: Bless.
: 念Code要把每个括符都念出来来么?
: 你怎么熟悉印度口音啊?找个印度同学狂砍么?
☆─────────────────────────────────────☆
aumydear (orange) 于 (Mon Jun 14 16:31:10 2010, 美东) 提到:
Cong first!
I was phone interviewed with Google last week and they didn't let me ask
questions at the second part...
I do not think that was a bad sign, since I think I did not so bad.
Keep being positive thinking all the time while prepare for the next round!
This is the best we can do!
☆─────────────────────────────────────☆
novastar (星云) 于 (Mon Jun 14 16:42:48 2010, 美东) 提到:
没让问问题很正常，问了你这么多问题，没时间了，是好事
big bless！
【 在 linulysses (夜鱼) 的大作中提到: 】
: 刚刚放下电话，很新鲜的面经~
: 一印度同学面的，之前一直在担心印度口音，没想到这位同学英语很好，几乎没有什么
: 口音，听起来很舒服。整个过程才35分钟，基本上很smooth，除了开始时他把我的名字
: 念得不像样以至于我以为是wrong number之外。还有一个奇怪的事，他最后没让我问问
: 题，就说 thanks for your time. 88~ 不知道这是不是不吉之兆。。。大伙有没有碰
: 到这种情况的？
: 1. talk about his team and amazon
: 2. introduce yourself
: 3. talk about my research
: 4. what's linked list? how to insert a node into middle?
: ...................
☆─────────────────────────────────────☆
KingMing (洱东金茗) 于 (Tue Jun 15 12:35:40 2010, 美东) 提到:
请问是不是Amazon的面试都不需要在editor里coding啊？
【 在 linulysses (夜鱼) 的大作中提到: 】
: 刚刚放下电话，很新鲜的面经~
: 一印度同学面的，之前一直在担心印度口音，没想到这位同学英语很好，几乎没有什么
: 口音，听起来很舒服。整个过程才35分钟，基本上很smooth，除了开始时他把我的名字
: 念得不像样以至于我以为是wrong number之外。还有一个奇怪的事，他最后没让我问问
: 题，就说 thanks for your time. 88~ 不知道这是不是不吉之兆。。。大伙有没有碰
: 到这种情况的？
: 1. talk about his team and amazon
: 2. introduce yourself
: 3. talk about my research
: 4. what's linked list? how to insert a node into middle?
: ...................
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
同主题阅读：Amazon 电面面经
[版面:待字闺中][首篇作者：Snowy101] , 2012年11月04日20:16:09
[分页:1 ]
Snowy101
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]
发信人: Snowy101 (Snowy), 信区: JobHunting
标 题: Amazon 电面面经
发信站: BBS 未名空间站 (Sun Nov 4 20:16:09 2012, 美东)
前两天电面amazon，说来丢人，一面就挂了。去年还onsite过，可能真的和amazon没有
缘分吧。
题目都是本版的基础题，常见的口水题，自己也练过很多遍。题目都能打出来，但是有
bug。面试之前Collabedit上面练过，但是发现面试时候我编辑哪行哪行重影，模糊，
完全看不清我在写什么，鼠标的位置也是错乱的。只能凭着感觉写，切换到下一行后在
回头看上一行写的是什么。
面试官女烙印，没怎么刁难我，但是我听不懂她她听不懂我。面试时候和她说了我看不
清我写的什么，面完后还截屏让她看到我这里到底是什么情况，希望她能take into
consideration。因为紧张和软件的问题，题目出了bug，HashSet写成Hashset,一个特
殊情况的处理没有把结果加到return set里面。结果一面就挂了， 可能烙印还是在背
后没说什么好话吧。。。
题目：
1. 工作中遇到过最难得问题。
2. 给一个文件，里面有name，address, zip code,每行一个数据。格式什么的没问题
，都是comma separted， 问怎么列出来所有的zip code，结果不能有重复。 我说用
regular expression， 然后pipe到uniq命令里面。她让我写，我说我unix用的不多，
要看regular expression 的reference。然后就用java写了一个。
3. 一个网站出了问题没响应，可能的问题。我就和她前端后端，小型大型，网络传输
数据库查询，分布式服务器负载什么的一大通和她扯了扯。她说不错。
4. Two sum。 她出题时候觉得她对duplicate的定义错了，但是没敢和她讲。就按照排
序然后前后指针做了。处理duplicate的时候就是因为看不到写的什么心理面焦急出了
bug。写完了觉得挺傻逼的说我给你写一个用HashTable的吧，她说时间到了算了。。。
。。
结果就是悲催的一轮游。本来觉得去年能到onsite今年电面不是问题的。
总结：大家还是要认真，多和面试官交流，觉得他出错时候也不要不敢说。我感觉那人
就随便找道题自己也没想过duplicate的问题。我写完了她问我那段特殊代码是干啥的
，我说处理duplicated。。。她这才明白。也可能我老实的告诉她去年我fail onsite
了，她就直接把我挂了。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1. Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can’t pass the value k to any function also.
2. What are the 4 basics of OOP?
3. Define Data Abstraction. What is its importance?
4. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
5. Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren’t present.
6. Given a string,find the first un-repeated character in it? Give some test cases
7. You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
8. Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
9. What is a C array and illustrate the how is it different from a list.
10. What is the time and space complexities of merge sort and when is it preferred over quick sort?
11. Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
12. Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
13. Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
14. Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
15. How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
16. Explain polymorphism. Provide an example.
17. Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
18. You are given some denominations of coins in an array (int denom)and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
19. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number. |
评分
-
查看全部评分
|
流光溢彩歌剧院，浓妆淡抹总相宜(升级版） (2009-6-9) 老song 
台湾的点点点滴滴滴 (2016-10-21) 蚝 
楼主:cppbug
发表于 2014-3-20 09:47
