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

 找回密码
 立即注册
  • 男生“换心”后秒变学霸!这才是真相
  • 18万元!日本无印良品推9平单间小屋:海边山脚都能建
  • 大疆发飙!举报干扰成都机场无人机奖100万
  • 把猫头鹰羽毛一撩 网友惊呼:竟是大长腿
  • 夸张!科学家揭开人类大秘密:《魔戒》小矮人成真
  • 捡回一条命!男子深海垂钓巨大鲨鱼上钩:结果意外
  • 胖子有救!利用大脑电磁刺激技术进行减肥:效果不错
  • 男子和机器人手臂玩刀戳手指缝:这结果没想到
  • 催眠是真的吗?其实 你被骗很多年了!
  • 担任戛纳主竞赛评委 范冰冰:深感荣幸 很有压力
  • 特朗普的狂想——不切实际的公司税计划
  • AMD:增长和损失同在,有改变才会有进步
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
  • Tom Lee警示下行风险,揭示市场三大“地雷”
  • 在Buffalo Wild Wings季度财报中出现了“天文误差”
  • 巴菲特该高兴了,IBM加息至每股1.5美元
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3040|回复: 22

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

[复制链接]

15

主题

232

帖子

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



--

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

举报

27

主题

109

帖子

167

积分

注册会员

Rank: 2

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



--

27

主题

97

帖子

156

积分

注册会员

Rank: 2

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


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

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



--

21

主题

102

帖子

141

积分

注册会员

Rank: 2

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

主题

84

帖子

121

积分

注册会员

Rank: 2

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


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

8

主题

262

帖子

276

积分

中级会员

Rank: 3Rank: 3

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


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

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

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



--

25

主题

117

帖子

173

积分

注册会员

Rank: 2

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


what???  are you kidding me?


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



--

23

主题

102

帖子

152

积分

注册会员

Rank: 2

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


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

--

30

主题

111

帖子

167

积分

注册会员

Rank: 2

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


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

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



--

5

主题

237

帖子

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|唐人社区

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

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