share一下最近三个电话面试题Amazon, Groupon, Google - 未名空间MITBBS历史存档

share一下最近三个电话面试题Amazon, Groupon, Google# JobHunting - 待字闺中

B*22015-01-28 08:01

1 楼

Amazon
1.括号匹配
1.1 已知一个字符流，只有'('或者')'，检查是否是balance
解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
，直接就return false. 全扫完如果等于0就return true, 否则return false
1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
意右括号，直接return false。如果全扫完是空栈return true, 否则return false
2.Anagram
给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和
eat一定要挨着
解：同一anagram单词特点是把这个单词按字母排序之后，长得都一样。所以用一个字
典来维护anagram
同一单词排序后为key, 关于单词的list就是value。如果有这个key,就append到list里
，没有就另开一个。最后把这些anagram连起来输出
Groupon
零钱问题
1. 给一个整数值的金额(n cents)，返回最少总硬币数，用(quarter, dime, 5 cents,
penny)
解：直接用贪心策略。先算用多少quarter，再dime，再5 cents，再penny
2. 还是一个金额(n cents)，但是硬币用自己定义的额度，比如[10, 7, 1]
解：这个问题存在无解情况。比如给个额度3，但是硬币面值只有2的，这种情况fail，
返回-1
剩下的，用背包问题解。DP
Google
1. Reverse link list，递归和循环。并分析性能
解：太标准了，略
2. 3-sum question:
给N = 1,000,000个不相同的int整数以及一个int X. 如果 a + b + c <= X，(a < b <
c)则称有一个triplet, 求triplet count。
解：sort & scan. 先sort，O(N logN)时间
然后scan, i form 0 to N-3，j从i+1开始递增，k从N-1开始递减，优先动k,只要k < j
，则k递减，直到找到第一个 A[i] + A[j] + A[k] <= X. 则 count += (k - j)，然后
j加一个
对于每个i, 找一轮时间O(N) （j, k 相遇，不会超过N步）
总体时间复杂度 O(N^2)
目前三家的结果
Amazon 本周五onsite
Google 下周一电话第二轮
Groupon 下周五onsite
求保佑

M*72015-01-28 08:01

2 楼

多谢分享！
Bless!!

e*d2015-01-28 08:01

3 楼

答的很好啊，有啥可担心的。

0

【在 B**********2 的大作中提到】

: Amazon
: 1.括号匹配
: 1.1 已知一个字符流，只有'('或者')'，检查是否是balance
: 解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
: ，直接就return false. 全扫完如果等于0就return true, 否则return false
: 1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
: 解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
: 意右括号，直接return false。如果全扫完是空栈return true, 否则return false
: 2.Anagram
: 给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和

m*92015-01-28 08:01

4 楼

请问LZ google是多长时间回复的？

c*t2015-01-28 08:01

5 楼

anagram排序的话，能直接用Arrays.sort()么，还是需要自己写comparator啥的？

g*42015-01-28 08:01

6 楼

多谢LZ分享！
google第2题，当找到第一个triplet后，k也应该返回末尾，j加1，重新开始吧。这样
应该是O(n^3).应该可以用二分降到O(N^2 * lgN)
但是既然面试官给了个总数量大于1m的数组，是否是要求有别的解法？还得等高手来回
答。
另外请问下LZ，google第2题要求把完整代码写出来，bug free吗？

0

【在 B**********2 的大作中提到】

: Amazon
: 1.括号匹配
: 1.1 已知一个字符流，只有'('或者')'，检查是否是balance
: 解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
: ，直接就return false. 全扫完如果等于0就return true, 否则return false
: 1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
: 解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
: 意右括号，直接return false。如果全扫完是空栈return true, 否则return false
: 2.Anagram
: 给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和

n*n2015-01-28 08:01

7 楼

Groupon 1, 如何证明贪心法可以最优？

0

【在 B**********2 的大作中提到】

: Amazon
: 1.括号匹配
: 1.1 已知一个字符流，只有'('或者')'，检查是否是balance
: 解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
: ，直接就return false. 全扫完如果等于0就return true, 否则return false
: 1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
: 解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
: 意右括号，直接return false。如果全扫完是空栈return true, 否则return false
: 2.Anagram
: 给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和

