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

 找回密码
 立即注册
  • 李英爱新剧《师任堂》接档《蓝海传说》 26日首播
  • 48岁许晴与友人庆生 素颜出镜似18岁少女
  • 林允牙齿大变样 网友惊呼认不出
  • 姚晨三亚度假摘芒果 偶遇儿时同学趣事多
  • 赵丽颖有新恋情?邓超一不小心提到了她男朋友
  • 林心如谈“幸福”的定义:每天都在笑
  • 外媒称中国正在研发百亿亿次超级计算机
  • 邓超狂晒打篮球帅照 孙俪冷回10字笑翻众人
  • 48亿:北京打造全球最亮“慧眼”
  • 中国基建狂魔:11072米世界第一航道桥合龙
  • 中国建立了146亿美元的互联网投资基金
  • 历届美国总统经历的市场
  • 市场:特朗普就任的第一周
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3027|回复: 22

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

[复制链接]

14

主题

227

帖子

261

积分

中级会员

Rank: 3Rank: 3

积分
261
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。想了好久不知道答案。



--

回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

26

主题

103

帖子

159

积分

注册会员

Rank: 2

积分
159
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



--

24

主题

90

帖子

143

积分

注册会员

Rank: 2

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


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

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



--

19

主题

95

帖子

127

积分

注册会员

Rank: 2

积分
127
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

主题

254

帖子

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。



--

21

主题

96

帖子

139

积分

注册会员

Rank: 2

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


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

--

30

主题

104

帖子

167

积分

注册会员

Rank: 2

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


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

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



--

5

主题

232

帖子

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.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

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

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

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