详谈如何最大化利用career fair

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1834|回复: 21
收起左侧

[找工就业] 请教一道国内面试算法题,很短,没做出来

[复制链接] |试试Instant~
我的人缘0
EddieStallworth 发表于 2017-10-28 21:21:40 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (150)
 
 
5% (9)  踩

2018(7-9月)-[18]CS硕士+fresh grad 无实习/全职 - 内推|BayArea 码农类General其他@Googlefresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
国内面试题 没做出来.... more info on 1point3acres

给一个DNA序列 只包含ACGT四个字符-google 1point3acres
返回一个整数,这个整数是最短的没出现过的组合

比如 给一个字符串"ACGTAG" 返回2
因为A出现过 C出现过 G出现过 T出现过 所以返回1
但是CA没出现过 这个就是最短的 长度2 所以返回2

. visit 1point3acres for more.
补充内容 (2017-10-29 07:13):
有个地方错了

因为A出现过 C出现过 G出现过 T出现过 所以"不"返回1
但是CA没出现过 这个就是最短的 长度2 所以最终返回2

上一篇:Google onsite 時間請問該填什麼時候比較好
下一篇:报个Amazon summer实习no longer
我的人缘0
yanshuo619 发表于 2017-10-29 06:40:28 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  80% (153)
 
 
19% (38)  踩
要求只是返回长度 所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合,然后每个长度分别是一个set,遍历时 A就扔1级set,AC扔C进1级set,同时AC扔二级set,以此类推,要保存每一级长度set的前一个状态,最后从1级set往上看set的size,到哪级set比理论组合size少 就返回哪级就好了。理论上是n复杂度?
回复

使用道具 举报

我的人缘0
wdxh1 发表于 2017-10-28 21:35:19 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (273)
 
 
8% (24)  踩
brute force 从长度2开始 生成所有的排列 看看是不是substring 如果都是 长度增加 继续 另外 如果不写code 可以用suffix tree 找一个depth最小 并且child数量小于4的node 就行
回复

使用道具 举报

我的人缘0
 楼主| EddieStallworth 发表于 2017-10-29 03:40:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (150)
 
 
5% (9)  踩
wdxh1 发表于 2017-10-28 21:35
brute force 从长度2开始 生成所有的排列 看看是不是substring 如果都是 长度增加 继续 另外 如果不写code  ...
. Waral 博客有更多文章,
对啊 我也是只会暴力解...
回复

使用道具 举报

我的人缘0
k1938slll 发表于 2017-10-29 05:03:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  60% (23)
 
 
39% (15)  踩
好难?! Google的题吗

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
fangdanzai 发表于 2017-10-29 05:10:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (160)
 
 
7% (13)  踩
先把所有可能的组合存在hash里 然后用长度从1到length遍历?
回复

使用道具 举报

我的人缘0
a92921 发表于 2017-10-29 05:35:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (90)
 
 
14% (15)  踩
我只能想到类似暴力解的,因为只有4个字母,所以每种length的排列组合数量你都可以直接算出来。
从最小length开始,对于某个length都新建一个hash set,用个sliding window把substring扔进set里,如果set的大小不等于你排列组合算出来的数量就直接返回当前length

补充内容 (2017-10-29 06:22):
打错,不是某个,是每个
回复

使用道具 举报

我的人缘0
zzrdwj 发表于 2017-10-29 05:46:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (174)
 
 
24% (55)  踩
A for 0, T for 1, C for 2, G for 3,
k tuples----->四进制数字
k=1. more info on 1point3acres
while(k){
取k-tuples转化为4进制,得到n-k+1长的数组.留学论坛-一亩-三分地
for (i=k位四进制的所有数){数组减去i,搜索是否存在0,不存在返回k}
k++
}. more info on 1point3acres



补充内容 (2017-10-29 05:53):
n=length(gene)
回复

使用道具 举报

头像被屏蔽
我的人缘0
wodexiaohao5 发表于 2017-10-29 06:17:39 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

我的人缘0
yanshuo619 发表于 2017-10-29 06:44:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (153)
 
 
19% (38)  踩
yanshuo619 发表于 2017-10-29 06:40
要求只是返回长度 所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合 ...
.留学论坛-一亩-三分地
前面有一点会产生误会,理论组合size组合数字是根据有多少元素算出来,不是input string那个长度
回复

使用道具 举报

我的人缘0
empy 发表于 2017-10-29 06:49:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (6)
 
 
33% (3)  踩
yanshuo619 发表于 2017-10-29 06:40
要求只是返回长度 所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合 ...

set长度最高为log4(n),所以遍历每个元素时遍历log4(n)次,总的时间复杂度为nlog4(n)。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
yanshuo619 发表于 2017-10-29 06:58:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (153)
 
 
19% (38)  踩
empy 发表于 2017-10-29 06:49-google 1point3acres
set长度最高为log4(n),所以遍历每个元素时遍历log4(n)次,总的时间复杂度为nlog4(n)。

