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

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 韩演员朴信惠做慈善 支持大邱传统市场灾后重建
  • 渔民捡到四四方方怪鱼:狠起来能把自己毒死
  • 中国高铁全靠引进?工程院院士愤怒驳斥
  • 120岁世界最长寿男人:至今仍是“童子身”
  • 想想都疼 男子用水果刀自割痔疮六七次 差点要命
  • 关之琳现身澳门影展 礼服似不合身胸部被挤变形
  • 小松鼠屁股太大被卡井盖孔 表情好无辜
  • 活久见!猪竟然成了机场工作人员
  • 日本出现新血型?吃瓜群众们脑洞大到飞起
  • 画风突变!哈尔滨的东北虎胖得不像样儿了
  • 美国股市道琼指数一路狂飙超过19000点,创下百年来记录-美国房产信息
  • Rusty Braziel预测石油价格下跌
  • 12月市场基调是如何转变的
  • Cramer Remix:特朗普管理下的股票风险
  • 历史新高后,交易商把目光转向欧洲
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3098|回复: 8

内推面经 -请教一道 G 家 DNA edit distance的题- 唐人社区|北美华人论坛

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

15

主题

31

帖子

78

积分

注册会员

Rank: 2

积分
78
QQ
发表于 2016-10-18 07:42:08 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-请教一道 G 家 DNA edit distance的题


  JobHunting
标 题: 请教一道 G 家 DNA edit distance的题


Assume the gene library exist for all 7 Billion people on earth. Each person
's gene sequence is 3 billion length of 4 basic construction unit. You are
given the genetic sequence of one person. Describe how you can find his
closest genetic sequence neighbor. The closeness is defined by the edit-
distance between the two sequences. Describe how you store data and conduct
search.

朋友Onsite面的, 完全没思路。谢谢
--

新浪微博官方账号】美国省钱快报FunInUSA : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

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

19

主题

82

帖子

119

积分

注册会员

Rank: 2

积分
119
QQ
发表于 2016-10-18 08:17:35 | 显示全部楼层
JobHunting
标  题: Re: 请教一道 G 家 DNA edit distance的题


suffix tree

check out  ukkonen's algorithm
--
TA在交友中心
0 0 52
  @ME:   

26

主题

101

帖子

150

积分

注册会员

Rank: 2

积分
150
QQ
发表于 2016-10-18 09:20:47 | 显示全部楼层
JobHunting
标  题: Re: 请教一道 G 家 DNA edit distance的题


8位? 你的整个DNA sequence是什么结构?

【 在 sza (sza) 的大作中提到: 】
: 编码,AGTC分别用00,01,10,11表示,可以编码成一个8位的int



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

10

主题

220

帖子

256

积分

中级会员

Rank: 3Rank: 3

积分
256
QQ
发表于 2016-10-18 09:31:34 | 显示全部楼层
JobHunting
标  题: Re: 请教一道 G 家 DNA edit distance的题


编码,AGTC分别用00,01,10,11表示,可以编码成一个8位的int

【 在 stratton (搬家) 的大作中提到: 】
: 基本方法应该就是Edit Distance的定义用Dynamic Programming来做。面试的本意大概
: 就是考这个点吧。
: 不过字符集这么小,字符串这么长,应该有能优化的地方。



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

26

主题

104

帖子

153

积分

注册会员

Rank: 2

积分
153
QQ
发表于 2016-10-18 09:36:09 | 显示全部楼层
JobHunting
标  题: 请教一道 G 家 DNA edit distance的题


Assume the gene library exist for all 7 Billion people on earth. Each person
's gene sequence is 3 billion length of 4 basic construction unit. You are
given the genetic sequence of one person. Describe how you can find his
closest genetic sequence neighbor. The closeness is defined by the edit-
distance between the two sequences. Describe how you store data and conduct
search.

朋友Onsite面的, 完全没思路。谢谢
--
TA在交友中心
0 0 47
  @ME:   

21

主题

96

帖子

143

积分

注册会员

Rank: 2

积分
143
QQ
发表于 2016-10-18 09:57:29 | 显示全部楼层
JobHunting
标  题: Re: 请教一道 G 家 DNA edit distance的题


Edit Distance可增可删。

【 在 njuhuangmy (茶) 的大作中提到: 】
: suffix tree
: check out  ukkonen's algorithm



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

1

主题

225

帖子

187

积分

注册会员

Rank: 2

积分
187
QQ
发表于 2016-10-18 11:18:48 | 显示全部楼层
JobHunting
标  题: Re: 请教一道 G 家 DNA edit distance的题


这是算法题还是system design题?
[在  xm1223 (天天想上) 的大作中提到:]
:Assume the gene library exist for all 7 Billion people on earth. Each
person's gene sequence is 3 billion length of 4 basic construction unit.
You are
:given the genetic sequence of one person. Describe how you can find his
:closest genetic sequence neighbor. The closeness is defined by the edit-
:distance between the two sequences. Describe how you store data and conduct
search.
:朋友Onsite面的, 完全没思路。谢谢
--
TA在交友中心
0 0 54
  @ME:   

23

主题

91

帖子

145

积分

注册会员

Rank: 2

积分
145
QQ
发表于 2016-10-18 12:24:32 | 显示全部楼层
JobHunting
标  题: Re: 请教一道 G 家 DNA edit distance的题


基本方法应该就是Edit Distance的定义用Dynamic Programming来做。面试的本意大概
就是考这个点吧。
不过字符集这么小,字符串这么长,应该有能优化的地方。
--
TA在交友中心
0 0 1033
  @ME:   

19

主题

1069

帖子

2102

积分

金牌会员

Rank: 6Rank: 6

积分
2102
QQ
发表于 2016-10-28 14:04:14 | 显示全部楼层
good!!!!!!!!!!!!!!!
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -请教一道 G 家 DNA edit distance的题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -请教一道 G 家 DNA edit distance的题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

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

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

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

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