Product Design + Engineering 相關MS@Harvard,MIT,CMU,Stanford

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 11104|回复: 34
收起左侧

脸书onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
yzlwjs 发表于 2016-10-22 14:42:39 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩

2016(10-12月) 码农类General 硕士 全职@Facebook - 内推 - Onsite  | Pass | fresh grad应届毕业生

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

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

x
  • 利扣91,做完dp解之后,又被问了不用dp怎么做(不限算法时间复杂度)
  • 给n个d维的vector和一个first selected的vector, 选出k个vector,每次选择下一个时要求:选离所有selected vector最远的vector, 计算距离的函数已给出D(v1,v2)并假设调用此函数时间复杂度为O(1), 某vector与所有selected vectors的距离定义为这个vector与其nearest selected neighbor的距离。在面试官的提示下最终找到了复杂度为O(nk)的最优解,对每个unselected的vector存下其与selected vectosr的距离,每次遍历unselected vectors找出距离最远的vector为下一个selected vector, 用这个vector与每个unselected vector的距离去更新距离(若小于原距离,表示nearest selected neighbor更换了)
  • 给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行时间为5(B_ _ _ B, _ 表示wait). 写一个函数输入task序列和interval, 输出总的运行时间。 follow up是给一个序列和interval,task的执行顺序可以打乱,输出optimal(总执行时间最短)的执行顺序
  • 最近在做什么以及细问了简历。
    游客,本帖隐藏的内容需要积分高于 166 才可浏览,您当前积分为 0。
    查看如何攒积分 Click here for more info.


评分

参与人数 2大米 +205 收起 理由
admin + 200
leixiang5 + 5 欢迎来一亩三分地论坛!

查看全部评分


上一篇:Interactive brokers Java OA 90min版
下一篇:LiveRamp Intern OA

本帖被以下淘专辑推荐:

我的人缘0
mengmeng88717 发表于 2016-10-28 10:01:01 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
第四题的思路
res = sum(dp[i][k])
dp[i][j] = sum { dp[m][j - 1] | if canReach[i][m]}. 1point 3acres 论坛
canReach : boolean[10][10]
canReach[1][6], canReach[1][8], [2][7], [2][9], [3][4], [3][8], [4][3], [4][9], [4][0], [6][1], [6][7], [6][0], [7][2], [7][6], [8][1], [8][3], [9][2], [9][4] = true.本文原创自1point3acres论坛
init : dp[1][0] = 1;
一维dp就可以,时间应该是O(steps), 空间O(steps + 100)
回复

使用道具 举报

我的人缘0
leixiang5 发表于 2016-10-22 14:54:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (196)
 
 
17% (41)  踩
楼主啥时候面的啊??...比我的难好多- -
回复

使用道具 举报

我的人缘0
samuelling 发表于 2016-10-22 15:16:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (42)
 
 
6% (3)  踩
leixiang5 发表于 2016-10-21 22:54
楼主啥时候面的啊??...比我的难好多- -

群主这么晚还不就寝啊
回复

使用道具 举报

我的人缘0
hrl1991 发表于 2016-10-22 15:51:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (69)
 
 
2% (2)  踩
第三轮task schedule第一问你的space complexity是多少? 我用的hashmap的方法做space compexity是O(n) interviewer说有更optimal的 但是我没想出来 时间也不多了

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
leixiang5 发表于 2016-10-22 21:06:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (196)
 
 
17% (41)  踩
samuelling 发表于 2016-10-22 15:16
群主这么晚还不就寝啊
. Waral 博客有更多文章,
在加州 有时差的
回复

使用道具 举报

我的人缘0
steveguang 发表于 2016-10-22 22:54:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (87)
 
 
4% (4)  踩
楼主可以讲下第一题第四题怎么做的吗?
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-23 05:57:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
求问楼主第一题不用dp能咋做??backtrack?
回复

使用道具 举报

我的人缘0
 楼主| yzlwjs 发表于 2016-10-24 01:24:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
chestnut9919 发表于 2016-10-23 05:57
求问楼主第一题不用dp能咋做??backtrack?
. visit 1point3acres for more.
嗯对,字数字数
回复

使用道具 举报

我的人缘0
 楼主| yzlwjs 发表于 2016-10-24 01:24:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
leixiang5 发表于 2016-10-22 14:54
楼主啥时候面的啊??...比我的难好多- -
. Waral 博客有更多文章,
本月初,字数字数

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| yzlwjs 发表于 2016-10-24 01:30:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
steveguang 发表于 2016-10-22 22:54
楼主可以讲下第一题第四题怎么做的吗?