每个元素只是跟前一个状态合起来仍set里,为啥会需要遍历呢
回复

使用道具 举报

我的人缘0
empy 发表于 2017-10-29 07:10:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (6)
 
 
33% (3)  踩
yanshuo619 发表于 2017-10-29 06:58
每个元素只是跟前一个状态合起来仍set里,为啥会需要遍历呢
  1. int leastLen(string str) {
  2.         int strLen = str.length();
  3.         int maxLen = log(strLen) / log(4);
  4.         vector<unordered_set<string>> comb(maxLen);
  5.         for (int i = 0; i < strLen; i++) . From 1point 3acres bbs
  6.                 for (int j = 0; j <maxLen && i-j>=0; j++)
  7.                         comb[j].insert(str.substr(i - j, j+1));
  8.         int res = maxLen + 1;
  9.         for (int i = 0; i < maxLen; i++) 来源一亩.三分地论坛.
  10.                 if (comb[i].size() < pow(4, i + 1))
  11.                         res = i + 1;. visit 1point3acres for more.
  12.         return res;
  13. }
复制代码
时间复杂度 nlog4(n)

补充内容 (2017-10-29 07:13):
最后那个if应该是.本文原创自1point3acres论坛
                if (comb.size() < pow(4, i + 1)) {
                        res = i + 1;
                        break;
                }
回复

使用道具 举报

我的人缘0
 楼主| EddieStallworth 发表于 2017-10-29 07:13:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (150)
 
 
5% (9)  踩
k1938slll 发表于 2017-10-29 05:03
好难?! Google的题吗

百度的 字数字数
回复

使用道具 举报

我的人缘0
 楼主| EddieStallworth 发表于 2017-10-29 07:15:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (150)
 
 
5% (9)  踩
fangdanzai 发表于 2017-10-29 05:10
先把所有可能的组合存在hash里 然后用长度从1到length遍历?

不能暴力解啊 那还有啥意思了..
回复

使用道具 举报

我的人缘0
 楼主| EddieStallworth 发表于 2017-10-29 07:16:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (150)
 
 
5% (9)  踩
yanshuo619 发表于 2017-10-29 06:40
要求只是返回长度 所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合 ...

面试完了以后我又想了一下 应该这样做是可行的
回复

使用道具 举报

我的人缘0
a92921 发表于 2017-10-29 07:40:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (90)
 
 
14% (15)  踩
empy 发表于 2017-10-29 07:10
时间复杂度 nlog4(n)

补充内容 (2017-10-29 07:13):

substr也是需要时间的
回复

使用道具 举报

我的人缘0
mmymichael 发表于 2017-10-29 07:43:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (305)
 
 
32% (146)  踩
twitter OA questions. i have seen this question last year
回复

使用道具 举报

我的人缘0
empy 发表于 2017-10-29 07:58:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (6)
 
 
33% (3)  踩
a92921 发表于 2017-10-29 07:40
substr也是需要时间的

即使substr的时间复杂度是O(n),总的复杂度也不过是多乘一个log4(n)
回复

使用道具 举报

我的人缘0
magicsets 发表于 2017-10-29 16:40:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (254)
 
 
2% (6)  踩
用suffix tree可以时间O(n),空间O(n)。具体就是先O(n)建树,然后从树根逐层BFS做一些判断。不过建树算法非常复杂。. from: 1point3acres
.本文原创自1point3acres论坛
其实看到ACGT,第一反应是压缩索引技术,例如FM-index (burrow wheeler transform),不过对于这一题好像不适用。


估计面试想要的做法是把每个字符压缩为2bit编码,然后用一个32位整数编码子串(可以处理最多4*10^9长度的输入,更长的话要用64位整数)。
在编码后,就不需要用hash set了,因为压缩后的整数分布是稠密的,只需要用一个bitmap。. 留学申请论坛-一亩三分地

