回复: 21
跳转到指定楼层
上一主题 下一主题
收起左侧

请教一道国内面试算法题,很短,没做出来

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
国内面试题 没做出来...

给一个DNA序列 只包含ACGT四个字符
返回一个整数,这个整数是最短的没出现过
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
;不"返回1
但是CA没出现过 这个就是最短的 长度2 所以最终返回2

上一篇:Google onsite 時間請問該填什麼時候比較好
下一篇:狗家实习转正面试
推荐
chowhound 2017-10-29 06:40:28 | 只看该作者
全局:
要求只是返回长度 所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合,然后每个长度分别是一个set,遍历时 A就扔1级set,AC扔C进1级set,同时AC扔二级set,以此类推,要保存每一级长度set的前一个状态,最后从1级set往上看set的size,到哪级set比理论组合size少 就返回哪级就好了。理论上是n复杂度?
回复

使用道具 举报

推荐
magicsets 2017-10-29 16:40:40 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

推荐
empy 2017-10-29 07:10:04 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
wdxh1 2017-10-28 21:35:19 | 只看该作者
全局:
brute force 从长度2开始 生成所有的排列 看看是不是substring 如果都是 长度增加 继续 另外 如果不写code 可以用suffix tree 找一个depth最小 并且child数量小于4的node 就行
回复

使用道具 举报

🔗
 楼主| EddieStallworth 2017-10-29 03:40:14 | 只看该作者
全局:
wdxh1 发表于 2017-10-28 21:35
brute force 从长度2开始 生成所有的排列 看看是不是substring 如果都是 长度增加 继续 另外 如果不写code  ...

对啊 我也是只会暴力解...
回复

使用道具 举报

🔗
k1938slll 2017-10-29 05:03:44 | 只看该作者
全局:
好难?! Google的题吗
回复

使用道具 举报

🔗
fangdanzai 2017-10-29 05:10:27 | 只看该作者
全局:
先把所有可能的组合存在hash里 然后用长度从1到length遍历?
回复

使用道具 举报

🔗
无量塔 2017-10-29 05:35:31 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
zzrdwj 2017-10-29 05:46:01 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
chowhound 2017-10-29 06:44:46 | 只看该作者
全局:
yanshuo619 发表于 2017-10-29 06:40
要求只是返回长度 所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合 ...

前面有一点会产生误会,理论组合size组合数字是根据有多少元素算出来,不是input string那个长度
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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