Amazon 面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Amazon 面试题

Amazon 面试题# JobHunting - 待字闺中

s*i2014-09-14 07:09

1 楼

Given three arrays A,B,C containing unsorted numbers. Find three numbers a,
b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
Please provide as efficient code as you can.

l*a2014-09-14 07:09

2 楼

sort separately,
then merge multiple sorted list?

,
minimum

【在 s*i 的大作中提到】

: Given three arrays A,B,C containing unsorted numbers. Find three numbers a,
: b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
: Please provide as efficient code as you can.

A*i2014-09-14 07:09

3 楼

赶脚像小学奥数题

A*i2014-09-14 07:09

4 楼

错了应该是初中奥数题，多项式展开还是怎么来着，以前一定做过

f*w2014-09-14 07:09

5 楼

什么叫|a-b|, |b-c|, |c-a|最小？
三个的和最小？

s*i2014-09-14 07:09

6 楼

他们之间最大的，最小。
彼此间的距离。
【2，4，8】
【1，9，3】
【-4，7，6】
8，9，7是解

r*72014-09-14 07:09

7 楼

any better solution so far?

【在 l*****a 的大作中提到】

: sort separately,
: then merge multiple sorted list?
:
: ,
: minimum

h*e2014-09-14 07:09

8 楼

O(n logn)?
刚看了阿里题目 2013ali也有这道题。

r*32014-09-14 07:09

9 楼

O(n1+n2+n3) n1,n2,n3 是三个数组的长度
|a-b|+|b-c|+|c-a| 其实就是求 2*(最大数-最小数) (eg. 如果a>b>c, |a-b|+|b-c|+|
c-a| = 2(a-c) )
三个指针i, j, k
从头开始扫, 总是移动最小的那个指针更新当前最小的 2*(最大数-最小数) 即可
证明正确性:
在扫的过程中, 对于三个数组中的任意一个数, 分三种情况讨论 (下面假设取出的三个
数 a>b>c)
1. 如果他作为b, 那么永远不影响最后结果
2. 如果他作为a, 在他作为a的时候, 由于一直在移动另两个指针并接近a, 肯定能扫到
那个对于a而言最大的c
3. 如果他作为c, 假设 a或者b不是自己数组中比c大的最小值, 那么肯定有在c数组还
没扫到c的时候有移动a,b数组指针的情况, 但这和假设矛盾
证明写的有点乱求大神更好更清楚的证明
EDIT: 看错了, 应该先sort的 = =

n*n2014-09-14 07:09

10 楼

语文水平需要提高

【在 s*i 的大作中提到】

: 他们之间最大的，最小。
: 彼此间的距离。
: 【2，4，8】
: 【1，9，3】
: 【-4，7，6】
: 8，9，7是解

t*e2014-09-14 07:09

11 楼

这题有比较简洁明了的解法么? careercup上看到20多个回帖，看上去每个都不一样

s*i2014-09-14 07:09

12 楼

我看 robot13的解法挺好的。

[发表自未名空间手机版 - m.mitbbs.com]

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

: 这题有比较简洁明了的解法么? careercup上看到20多个回帖，看上去每个都不一样

t*e2014-09-14 07:09

13 楼

有具体的代码实现么？感觉先决条件a>b>c不一定能满足啊

【在 s*i 的大作中提到】

: 我看 robot13的解法挺好的。
:
: [发表自未名空间手机版 - m.mitbbs.com]

z*t2014-09-14 07:09

14 楼

写了一下代码，放在
http://ideone.com/M3ZaKt
测了几个test case，都过了

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

: 有具体的代码实现么？感觉先决条件a>b>c不一定能满足啊

m*a2014-09-14 07:09

15 楼

可以直接就用set来做，A和B分别放到seta, setb里面，然后遍历C，对C[i]找seta.
lower_bound(C[i]), seta.lower_bound(C[i])-1, setb.lower_bound(C[i]), setb.
lower_bound(C[i])-1，然后seta, setb和C[I]组合来计算，也是nlogn的