一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3199|回复: 28
收起左侧

Google电面面经,一道难题

[复制链接] |试试Instant~ |关注本帖
getway32 发表于 2015-9-18 01:03:31 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一开始先聊了聊简历,我做过一个安卓的项目,他挺感兴趣,聊了聊,然后开始技术面:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. best time to sell stock 2;
2 在第一题的基础上加了个限制,就是如果今天卖出股票,则第二天不能进行买进操作,需要隔一天,而就是说第三天才能;
举例: 1,2,3,4,2,3,4; 则利润为4, 因为第一天买,第4天卖,第5天不能买,所以第六天买第7天卖。. visit 1point3acres.com for more.

我提到用DP,但一直想不出转移方程,面试官提示说可以用两个数组纪录状态,一个是持有股票,一个说没有持有股票,,LZ太笨,没想出来。

最后是被拒了。
. From 1point 3acres bbs

补充内容 (2015-9-18 01:10):
另外求点大米,,想看另外一个面经,权限太低看不到图。。。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

xiaoyucool 发表于 2015-9-18 09:32:17 | 显示全部楼层
按照楼主的提示,我也写了一下,代码就和楼上那位的差不多,不过我感觉她的变量名好像正好和数组含义相反。。
  1.   public static int maxProfit(int[] prices){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.           if(prices == null || prices.length == 0){
  3.                     return 0;
  4.       }

  5.     //整个交易过程中,我们有两种状态,一种是手头只有钱没股票,一种是手头有股票没钱.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.     //而最后获得最大利润的状态肯定是手头只有钱,所有股票都被抛售的状态. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.         int[] bear = new int[prices.length];
  8.         //bear position 就是空仓,表示在这个位置我们手头没有股票
  9.         int[] bull = new int[prices.length];. From 1point 3acres bbs
  10.         //bull position 就是满仓,表示在这个位置我们手头已经买了股票,在等待机会抛售
  11.         bear[0] = 0;
  12.         //初始情况,因为手头没股票,所以盈利是0
  13.         bull[0] = 0-prices[0];
  14.         //初始情况,我们钱买了股票,所以是 0-prices[0]
  15.         for(int i =  1;i<prices.length;i++){
  16.                 bear[i] = Math.max(bear[i-1],bull[i-1]+prices[i]);
  17.                 //空仓的最大利润的递归式是:bear[i] = max(bear[i-1],bull[i-1]+prices[i]);
  18.                 //意思就是当前最大利润应该为前一天空仓的利润(既我们这一天不做任何买卖)和前一天满仓和今天卖出 两者中的最大值
  19.                 if(i == 1){. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                         //而对于满仓的话,递归式应该为 bull[i] = max(bull[i-1],bear[i-2]-prices[i])
  21.                         //意思即是 满仓的最大值应该是 前一天满仓,和两天之前空仓今天买入 中的最大值
  22.                         //因为题目限定了要隔一天才能买
  23.                         //对于第一天要单独考虑,因为之前没有买过股票.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                         bull[i] = Math.max(bull[0],0-prices[1]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  25.                 }else{
  26.                         bull[i] = Math.max(bull[i-1],bear[i-2]-prices[i]);
  27.                 }
  28.         }
  29.         return bear[prices.length-1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30. }
复制代码

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

flexwang 发表于 2015-9-18 21:22:18 | 显示全部楼层
  1. int maxProfit5(vector<int>& prices) {
  2.     if (prices.size() < 2) return 0;. 鍥磋鎴戜滑@1point 3 acres
  3.     vector<int> hold(prices.size()), unhold(prices.size());. more info on 1point3acres.com
  4.     hold[0] = -prices[0];
  5.     unhold[0] = 0;
  6.     for (int i=1; i<prices.size(); i++) {
  7.         hold[i] = max(hold[i-1], unhold[i-1]-prices[i]);
  8.         unhold[i] = max(unhold[i-1], hold[i-1]+prices[i]);. visit 1point3acres.com for more.
  9.     }
  10.     return *max_element(unhold.begin(), unhold.end());
  11. }
复制代码
回复 支持 1 反对 0

使用道具 举报

坐看云起 发表于 2015-9-18 04:54:17 | 显示全部楼层
可以写出基于best time to buy IV的万能解法吧,就是说把gap长度和购买次数当参量传入;
OPT[i][j] = Math.max(OPT[i][j-1], last[j-1] + input[j]);
res = Math.max(res, OPT[i][j]);
last[j] = Math.max(last[j-1], OPT[i-1][j-gap] - input[j]);
主要就是这三行
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-9-18 01:05:06 | 显示全部楼层
第二题求啥?
回复 支持 反对

使用道具 举报

 楼主| getway32 发表于 2015-9-18 01:05:44 | 显示全部楼层

也是求最大利润
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-18 01:17:41 | 显示全部楼层
..这个one pass 没想出来,
感觉面试官的意思是, 对于第i个stock, 用2个数组, 第一个数组是如果买i, 当前的最大利润, 第二个数组是如果不买i,当前的最大利润.
不过这个one pass不行吧..
回复 支持 反对

使用道具 举报

juslun 发表于 2015-9-18 01:28:55 | 显示全部楼层
这样如何,用一个数组profit[i]记录到当天的max profit
判断num[i-2] num[i-1] num[i], 如果是递增,则 profit[i] = profit[i-1] + diff
如果num[i-1]是最小的,则profit[i] = Math.max(diff + profit[i-3], profit[i-1])
如果num[i] < num[i-1] profit[i] = profit[i-1]
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-18 02:35:37 | 显示全部楼层
Based on linear solution for Q1,  all you need to do is adding a conditional logic when selling.

What we need to consider is whether to sell at the peak or the day before peak. Only reason we sell before peak is to capture low price after the peak, thus we only need to compare two price differences and choose whichever larger.

Say day i is the peak price day, then compare (prices[i+2]-prices[i+1]) and (prices[i]-prices[i-1]). If former is larger then it means after peak low price is low enough to justify buying in before peak price.
.鐣欏璁哄潧-涓浜-涓夊垎鍦
For the last day, we don't need to consider these as we will not be buying in after.

This makes it still a linear solution.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-18 02:49:09 | 显示全部楼层
说个简单的思路,从price array可以拿到一个profit array。
. more info on 1point3acres.com
对于这个profit array来说,先找到第一个非负的数,然后对接下来的,如果 i 对应的是正数就往下走,如果 i 对应的是负数就看i+1,如果 i 和 i+1的和是负数,就在i位置卖掉然后从i+2开始找下一个正数;如果 i 和 i+1的和是正数,就不卖,也跳去i+2。

总结一下,就是对于profit array,要跳(卖)就要跳最少两个数,看这两个数的和是否大于0了。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-18 03:22:03 | 显示全部楼层
根据lz给的hint写了一个 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        public int maxProfit(int[] prices){
                if(prices == null || prices.length == 0){
                        return 0;
                }
                int length = prices.length;
                int[] waitForSell = new int[length];
                int[] waitForBuy = new int[length];
                waitForSell[0] = 0;
                waitForBuy[0] = 0 - prices[0];
                for(int i=1;i<length;i++){. Waral 鍗氬鏈夋洿澶氭枃绔,
                        waitForSell[i] = Math.max(waitForSell[i-1],prices[i]+waitForBuy[i-1]);
                        if(i == 1){
                                waitForBuy[i] = Math.max(waitForBuy[0],0-prices[i]);
                        }
                        else{. From 1point 3acres bbs
                                waitForBuy[i] = Math.max(waitForBuy[i-1],waitForSell[i-2]-prices[i]);. 1point3acres.com/bbs
                        }
                }. more info on 1point3acres.com
                return waitForSell[length-1];
        }
回复 支持 反对

使用道具 举报

purplesky85 发表于 2015-9-18 06:02:08 | 显示全部楼层
不知道这样行不行.鏈枃鍘熷垱鑷1point3acres璁哄潧
用profit[i]记录在第i天卖能获得的最大利润。因为要隔一天才能买, 所以如果第i - 1卖了, 第i天不能买也不能卖。 如果第i - 2天卖了, 第i天只能买不能卖, 这个时候的最大值就等于第i - 2天卖的最大利润,如果是第i - 3天卖,第i天就可以卖,并且买入的价格就是第i - 1天的价格。. more info on 1point3acres.com
profit[i] = Max(profit[i - 3] + Max(A[i] - A[i - 1], 0), profit[i - 3] + A[i] - A[i - 3]).
用一个globalMax记录最大值就可以了。
回复 支持 反对

使用道具 举报

atlas1017 发表于 2015-9-18 07:01:12 | 显示全部楼层
edna 发表于 2015-9-18 02:49
说个简单的思路,从price array可以拿到一个profit array。

对于这个profit array来说,先找到第一个非 ...
-google 1point3acres
好像有一个问题 就是对于profit array而言, 如果i 之前(不包括 i) 都是正数, i 为负数 i + 1为正数。 虽然 p + p[i + 1] > 0 但是有可能discard p[i - 1] && take p[i +1] 更大。 比如p[i - 1] = 1; p = -3; p[i + 1] = 5;
不卖走到后面的profit是3, 只拿第二个是5
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-18 08:06:05 | 显示全部楼层
atlas1017 发表于 2015-9-18 07:01
好像有一个问题 就是对于profit array而言, 如果i 之前(不包括 i) 都是正数, i 为负数 i + 1为正数。 ...

你说的对,这个是我疏忽了。

如果遇到正数,那就要看它后面的两个数,那这个过程有点繁琐了。
回复 支持 反对

使用道具 举报

aplusplus 发表于 2015-9-18 12:14:52 | 显示全部楼层
maxProfit[i] = max { maxProfit[i-1],  maxProfit[i-2] + Math.max(0, price[i]-prices[i-1]) }
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-27 03:34:43 | 显示全部楼层

hold = max(hold[i-1], unhold[i-1]-prices);
这行有问题,应该是hold = max(hold[i-1], unhold[i-2]-prices);
因为如果前一天卖出了股票,当天不能买入
回复 支持 反对

使用道具 举报

charles92 发表于 2015-9-27 06:21:07 | 显示全部楼层
坐看云起 发表于 2015-9-27 03:34
hold = max(hold, unhold-prices);
这行有问题,应该是hold = max(hold, unhold-prices);. visit 1point3acres.com for more.
因为如果前一 ...
-google 1point3acres
有道理,但这么改也不对吧…因为你并不知道unhold的值是否是第i天卖股票得到的。第i天卖没卖股票从unhold这个array上是看不出来的。

补充内容 (2015-9-27 06:25):
不对…我好想想错了…等等…
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-27 06:59:33 | 显示全部楼层
charles92 发表于 2015-9-27 06:21
有道理,但这么改也不对吧…因为你并不知道unhold的值是否是第i天卖股票得到的。第i天卖没卖股票从unhold ...

hold和unhold都是那一天的最大收益,不保证当天有买卖啦
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2015-9-27 07:55:56 | 显示全部楼层
lz是否记得LC那道偷东西的题?就是相隔两家不能偷。我觉得那个解法应该可以?sry我比较早做的题,印象中应该是你follow up的思路
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-9-28 01:01:30 来自手机 | 显示全部楼层
很好的解答
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 12:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表