google onsite 2/29

kinggarden2001 发表于 2016-3-1 12:19
题都挺难的。请教第一题hashcode 怎么取才能保证对应边会分到一个bucket？

就是这个讨论了半天，我提出的几种方案都不是特别好，姐姐不满意，最后也没说该怎么做比较好

楼主可以解释下A->B,B->A,A->C那么边的条数就是2，是怎么找到的吗？

第四题有更好的方法吗？

哪位能指点一下第四题？我觉得楼主的解法已经很好了！

bobzhang2004 发表于 2016-3-2 01:48
楼主可以解释下A->B,B->A,A->C那么边的条数就是2，是怎么找到的吗？

A和B两个节点，有直接A到B的边，也有直接B到A的边，这两条边算是满足条件的边，所以边数是2

bobzhang2004 发表于 2016-3-2 01:49
第四题有更好的方法吗？

不知道了，哥哥刚想follow up时间就到了，房间被后面来的人定了，又跟了一个印度shadow，哥哥也不能多说什么

第四题写code了吗？复杂度好高啊
first thought是给一个hash table记录每个字符出现过的位置
做dp的时候对于s[i] for 2<=k<=i 找所有s[:i]里含有这个字符的长度为k的substring跟s[i+1-k:i+1]比较是否只差1个 应该不会很久，取决于是否有大量重复出现的字符
k=1的情况是character 只要不同的character都算一个pair吧？

我也想知道第四题有没有什么精妙解答 trick应该就在比较substring那里 是否可以通过rolling hash之类的大大减少计算？

echo33 发表于 2016-3-2 01:58
第四题写code了吗？复杂度好高啊
first thought是给一个hash table记录每个字符出现过的位置
做dp的时候 ...

code写完了，测的时候因为比较复杂就只测了一半，做的时候脑子一直不太清楚，还是国人哥哥一直在帮我整理思路

“两个substring只有一个字母不同” 指的是 一定有一个字母不同 还是 最多有一个字母不同？