这次ink的offer能坚持多久啊？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

这次ink的offer能坚持多久啊？

这次ink的offer能坚持多久啊？# Money - 海外理财

m*12014-09-30 07:09

1 楼

Given three arrays: A,B,C, you can get three element a,b,c from each of them
. Find the
minimum distance |a-b|+|b-c|+|c-a|.

l*q2014-09-30 07:09

2 楼

官网上没找到……

p*22014-09-30 07:09

3 楼

them
这题就是前几天有人贴过一个说的不清楚的。我印象中，这个才是真正的题目。

【在 m*****1 的大作中提到】

: Given three arrays: A,B,C, you can get three element a,b,c from each of them
: . Find the
: minimum distance |a-b|+|b-c|+|c-a|.

j*r2014-09-30 07:09

4 楼

https://creditcards.chase.com/ink-business-credit-cards
妈呀，，这么大的红字卡不到？？？

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

: 官网上没找到……

m*12014-09-30 07:09

5 楼

二爷来搞一下~~

l*q2014-09-30 07:09

6 楼

这。。。难道每个人打开看到的是不一样的么？我这里的红字只有：limited time
offer...没有然后了……

【在 j*********r 的大作中提到】

: https://creditcards.chase.com/ink-business-credit-cards
: 妈呀，，这么大的红字卡不到？？？

r*e2014-09-30 07:09

7 楼

只能想到nlogn的笨办法
把A,B,C都排序
然后遍历A中的元素a
对于每一个a，在B里找小于a的最大元素b'(二分查找logn)
再在C里找小于b'的最大元素c'（二分logn）
记录distance = a-b + b-c + a-c = 2(a-c)
由于A,B,C排列有六种可能，重复六遍上述过程，复杂度不变。。

them

【在 m*****1 的大作中提到】

: Given three arrays: A,B,C, you can get three element a,b,c from each of them
: . Find the
: minimum distance |a-b|+|b-c|+|c-a|.

r*b2014-09-30 07:09

8 楼

Oct 20. Referral link 上写的

m*12014-09-30 07:09

9 楼

为什么只找小于a的最大元素，不考虑大于a的最小元素吗

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

: 只能想到nlogn的笨办法
: 把A,B,C都排序
: 然后遍历A中的元素a
: 对于每一个a，在B里找小于a的最大元素b'(二分查找logn)
: 再在C里找小于b'的最大元素c'（二分logn）
: 记录distance = a-b + b-c + a-c = 2(a-c)
: 由于A,B,C排列有六种可能，重复六遍上述过程，复杂度不变。。
:
: them

w*s2014-09-30 07:09

10 楼

貌似第一年有年费？

c*a2014-09-30 07:09

11 楼

我智力有限
brute force...generate all combination triplets( 3^n)...
找distant最小的
假如面试时问我，我会先给brute force，然后慢慢改
这题有点像subset sum,用DP,找possible diff = 0, 1,....

l*q2014-09-30 07:09

12 楼

thanks!

【在 r****b 的大作中提到】

: Oct 20. Referral link 上写的

f*e2014-09-30 07:09

13 楼

sort, merge，find consecutive triplets

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

: 我智力有限
: brute force...generate all combination triplets( 3^n)...
: 找distant最小的
: 假如面试时问我，我会先给brute force，然后慢慢改
: 这题有点像subset sum,用DP,找possible diff = 0, 1,....

r*e2014-09-30 07:09

14 楼

也可以在C里找大于a的最小元素，同时记录distance = 2(c-b)
又想了一下，其实搜索过程可以简化
把A,B,C sort之后merge
然后在merged array里找元素来源的substr
这样的substr必须包含a,b,c，而且只有中间那个元素可以重复
例如merged之后的下标是 aabbcabc...
abbc和bca，cab，abc都符合条件
这样用两个指针扫一遍merged array，然后比较所有的substr的头尾之差
找的过程是O(n)

【在 m*****1 的大作中提到】

: 为什么只找小于a的最大元素，不考虑大于a的最小元素吗

D*d2014-09-30 07:09

15 楼

如果每个元素是 vector 不是 scalar 呢？是否除了穷举就没有办法了？

them

【在 m*****1 的大作中提到】

: Given three arrays: A,B,C, you can get three element a,b,c from each of them
: . Find the
: minimum distance |a-b|+|b-c|+|c-a|.

d*32014-09-30 07:09

16 楼

这个怎么保证consecutive triplets是分别来自A,B,C三个数组？

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

: sort, merge，find consecutive triplets

f*e2014-09-30 07:09

17 楼

leetcode上有个什么蠕虫算法的，先伸头，再缩尾，再伸头，再缩尾，。。。，O(N)可
以搞定，也不知道是否work。

【在 d*******3 的大作中提到】

: 这个怎么保证consecutive triplets是分别来自A,B,C三个数组？

r*e2014-09-30 07:09

18 楼

跟leetcode longest substr without repeating char差不多思路

【在 d*******3 的大作中提到】

: 这个怎么保证consecutive triplets是分别来自A,B,C三个数组？

m*12014-09-30 07:09

19 楼

那就是还要另外开一个同样长度的char数组helper[]，在merge的同时，存哪个数字属
于哪个数组，比如merge a数组中的2到i这个位置了，就存helper[i]='a'吧。。要不怎
么知道这个信息？

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

: 跟leetcode longest substr without repeating char差不多思路

c*t2014-09-30 07:09

20 楼

再好好想想。sort了以后，三个数组，你会怎样找最小绝对差值？
1）遍历会怎么找？
2）如果你现在取到 a 1, b 3, c 5 你下一个会怎么取？

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

