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

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 熊黛林晒自拍秀性感 被指故意拉低衣服
  • 葛优诉某网站擅用“葛优躺” 索赔40万元
  • 林丹“出轨门”后首发声 感谢粉丝:我会努力
  • 李东旭金高银领衔《鬼怪》开播 情节爆表演技高
  • 唐嫣罗晋公布恋情后,胡歌彭于晏成“国民单身狗”?
  • 环球风尚盛典圆满落幕 杨澜、陆川等被授予风尚领秀
  • 张伦硕赞钟丽缇皮肤超好身材超棒 自曝要一年内造人
  • 姚明女儿才6岁 身高就超过了妈妈的腰
  • 澳洲男子跳进河里救考拉 那画面太喜感
  • 口水直流!在大学寝室做饭还能这么玩
  • 明年第一季度美国地产可能成为交易高峰期-美国房产信息
  • 美元资产是海外置业的优秀配置,未来升值空间可观-美国房产信息
  • 经济学家:希腊可能从欧洲的政治动荡获利
  • 克莱姆对新股票市场的态度:升息或死亡
  • 市场反弹继续,但注意漏洞
  • 摩根大通首席执行官说可能发布特别股息
  • 策略师斯托瓦尔:11月的强势不会偷走12月的收益
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3014|回复: 22

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

[复制链接]
TA在交友中心
0 0 37
  @ME:   

14

主题

225

帖子

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



--
【中国海淘拼单总群】36382164
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 50
  @ME:   

23

主题

95

帖子

139

积分

注册会员

Rank: 2

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



--
TA在交友中心
0 0 53
  @ME:   

23

主题

87

帖子

134

积分

注册会员

Rank: 2

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


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

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



--
TA在交友中心
0 0 37
  @ME:   

19

主题

94

帖子

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



--


TA在交友中心
0 0 38
  @ME:   

14

主题

78

帖子

114

积分

注册会员

Rank: 2

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


B里选与A的sum最接近的n个数
--
TA在交友中心
0 0 17
  @ME:   

7

主题

252

帖子

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中的相同长度的子列,算出长度来和每个配对元素的长度。
: 下一步,添一个元素,只需要循环一次,就可以算出最佳长度和最佳配对,以此递归。



--
TA在交友中心
0 0 54
  @ME:   

23

主题

106

帖子

158

积分

注册会员

Rank: 2

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


what???  are you kidding me?


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



--

TA在交友中心
0 0 47
  @ME:   

21

主题

94

帖子

139

积分

注册会员

Rank: 2

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


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

--
TA在交友中心
0 0 66
  @ME:   

30

主题

103

帖子

167

积分

注册会员

Rank: 2

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


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

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



--
TA在交友中心
0 0 10
  @ME:   

5

主题

225

帖子

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 华人娱乐论坛发布的内推面经 -一个面试问题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -一个面试问题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

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

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

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

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