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

 找回密码
 立即注册
  • 中国胖子服了!最新研究:喜爱重口食物容易胖
  • 切尔诺贝利核事故30年后恐怖一幕:千里外野猪仍受辐射
  • 儿子等等病了 邓超一小时问800次要不要去医院
  • "王柏川"原配谈出轨门始末:他的聊天记录内容露骨
  • 贴心小棉袄!贾乃亮将出门 甜馨早起为爸爸包饺子
  • 34岁的唐嫣卖萌毫不费力 齐刘海短发清纯可爱
  • 赵薇深夜暖心发文:要记得这些人 使你远离阴霾
  • 美媒:《排华法案》证明“移民癔症”绝非新现象
  • 戚继光舰不仅是教练舰 可海外撤侨大量运兵
  • 著名LOL和Dota2玩家“互斥”不算男人 真相竟是这样
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3118|回复: 8

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

    [复制链接]

    18

    主题

    35

    帖子

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

    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    20

    主题

    89

    帖子

    125

    积分

    注册会员

    Rank: 2

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

    主题

    224

    帖子

    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

    主题

    106

    帖子

    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

    主题

    231

    帖子

    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

    主题

    93

    帖子

    154

    积分

    注册会员

    Rank: 2

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


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

    20

    主题

    1137

    帖子

    2239

    积分

    金牌会员

    Rank: 6Rank: 6

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

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

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