n*n2015-01-28 08:01

8 楼

G答的好就不会有第二次电面。

【在 e********d 的大作中提到】

: 答的很好啊，有啥可担心的。
:
: 0

i*e2015-01-28 08:01

9 楼

no need to move k to the end..OP is correct.

【在 g**4 的大作中提到】

: 多谢LZ分享！
: google第2题，当找到第一个triplet后，k也应该返回末尾，j加1，重新开始吧。这样
: 应该是O(n^3).应该可以用二分降到O(N^2 * lgN)
: 但是既然面试官给了个总数量大于1m的数组，是否是要求有别的解法？还得等高手来回
: 答。
: 另外请问下LZ，google第2题要求把完整代码写出来，bug free吗？
:
: 0

J*n2015-01-28 08:01

10 楼

楼主给的答案明显O(n^2)啊。

【在 g**4 的大作中提到】

: 多谢LZ分享！
: google第2题，当找到第一个triplet后，k也应该返回末尾，j加1，重新开始吧。这样
: 应该是O(n^3).应该可以用二分降到O(N^2 * lgN)
: 但是既然面试官给了个总数量大于1m的数组，是否是要求有别的解法？还得等高手来回
: 答。
: 另外请问下LZ，google第2题要求把完整代码写出来，bug free吗？
:
: 0

S*w2015-01-28 08:01

11 楼

你这算法好像不对
为啥k-j 在google题上？

0

【在 B**********2 的大作中提到】

: Amazon
: 1.括号匹配
: 1.1 已知一个字符流，只有'('或者')'，检查是否是balance
: 解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
: ，直接就return false. 全扫完如果等于0就return true, 否则return false
: 1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
: 解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
: 意右括号，直接return false。如果全扫完是空栈return true, 否则return false
: 2.Anagram
: 给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和

f*l2015-01-28 08:01

12 楼

mark学习一下。

r*t2015-01-28 08:01

13 楼

How long did it take to get the result of phone interview?

0

【在 B**********2 的大作中提到】

: Amazon
: 1.括号匹配
: 1.1 已知一个字符流，只有'('或者')'，检查是否是balance
: 解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
: ，直接就return false. 全扫完如果等于0就return true, 否则return false
: 1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
: 解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
: 意右括号，直接return false。如果全扫完是空栈return true, 否则return false
: 2.Anagram
: 给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和

B*22015-01-28 08:01

14 楼

The 2nd day after phone interview

【在 m****9 的大作中提到】

: 请问LZ google是多长时间回复的？

B*22015-01-28 08:01

15 楼

No, not work like that.
If you have a A[i] + A[j] + A[k] <= X, the next should move j, while j
increasing in the sorted array A, k must be less than current k.
Sorry for no Chinese input in hotel

【在 g**4 的大作中提到】

: 多谢LZ分享！
: google第2题，当找到第一个triplet后，k也应该返回末尾，j加1，重新开始吧。这样
: 应该是O(n^3).应该可以用二分降到O(N^2 * lgN)
: 但是既然面试官给了个总数量大于1m的数组，是否是要求有别的解法？还得等高手来回
: 答。
: 另外请问下LZ，google第2题要求把完整代码写出来，bug free吗？
:
: 0

B*22015-01-28 08:01

16 楼

All the 2nd day they tell me
Google and Amazon are the recruiter asked me via LinkedIn, then I called
them.
Groupon is referred from friend.

【在 r*****t 的大作中提到】

: How long did it take to get the result of phone interview?
:
: 0

B*22015-01-28 08:01

17 楼

Would you please offer more detail?
I think those are very basic questions. Much easier than ACM

【在 S***w 的大作中提到】

: 你这算法好像不对
: 为啥k-j 在google题上？
:
: 0

B*22015-01-28 08:01

18 楼

Don't have to sort the array. Just take every word make a copy and then sort
the word as a key.
now you have both key and value

【在 c******t 的大作中提到】

: anagram排序的话，能直接用Arrays.sort()么，还是需要自己写comparator啥的？