一亩三分地论坛

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

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

前几天的facebook电面

[复制链接] |试试Instant~ |关注本帖
sauceforge 发表于 2016-10-7 02:46:24 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 博士 全职@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

前几天的电面,一来先说了他做什么,然后自己简要的介绍了下research和project, 可能一共5分钟得样子,然后开始做题

股票1和股票2,当时瞬间觉得人品碉堡了,太简单了吧,然后从最简单的方法写,然后慢慢优化,介绍写完30分钟得样子。. From 1point 3acres bbs

以为最后就是聊天了,结果他又出了个题,还是股票,但是没做过:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
可以随便交易很多次,可以同时买很多股票,但是一旦卖就要把手里的股票全部卖了,问怎样最大化收益。比如[1, 2,3], 前2天都买,第三天全部卖,收益就是(3-1)+(3-2).

拿到题有点紧张,毕竟只有10分钟左右了,然后想了5分钟,提了个算法,然后马上写,提前5分钟写完,让优化,又想了2分钟提了个优化,最后说代码就不用改了,聊天2分钟。

最后10分钟太紧张了,有点吓尿的感觉,感觉要挂了。
. 鍥磋鎴戜滑@1point 3 acres
一天后收到Onsite通知。

评分

2

查看全部评分

waikai 发表于 2016-10-8 03:25:32 | 显示全部楼层
iPhD 发表于 2016-10-8 01:54
楼主方便把follow up的代码贴下不?感觉代码不是很好写呀。。。祝onsite好运!
  1. //input : int[] stock;
  2.                 int max = 0;
  3.                 int rst = 0;
  4.                 for (int i = stock.length; i >= 0; i--) {
  5.                         if (max > stock[i]) {
  6.                                 rst += max - stock[i];
  7.                                 // i 天买入 max卖出
  8.                         }else {
  9.                                 max = stock[i];.1point3acres缃
  10.                                 //再i天卖出全部股票
  11.                         }
  12.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.                 return rst;
复制代码
回复 支持 3 反对 0

使用道具 举报

喜马拉雅疯子 发表于 2016-10-7 23:25:21 | 显示全部楼层
大神求稳最后一个股票的题是什么思路。是从右往左维护一个最大值的变量这样吗?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-7 23:34:25 | 显示全部楼层
楼主是因为博士,所以他才问你research和project吗?FB面博士和硕士是不是要求不同?
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-10-8 01:16:03 | 显示全部楼层
喜马拉雅疯子 发表于 2016-10-7 23:25
大神求稳最后一个股票的题是什么思路。是从右往左维护一个最大值的变量这样吗?

基本思路是不停的找最大值,找到最大值就卖,然后再从最大值后面开始处理,最后能优化成O(N)
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-10-8 01:17:09 | 显示全部楼层
iPhD 发表于 2016-10-7 23:34
楼主是因为博士,所以他才问你research和project吗?FB面博士和硕士是不是要求不同?

具体我也不清楚,但是问我简历也就是让我简单介绍下而已。收到Onsite说2轮coding, 1轮system design, 1轮讲自己的research
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-8 01:39:12 | 显示全部楼层
sauceforge 发表于 2016-10-8 01:16
基本思路是不停的找最大值,找到最大值就卖,然后再从最大值后面开始处理,最后能优化成O(N)

感谢楼主分享! 请问如何能优化到On呢~
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-8 01:54:48 | 显示全部楼层
sauceforge 发表于 2016-10-8 01:16-google 1point3acres
基本思路是不停的找最大值,找到最大值就卖,然后再从最大值后面开始处理,最后能优化成O(N)

楼主方便把follow up的代码贴下不?感觉代码不是很好写呀。。。祝onsite好运!
回复 支持 反对

使用道具 举报

XavierWangXY 发表于 2016-10-8 03:16:15 | 显示全部楼层
找到最大值,最大值之前的都买,在最大值时候卖。然后对最大值后边的做递归
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-8 03:21:58 | 显示全部楼层
XavierWangXY 发表于 2016-10-8 03:16
找到最大值,最大值之前的都买,在最大值时候卖。然后对最大值后边的做递归

这样做的复杂度最差可能是n^2诶~ 不知道大家on的解法怎么写0.0
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-10-8 07:13:38 | 显示全部楼层
优化1: 把从右到左的max全部存起到a数组里,a[i]表示 i ~ n-1 的最大值。. 1point3acres.com/bbs
优化2: 预处理数组sum, sum[i]表示 0~i之和。
通过这两个优化,每次查询都是O(1) 所以总共是O(n)
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-8 14:27:17 | 显示全部楼层
. visit 1point3acres.com for more.
int i = stock.length()-1. visit 1point3acres.com for more.

这个解法真棒啊!

补充内容 (2016-10-8 14:38): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想了想,其实就是在所有的peek element处卖掉,
比如{9, 20, 8, 10, 15, 11}, 20和15是peek element, max_profit=(15-10)+(15-8)+(20-9),不过面试的时候能想出这个不容易啊。
回复 支持 反对

使用道具 举报

jinyyy666 发表于 2016-11-4 10:42:38 | 显示全部楼层
感谢楼主分享! 祝楼主onsite好运!
回复 支持 反对

使用道具 举报

yjob2016 发表于 2016-11-6 08:13:09 | 显示全部楼层
想吐槽一下“ 毕竟只有10分钟左右了,然后想了5分钟,提了个算法,然后马上写,提前5分钟写完”。。

意思就是想了5分钟+0分钟写完吗2333
回复 支持 反对

使用道具 举报

kevindx1120 发表于 2016-11-8 04:56:28 | 显示全部楼层
minggr 发表于 2016-10-8 14:27 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
int i = stock.length()-1

这个解法真棒啊!

一次要同时卖掉.你这是在两处卖掉?
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-11-8 08:55:01 | 显示全部楼层
楼主team match怎么样?可以分享一下经历吗?谢谢啦
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-11-8 12:16:40 | 显示全部楼层
knight0clk 发表于 2016-11-8 08:55
楼主team match怎么样?可以分享一下经历吗?谢谢啦

还没onsite呢,就过几天
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-11-8 20:37:30 | 显示全部楼层
sauceforge 发表于 2016-11-8 12:16
还没onsite呢,就过几天

那祝楼主好运啊!后面可以交流下team match。一直有个问题?感觉一般phd实习的话都是电面,而你却是Onsite,难道是Facebook直接把candidate分为369等,楼主水平特别高,然后直接给了onsite吗?
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-11-10 02:43:03 | 显示全部楼层
knight0clk 发表于 2016-11-8 20:37
那祝楼主好运啊!后面可以交流下team match。一直有个问题?感觉一般phd实习的话都是电面,而你却是Onsit ...

我是找fulltime不是实习呢
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-11-10 09:33:29 | 显示全部楼层
sauceforge 发表于 2016-11-10 02:43
我是找fulltime不是实习呢

哦哦,sorry,我搞错了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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