k*j
发帖数: 153 | 1 面了2轮电话。应该挂了。
第一轮电话面试，老印。已知每天的股票价格，计算何时买卖获益最大。这是个老题，
O(n)。
然后他扩展了一下，问如果可以多次买进卖出。如何maximize收益最大。
我先用DP，他说可以用recursive call。要我编程念给他听。然后说如何加速，我说建
一个table, O(n^2)。他说再怎么加速，我没答出来，他自己说应该是greedy 解法，O(
n).
第二轮，g docs 编程。是一个ABC面的。两个线段数组，求common区间
A［1，5］［10，15］
B [3,12]
return [3,5],[10,12]
这题有好几种情况要考虑。我没写好。
总结：
我是网上申请的。感觉他们家就只考算法，而且大部分都是如何加速到O(n)的题。没有
设计之类的问题。另外我发现glassdoor上的有关P家的题目很多，而且重复出的概率很
大，建议大家去做一下。Good luck。 |
v*****k
发帖数: 7798 | |
d********t
发帖数: 9628 | 3
同问，到底是啥P啊？
【在 v*****k 的大作中提到】
: P家？Pandora？
|
h*********n
发帖数: 915 | 4 palantir? i don't think they have many problems at glassdoor.
O(
【在 k*j 的大作中提到】
: 面了2轮电话。应该挂了。
: 第一轮电话面试，老印。已知每天的股票价格，计算何时买卖获益最大。这是个老题，
: O(n)。
: 然后他扩展了一下，问如果可以多次买进卖出。如何maximize收益最大。
: 我先用DP，他说可以用recursive call。要我编程念给他听。然后说如何加速，我说建
: 一个table, O(n^2)。他说再怎么加速，我没答出来，他自己说应该是greedy 解法，O(
: n).
: 第二轮，g docs 编程。是一个ABC面的。两个线段数组，求common区间
: A［1，5］［10，15］
: B [3,12]
|
n**********n
发帖数: 196 | 5 re
【在 h*********n 的大作中提到】
: palantir? i don't think they have many problems at glassdoor.
:
: O(
|
k*j
发帖数: 153 | 6 palantir. 有超过10题吧。做一下就知道他们家的风格了
【在 h*********n 的大作中提到】
: palantir? i don't think they have many problems at glassdoor.
:
: O(
|
c**********6
发帖数: 105 | |
h*********n
发帖数: 915 | 8 十题真不多。主要还是看coding。
他们给通知挺快的。到时吱一声吧。
【在 k*j 的大作中提到】
: palantir. 有超过10题吧。做一下就知道他们家的风格了
|
A**u
发帖数: 2458 | 9 cong
第一题，多次买卖 大牛有什么好办法嘛
O(
【在 k*j 的大作中提到】
: 面了2轮电话。应该挂了。
: 第一轮电话面试，老印。已知每天的股票价格，计算何时买卖获益最大。这是个老题，
: O(n)。
: 然后他扩展了一下，问如果可以多次买进卖出。如何maximize收益最大。
: 我先用DP，他说可以用recursive call。要我编程念给他听。然后说如何加速，我说建
: 一个table, O(n^2)。他说再怎么加速，我没答出来，他自己说应该是greedy 解法，O(
: n).
: 第二轮，g docs 编程。是一个ABC面的。两个线段数组，求common区间
: A［1，5］［10，15］
: B [3,12]
|
a*****t
发帖数: 30 | 10 for the first one, will this work:
buy whenever the price reaches local minimum, and sell whenever the price is
in local maximal ? |
l******c
发帖数: 2555 | 11 that's my solution, I don't why bothering DP.
is
【在 a*****t 的大作中提到】
: for the first one, will this work:
: buy whenever the price reaches local minimum, and sell whenever the price is
: in local maximal ?
|
l***i
发帖数: 1309 | 12 I think it works, but you need to prove it is optimal.
is
【在 a*****t 的大作中提到】
: for the first one, will this work:
: buy whenever the price reaches local minimum, and sell whenever the price is
: in local maximal ?
|
a*****t
发帖数: 30 | 13 I’m thinking a proof that could work. Here is the sketch--
1. Prove by contradiction that optimal strategy (with maximized profits)
must make a purchase when the price is at local minimum. Similarly, prove it
must sell at local maximum.
2. Prove by contraction, when selling and buying at all extreme price points
according to 1), the other transactions are unnecessary – they are not
producing more profits
【在 l***i 的大作中提到】
: I think it works, but you need to prove it is optimal.
:
: is
|
