Google Internship电面

knight0clk 发表于 2016-11-6 01:25
就是你按照二进制拆分K，然后preprocess一下，准备好二进制组合方式组合出结果。比如K=5=0b(101)，所以结 ...

楼主preprocess 的结果是啥？101组合方式为啥就得到最后的结果了？

多谢楼主哈，想请问一下有什么比较快的方法能够在preprocess的时候生成类似如 BCDE, CDEF, DEFG, EFGH的方法吗？还是就是暴力的对每个i进行循环？
多谢啦

sccnju 发表于 2016-11-6 02:22
多谢楼主哈，想请问一下有什么比较快的方法能够在preprocess的时候生成类似如 BCDE, CDEF, DEFG, EFGH的方 ...

ABCD用之前的结果生成，你能生成ABCD，你之前肯定生成AB,BC,CD,DE,EF了，所以不用暴力算法，这就是一个二进制的问题

tinyrookie 发表于 2016-11-6 02:07
楼主preprocess 的结果是啥？101组合方式为啥就得到最后的结果了？

看楼下的回复，另外多想想，就是二进制的问题

有人理解楼主的第二题思路了吗？我还是一头雾水。。。

是不是第二题用一个二分查找来模拟除法比较好？这样时间复杂度还是O（n）

坨坨 发表于 2016-11-6 12:48
有人理解楼主的第二题思路了吗？我还是一头雾水。。。

还是没理解。。

tinyrookie 发表于 2016-11-6 17:01
还是没理解。。

好吧，我在统一说一下，最初，我们有A1=[A,B,C,D,E,F,G,H,I,J], 根据A1，可以有A2=[AB, BC, CD, DE, EF, FG,GH,HI,IJ], 根据A2可以有A3=[ABCD,BCDE,CDEF,DEFG,EFGH,FGHI,GHIJ],然后可以有A4=[ABCDEFGH, BCDEFGHI, CDEFGHIJ] ... 依此类推，就像二进制1，2，4，8，16，有了这些，我们就可以随便产色任意组合，比如说K=5=0b(101)，所以结果就是A*BCDE, B*CDEF, C*DEFG, D*EFGH，所以复杂度就降为nlog(k)了。如果再不懂，我也没办法了。。。谢谢

笑眯眯的白云 发表于 2016-11-6 01:46
楼主加油！ 请问没被问design 或者scalability 的题目吗？

实习生，不会考这么难的。。。我都不懂design的。。。

构造辅助数组的时间复杂度应该是 O(n)? 构造的时候时间复杂度是 O(logk), 但是得到结果的时候应该是O(n), 这两个步骤是分别进行的，所以总的时间复杂度是O(n)。
如果是我的话，我也会采用保存中间值的方法，因为如果不保存的话会有大量的重复计算，但是这种解法用空间复杂度换了时间复杂度，不知道有没有更好的解法。