【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5048|回复: 28
收起左侧

Google电面面经,一道难题

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

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

最后是被拒了。

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

评分

4

查看全部评分

本帖被以下淘专辑推荐:

xiaoyucool 发表于 2015-9-18 09:32:17 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
按照楼主的提示,我也写了一下,代码就和楼上那位的差不多,不过我感觉她的变量名好像正好和数组含义相反。。
  1.   public static int maxProfit(int[] prices){. from: 1point3acres.com/bbs
  2.           if(prices == null || prices.length == 0){
  3.                     return 0;
  4.       }

  5.     //整个交易过程中,我们有两种状态,一种是手头只有钱没股票,一种是手头有股票没钱
  6.     //而最后获得最大利润的状态肯定是手头只有钱,所有股票都被抛售的状态. from: 1point3acres.com/bbs
  7.         int[] bear = new int[prices.length];. 鍥磋鎴戜滑@1point 3 acres
  8.         //bear position 就是空仓,表示在这个位置我们手头没有股票
  9.         int[] bull = new int[prices.length];.1point3acres缃
  10.         //bull position 就是满仓,表示在这个位置我们手头已经买了股票,在等待机会抛售
  11.         bear[0] = 0;
  12.         //初始情况,因为手头没股票,所以盈利是0. Waral 鍗氬鏈夋洿澶氭枃绔,
  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){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.                         //而对于满仓的话,递归式应该为 bull[i] = max(bull[i-1],bear[i-2]-prices[i]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.                         //意思即是 满仓的最大值应该是 前一天满仓,和两天之前空仓今天买入 中的最大值
  22.                         //因为题目限定了要隔一天才能买
  23.                         //对于第一天要单独考虑,因为之前没有买过股票
  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 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. int maxProfit5(vector<int>& prices) {-google 1point3acres
  2.     if (prices.size() < 2) return 0;
  3.     vector<int> hold(prices.size()), unhold(prices.size());. 鍥磋鎴戜滑@1point 3 acres
  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]);
  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]);. more info on 1point3acres.com
res = Math.max(res, OPT[i][j]);
last[j] = Math.max(last[j-1], OPT[i-1][j-gap] - input[j]);. visit 1point3acres.com for more.
主要就是这三行
回复 支持 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 没想出来,
. 鍥磋鎴戜滑@1point 3 acres感觉面试官的意思是, 对于第i个stock, 用2个数组, 第一个数组是如果买i, 当前的最大利润, 第二个数组是如果不买i,当前的最大利润.
不过这个one pass不行吧..
回复 支持 反对

使用道具 举报

juslun 发表于 2015-9-18 01:28:55 | 显示全部楼层
这样如何,用一个数组profit[i]记录到当天的max profit. more info on 1point3acres.com
判断num[i-2] num[i-1] num[i], 如果是递增,则 profit[i] = profit[i-1] + diff. from: 1point3acres.com/bbs
如果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.
. 1point3acres.com/bbs
This makes it still a linear solution.

-google 1point3acres
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-18 02:49:09 | 显示全部楼层
说个简单的思路,从price array可以拿到一个profit array。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

对于这个profit array来说,先找到第一个非负的数,然后对接下来的,如果 i 对应的是正数就往下走,如果 i 对应的是负数就看i+1,如果 i 和 i+1的和是负数,就在i位置卖掉然后从i+2开始找下一个正数;如果 i 和 i+1的和是正数,就不卖,也跳去i+2。
.1point3acres缃
总结一下,就是对于profit array,要跳(卖)就要跳最少两个数,看这两个数的和是否大于0了。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-18 03:22:03 | 显示全部楼层
根据lz给的hint写了一个
        public int maxProfit(int[] prices){-google 1point3acres
                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++){
                        waitForSell[i] = Math.max(waitForSell[i-1],prices[i]+waitForBuy[i-1]);. 1point 3acres 璁哄潧
                        if(i == 1){. from: 1point3acres.com/bbs
                                waitForBuy[i] = Math.max(waitForBuy[0],0-prices[i]);
                        }. 鍥磋鎴戜滑@1point 3 acres
                        else{
                                waitForBuy[i] = Math.max(waitForBuy[i-1],waitForSell[i-2]-prices[i]);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        }
                }
                return waitForSell[length-1];. 1point 3acres 璁哄潧
        }
回复 支持 反对

使用道具 举报

purplesky85 发表于 2015-9-18 06:02:08 | 显示全部楼层
不知道这样行不行
用profit[i]记录在第i天卖能获得的最大利润。因为要隔一天才能买, 所以如果第i - 1卖了, 第i天不能买也不能卖。 如果第i - 2天卖了, 第i天只能买不能卖, 这个时候的最大值就等于第i - 2天卖的最大利润,如果是第i - 3天卖,第i天就可以卖,并且买入的价格就是第i - 1天的价格。
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来说,先找到第一个非 ...

好像有一个问题 就是对于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为正数。 ...

. Waral 鍗氬鏈夋洿澶氭枃绔,你说的对,这个是我疏忽了。.1point3acres缃

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

使用道具 举报

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. From 1point 3acres bbs
hold = max(hold, unhold-prices);
这行有问题,应该是hold = max(hold, unhold-prices);
因为如果前一 ...

有道理,但这么改也不对吧…因为你并不知道unhold的值是否是第i天卖股票得到的。第i天卖没卖股票从unhold这个array上是看不出来的。
.1point3acres缃
补充内容 (2015-9-27 06:25):.1point3acres缃
不对…我好想想错了…等等…
回复 支持 反对

使用道具 举报

坐看云起 发表于 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 来自手机 | 显示全部楼层
很好的解答
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-20 20:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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