google onsite 2/29

say543 发表于 2016-3-4 15:50
不知道有没有离解错题目意思? 第一步先枚举所有的substrings o(n^3) 第二步根据长度分类每一个长度里面分 ...

感觉也是可行的

hzyslddm 发表于 2016-3-2 01:45
就是这个讨论了半天，我提出的几种方案都不是特别好，姐姐不满意，最后也没说该怎么做比较好

找hashcode这题，直接把“A,B”的hashcode（）和“B,A”的hashcode（）加起来作为这组边的hashcode可以吗？

解决方法是hashmap里面不存字符的occurance,而是存字符最后出现的位置。返回值是substring的start index和end index
这种方法不懂 ，求解释，最好给个例子

Czon 发表于 2016-3-2 01:26
楼主麻烦问一下第二题存了index以后怎么处理

我也在想这个问题

qiuxuxing007 发表于 2016-3-7 10:30
解决方法是hashmap里面不存字符的occurance,而是存字符最后出现的位置。返回值是substring的start index和e ...

hashmap里存 字符 - 该字符最后出现的位置，那么一旦遇到新字符导致超出最多K个不同字符的限制时，start index就是之前记录的值，end index为当前index-1, 然后找到hashmap里面value最小的key（也就是最后出现位置最靠前的字符）, 把start index设为该value+1 (也就是移掉了一个字符的出现)，并把这对key-value pair从hashmap里删除
比如aabaacaab, k为2。那么在遇到c的时候，a最后出现的index是4，b最后出现的index是2，那么通过把start index设为3以及把(b,2)这个pair从map中移除，把map中不同字符的个数减小到了1，就可以新加不同字符了

我理解你的意思了， 这种算法很精巧， 点赞， 但是还是不能处理string很长很长，而且只给一个iterator,每次调用给一个字符的问题啊？（因为这种方法本质上跟hashmap加two pointer的方法原理是一致的）我觉得follow up其实是没有code 的，我觉得应该用divide and conquer来做， 把string分段来看看每段的情况， 看看每段 substring的distribution 和稀疏情况， 你觉得呢？

qiuxuxing007 发表于 2016-3-8 03:46
我理解你的意思了， 这种算法很精巧， 点赞， 但是还是不能处理string很长很长，而且只给一个iterator,每次 ...

可是follow up要改写之前写的code。string很长很长可以处理呀，只要记录字符出现的index就好了（加个变量计数），方法的本质没有变化，只是可以处理每次给一个字符的情况。divide&conquer不是特别好做吧，一次给一个字符的话，要怎么divide呢？调用很多次，处理一下这段，再调用很多次，处理下一段，再合并？

csgtc 发表于 2016-3-2 15:14
如果是任意character也是256*n^3，比n^4好啊。。

那为啥不直接用lz的dp思路加上个hashset（hashmap）求那个以i结尾的substring的时候 在hahsset 走之前的就可以了，复杂度就变成了256*n^2了

补充内容 (2016-3-13 09:39):
在hashset里头搜索

cx00001 发表于 2016-3-13 09:39
那为啥不直接用lz的dp思路加上个hashset（hashmap）求那个以i结尾的substring的时候 在hahsset 走之前的 ...

然后把这些以i结尾的substring加入到hashset里头

补充内容 (2016-3-13 09:40):

请问楼主有结果了吗