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

 找回密码
 立即注册
  • 科学家发现寒武纪最大掠食者:竟是龙虾祖先
  • 中国研发出超级隔热材料:两面温差1500度!
  • 张杰谢娜前后脚为何炅庆生 顺便秀了个恩爱
  • 黄子韬工作室回应韩国一审败诉:不公平我们不接受
  • 《奔跑吧》热巴贴面耳语玩心跳 鹿晗心跳飙升160
  • 谢霆锋晒泳照文身才是亮点 那是对王菲爱的印记
  • 摄影师纪念拍摄baby孕照 侧面辟谣"代孕说"
  • 这些动物太神奇了:被吃掉也毫发无损
  • 菲律宾突发7.0级大地震:小心海啸
  • 男子伸个懒腰 居然高位瘫痪了……
  • 专家认为 美国房产前景乐观-美国房产信息
  • 专家认为 现在美国房产适合投资-美国房产信息
  • 中美房价比较 对比投资环境-美国投资指南
  • 《牛津剑桥暑期课程》海外游学宝典-美国留学指南
  • 留学专家解析大学排名-美国留学指南
  • 怀俄明州 美国留学最便宜目的地-美国留学指南
  • 摩根大通表示:美经济第一季度显疲态
  • 降不降税?美零售股“草木皆兵”
  • 海外资金遣返,仅有利于少数公司
  • 五月份卖出股票?有道理,但夏季也是有利可图的
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3122|回复: 8

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

[复制链接]

19

主题

38

帖子

94

积分

注册会员

Rank: 2

积分
94
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 : 每日微信滚动更新美国市场打折团购折扣Coupon讯息。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

22

主题

95

帖子

138

积分

注册会员

Rank: 2

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


suffix tree

check out  ukkonen's algorithm
--

29

主题

111

帖子

167

积分

注册会员

Rank: 2

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



--

11

主题

230

帖子

268

积分

中级会员

Rank: 3Rank: 3

积分
268
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来做。面试的本意大概
: 就是考这个点吧。
: 不过字符集这么小,字符串这么长,应该有能优化的地方。



--

29

主题

111

帖子

173

积分

注册会员

Rank: 2

积分
173
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面的, 完全没思路。谢谢
--

22

主题

105

帖子

151

积分

注册会员

Rank: 2

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


Edit Distance可增可删。

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



--

1

主题

240

帖子

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面的, 完全没思路。谢谢
--

24

主题

96

帖子

154

积分

注册会员

Rank: 2

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


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

20

主题

1182

帖子

2329

积分

金牌会员

Rank: 6Rank: 6

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

本版积分规则

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

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

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

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

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