Amazon SDE Interview Opportunity (Software Development Engineer)

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

多谢分享，这是onsite的题还是电话面试？

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

woaibai 发表于 2012-9-10 12:48
多谢分享，这是onsite的题还是电话面试？

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

paradox 发表于 2012-9-10 13:28
亲，必须是java或者C++么？其他语言a家不收？昨天收到A家的onsite,所以有这个问题.

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

其实我好想知道Q3有什么比较好的解法…

孤笑客 发表于 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).

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）

楼主真好！收藏啦！

imwmwm 发表于 2012-9-23 20:33
貌似amazon经典题了 建一个长度为K的最大堆 当插满了以后 只要值小于堆顶 则替换堆顶 然后执行shiftdown
...

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