工业界资深数据科学家现场教你修改求职简历
小K现场教你修改求职简历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 3823|回复: 15
收起左侧

Q代码挑战

[复制链接] |试试Instant~
我的人缘0
slaink 发表于 2016-10-13 03:48:49 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类General 博士 实习@Quora - 内推 - 在线笔试  | Fail | 其他

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

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

x
这家我死的心服口服。
. 牛人云集,一亩三分地
六十分钟一道题,给一堆二维的信封,每个信封有长和宽,如果一个信封的长比另一个的长而且宽也比另一个的宽,那么就能把小的放大的里面。也就是说只能长比长宽比宽,不能旋转,而且一个信封里面只能塞一个信封(甲装乙里,乙装丙里,但是不是甲和乙都放丙里。放完之后甲乙丙就从三个信封变成了一个信封)。把小信封放到大信封里,最后需要几个信封?

这题后来高人说是min path coverage,用最大流解。
.1point3acres网. more info on 1point3acres

补充内容 (2016-10-13 09:50):. 牛人云集,一亩三分地
我是写的LIS,每次取出来最长的那个LIS,然后剩下的继续做LIS直到所有信封都没了。复杂度N方。但是这样贪心应该是错的。

评分

参与人数 4大米 +49 收起 理由
动物园里的辛巴 + 3 感谢分享!
格格笑 + 5 来一波大米~
kradnangel + 1 感谢分享!
whdawn + 40

查看全部评分


上一篇:P实习代码挑战
下一篇:Course Hero新鲜面经
我的人缘0
格格笑 发表于 2016-11-7 14:51:02 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩
我想说的,第一,我们570算法课讲过这道题,是用dp做的,按照面积大小排序,但是最后是问最多能堆几个盒子,求最大高度.留学论坛-一亩-三分地
第二,楼主这里说的信封,我大概理解为是抽象了一下 这个box,  没有理解的是什么叫 求把小信封放到大信封里,最后需要几个信封?
  神马叫需要几个信封? 你不是都说了N个信封,如果全都装进去 那就是N个信封啊,还是说你想问的是 最多·能这样进行装入,能装几个信封为一体?
回复

使用道具 举报

我的人缘0
zt5840 发表于 2016-10-13 11:22:34 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  66% (2)
 
 
33% (1)  踩
问题描述
          给定有向图 G=(V,E)。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始,长度也是任意的,特别地,可以为0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。
. 1point 3acres 论坛
算法思想
        把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

有向无环图最小覆盖算法流程
        1.构建二分图,原图中的每个点V拆成Vx和Vy,如果有一条有向边A->B,那么就加边Ax-By。这样就得到了一个无向的二分图。
        2.求最大匹配数

确实是个经典的题,会就是会,不会就不会。
回复

使用道具 举报

我的人缘0
yhatl 发表于 2016-10-13 09:19:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
见LC354
. from: 1point3acres
字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数
回复

使用道具 举报

我的人缘0
 楼主| slaink 发表于 2016-10-13 09:25:42 | 显示全部楼层
yhatl 发表于 2016-10-13 09:19
见LC354

字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数 ...
来源一亩.三分地论坛.
并不是,那个简单。这个是要你按russian doll 放完之后剩下几堆那样的russian doll。
.本文原创自1point3acres论坛
补充内容 (2016-10-13 09:26):
我就是按LIS写的贪心,每次把最长的那个取出来。
回复

使用道具 举报

我的人缘0
yhatl 发表于 2016-10-13 09:31:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
嗯 不是原题。
是不是应该重复russian doll 一直到装完?
回复

使用道具 举报

我的人缘0
 楼主| slaink 发表于 2016-10-13 09:35:12 | 显示全部楼层
yhatl 发表于 2016-10-13 09:31
嗯 不是原题。
是不是应该重复russian doll 一直到装完?

不,我就是那么写的,应该是错的。你可以理解为一个有向图,A指向B如果B可以装下A。目标是找到最少需要多少没有重叠的线段(不重复使用边和点),能够把整个有向图cover。
回复

使用道具 举报

我的人缘0
suiyuan2009 发表于 2016-10-13 09:45:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
dp比最大流快吧
回复

使用道具 举报

我的人缘0
1peter 发表于 2016-10-25 12:58:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
我也是这道题,挂的没脾气
回复

使用道具 举报

我的人缘0
peteraristo 发表于 2016-10-27 03:48:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  14% (1)
 
 
85% (6)  踩
按匈牙利算法写了,还是挂。。。
感觉他家目前不想招人,据说以前都没有OA。
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-23 14:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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