google onsite

cszeus 发表于 2015-12-6 14:36
第一题主要了优化数据结构，讨论了用堆，BST，python里的OrderedDict的可行性。第二轮NP-hard，我不觉得 ...

longest substring with at most m distinct characters如何用堆和bst？ 另外，tsp是有dp解法的。

hyliu0000 发表于 2015-12-7 05:54
longest substring with at most m distinct characters如何用堆和bst？ 另外，tsp是有dp解法的。

我存了每个字母出现的位置，我要删最早出现的那个。他就希望我讨论，用什么结构，找这个最早出现的，比较快

cszeus 发表于 2015-12-7 09:39
我存了每个字母出现的位置，我要删最早出现的那个。他就希望我讨论，用什么结构，找这个最早出现的，比较 ...

这样会不会太费内存了？ 最好的方法是不是用hashmap存 char -》 count ， 然后用两个指针从前往后扫久行了？

hyliu0000 发表于 2015-12-7 11:24
这样会不会太费内存了？ 最好的方法是不是用hashmap存 char -》 count ， 然后用两个指针从前往后扫久行 ...

只要存m个字母，每个字母最后出现的位置。然后找删除哪个的时候，扫一遍这个table，cost O(m)。 但是如果有比较好的数据结构，像是python里的OrderedDict, 连找删除哪一个都是 O(1)，所以会很快

cszeus 发表于 2015-12-9 01:00
只要存m个字母，每个字母最后出现的位置。然后找删除哪个的时候，扫一遍这个table，cost O(m)。 但是如果 ...

楼主啊， 能不能详细说说你是怎么做的？
我先说下我的：
定义两个pointer left ，right
定义hashmap<char, int> map
int maxLength = Integer.MAX_VALUE;
while(right < n)
   map[char] ++
   if(map.size() > m)
     left ++;
     map[char at left] -- ;
     maxLength = max(maxLength, right - left);
   right ++;
maxLength = max(maxLength, right - left);
return maxLength
  
  

hyliu0000 发表于 2015-12-9 02:09
楼主啊， 能不能详细说说你是怎么做的？
我先说下我的：
定义两个pointer left ，right

maxLen = 0
dic = {}
end = start = 0
while end < len(s):
    if ch in dic or len(dic) < m:
        dic[ch] = end
    else:
        maxLen = max(maxLen,end-start)
        # find minimum index in dic and its ch, O(m)
        start = index+1
        dic.pop(ch)
    end += 1


大致是这样，当你有m个字母，并且出现m+1个字母的时候，你要试图删掉某个字母吧？我就找m个字母里面，出现最早的那个。

比如， ababac, m = 2
当出现c时，字典里面有{"b":3,"a":4}. 我只记录某个字母最后一次出现的位置。现在我可以知道，最后一个b出现在位置3，从位置4开始，只有m-1个字母。

然后这个地方，找到b，要扫一遍这个table。但是如果用OrderDict结合LRU cache的思想，每次更新一个字母的位置时，把它放到字典的最后，你就知道，字典中第一个，永远是我要找的那个。


补充内容 (2015-12-9 02:53):
这个字典会变成： {"a":0}, {"a":0,"b":1}, {"b":1,"a":2},{"a":2,"b":3}......m很大，你就看看出这个好处了

cszeus 发表于 2015-12-9 02:50
maxLen = 0
dic = {}
end = start = 0

不错的方法。 不过其实我的方法也很简单。 思路和你的差不多。 不过start是 ++ 而不是 start = index + 1. 另外，直接用hashmap， 所以time complexity is O（n）

hyliu0000 发表于 2015-12-9 05:13
不错的方法。 不过其实我的方法也很简单。 思路和你的差不多。 不过start是 ++ 而不是 start = index + 1 ...

面试官说了，一般人都会用你那种方法做。我用了我那个方法，他很奇怪，问我是不是见过类似的。我说有，他很不开心，说我应该提出来。

randomusername 发表于 2015-12-22 03:06
楼主送进hc审核了嘛...我面试时间跟你很近噢

悲剧了，让我参加一个ITRP的项目。应该不会去。