参考代码如下:. 1point3acres

  1. #include <cstddef>
  2. #include <cstdint>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>

  8. // BitSet的简单实现
  9. class BitSet {
  10. public:. 围观我们@1point 3 acres
  11.   explicit BitSet(const std::size_t num_bits)
  12.       : data_array_size_((num_bits >> kHigherOrderShift) +
  13.                          (num_bits & kLowerOrderMask ? 1 : 0)),.1point3acres网
  14.         data_array_(static_cast<std::size_t*>(std::malloc(data_array_size_ * kDataSize))) {
  15.     std::memset(data_array_, 0, data_array_size_ * kDataSize);
  16.   }

  17.   ~BitSet() {
  18.     std::free(data_array_);
  19.   }. 留学申请论坛-一亩三分地
  20. . Waral 博客有更多文章,
  21.   inline void setBit(const std::size_t bit_num) const {
    .本文原创自1point3acres论坛
  22.     data_array_[bit_num >> kHigherOrderShift] |= kTopBit >> (bit_num & kLowerOrderMask); 来源一亩.三分地论坛.
  23.   }

  24.   inline std::size_t onesCount() const {
  25.     std::size_t count = 0;
  26.     for (std::size_t array_idx = 0; array_idx < data_array_size_; ++array_idx) {
  27.       count += __builtin_popcountl(data_array_[array_idx]);. 一亩-三分-地,独家发布
  28.     }
  29.     return count;
  30.   }

  31. private:
  32.   static constexpr std::size_t kDataSize = sizeof(std::size_t);
  33.   static constexpr std::size_t kLowerOrderMask = (kDataSize << 3) - 1;
  34.   static constexpr std::size_t kHigherOrderShift = kDataSize == 4 ? 5 : 6;
  35.   static constexpr std::size_t kOne = 1ull;
  36.   static constexpr std::size_t kTopBit = kOne << kLowerOrderMask;

  37.   const std::size_t data_array_size_;
  38.   std::size_t *data_array_;
  39. };
  40. . 围观我们@1point 3 acres
  41. int Solve(const std::string &dna) {
  42.   // 编码索引
  43.   std::uint32_t dna2code[128];
  44.   memset(dna2code, 0, sizeof(dna2code));
  45.   dna2code[(int)'a'] = dna2code[(int)'A'] = 0;
  46.   dna2code[(int)'c'] = dna2code[(int)'C'] = 1;
  47.   dna2code[(int)'g'] = dna2code[(int)'G'] = 2;
  48.   dna2code[(int)'t'] = dna2code[(int)'T'] = 3;
  49. . From 1point 3acres bbs
  50.   // 编码.1point3acres网
  51.   constexpr std::size_t kNumBitsInWord = 32;
  52.   constexpr std::size_t kNumCodesInWord = kNumBitsInWord / 2;. more info on 1point3acres

  53.   std::vector<std::uint32_t> words;
  54.   std::size_t shift = 0;
  55.   std::uint32_t word = 0;
  56.   for (const unsigned char c : dna) {
  57.     word |= dna2code[c] << shift;. 一亩-三分-地,独家发布
  58.     if (shift == kNumBitsInWord - 2) { 来源一亩.三分地论坛.
  59.       words.emplace_back(word);
  60.       shift = 0;
  61.       word = 0;
  62.     } else {
  63.       shift += 2;
  64.     }
  65.   }
  66.   if (shift != 0) {
  67.     words.emplace_back(word);
  68.   }

  69. //  for (const std::uint32_t w : words) {. 围观我们@1point 3 acres
  70. //    std::cout << std::bitset<32>(w) << "\n";
  71. //  }

  72.   // 枚举长度
  73.   const std::size_t dnaL = dna.length();
  74.   std::size_t subL = 1;
  75.   while (true) {
  76.     const std::size_t max_combinations = 1ull << (subL * 2);
  77.     if (max_combinations > dnaL) {
  78.       break;
  79.     }
  80. .留学论坛-一亩-三分地
  81.     // 遍历子串.留学论坛-一亩-三分地
  82.     BitSet existence(max_combinations);
  83.     const std::uint64_t sub_mask = max_combinations - 1;. from: 1point3acres

  84.     std::uint64_t buffer = words.front();
  85.     for (std::size_t i = 0; i < words.size() - 2; ++i) {
  86.       buffer |= static_cast<std::uint64_t>(words[i+1]) << kNumBitsInWord;.本文原创自1point3acres论坛
  87.       for (std::size_t k = 0; k < kNumCodesInWord; ++k) { 来源一亩.三分地论坛.
  88.         existence.setBit(buffer & sub_mask);
  89.         buffer >>= 2;
  90.       }
  91.     }
  92.     buffer |= static_cast<std::uint64_t>(words.back()) << kNumBitsInWord;
  93.     const std::size_t last = dnaL % kNumCodesInWord;.留学论坛-一亩-三分地
  94.     const std::size_t num_residual =
  95.         (kNumCodesInWord + (last == 0 ? kNumCodesInWord : last) - subL + 1);. From 1point 3acres bbs
  96.     for (std::size_t k = 0; k < num_residual; ++k) {
  97.       existence.setBit(buffer & sub_mask);
  98.       buffer >>= 2;. 留学申请论坛-一亩三分地
  99.     }

  100.     if (existence.onesCount() != max_combinations) {
  101.       break;
  102.     }
  103.     ++subL;
  104.   }
  105.   return subL;
  106. }
复制代码
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-23 18:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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