Amazon 2.8 9AM 面经

cynthiazhxu

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

x

2月98号大年初一早上9点的面经，烙印面的（有一个人shadow），没有问到OOD和任何data structure,上来直接让自我介绍，说project,说challenge。两道coding题目：
1.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

strong>补充内容 (2016-2-27 09:07):
2.26拿到offer。大家加油^_^

猪小乐

autumnhu 发表于 2016-2-10 13:52
我想讨论一下时间复杂度。我觉得找出相同的sum的组合之后要两两匹配，所以是O(n^3)。数组没有重复元素。

我也觉得是n^3，输出的复杂度就是立方级的，时间复杂度不可能比输出复杂度小。

猪小乐

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

aangel

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

aangel

第一题用HashMap来hash sum吧，两个for loop, 时间复杂度O(N^2),空间复杂度O(N^2)
数组里有重复元素吗，有重复的元素的先排序吧

cynthiazhxu

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yrfzh

第一题是4sum嘛。。。。感觉好难啊。。。。lz是怎么做的？？？

yrfzh

aangel 发表于 2016-2-11 10:20
建造一个HashMap
Integer存两个每两个元素的sum, List存满足这个sum的所有pair
class pair {

诺！！！明白了！！！这个方法应该是O(n^2)的！！！

pepero

如果用hash，光输出就是立方级的，怎么是n^2

处川

yrfzh 发表于 2016-2-11 11:24
诺！！！明白了！！！这个方法应该是O(n^2)的！！！

这样还需要override equals()这个函数，不然会分别不出