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

 找回密码
 立即注册
  • 杨幂刘恺威再生二胎?公公刘丹这样回应…
  • 1岁咘咘登名校考题!贾静雯:怎么知道我爱草莓
  • 自拍露出白发!舒淇喊话粉丝见证她变老
  • 韩歌手IU和男友3年恋情告吹 各忙事业关系疏远
  • 超霸气!范冰冰一听吴亦凡受伤 秒问:你在哪?
  • 刚满月的儿子要网购?陈妍希一孕傻三年模式开启
  • 马伊琍罕见晒3岁小女儿近照 小公主乖巧可爱
  • 朱丹晒素颜自拍 卸了妆根本就是换了个人
  • 罗志祥深夜泄感情状态 要给女友颁“终身成就奖”
  • 多多帮妹妹装饰柜子 网友:这样的好姐姐来一沓
  • 特朗普反弹并没有结束
  • 推动市场的最大驱动力
  • 星期一上午重要的投资事件
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3116|回复: 8

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

[复制链接]

17

主题

34

帖子

86

积分

注册会员

Rank: 2

积分
86
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奇虎

举报

20

主题

85

帖子

125

积分

注册会员

Rank: 2

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


suffix tree

check out  ukkonen's algorithm
--

26

主题

103

帖子

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



--

10

主题

221

帖子

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



--

26

主题

105

帖子

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

21

主题

98

帖子

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



--

1

主题

227

帖子

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

23

主题

92

帖子

145

积分

注册会员

Rank: 2

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


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

19

主题

1106

帖子

2176

积分

金牌会员

Rank: 6Rank: 6

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

本版积分规则

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

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

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

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

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