狗狗家的onsite

12/1的onsite。4轮+午饭。

要求11点到，结果还没到点面试官就来了。
第一轮：白人小哥
小哥人超帅又很nice，他家在我本科学校城市，所以上来寒暄了一下当地风土。
题目：longest m-unique substring. e.g. 'ababababcdedede' --> return 8
Follow up: input是stream data，比如上例，每次call api function has_next()和next_char()，如何处理。

第二轮：白人小叔
气场超足，全程不太给提示

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

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

ewer沟通了好几分钟，写答案过程中发现的细节总结给大家，所以看起来简单。实际上简单的题目满是坑，不可掉以轻心。

补充内容 (2016-12-6 07:58):
第一题m-unique是指m个unique character

补充内容 (2016-12-6 08:00):
我的表述太差了抱歉啊！第一题我举的例子，m = 2

小A要当码农 发表于 2016-12-6 02:34
多谢解释。然而还是没看懂啊。。有原题链接么？

这题做的很繁琐，有好办法请告知
维护一个pattern，如果有match了，还要维护一个tmp match.

1. #include <string>
   
2. #include <set>
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. int eval(string &s) {
   
7.   string pattern="";
   
8.   set<char> spat;
   
9.   int count=0;
   
10.   int tmp_count=0;
    
11.   string tmp="";
    
12. 
    
13.   for(int i=0; i<s.length(); i++) {
    
14.     if(tmp!="") {
    
15.       if(pattern[tmp.length()]==s[i]) {
    
16.         tmp+=s[i];
    
17.         if(pattern.length()==tmp.length()) {
    
18.           tmp_count++;
    
19.           tmp="";
    
20.           if(tmp_count*pattern.length()>count) {
    
21.             count=tmp_count*pattern.length();
    
22.           }
    
23.         }
    
24.       } else {
    
25.         set<char> stmp;
    
26.         int j=i;
    
27.         for(; j>=i-tmp.length(); j--) {
    
28.           if(stmp.count(s[j])) break;
    
29.           else stmp.insert(s[j]);
    
30.         }
    
31.         spat=stmp;
    
32.         pattern=s.substr(j, i-j);
    
33.         tmp_count=1;
    
34.       }
    
35.     } else {
    
36.       if(spat.count(s[i])) {
    
37.         if(s[i]==pattern[0]) {
    
38.           tmp=s[i];
    
39.           if(tmp_count==0) tmp_count=1;
    
40.         } else {
    
41.           int j=i-pattern.length();
    
42.           for(; s[j]!=s[i]; j++) {
    
43.             spat.erase(s[j]);
    
44.           }
    
45.           pattern=s.substr(j, i-j);
    
46.           tmp=s[j];
    
47.           tmp_count=1;
    
48.          }
    
49.       } else {
    
50.         spat.insert(s[i]);
    
51.         pattern+=s[i];
    
52.         tmp_count=1;
    
53.       }
    
54.     }
    
55.   }
    
56.   return count;
    
57. }
    
58. 
    
59. int main() {
    
60.   string s="ababababababcdeabcdeabcdedede";
    
61.   cout<<s<<endl;
    
62.   cout<<eval(s)<<endl;
    
63.   return 0;
    
64. }
    

复制代码

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

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

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

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

想问LZ第二轮的follow up有什么思路呢

同问第二轮

wsrrzxl 发表于 2016-12-4 01:33
同问第二轮

见回复

凑字数凑字数凑字数凑字数

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

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

catinclay 发表于 2016-12-4 02:23
谢谢回覆
所以是用类似bucket sort的方式吗？
不然在sort那个queue的时候复杂度就是O(nlgn)了耶？

counting sort的话就是O(n)了

楼主在哪里面，我也是12/1面，在tech corner

楼主第一题什么意思啊  没看懂。。。这个m是啥？

小A要当码农 发表于 2016-12-5 06:13
楼主第一题什么意思啊  没看懂。。。这个m是啥？

抱歉。m是substring里unique character的个数。