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

 找回密码
 立即注册
  • 女汉子又回来了!辣妈angelababy一大清早就健身
  • 好事将近!方媛现身办理港澳通行证
  • 李晨被问要不要娶女友 范冰冰秒答七个字
  • 黄轩终于回应恋情了:试图开始一段感情但不合适
  • 姐的时尚你不懂!蔡依林内衣外穿秀出小蛮腰
  • 和高圆圆接吻什么感觉?赵又廷竟然说…
  • 说好的承诺呢?冯轲被曝未将财产转移给张靓颖
  • 冯轲晒股权变更信息自己仅持有十万 990万给靓颖
  • 全球首座“竹子”基站亮相:抗风210公里/小时
  • 英国狗狗痴迷可口可乐每天必喝:16颗牙掉了12颗
  • Triforce:英特尔、NVIDIA和AMD,你选择哪个?
  • 在Facebook推出更多类似Snap的功能后,Snap股票跌了
  • AMD的股价将进一步上涨
  • 零售死亡漩涡继续
  • 中国电信开启5G网络时代
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3121|回复: 8

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

[复制链接]

18

主题

36

帖子

89

积分

注册会员

Rank: 2

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

举报

21

主题

91

帖子

135

积分

注册会员

Rank: 2

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


suffix tree

check out  ukkonen's algorithm
--

28

主题

105

帖子

161

积分

注册会员

Rank: 2

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

主题

227

帖子

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



--

28

主题

109

帖子

169

积分

注册会员

Rank: 2

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

主题

101

帖子

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

主题

238

帖子

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

主题

1164

帖子

2293

积分

金牌会员

Rank: 6Rank: 6

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

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

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