Palantir面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Palantir面经

Palantir面经# JobHunting - 待字闺中

s*e2011-10-06 07:10

1 楼

Java整数最大值是多少
2个数组求交集，一个大，一个小怎么办
stock price在一个数组里，求赚最多
买2次，求赚最多，条件：第二次的买入要迟于第一次的卖出。

h*n2011-10-06 07:10

2 楼

买卖两次？

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

: Java整数最大值是多少
: 2个数组求交集，一个大，一个小怎么办
: stock price在一个数组里，求赚最多
: 买2次，求赚最多，条件：第二次的买入要迟于第一次的卖出。

k*n2011-10-06 07:10

3 楼

这个题我听说买卖k次有O(n)的解法，一直没想出来，谁知道么？

【在 h*********n 的大作中提到】

: 买卖两次？

c*o2011-10-06 07:10

4 楼

2个数组求交集，一个大，一个小怎么办
这个是什么意思？一个数组长，一个数组短？

h*n2011-10-06 07:10

5 楼

no way

【在 k****n 的大作中提到】

: 这个题我听说买卖k次有O(n)的解法，一直没想出来，谁知道么？

k*n2011-10-06 07:10

6 楼

我估计意思是不能用hashmap，不能用extra memory，所以只能Inplace sort其中一个
那么应该sort哪一个。
假设长度分别是m，n，m>>n。
如果sort短的，时间是O(nlogn)+O(mlogn) = O((m+n) logn)
如果sort长的，时间是O(mlogm)+O(nlogm) = O((m+n) logm)
所以应该sort短的。
但是实际也有可能是这样
sort短的，时间是anlogn + bmlogn = (an + bm) logn
sort长的，时间是amlogm + bnlogm = (am + bn) logm
a和b分别是排序和二分查找的常数系数
因为 m >> n，所以带n的可以忽略，那么就是b * logn * m vs a * logm * m
所以当查找的常数项b和排序的常数项a满足 b logn > a logm的时候
排序长的可能比较快。
不过这一般不会发生。。。除非二分查找写成shit...
（刚才写错了，不过结论是一样的）

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

: 2个数组求交集，一个大，一个小怎么办
: 这个是什么意思？一个数组长，一个数组短？

m*q2011-10-06 07:10

7 楼

我觉得第二题是可以O(n)的
可以把原数组的所有波峰波谷分别记录到两个数组a[k],b[k]中，
题目相当于是在把数组a，b分成两段使得两段中的a，b差值和
为最大。
可以先从前向后扫描数组a，b，对于所有index i,计算 b[q]-a[p]
的最大值，存在c[i]中，其中 0<= p <= q <=i；
然后从后向前扫描数组a，b，对于所有index i，计算 b[q]-a[p]
的最大值，存在d[i]中，其中 i<= p <= q <=k-1
然后计算index j使得c[j]+d[k-1-j]最大， 0<= j<= k-1
举个例子:
3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6
则 k=3
数组a[] = {3, 5, 2}
数组b[] = {8, 15, 11}
数组c[] = {5, 12, 12}
数组d[] = {12, 10, 9}
对应的和分别为 5+10=15, 12+9=21
最大值为21
a，b两个数组的空间可能可以优化掉，
c，d两个数组应该需要一个就够
求大牛们指正

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

h*n2011-10-06 07:10

8 楼

such one step requires O(1) if you want total is O(n). how?

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

: 我觉得第二题是可以O(n)的
: 可以把原数组的所有波峰波谷分别记录到两个数组a[k],b[k]中，
: 题目相当于是在把数组a，b分成两段使得两段中的a，b差值和
: 为最大。
: 可以先从前向后扫描数组a，b，对于所有index i,计算 b[q]-a[p]
: 的最大值，存在c[i]中，其中 0<= p <= q <=i；
: 然后从后向前扫描数组a，b，对于所有index i，计算 b[q]-a[p]
: 的最大值，存在d[i]中，其中 i<= p <= q <=k-1
: 然后计算index j使得c[j]+d[k-1-j]最大， 0<= j<= k-1
: 举个例子:

