Google onsite

上周在皮村面的，j今天HR通知HC没过。题目感觉不是很难，然鹅。。。还是挂了，估计做题太慢

第一轮，白人小哥。给一个字典，里面一堆单词

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

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

:
点错了，码农类，不是统计类

补充内容 (2016-12-15 13:30):
第四轮 要求不让用extra memory，复杂度要O(N)

第一轮对dict建trie在target string很长的情况下还是有用的，比如原本4个string（aaab, aaac, aaad）需要遍历4遍 target，现在只需要遍历一遍了

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

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

KimiZJ 发表于 2016-12-15 01:41
第一题建立trie树的确有优化效果，但是对复杂度没有影响。然后susequence是要求word必须依次出现在targrt ...

差值n个字符都可以用相同的思路来做啊。我写了个差值两个字符的

1. public class Solution {
   
2.     public char[] differentChar(String s, String t) {
   
3.         int[] tmp = new int[26];
   
4.         for (int index = 0; index < s.length(); index ++) {
   
5.             tmp[s.charAt(index) - 'a'] ++;
   
6.             tmp[t.charAt(index) - 'a'] --;
   
7.         }
   
8.         tmp[t.charAt(t.length() - 2) - 'a'] --;
   
9.         tmp[t.charAt(t.length() - 1) - 'a'] --;
   
10.         char[] res = new char[2];
    
11.         int resIndex = 0;
    
12.         for (int index = 0; index < 26; index ++) {
    
13.             if (tmp[index] == -1) {
    
14.                 res[resIndex ++] = (char)(index + 'a');
    
15.             } else if (tmp[index] == -2) {
    
16.                 res[0] = (char)(index + 'a');
    
17.                 res[1] = (char)(index + 'a');
    
18.             }
    
19.         }
    
20.         return res;
    
21.     }
    
22.     public static void main(String[] args) {
    
23.         Solution sol = new Solution();
    
24.         char[] res = sol.differentChar("daabc", "bzcaade");
    
25.         System.out.println(res[0] + ", " + res[1]);
    
26.     }
    
27. }

复制代码

第一题这两天看到好几遍了，LZ 有啥好方法优化？

houqingniao 发表于 2016-12-14 08:33
第一题这两天看到好几遍了，LZ 有啥好方法优化？

木有，和小哥讨论了半天他也不没给hint，我给优化对worst case都没啥用。。。

KimiZJ 发表于 2016-12-14 08:36
木有，和小哥讨论了半天他也不没给hint，我给优化对worst case都没啥用。。。

用trie ?

zyoppy008 发表于 2016-12-14 08:49
用trie ?

当时想到了顺口说了trie，但是和小哥商量了下发现并木有什么用。。。童鞋怎么用trie优化复杂度啊？

第二轮 对象很多 依然logn啊 没办法 还是说多到内存装不下那种

KimiZJ 发表于 2016-12-14 08:51
当时想到了顺口说了trie，但是和小哥商量了下发现并木有什么用。。。童鞋怎么用trie优化复杂度啊？

可以 很多字典 前缀相同的 单词 前缀只用check一次

zyoppy008 发表于 2016-12-14 08:49
用trie ?

愿闻其详~~~~

KimiZJ 发表于 2016-12-14 08:36
木有，和小哥讨论了半天他也不没给hint，我给优化对worst case都没啥用。。。

感觉sort下，还是暴力啊 没啥用

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

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