查看: 9122| 回复: 18
跳转到指定楼层
上一主题 下一主题
收起左侧

Amazon SDE Interview Opportunity (Software Development Engineer)

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Q1:
Given two lists of integers, write a function that returns a list that contains only the intersection (elements that occur in both lists) of the two lists. The returned list should only contain unique integers, no duplicates.
For example, [4, 2, 73, 11, -5] and [-5, 73, -1, 9, 9, 4, 7] would return the list [-5, 4, 73] in no particular order.
•        You may use the JDK or the standard template library. The solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following:
1. Document your assumptions
2. Explain your approach and how you intend to solve the problem
3. Provide code comments where applicable
4. Explain the big-O run time complexity of your solution. Justify your answer.
5. Identify any additional data structures you used and justify why you used them.
6. Only provide your best answer to each part of the question.

Q2:
Given a binary tree, write a function that returns true if and only if it is a binary search tree.  Your solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices

Q3:
Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multiplication, and division).


以上是Amazon的几道算法题。给一个半小时的时间。要求用java或者是cpp.
希望有心的同学多多联系。
我就当攒rp了。

评分

参与人数 5大米 +235 萝卜 +2 收起 理由
mamengduo + 25 好资源,赞好人。
paradox + 100
zengxinzhy + 25 + 2 感谢分享!
woaibai + 60
Janet.Ding + 25 多谢分享

查看全部评分


上一篇:CareerCup 14.2
下一篇:CareerCup 14.3
🔗
woaibai 2012-9-10 12:48:26 | 只看该作者
全局:
多谢分享,这是onsite的题还是电话面试?

点评

应该是on-site。。  发表于 2012-9-10 13:28
回复

使用道具 举报

🔗
paradox 2012-9-10 13:28:38 | 只看该作者
全局:
本帖最后由 paradox 于 2012-9-10 13:34 编辑

亲,必须是java或者C++么?其他语言a家不收?昨天收到A家的onsite,所以有这个问题.
回复

使用道具 举报

🔗
 楼主| cynthiamo 2012-9-11 10:04:41 | 只看该作者
全局:
woaibai 发表于 2012-9-10 12:48
多谢分享,这是onsite的题还是电话面试?

不是on-site面试,也不是电话面试,就是投过简历之后给你发了邮件,有链接,让你直接去做题。应该算是第一轮吧。还有另一个连接,类似于头脑风暴神马的。问你大概是什么类型的人员,还问你工作中如果遇到这种情况应该怎么做。都是选择题。

点评

多谢!  发表于 2012-9-11 10:13
回复

使用道具 举报

🔗
 楼主| cynthiamo 2012-9-11 10:06:35 | 只看该作者
全局:
paradox 发表于 2012-9-10 13:28
亲,必须是java或者C++么?其他语言a家不收?昨天收到A家的onsite,所以有这个问题.

你再看看楼上我的回答。我这个就是直接在网上答题的那种。这个题只要求了java和Cpp。并且给了你开头框架。比如第一题要用list不用数组。我不大清楚onsite的时候会不会要求语言。这是我所能提供给你的信息。祝onsite好运。

点评

thanks!  发表于 2012-9-11 11:06
回复

使用道具 举报

🔗
孤笑客 2012-9-15 10:42:17 | 只看该作者
全局:
其实我好想知道Q3有什么比较好的解法…
回复

使用道具 举报

🔗
paradox 2012-9-15 11:09:09 | 只看该作者
全局:
孤笑客 发表于 2012-9-15 10:42
其实我好想知道Q3有什么比较好的解法…

其实就是要求你找最小 K个cells which sqr(abs(x)) + sqr(abs(y)), in the entire NxN matrix. You can certainly treat the matrix as long array(append each row). Then, do a comparetor interface where compares each cell by sqr(abs(x)) + sqr(abs(y)). So, you can sort this array, lets say you do qSort, which is takes nLog(n).And then takes the smallest first K cell, and return them. Complexity is about nlog(n), if use N the length as the base. the Complexity is N^2log(N^2).
回复

使用道具 举报

🔗
imwmwm 2012-9-24 12:33:15 | 只看该作者
全局:
paradox 发表于 2012-9-15 11:09
其实就是要求你找最小 K个cells which sqr(abs(x)) + sqr(abs(y)), in the entire NxN matrix. You can c ...

貌似amazon经典题了 建一个长度为K的最大堆 当插满了以后 只要值小于堆顶 则替换堆顶 然后执行shiftdown

复杂度为O(NlogK)
回复

使用道具 举报

🔗
offersathands 2012-9-25 12:08:15 | 只看该作者
全局:
楼主真好!收藏啦!
回复

使用道具 举报

🔗
xusi 2012-10-2 06:23:54 | 只看该作者
全局:
imwmwm 发表于 2012-9-23 20:33
貌似amazon经典题了 建一个长度为K的最大堆 当插满了以后 只要值小于堆顶 则替换堆顶 然后执行shiftdown
...

问一下,如果建一个长度N的priority queue,再extract-min K次的话,就是O(N)+O(KlgN),这个复杂度和你的O(NlogK)谁大?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表