: 也可以在C里找大于a的最小元素，同时记录distance = 2(c-b)
: 又想了一下，其实搜索过程可以简化
: 把A,B,C sort之后merge
: 然后在merged array里找元素来源的substr
: 这样的substr必须包含a,b,c，而且只有中间那个元素可以重复
: 例如merged之后的下标是 aabbcabc...
: abbc和bca，cab，abc都符合条件
: 这样用两个指针扫一遍merged array，然后比较所有的substr的头尾之差
: 找的过程是O(n)

r*e2014-09-30 07:09

21 楼

没看懂。我说的是sort之后merge成一个，然后扫描merged array
现在找到了a=1, b=3, c=5，记录差值8，然后保留b,c,找c的下一个

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

: 再好好想想。sort了以后，三个数组，你会怎样找最小绝对差值？
: 1）遍历会怎么找？
: 2）如果你现在取到 a 1, b 3, c 5 你下一个会怎么取？

r*e2014-09-30 07:09

22 楼

恩，这个是必要的
不merge其实也可以同时从三个sorted array扫描，写起来更麻烦一些

【在 m*****1 的大作中提到】

: 那就是还要另外开一个同样长度的char数组helper[]，在merge的同时，存哪个数字属
: 于哪个数组，比如merge a数组中的2到i这个位置了，就存helper[i]='a'吧。。要不怎
: 么知道这个信息？

c*t2014-09-30 07:09

23 楼

先不考虑merge
你是想说保留b,c,找“a”的下一个吧？为什么找a的下一个，而不是找b或c下一个？如
果想明白了，这道题就很容易了。

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

: 没看懂。我说的是sort之后merge成一个，然后扫描merged array
: 现在找到了a=1, b=3, c=5，记录差值8，然后保留b,c,找c的下一个

d*32014-09-30 07:09

24 楼

@recursive 和@fatalme的蠕虫算法好，我试着写了下
struct Tuple
{
int val;
char from;//A,B,or C
};
int MinAbsDiff(vectr& A,vector& B,vector& C)
{
sort(A.begin(),A.end());
sort(B.begin(),B.end());
sort(C.begin(),C.end());
vector D = Merge(A,B,C);
int findCount[3]={0};
int count = 0;
int ans = 2147483647;
for(int start =0,end =0;end < D.length();end++)
{
if(findCount[D[end].from-'A'] == 0)count++:
findCount[D[end].from-'A']++;
if(count == 3)
{
while(findCount[D[start].from-'A'] > 1)
{
start++;
findCount[D[start].from-'A']--;
}
if(ans == 0)return 0;
ans = min(ans,2*(D[end].val - D[start].val));
}
}
return ans;
}
简单的测了几组数组：
{1,2,3,5};{-3,4,6};{4,6,6,9}; 2
{1,2,3,};{2,3,4};{6,7,8,}; 6
{-9,-5,-10,};{0};{8,2,5,}; 14
{1,2,};{6,5, 4};{7,9,8}; 10
{2,2};{5,5, 5};{8,8,8,8,8}; 12

d*32014-09-30 07:09

25 楼

话说怎么把代码对齐啊~

e*l2014-09-30 07:09

26 楼

先sort，然后从3个头开始，最小的那个元素前进。扫一遍就可以了。
这个目标函数其实就是最大最小的差值的2倍，和中间的那个数没关系

r*e2014-09-30 07:09

27 楼

恩
a前进直到超过b或c，然后找出新的最小值再前进，重复到任何一个array走到头为止
之前想复杂了，和和

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

: 先不考虑merge
: 你是想说保留b,c,找“a”的下一个吧？为什么找a的下一个，而不是找b或c下一个？如
: 果想明白了，这道题就很容易了。

c*t2014-09-30 07:09

28 楼

是地，还是要走完所有吧。那么还需要sort吗？

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

: 恩
: a前进直到超过b或c，然后找出新的最小值再前进，重复到任何一个array走到头为止
: 之前想复杂了，和和

f*e2014-09-30 07:09

29 楼

那你的复杂度是多少？

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

: 是地，还是要走完所有吧。那么还需要sort吗？

f*e2014-09-30 07:09

30 楼

是用quick select那种思想吗？
A B C
1 2 3
2 3 4
3 4 5
......
....n
那这个的复杂度是多少？

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

: 恩
: a前进直到超过b或c，然后找出新的最小值再前进，重复到任何一个array走到头为止
: 之前想复杂了，和和

r*e2014-09-30 07:09

31 楼

每找出一个min of 3之后就走一步，一共3n步

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

: 是用quick select那种思想吗？
: A B C
: 1 2 3
: 2 3 4
: 3 4 5
: ......
: ....n
: 那这个的复杂度是多少？

L*r2014-09-30 07:09

32 楼

I think this is the right way to solve the problem. The time complexity is O
(n). Space is constant.

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

: 先sort，然后从3个头开始，最小的那个元素前进。扫一遍就可以了。
: 这个目标函数其实就是最大最小的差值的2倍，和中间的那个数没关系

f*e2014-09-30 07:09

33 楼

要用到，下面那个A,B,C都sorted了。
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
isplay;num=1189053613
还有stackflow那个都是先对A，B，C sort。
http://stackoverflow.com/questions/6567368/minimum-of-sum-of-ab

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

: 每找出一个min of 3之后就走一步，一共3n步

c*t2014-09-30 07:09

34 楼

嗯，确实要sort。还是O(nlgn)

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

: 要用到，下面那个A,B,C都sorted了。
: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
: isplay;num=1189053613
: 还有stackflow那个都是先对A，B，C sort。
: http://stackoverflow.com/questions/6567368/minimum-of-sum-of-ab