w******f
发帖数: 620 | 1 According to the latest data released by Synergy Research, Amazon (AMZN) has
clearly maintained its lead in the IaaS (infrastructure as a service)/PaaS
(platform as a service) market, which passed the $2.5 billion milestone
during the Q3 2013, up from $2.25 billion in Q2 2013. Amazon alone generated
15% more revenues than the nearest four competitors namely Microsoft (MSFT)
, IBM (IBM), Salesforce (CRM), and Google (GOOG) (see the chart below). |
|
|
n****a
发帖数: 5 | 3 今天上午刚做了Amazon发来的online assessment，还是在interview street上面做的
，题目没有变化，一道linkedlist cycle check，一道merge two sorted list，一道k
nearest nodes，面经之前地里的帖子都有。我有个问题是最后一道题做完了之后我还
在检查，没有点submit就到时间了，那我最后一道题的结果会自动submit吗？希望知道
情况的同学们帮忙解答下，谢谢！ |
|
i*****e
发帖数: 63 | 4 Find K closest points in N points on a 2D plane
可以试试 R-Tree的nearest neighbor search |
|
x********i
发帖数: 54 | 5 一个数据库中已经有N个数据点(Xi,Yi）。给定一个新的点（X,Y），如何快速从数据库
中找到距离最近的点？ |
|
|
r****s
发帖数: 1025 | 7 d=sqrt(x*2+y*2)
所有的点计算（Xi-x)**2+(Yi-y)**2,然后累计最小值。O(n)。 |
|
x********i
发帖数: 54 | 8 最显然的方法当然是O（N）。 楼上用kd tree怎么解呢，算法复杂度是多少？ |
|
|
|
|
|
|
|
t********e
发帖数: 344 | 15 什么意思？要求原来的点都sorted好才能二分吧？ |
|
c***0
发帖数: 449 | 16 是啊，题目说已经建立好了啊，如果你按照kd tree建立的话，查找的复杂度不是lgn吗
？建立的复杂度是排序 |
|
e******x
发帖数: 184 | 17 因为之前发过贴，背景就不赘述了，具体说说怎么准备还有面经吧。
骑驴找马，一月底开始刷leetcode，到三月中第一个面试，刷了一遍半吧，明显觉得写
第二遍的时候思路清晰多了，code也比第一遍的简洁。其他的就是每家面试前争对性的
看面经，能看多少是多少，四家只有L面经重复率很高，g家最不能预料题型。后面准备
design的时候都是乱看，一些fb tech talk的视频还有之前有人贴过的fb design的总
结，
但我基础不好，临时抱佛脚感觉也没什么用。面经我就只贴面完有及时记下来的，反正
也给过很多朋友了，就贴上来吧。
已经签了fb，准备八月初start，有同一期的pm我，哈。
脸书:
1. Print all paths of a binary tree
I gave a recursive solution.
Then he wanted to give an iterative way.
2a. Fibonacci (iterative)
2b. Buckets of anagrams
[“cart”,”tarc”, “cat”, “act”, “ract”] -> [[“... 阅读全帖 |
|
y***n
发帖数: 1594 | 18 K nearest points (solution see below) Time: O(nlgk),我没有看到solution，被
删掉了吗？ |
|
n********n
发帖数: 529 | 19 好象以前讨论过，记不清楚了。这题有比较好的解法吗？ |
|
|
|
|
|
Z**********4
发帖数: 528 | 24 输入是什么？是一个点和一个点集合嘛？ 我是assume你要找离这个点最近的k个点的。 |
|
|
|
|
w***g
发帖数: 5958 | 28 2维空间kd-tree足够好了。 高维空间的话用我写的kgraph。上面说的用heap在扫描的
时候维护top K列表实际上只有在K很大的时候才会起作用。K在几百以下的时候用heap
因为判断结构复杂导致cache和分支预测性能下降，反而不如直接插入快。 |
|
|
q****m
发帖数: 153 | 30 1 return n closest points on a plane
这个题目是什么意思？
同样类似的
Find the nearest K point given a set of N point.
2 find the largest subsequence given an array that yields the largest sum
Find maximum sum subset in an array with negative integers
这两题，一个是subsequence一个是subset，如果不是连续的，难道不是所有的正数加
起来就行了么？
同理这样的两题
largest subsequence of the given array that yields the largest PRODUCT
Maximum product subset with negative and positive integers |
|
l******6
发帖数: 340 | 31 lines are sorted by b?
Otherwise no way to find the nearest line to the point without go through
all the lines |
|
c***z
发帖数: 6348 | 32 Do not stand on moving sand.
If you happen to stand on moving sand, lie down and crawl away, to the
nearest stepping stone.
Then repeat the title. :) |
|
j******4
发帖数: 66 | 33 新人选组，特别纠结，不知道这2个组怎么样？哪个oncall重一些呢？
一个是Edge
Amazon Edge is a web service for content delivery. It integrates with other
Amazon Web Services to give developers and businesses an easy way to
distribute content to end users with low latency, high data transfer speeds,
and no commitments. AWS Edge can be used to deliver your entire website,
including dynamic, static and streaming content using a global network of
edge locations. Requests for your content are automatically routed to the
nearest edge l... 阅读全帖 |
|
y********e
发帖数: 7 | 34 lz现在cs ms在读，读书期间主要做data mining的research，但是并不深，本来也只是
想毕业了找个码农工作。之前面L家的data track悲剧但是design和coding据hr反馈说
还行，于是转到了application track，需要加面一个host manger interview。想问问
host manager interview时的面试官就是以后入职的manager吗？因为今天跟那个
manager聊感觉他对我做的东西不是很感兴趣（貌似太理论)，怕因为这个给我拒了...
如果是的话，我需不需要联系HR在换个manager面面看什么的。。。
初来乍到，附上L家面经：
电面没签NDA, 直接上题目了：
电面1
search a number in rotated sorted array (leetcode)
sum of nested list
电面2
Given n points, find the nearest K points to a new point.
permutation (leetcode)
Onsite
因为Onsite签了NDA... 阅读全帖 |
|
k*******a
发帖数: 433 | 35 sum of nested list 和 Given n points, find the nearest K points to a new
point.可以详细说一下吗？
谢谢！ |
|
l******i
发帖数: 194 | 36 k nearest points，k most frequent words这种，或者一个n长的array或者什么东西
，output top k elements，到底怎
么做啊～能不能给点code～ |
|
c**********1
发帖数: 32 | 37 given a data point outside a circle, find the nearest point on a circle.
Use any program language to implement it. |
|
c*******e
发帖数: 621 | 38 PointsOnAPlane这题怎么做？
感觉要用kd tree求k nearest neighbour?
这面试哪里写得完。。 |
|
y*****e
发帖数: 712 | 39 很多家都有这题，假如有很多points，找出离原点最近的k个点。
做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有
insert/pop operation的complexity是（n-k）log(k), 综合下来是nlogk
另外一种方法是任意去pivot, 每次call partition function, 把数组按放到pivot的
左边和右边，一直到pivot = k为止，直接return pivot左边的所有点。这种做法应该
是每次去掉一半的数组
n + n/2 + n/4 +.... = 2n也就是o(n),
应该是selection sort更好啊，为啥面试官总是让写heap? 是不是有其他的考量？比如
是streaming data或者数据量太大，不能一次完全放到array里？ |
|
j********l
发帖数: 325 | 40 这两种方法各有优缺点，如果数据量真的太大，内存hold不住的话，maxheap不存在这
个问题，但方法二不行。。。
如果强行使用方法二的话，需要使用divide and conquer，估计这就是一道系统设计
题了 |
|
c******n
发帖数: 4965 | 41 一般是要求不断地往里加点， heap/insertion 可以， partition 不行 |
|
x******8
发帖数: 48 | 42 快速排序也可以，follow up 数据很大或者数据是stream的 |
|
P******r
发帖数: 1342 | 43 你pivot怎么选？每次去掉一半是最优状况。最差状况每次只能去掉一个吧。
：很多家都有这题，假如有很多points，找出离原点最近的k个点。
：做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有 |
|
h****3
发帖数: 89 | 44 这个问题很好，感觉一改改就变系统设计了
我觉得楼上几位分析的很对，如果你有海量数据，维持k个固定space应该会更优；但如
果数据量有限，selection sort会更好 |
|
g******n
发帖数: 10 | 45 你的第二种方法最坏情况下时间复杂度是 O(n^2)，不是 O(n)，因为不是每次都刚好把
数组分成长度相当的两半，最坏情况下两边长度分别是 0 和 n-1，所以 T(n) = T(n-1
) + O(n)，总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort，而是
叫做 randomized-select，因为过程跟 randomized-quicksort 的 partition 非常相
似，期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215, §9.2
Selection in expected linear time |
|
|
c******w
发帖数: 1108 | 47 数据分5个5个的partition，然后pivot用median of medians来选就好了。textbook
material。 |
|
n******n
发帖数: 12088 | 48 方法2也可以。维护一个大小为2K的缓存，在里面做选择。 |
|
n******n
发帖数: 12088 | 49 快排最坏也是平方。这里回答平均复杂度够了
-1 |
|
n*****5
发帖数: 984 | 50 Amplify : 做K12教育的公司
HackerRank online coding。需要自己写读入函数。有点像nearest common ancestor
with parents。 最后快一半的test case 没过，我也不知道问啥，也没搞明白怎么调
试... 就没有然后了。
MLB ： 专做baseball相关的公司，好像很大，还在扩招。
core java question, hashcode equals.
然后问了很多spring的问题。 why use spring mvc, 怎么deploy jar， container
是啥。。。
没算法，电面就挂了。
Portware: 好像做交易平台的。 电面全是core java 相关的小问题。
Diff : String , StringBuffer, StringBuilder
Serialize, deserialize, transient
final var, method, class
try catch finally. can go with only try and finally . When ... 阅读全帖 |
|
