google onsite 7/25

第一题是不是要找循环节？

playgames 发表于 2016-7-26 11:39
举个例子
字符串 “123456” 能够cover 的密码 “1234”， “3456”， “2345”。 其实也已经把解法说出 ...

是不是给一个4位密码集合S，然后求一个最短字符串str使得S中的任意4位密码都是str的子串。。。

我来给印度人点个赞

第一个题的I am student 能打乱顺序么?

第二题 先sort一下strings, 然后找strings[i]的后缀和string[i+1]的前缀的最长匹配?比如string[i] = "1234" string[i+1] = "3456" 所以 结果就是 12[34]56?

第三题 几个骰子?

我觉得第一题i am student 顺序不能打乱。而且要考虑到一行能容纳一至多条文本与一行容纳不了完整的一条文本。我建了vector作为循环数组，存读一次完整的文本占的行数与这些行数能读多少条完整的文本。在用一个map，映射行首词的下标与vector中对应的下标。

第一题我的做法是可以先循环遍历文本，遍历的过程中不断记录新一行起始单词的坐标，如果找到一个重复的起始坐标就证明找到了循环节。然后可以算出第一次循环开始之前需要占多少空间 & 包含了多少次文本 + 每个循环占的空间&文本次数 * 循环次数 + 最后一次未完成的循环之中文本次数。
这个做法找循环节的worst case 是O(n^2)，n是文本单词个数
计算文本次数的worst case是O(n)

playgames 发表于 2016-7-26 11:39
举个例子
字符串 “123456” 能够cover 的密码 “1234”， “3456”， “2345”。 其实也已经把解法说出 ...

楼主能说说解法吗? thanks

CescTom 发表于 2016-7-27 12:50
第一题我的做法是可以先循环遍历文本，遍历的过程中不断记录新一行起始单词的坐标，如果找到一个重复的起始 ...

是不是用文本第一行的第一个word 的row ㄝcol index 来判断有没有重复? 如果有重复就知道文本绕了几次是这个meaning 吗? 这样的话找重复循环节的time complexity 怎么算出o (n^2)?

第一题暴力做不就是O（RC）的嘛？还是我理解错了？

感谢分享。 关注下第一题的解法