share一下最近三个电话面试题Amazon, Groupon, Google

发信人: BigTailWolf2 (大尾巴狼), 信区: JobHunting
标  题: share一下最近三个电话面试题Amazon, Groupon, Google
发信站: BBS 未名空间站 (Wed Jan 28 21:33:33 2015, 美东)

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


求保佑
--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 69.]

http://www.mitbbs.com/article_t/JobHunting/32877471.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东极速达北京支持货到付款 ， 更多京东优惠券