一亩三分地论坛

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

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

Facebook Intern两轮电面面经

[复制链接] |试试Instant~ |关注本帖
鹰狼星 发表于 2015-4-15 13:57:51 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Facebook - Other - 技术电面 |Passfresh grad应届毕业生

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

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

x
有幸通过骚扰HR拿到了Intern的面试。在此写一发面经回馈一下地里:
第一轮电面:
1. 一个只有1、2和3的数组,要求排序。和Leetcode的sort color基本是一道题。基本做法是count sort,但是要多次pass,一次pass的做法是两个指针,做类似于3路快排的partition。. Waral 鍗氬鏈夋洿澶氭枃绔,
2. Given an array of non negative integers and a number N, finda length of shortest subarray sum of whose all elements is N.
一紧张只写了一个基于DP的O(n^2)做法,然后口述了一下改进做法,也就是维护一个window,下一个加进来如果大了就开始从window的开头开始去除元素直到和小于N,时间是O(n)

第二轮本来应该是Onsite的,但是因为另一个offer催得紧,就改成了电面:
题目是有n个房子(一排),m种颜色,有一个cost[i][j]的数组存着用第j种颜料刷第i个房子的价格。限制是相邻的房子不能用同一种颜色,问把每个房子都刷一遍的最少花费。
方法是用DP做,维护一个n*m的数组res,res[i][j]表示刷到第i个房子时,用第j种颜料的话的最低cost。因为对于每一种颜色,都要逐一查看上一个房子里除这个颜色外的所有颜色花费,选出最低,时间O(m^2*n),空间O(n*m)
Follow up自然是改进,使用O(m)的空间和O(nm)的时间。
提高空间很简单,可以注意到只需要上个房子的结果,因此可以只用一维数组。
提高时间的方法是这样的:
在计算n-1个房子的所有颜色cost时,就维护记录cost最小的前两种颜色。这样针对第n个房子的每个颜色,不用观察n-1的m-1个颜色,而是只要基于n-1时cost最小的那种颜色计算新的cost就行。如果是同一种颜色,就基于cost第二小的颜色。

最后顺利拿到OFFER,也算是圆了转系CS的心愿了。希望能帮到还在面试的小伙伴们。

评分

3

查看全部评分

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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