非PHD在大公司做机器学习

一亩三分地论坛

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

最近看过此主题的会员

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

Q代码挑战

[复制链接] |试试Instant~ |关注本帖
我的人缘0
slaink 发表于 2016-10-13 03:48:49 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (106)
 
 
8% (10)  踩

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

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

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

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

这题后来高人说是min path coverage,用最大流解。


补充内容 (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)   【踩】
全局: 顶  88% (40)
 
 
11% (5)  踩
我想说的,第一,我们570算法课讲过这道题,是用dp做的,按照面积大小排序,但是最后是问最多能堆几个盒子,求最大高度
第二,楼主这里说的信封,我大概理解为是抽象了一下 这个box,  没有理解的是什么叫 求把小信封放到大信封里,最后需要几个信封?
  神马叫需要几个信封? 你不是都说了N个信封,如果全都装进去 那就是N个信封啊,还是说你想问的是 最多·能这样进行装入,能装几个信封为一体?
回复

使用道具 举报

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

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

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

使用道具 举报

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

字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数
回复

使用道具 举报

我的人缘0
 楼主| slaink 发表于 2016-10-13 09:25:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (106)
 
 
8% (10)  踩
yhatl 发表于 2016-10-13 09:19
见LC354

字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数 ...

并不是,那个简单。这个是要你按russian doll 放完之后剩下几堆那样的russian doll。

补充内容 (2016-10-13 09:26):
我就是按LIS写的贪心,每次把最长的那个取出来。

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
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 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (106)
 
 
8% (10)  踩
yhatl 发表于 2016-10-13 09:31
嗯 不是原题。
是不是应该重复russian doll 一直到装完?

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

使用道具 举报

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

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘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)   【踩】
全局: 顶  20% (1)
 
 
80% (4)  踩
按匈牙利算法写了,还是挂。。。
感觉他家目前不想招人,据说以前都没有OA。
回复

使用道具 举报

我的人缘0
格格笑 发表于 2016-11-7 15:30:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (40)
 
 
11% (5)  踩
哦 你想问的是 最后最少能装到只剩下几个一体的信封~

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

回复

使用道具 举报

我的人缘0
peteraristo 发表于 2016-11-8 03:13:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  20% (1)
 
 
80% (4)  踩
格格笑 发表于 2016-11-7 15:30
哦 你想问的是 最后最少能装到只剩下几个一体的信封~

所以你理解DP不对了吧。
不过也可能出题人就是想考DP呢。
回复

使用道具 举报

我的人缘0
格格笑 发表于 2016-11-8 04:08:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (40)
 
 
11% (5)  踩
嗯,但我仍然不知道最大流怎么做 ,待会发一个我用最大流做出的不对的解法~还有一个重要的事,楼主有oa截图啥的吗
回复

使用道具 举报

我的人缘0
格格笑 发表于 2016-11-8 05:34:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (40)
 
 
11% (5)  踩
你看楼主, 如果有三个 信封 分别是 [1,3] [2, 3] [2,2] 最后算出来应该是2对吧  你说的最大流怎么做?  哦  突然想明白了  你说的那个箭头的方向有点问题哈,应该是 A 能装 下B 就用A 指向B   A是大的 B是小的  这样才能解~,  不然  [1,3] [2, 3] [2,2]  这个例子你会算出来是1   而其实应该是2~
回复

使用道具 举报

我的人缘0
jerry1394 发表于 2016-12-7 10:18:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (12)
 
 
7% (1)  踩
按长sort,然后算宽的最长递增子列。
回复

使用道具 举报

我的人缘0
garycheck 发表于 2016-12-29 08:37:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (81)
 
 
4% (4)  踩
求问怎么用匈牙利算法写
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-8-22 10:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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