美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 否认完南京大屠杀又抨击犹太人 APA这是要撕全世界?
  • 中国发起“厕所革命”:各国管理洗手间方式大不同
  • 宋小宝龙凤胎曝光!颜值竟然这么高
  • 于正谈"袁姗姗滚出娱圈":自己经历过的一件大事
  • 上海戏剧学院艺考进入三试阶段 林妙可初试就落榜
  • 有点乱 张俪男友朱镇模自曝曾被章子怡暗恋
  • 美媒:美海关严查持F1签证者 多名中国留学生被遣返
  • 日媒:特朗普在贸易层面上点名批评中日 有何目的?
  • 美媒:特朗普欲将工厂搬回美 是否影响中方战略?
  • 揭秘中国生物安全实验室:研究世上最危险病原体
  • 道琼斯、标准普尔、Nasdaq和罗素创纪录新高,上涨超过10%
  • AMD股票预期将回升
  • 推动美国股市走高的动力与阻力
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3033|回复: 22

内推面经 -一个面试问题- 唐人社区|北美华人论坛

[复制链接]

15

主题

229

帖子

268

积分

中级会员

Rank: 3Rank: 3

积分
268
QQ
发表于 2016-10-4 20:10:27 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-一个面试问题


  JobHunting
标 题: 一个面试问题


有两个整数sequence a 和 b,len(a)=n,len(b)=m,m>=n,从b中取一个subsequence
b'长度和a一样。注意subsequence b'可以跳过元素,但不能改变b中元素的顺序。

定义a和b'的距离为 dist(a,b') =sum(|a_i - b'_i|)。现在求如何找到subsequence b
'使这个距离最小

面试官说这个题能找到exact solution。想了好久不知道答案。



--
【COACH美国代购总群】99634155
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

27

主题

106

帖子

164

积分

注册会员

Rank: 2

积分
164
QQ
发表于 2016-10-4 20:43:02 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


删除元素之前只要是两个序列长度不相等,距离就是无定义的。并不存在你说的D。


【 在 magician (爱情魔法师) 的大作中提到: 】
: the answer is exact editdistance(a,b)-m+n;
: in order to convert b to a, you need to at least delete m-n items.
: originally the distance from b to a is D,
: now you just got m-n deletion operations for free.
: so the answer is D-(m-n)
: O(m*n)
: in order to find the subsequence. just start from table[m-1][n-1] and
: backtrace to the optimal answer.
: subsequence
:  b



--

25

主题

93

帖子

148

积分

注册会员

Rank: 2

积分
148
QQ
发表于 2016-10-4 20:53:14 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


这个不work吧,怎么解决b'中数的顺序必须和a一样

【 在 noregrets (风满袖) 的大作中提到: 】
: B里选与A的sum最接近的n个数



--

20

主题

96

帖子

135

积分

注册会员

Rank: 2

积分
135
QQ
发表于 2016-10-4 21:09:53 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


the answer is exact editdistance(a,b)-m+n;

in order to convert b to a, you need to at least delete m-n items.
originally the distance from b to a is D,
now you just got m-n deletion operations for free.
so the answer is D-(m-n)

O(m*n)

in order to find the subsequence. just start from table[m-1][n-1] and
backtrace to the optimal answer.


【 在 Iverson3 (答案) 的大作中提到: 】
: 有两个整数sequence a 和 b,len(a)=n,len(b)=m,m>=n,从b中取一个
subsequence
: b'长度和a一样。注意subsequence b'可以跳过元素,但不能改变b中元素的顺序。
: 定义a和b'的距离为 dist(a,b') =sum(|a_i - b'_i|)。现在求如何找到subsequence
b
: '使这个距离最小
: 面试官说这个题能找到exact solution。想了好久不知道答案。



--


15

主题

81

帖子

121

积分

注册会员

Rank: 2

积分
121
QQ
发表于 2016-10-4 21:27:25 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


B里选与A的sum最接近的n个数
--

7

主题

258

帖子

266

积分

中级会员

Rank: 3Rank: 3

积分
266
QQ
发表于 2016-10-4 21:40:55 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


我感觉递归也不行,因为子问题的最优解不一定是全局问题的最优解

举个栗子,a是2 3 100,b是3 3 100 2 3 2

【 在 Rabboni (腹黑小白兔) 的大作中提到: 】
: 一般是用递归吧,不知道复杂度如何。
: 开始,给定序列a,取序列b中的相同长度的子列,算出长度来和每个配对元素的长度。
: 下一步,添一个元素,只需要循环一次,就可以算出最佳长度和最佳配对,以此递归。



--

24

主题

110

帖子

166

积分

注册会员

Rank: 2

积分
166
QQ
发表于 2016-10-4 21:45:56 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


what???  are you kidding me?


【 在 sza (sza) 的大作中提到: 】
: 删除元素之前只要是两个序列长度不相等,距离就是无定义的。并不存在你说的D。



--

22

主题

99

帖子

146

积分

注册会员

Rank: 2

积分
146
QQ
发表于 2016-10-4 21:49:29 | 显示全部楼层
JobHunting
标  题: 一个面试问题


一般是用递归吧,不知道复杂度如何。
开始,给定序列a,取序列b中的相同长度的子列,算出长度来和每个配对元素的长度。
下一步,添一个元素,只需要循环一次,就可以算出最佳长度和最佳配对,以此递归。

--

30

主题

106

帖子

167

积分

注册会员

Rank: 2

积分
167
QQ
发表于 2016-10-4 21:52:55 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


先想a的长度是2的情况如何枚举,再考虑推广到n

【 在 Iverson3 (答案) 的大作中提到: 】
: 怎么枚举?



--

5

主题

234

帖子

223

积分

中级会员

Rank: 3Rank: 3

积分
223
QQ
发表于 2016-10-4 22:15:53 | 显示全部楼层
JobHunting
标  题: Re: 一个面试问题


你这里的B还算是sequence 吗?随机序列的话,这不是实现草泥马吗?C(m,n),hehe
【 在 Iverson3 (答案) 的大作中提到: 】
: 我感觉递归也不行,因为子问题的最优解不一定是全局问题的最优解
: 举个栗子,a是2 3 100,b是3 3 100 2 3 2



--
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -一个面试问题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -一个面试问题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

安全联盟认证 安全联盟认证

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