B**********2
发帖数: 923 | 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**********7
发帖数: 378 | | e********d
发帖数: 1202 | 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****9
发帖数: 492 | | c******t
发帖数: 391 | 5 anagram排序的话，能直接用Arrays.sort()么，还是需要自己写comparator啥的？ | g**4
发帖数: 863 | 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******n
发帖数: 12088 | 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******n
发帖数: 12088 | 8 G答的好就不会有第二次电面。
【在 e********d 的大作中提到】
: 答的很好啊，有啥可担心的。
:
: 0
| i*********e
发帖数: 21 | 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***n
发帖数: 21 | 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***w
发帖数: 1014 | 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****l
发帖数: 8042 | | r*****t
发帖数: 68 | 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**********2
发帖数: 923 | 14 The 2nd day after phone interview
【在 m****9 的大作中提到】
: 请问LZ google是多长时间回复的？
| B**********2
发帖数: 923 | 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**********2
发帖数: 923 | 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**********2
发帖数: 923 | 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**********2
发帖数: 923 | 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啥的？
|
|
