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
|
