google onsite 2/29

1. 印度姐姐
给一组有向图的边的array，找A->B同时B->A，这样两个点之间直接有两条边相连，符合这样条件的边的条数。比如A->B,B->A,A->C那么边的条数就是2
LZ说用hashset解决，把to Node value + "#" + from Node value, 存进set里面，下次如果from node value + "#" + to node value已经在set中存在了，说明找到了一对，则边数+2
follow up是如果图很大，边很多，可以用多台machine，该怎么办。LZ说把边array分成几段，每段交给一个machine处理，得到的hashset和num数再merge。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

< i,  i-j <=k < i）可能的匹配个数
算法时间复杂度是O(N^4)，复杂度还是很高，哥哥想follow up的，结果没有时间了，sigh
国人哥哥人很好，一直在帮LZ整理思路，一直在给hint,走的时候还用中文跟我说“加油“和”好运啦“，可惜LZ反应太慢，才做了一题还没有时间follow up


发帖攒RP,希望有加面TAT

第四题如果题意有且只有一个不同的意思是A中的一个字母被原位替换的话变成B，这题是可以做到O(n^2)的
一个O(n^3)的解法是这样：

1. 找到s[i] != s[j]的pair (i < j)
2. 我们将s[i]和s[j]视作A和B中那个不同字母，从i和j分别向左右扩展，例如s[i-1]==s[j-1]就可以向左扩展
3. 最后我们可以找到以i,j为不同的长pair，[i-x, i+y] 和[j-x, j+y]，将总数增加 ans += y + x + 1;
4. return ans

这个方法可以进一步优化为O(n^2)

补充内容 (2016-5-31 08:57):
错了，应该是，ans += (y + 1) * (x + 1);
乘法原理

补充内容 (2016-5-31 08:59):
打不出来[~i~]前面那些s后面都有个i

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

只是纠正一下不能做那个字符都是字母的assumption,不是说你的算法不行。。另外，用hashset可能会漏算，比如aab这样的字符串，"a"和"b"这样的pair有两组,感觉要改用hashmap

第二题follow up hashmap还是可以存occurence吧，

1. public class LongestSubstringWithAtMostKDistinctCharactersStream {
   
2. 
   
3.         static class StreamReader {
   
4.                 int pos = 0;
   
5.                 String str;
   
6. 
   
7.                 public StreamReader(String str) {
   
8.                         this.str = str;
   
9.                 }
   
10. 
    
11.                 char next() {// return next character
    
12.                         return str.charAt(pos++);
    
13.                 }
    
14. 
    
15.                 boolean hasNext() {
    
16.                         return pos < str.length();
    
17.                 }
    
18.         }
    
19. 
    
20.         public static String lengthOfLongestSubstringKDistinct(StreamReader s, int k) {
    
21.                 if (s == null || !s.hasNext()) {
    
22.                         return "";
    
23.                 }
    
24.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    
25.                 int max = 0;
    
26.                 StringBuilder sb = new StringBuilder();
    
27.                 String res = "";
    
28.                 while (s.hasNext()) {
    
29.                         char c = s.next();
    
30.                         sb.append(c);
    
31.                         if (!map.containsKey(c)) {
    
32.                                 map.put(c, 1);
    
33.                                 while (sb.length() > 0 && map.size() > k) {
    
34.                                         char ch = sb.charAt(0);
    
35.                                         sb.deleteCharAt(0);
    
36.                                         map.put(ch, map.get(ch) - 1);
    
37.                                         if (map.get(ch) == 0) {
    
38.                                                 map.remove(ch);
    
39.                                         }
    
40.                                 }
    
41.                         } else {
    
42.                                 map.put(c, map.get(c) + 1);
    
43.                         }
    
44.                         if (sb.length() > max) {
    
45.                                 max = sb.length();
    
46.                                 res = sb.toString();
    
47.                         }
    
48.                 }
    
49. 
    
50.                 return res;
    
51.         }
    
52.        
    
53.         public static void main(String[] args) {
    
54.                 StreamReader sr = new StreamReader("ababcbcbaaabbdef");
    
55.                 System.out.println(lengthOfLongestSubstringKDistinct(sr, 2));
    
56.                 StreamReader sr1 = new StreamReader("ababc");
    
57.                 System.out.println(lengthOfLongestSubstringKDistinct(sr1, 2));
    
58.                
    
59.         }
    
60. }
    

复制代码

补充内容 (2016-3-26 05:00):
用一个stringbuilder存下substring, 然后用deleteCharAt(0)进行移动

第2题最近似乎经常出现啊

第二题 尼玛就是google 超高频

题都挺难的。请教第一题hashcode 怎么取才能保证对应边会分到一个bucket？

第四题也挺难的
不知道有什么好解法没有？

楼主进hc了吗？

panlong222 发表于 2016-3-1 12:38
楼主进hc了吗？

楼主的题比我的难一个档次。。。

第四题 每对substring pair里的俩substring允许overlap吗

楼主麻烦问一下第二题存了index以后怎么处理

panlong222 发表于 2016-3-1 13:11
第四题 每对substring pair里的俩substring允许overlap吗

允许overlap，一开始LZ写的是没overlap的，后来被中国哥哥提醒了下