Google onsite

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

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

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

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

KimiZJ 发表于 2016-12-15 03:15
额。。的确可以，我当时没用这思路，面试官也没给这个，给了个更复杂的

忽然想起来，当时第四题面试官不让用extra memory，就是拿hashmap那种记录不行，所以数组的这个应该也不可以

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

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

KimiZJ 发表于 2016-12-14 13:12
转成数字，列方程组 a+b+c = y1, a^2 + b^2 + c^2 = y2这样，方程组有专门的程序求，不用写。。。面试官 ...

a^2 + b^2 + c^2 = y2
怎么得来的？

sunnyroom 发表于 2016-12-19 13:54
a^2 + b^2 + c^2 = y2
怎么得来的？

就是列方程组啊，三个未知量就列三元三次方程组，方程组怎么解不用管

第一轮地里已有面经。我写过一个dfs解。一定要将target string 预处理类似于：计算pos[i][c-'a']=从index i 起第一个出现char c的index. 将这个2D array 存起来，时间不过O(string length), 但对于庞大的字典trie 免去相同prefix 的重复计算。然后在trie 中dfs 同时更新max word length

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

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

zzgzzm 发表于 2016-12-19 15:09
我也是这样预处理target, 但时间实际O(length (target))就可以了。因为对每个char, 一但找到下一个的话就 ...

求解怎么可以在len(target)的时间复杂度内预处理target?

对于第一题利用trie的思路稍微写的点代码，不知道这样行不行。遍历建好的trie，看当前索引位置的字符是不是能在trie的节点中，如果在，target串继续遍历下一个字符，同时还要考察，下一个字符在当前这个节点中是不是存在。

1. void dfs(TrieNode* root, int idx, string s, int &maxLen, string& res){
   
2.         if(root->isWord){
   
3.                 for(auto a : root->strs){
   
4.                         if(a.size()>maxLen){
   
5.                                 maxLen=a.size();
   
6.                                 res=a;
   
7.                         }
   
8.                 }
   
9.         }
   
10.         if(idx==s.size())
    
11.                 return;
    
12. 
    
13.         if(root->child[s[idx]-'a']){
    
14.                 dfs(root->child[s[idx]-'a'], idx+1,s, maxLen, res);
    
15.         }
    
16.         dfs(root, idx+1,s,maxLen,res);
    
17. }

复制代码