第一题就是利扣原题呀,不用dp的话,我说的是backtracking/DFS的做法,感觉这个follow up纯粹是小哥没准备别的题了硬加上的
第四题我的暴力解就挺直接的,用dp的话我后来想了想,可以记录到每个位置的走法数(初始状态只有数字1有1种),然后每走一步,根据前一步的位置更新下一步位置的走法数,步数走完以后,把所有位置的走法数加起来就可以了
回复

使用道具 举报

我的人缘0
steveguang 发表于 2016-10-24 04:06:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (87)
 
 
4% (4)  踩
yzlwjs 发表于 2016-10-24 01:30
第一题就是利扣原题呀,不用dp的话,我说的是backtracking/DFS的做法,感觉这个follow up纯粹是小哥没准 ...

楼主走日字是什么意思?矩形对角线吗?有什么限制没有
回复

使用道具 举报

我的人缘0
 楼主| yzlwjs 发表于 2016-10-24 10:57:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
steveguang 发表于 2016-10-24 04:06.留学论坛-一亩-三分地
楼主走日字是什么意思?矩形对角线吗?有什么限制没有

就是中国象棋里面的马走日,横2步纵1步,或者横1步纵2步
回复

使用道具 举报

我的人缘0
liyuanxi23 发表于 2016-10-24 13:05:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
居然看出来群主了
回复

使用道具 举报

我的人缘0
dowhatyoufear 发表于 2016-10-25 00:42:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (2)
 
 
33% (1)  踩
这个多少种可能走法,比如1开始走两步,最后1-6-1,1-6-7,1-8-1,1-8-3 应该是有1,7,3三个Positions. 结果是3吗?如果不是那就有问题了,那就应该是2^steps种不同路径了(即使最后到一样的点)   链接: https://instant.1point3acres.com/thread/195066 来源: 一亩三分地 (Instant 真垃圾!)
回复

使用道具 举报

我的人缘0
ericlee27 发表于 2016-10-25 03:37:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (191)
 
 
2% (4)  踩
dowhatyoufear 发表于 2016-10-25 00:42
这个多少种可能走法,比如1开始走两步,最后1-6-1,1-6-7,1-8-1,1-8-3 应该是有1,7,3三个Positions. 结 ...

我也是这么觉得的。。。
回复

使用道具 举报

我的人缘0
 楼主| yzlwjs 发表于 2016-10-25 12:22:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
dowhatyoufear 发表于 2016-10-25 00:42
这个多少种可能走法,比如1开始走两步,最后1-6-1,1-6-7,1-8-1,1-8-3 应该是有1,7,3三个Positions. 结 ...

是后者,看有多少种不同路径(即使最后到一样的点)。 另外应该是有O(m^steps)种不同路径,有些点出发到下一步的走法不一定是2种, 比如4->(3, 9, 0)
回复

使用道具 举报

我的人缘0
dowhatyoufear 发表于 2016-10-25 12:47:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (2)
 
 
33% (1)  踩
yzlwjs 发表于 2016-10-25 12:22
是后者,看有多少种不同路径(即使最后到一样的点)。 另外应该是有O(m^steps)种不同路径,有些点出发 ...

谢谢楼主~BFS或者DFS没觉得有什么不好的。恭喜楼主拿到Offer。
回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-25 12:57:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
想请教一下楼主第三问的followup怎么做的?能写一段代码看看吗,十分感谢
回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-25 13:18:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
试写了一下code,先统计了frequency of tasks然后用maxHeap做的,楼主能帮忙看看是这样么,感觉还有可以优化的地方,谢谢~
public static String taskSchedule(String str, int k) {. 一亩-三分-地,独家发布
        StringBuilder rearranged = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();. visit 1point3acres for more.
        for (char c : str.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }
. 1point3acres
        Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> entry1, Map.Entry<Character, Integer> entry2) {
                return entry2.getValue() - entry1.getValue();.1point3acres网
            }. 留学申请论坛-一亩三分地
        });. 围观我们@1point 3 acres
        maxHeap.addAll(map.entrySet());

        while (!maxHeap.isEmpty()) {. 一亩-三分-地,独家发布
            int i = 0;
            ArrayList<Map.Entry<Character, Integer>> temp = new ArrayList<>();
            while (i <= k && !maxHeap.isEmpty()) {
                Map.Entry<Character, Integer> curr = maxHeap.poll();.本文原创自1point3acres论坛
                rearranged.append(curr.getKey());. From 1point 3acres bbs
                curr.setValue(curr.getValue() - 1);
                temp.add(curr);
                i++;
            }. 一亩-三分-地,独家发布
            for (Map.Entry<Character, Integer> e : temp) {
                if (e.getValue() > 0) {
                    maxHeap.offer(e);
                }
            }
. 一亩-三分-地,独家发布        }
        return rearranged.toString();
    }
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-20 06:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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