m*q2011-10-06 07:10

9 楼

从前向后扫描一遍，生成数组c[]。基本上就是记录当前遇到过的最小a值，
然后对每个b[i]算差值,存到c[i]中。列一下伪代码可能清楚一点，生成
数组d的过程类似。
就是利用经典的买卖股票问题（一买一卖）
int min = MAX_INT;
int diff = 0;
for (int i=0; i< k; i++) {
if (a[i] < min)
min = a[i];

if (b[i] - min > diff)
diff = b[i] - min;
c[i] = diff;
}

h*n2011-10-06 07:10

10 楼

“买卖”是O(n)。
“买卖买卖”O(n^2)很容易，但O(n)怎么做到？

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

: 从前向后扫描一遍，生成数组c[]。基本上就是记录当前遇到过的最小a值，
: 然后对每个b[i]算差值,存到c[i]中。列一下伪代码可能清楚一点，生成
: 数组d的过程类似。
: 就是利用经典的买卖股票问题（一买一卖）
: int min = MAX_INT;
: int diff = 0;
: for (int i=0; i< k; i++) {
: if (a[i] < min)
: min = a[i];
:

m*q2011-10-06 07:10

11 楼

再解释一下
只考虑递增区间，假设原数组为
3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6
那么存在3个上升区间
（1）（2）（3）
[3 6 8] [4 5 7 9 13 15] [2 7 11]
根据题目的要求，我们要做的就是把这三个区间分成两部分，
可以有
1, (2, 3)
(1, 2), 3
两种分法
先从左边扫描原数组，计算数组c，就算出了区间 1 和区间（1，2）里
可以得到的最大差值
然后从右边扫描数组，计算数组d，就算出了区间 3 和区间（2，3）里
可以得到的最大差值
最后，计算 1+(2,3) 和 (1,2)+3, 去最大值即可
复杂度O(n)

【在 h*********n 的大作中提到】

: “买卖”是O(n)。
: “买卖买卖”O(n^2)很容易，但O(n)怎么做到？

h*n2011-10-06 07:10

12 楼

“上升区间”是说长度至少为2的连续递增序列？
为何转换成区间分组可解决这个问题？如果有十个区间呢？
没看懂你的思路。希望能看到严格证明。

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

: 再解释一下
: 只考虑递增区间，假设原数组为
: 3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6
: 那么存在3个上升区间
: （1）（2）（3）
: [3 6 8] [4 5 7 9 13 15] [2 7 11]
: 根据题目的要求，我们要做的就是把这三个区间分成两部分，
: 可以有
: 1, (2, 3)
: (1, 2), 3

m*q2011-10-06 07:10

13 楼

是的
要获得总的最大利润，一定是在两个局部低点买，在两个局部高点卖，
这里，上升区间都是从局部低点到局部高点的。假设一共有k个这样的
区间，由于第二次买要在第一次卖之后，所以可以把这些区间分成两半，
每一半里有一买一卖。
假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润，
最大利润 = max { profit[0, p] + profit[p+1, k-1] }
其中 0 <= p <= k-2

【在 h*********n 的大作中提到】

:
: “上升区间”是说长度至少为2的连续递增序列？
: 为何转换成区间分组可解决这个问题？如果有十个区间呢？
: 没看懂你的思路。希望能看到严格证明。

l*y2011-10-06 07:10

14 楼

如果有 n / 2 个区间怎么办？

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

:
: 是的
: 要获得总的最大利润，一定是在两个局部低点买，在两个局部高点卖，
: 这里，上升区间都是从局部低点到局部高点的。假设一共有k个这样的
: 区间，由于第二次买要在第一次卖之后，所以可以把这些区间分成两半，
: 每一半里有一买一卖。
: 假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润，
: 最大利润 = max { profit[0, p] + profit[p+1, k-1] }
: 其中 0 <= p <= k-2

f*52011-10-06 07:10

15 楼

for each p ,u need O(n) to get profit[0, p], profit[p+1, k-1]
while the possibility of p is also O(n)

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

m*q2011-10-06 07:10

16 楼

n/2个区间也没问题啊，只要题目要求还是两次买卖，都可以保证O(n)
如果是m次买卖，就得用DP了，恐怕就不是O（n）了

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

: 如果有 n / 2 个区间怎么办？

m*q2011-10-06 07:10

17 楼

扫描一遍所有的p就都出来了，这个是利用经典题
改天有空我写个code出来吧，更清楚些

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

: for each p ,u need O(n) to get profit[0, p], profit[p+1, k-1]
: while the possibility of p is also O(n)

k*n2011-10-06 07:10

18 楼

这么麻烦，我还以为你说k次买卖的解法呢

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

b*e2011-10-06 07:10

19 楼

这个是有O(N) for k 的解法的，实际上是kn并且有一个mN的上限，得空写出来。

【在 k****n 的大作中提到】

: 这么麻烦，我还以为你说k次买卖的解法呢

s*f2011-10-06 07:10

20 楼

int EarnMost(int prices[], int len){
if (!prices !! len < 1)
return 0;
int minp = prices[0];
int maxp = prices[0];
int ret = 0;
for (int i = 1; i < len; ++i){
if (prices[i] > maxp){
maxp = prices[i];
ret = maxp - minp > ret? maxp - minp:ret;
}else if (prices[i] < minp){
minp = prices[i];
maxp = prices[i];
}
}
return ret;
}
if [5,4,3,2,1], it returns 0, not -1.

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

j*x2011-10-06 07:10

21 楼

题目问的是两次买卖

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

: int EarnMost(int prices[], int len){
: if (!prices !! len < 1)
: return 0;
: int minp = prices[0];
: int maxp = prices[0];
: int ret = 0;
: for (int i = 1; i < len; ++i){
: if (prices[i] > maxp){
: maxp = prices[i];
: ret = maxp - minp > ret? maxp - minp:ret;

h*r2011-10-06 07:10

22 楼

下面这个方法行不行？ O(n), 模拟一次买卖的DP解法。大牛们看看对不对?
#include
#include
#include
void dump(int *x, int l) {

int i;
for (i = 0; i < l; ++ i) {

printf("%d ", x[i]);
}
printf("\n");
}
int main() {
int array[] = {3, 6, 8, 4, 5, 7, 9, 13, 15, 10, 6, 2, 7, 11, 8, 6};
int len = sizeof(array)/sizeof(int);
assert (len >= 4);
int *a = (int*)malloc(sizeof(int)*len);
int *b = (int*)malloc(sizeof(int)*len);
int *c = (int*)malloc(sizeof(int)*len);
int *d = (int*)malloc(sizeof(int)*len);
int i, diff, max;
a[0] = array[0];
b[1] = array[1] - array[0];
c[2] = (-array[2]) + array[1] - array[0];
d[3] = array[3] - array[2] + array [1] - array[0];
max = d[3];
for(i = 1; i < len; ++i) {
// generate the array of a;
a[i] = array[i] < a[i-1] ? array[i] : a[i-1];

// generate the array of b;
if (i >= 2) {

diff = array[i] - a[i-1];
b[i] = diff > b[i-1] ? diff : b[i-1];
}
// generate the array of c;
if (i >= 3) {

diff = (-array[i]) + b[i-1];
c[i] = diff > c[i-1] ? diff : c[i-1];
}
// generate the array of d;
if (i >= 4) {

diff = array[i] + c[i-1];
d[i] = diff > d[i-1] ? diff : d[i-1];

if (d[i] > max) max = d[i];
}
}
dump(a, len);
dump(b, len);
dump(c, len);
dump(d, len);
printf("Two times buy/sell stocks --- MAX: %d\n", max);

free(a);
free(b);
free(c);
free(d);
return 1;
}

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

: 题目问的是两次买卖

j*x2011-10-06 07:10

23 楼

精妙

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

: 下面这个方法行不行？ O(n), 模拟一次买卖的DP解法。大牛们看看对不对?
: #include
: #include
: #include
: void dump(int *x, int l) {
:
: int i;
: for (i = 0; i < l; ++ i) {
:
: printf("%d ", x[i]);