y***y 发帖数: 224 | 1 careercup 上看到的, 请教大家:
1 how would you create the index for a book?
http://www.careercup.com/question?id=3213666
2 Design a data structure to store a phone book so that you can search for a
phone number using name and vice verse. The solution should be time and
space efficient.
http://www.careercup.com/question?id=3488537
3 How do you think the updates on facebook work? What kind of a data
structure do you think they use? How would you be linked to your friends
updates?
http://www.careercup.com/q |
b********h 发帖数: 119 | 2 4.
设dp[i]为在i点抛出的最大收益,那么
dp[i] = dp[i-1]+val[i]-val[i-1]
int max_profit(vector val)
{
vector dp(val.size(), 0);
int max = 0;
for(int i = 1; i < val.size(); ++i)
if((dp[i-1]+val[i]-val[i-1])>0)
{
dp[i] = dp[i-1]+val[i]-val[i-1];
if(dp[i] > max) max = dp[i];
}
return max;
}
a
【在 y***y 的大作中提到】 : careercup 上看到的, 请教大家: : 1 how would you create the index for a book? : http://www.careercup.com/question?id=3213666 : 2 Design a data structure to store a phone book so that you can search for a : phone number using name and vice verse. The solution should be time and : space efficient. : http://www.careercup.com/question?id=3488537 : 3 How do you think the updates on facebook work? What kind of a data : structure do you think they use? How would you be linked to your friends : updates?
|
p********7 发帖数: 549 | 3 第一个用树,不是二叉树
第二个题名字查号码trie,号码查名字hash
第三题观察者模式? 你加一个好友,你就是他的主页观察者,他也是你主页的观察者,观察者有个list,如果你主页更新后会给每个观察者一个提示。 |
p********7 发帖数: 549 | 4 第四个题不是涨到最高卖,跌到最低买才是最多收益么?
不是DP吧
【在 b********h 的大作中提到】 : 4. : 设dp[i]为在i点抛出的最大收益,那么 : dp[i] = dp[i-1]+val[i]-val[i-1] : int max_profit(vector val) : { : vector dp(val.size(), 0); : int max = 0; : for(int i = 1; i < val.size(); ++i) : if((dp[i-1]+val[i]-val[i-1])>0) : {
|
x****k 发帖数: 2932 | 5 第四题是什么意思?已经知道了monday~friday的价格,计算最大可能profit?
那就是buy at lowest price and sell at highest price
or
short at highest then cover at lower,貌似没啥trick啊. |
y***y 发帖数: 224 | 6 第四题最好的情况是周一1块钱买入, 周三5块钱卖出, 周四2块钱再买入, 周五再3块钱
卖出, 利润是5块钱. 不是buy at lowest price and sell at highest price能解决的. |
p********7 发帖数: 549 | 7 利润不是5,周四你可以买2股,那么你周五卖出就赚了2块,总利润是6
是greedy算法,就是local min买,local max卖
的.
【在 y***y 的大作中提到】 : 第四题最好的情况是周一1块钱买入, 周三5块钱卖出, 周四2块钱再买入, 周五再3块钱 : 卖出, 利润是5块钱. 不是buy at lowest price and sell at highest price能解决的.
|
y***y 发帖数: 224 | 8
题中还说了,You are not allowed to do multiple trading in a day :)
【在 p********7 的大作中提到】 : 利润不是5,周四你可以买2股,那么你周五卖出就赚了2块,总利润是6 : 是greedy算法,就是local min买,local max卖 : : 的.
|
t****a 发帖数: 1212 | 9 prob 4:
Greedy strategy works.
int max_profit(int prices[], int n) {
int buy_date = -1, sell_date = -1;
int profit = 0;
for (int i=0; i
if (i==0 || prices[i] <= prices[i-1]) {
buy_date = i;
} else if (i==n-1 && prices[i]>prices[buy_date] ||
prices[i]>prices[i+1]) {
sell_date = i; profit += prices[sell_date] - prices[buy_date];
}
}
return profit;
}
// the output of the {1, 4, 5, 2, 3} is 5. |
y***y 发帖数: 224 | 10
觉得这个不对, 按这个算法,应该是周一买入,周二卖, 但其实周三卖才是最大收益~
【在 b********h 的大作中提到】 : 4. : 设dp[i]为在i点抛出的最大收益,那么 : dp[i] = dp[i-1]+val[i]-val[i-1] : int max_profit(vector val) : { : vector dp(val.size(), 0); : int max = 0; : for(int i = 1; i < val.size(); ++i) : if((dp[i-1]+val[i]-val[i-1])>0) : {
|
|
|
y***y 发帖数: 224 | 11
者,观察者有个list,如果你主页更新后会给每个观察者一个提示。
第一题能具体说说么?
第二题号码查名字用trie不也很好么?
麻烦了!
【在 p********7 的大作中提到】 : 第一个用树,不是二叉树 : 第二个题名字查号码trie,号码查名字hash : 第三题观察者模式? 你加一个好友,你就是他的主页观察者,他也是你主页的观察者,观察者有个list,如果你主页更新后会给每个观察者一个提示。
|
g*******s 发帖数: 490 | 12 第4题如果把股票价格想象成一个不断变化curve,就是找到所有的上升curve段。
所以假如1-n个价格,从1到n开始遍历,先设买入点为 1,如果i的价格减去i-1的价格
,这个差一直>0,就continue,一旦这个差<0,表示i的价格比i-1的价格低了,就在i-
1的时候卖一次,i的时候再买。如此继续。遍历一遍就能找出最大profit |
v****s 发帖数: 1112 | 13 i agree
【在 p********7 的大作中提到】 : 利润不是5,周四你可以买2股,那么你周五卖出就赚了2块,总利润是6 : 是greedy算法,就是local min买,local max卖 : : 的.
|
z*****x 发帖数: 4 | 14 what about
3, 1, 1, 4, 4
for the stock prices? |
f*******4 发帖数: 1401 | 15 同意这个
i-
【在 g*******s 的大作中提到】 : 第4题如果把股票价格想象成一个不断变化curve,就是找到所有的上升curve段。 : 所以假如1-n个价格,从1到n开始遍历,先设买入点为 1,如果i的价格减去i-1的价格 : ,这个差一直>0,就continue,一旦这个差<0,表示i的价格比i-1的价格低了,就在i- : 1的时候卖一次,i的时候再买。如此继续。遍历一遍就能找出最大profit
|
n**z 发帖数: 155 | 16
i-
但是有可能没有上升曲线,单调下降。
或者只有开始一段上升。然后下降。第二种情况只能买开始一次了。
【在 g*******s 的大作中提到】 : 第4题如果把股票价格想象成一个不断变化curve,就是找到所有的上升curve段。 : 所以假如1-n个价格,从1到n开始遍历,先设买入点为 1,如果i的价格减去i-1的价格 : ,这个差一直>0,就continue,一旦这个差<0,表示i的价格比i-1的价格低了,就在i- : 1的时候卖一次,i的时候再买。如此继续。遍历一遍就能找出最大profit
|
g*****e 发帖数: 3417 | 17 how about 1,2,1,5,7
i-
【在 g*******s 的大作中提到】 : 第4题如果把股票价格想象成一个不断变化curve,就是找到所有的上升curve段。 : 所以假如1-n个价格,从1到n开始遍历,先设买入点为 1,如果i的价格减去i-1的价格 : ,这个差一直>0,就continue,一旦这个差<0,表示i的价格比i-1的价格低了,就在i- : 1的时候卖一次,i的时候再买。如此继续。遍历一遍就能找出最大profit
|