美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 全球首个“机械战警”上岗:高1米7/重200斤
  • 无意识行为透露个性特征:早餐也吃辣或性格开朗
  • 2017年应届毕业生就业调查:平均月薪4014元
  • 爱因斯坦这个理论争议了100年:科学家尝试证明
  • 不愧“四害之首” 精子连宇宙射线都杀不死
  • NASA预警:即将有五颗小行星擦过地球
  • 无辐射!超级激光新用途:实时监测生物体内状况
  • 太空冷冻老鼠精子产出小鼠:太空繁育或成真
  • 两个AlphaGo对战谁会赢?答案很简单
  • NVIDIA市值达800亿美元 日本软银成第四大股东
  • 6个月高位:强劲数据、强硬言论助力欧元
  • 黄金十字:逆势扭转,贵金属是要翻身了啊!
  • 小瞧高通! 你可就错了
  • 美元大跌——成也特朗普,败也特朗普
  • 诺奖得主Robert Shiller:美股市场还能上涨50%
  • 焦点:特朗普"2018预算案"周二首秀
  • 周二关键词:美联储与中国市场
  • 比特币再发“洪荒之力”,5天收益增加40%
  • 诺贝尔物理学奖得主:我身上百分百流的是中国人的血液
  • 警告:小心债券市场带来寒意
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3125|回复: 8

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

[复制链接]

19

主题

39

帖子

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面的, 完全没思路。谢谢
--
【COACH美国代购总群】99634155
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

23

主题

97

帖子

145

积分

注册会员

Rank: 2

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


suffix tree

check out  ukkonen's algorithm
--

29

主题

115

帖子

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

主题

231

帖子

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

主题

112

帖子

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

主题

107

帖子

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

主题

244

帖子

244

积分

中级会员

Rank: 3Rank: 3

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

25

主题

98

帖子

161

积分

注册会员

Rank: 2

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


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

20

主题

1192

帖子

2350

积分

金牌会员

Rank: 6Rank: 6

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

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

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