狗家昂赛特

因为snapchat家的面筋一发就有昂赛特了。。所以也发个狗家的吧。。从地里也学习到了好多东西，回报回报。。。求不被发现。。准备：LC一百四十道狗家题刷了两遍。

上周昂赛特，遇到了史上最难题吧。。

第一轮：topological sort。我写了上百遍了（DFS wik版本），但是华人大叔没太看懂为什么有两个visited set，所以解释了好久。

第二轮：
int[][]矩阵，求是否满足性质：左上角到右下角的斜线上的值都要相等。比如(0,1)(1,2),(2,3)这些要相等。
小伙伴告诉过我这题，所以我知道follow up是矩阵很大，每次只能读一行怎么办，所以我一开始就写了两行两行比较的算法，面试小哥有点蒙蒙，依然也给了这个follow up，秒了。然后还剩二十多分钟，小哥就给了第二个follow up：现在一行都太大没法读进来，但是可以允许算法不是1

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

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

之到最后是给出了一个算法，写了一点点中间步骤的代码，但是整个代码是没写的。结束的时候考官问我感觉怎么样，我说没有想到是这种数学题，他说我们希望看到你分析这个题然后写成代码的整个过程，我说可惜我还是没写完代码呀，他点点头说嗯（我就觉得完蛋了）。最后朋友圈大神说这是计算机图形学最后几章的问题，什么z buff scan算法。。。。

好的就这样，等待HR反馈。。。。我个人觉得已经发挥我所有实力了，但感觉依然有风险。。第三轮followup不好，第四轮只分析出来算法没写出代码。

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

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

我也是醉了， 这次没空格，不好意思啊。怎么删回复啊····再贴一次吧， 不要打我啊····

1. bool checkRepeating(string& s, int l, int r, int start, int end){
   
2.         if((end-start+1)%(r-l+1) != 0)
   
3.                 return false;
   
4.         int len = r-l+1;
   
5.         bool res = true;
   
6.         for(int i=start; i<=end; i++){
   
7.                 if(s[(i-start)%len+l] != s[i]){
   
8.                         res = false;
   
9.                         break;
   
10.                 }
    
11.         }
    
12.         return res;
    
13. }
    
14. 
    
15. int getLength(int l1, int l2){
    
16.         return (int)(log10(l2/l1+1)+1);
    
17. }
    
18. 
    
19. string shortestEncodeString(string s){
    
20.         int len = s.length();
    
21. 
    
22.         vector< vector<int> > res(len, vector<int>(len, 0));
    
23.         for(int i=0; i<len; i++){
    
24.                 for(int j=0; j<=i; j++){
    
25.                         res[j][i] = i-j+1;
    
26.                 }
    
27.         }
    
28. 
    
29.         unordered_map<string, string> record;
    
30. 
    
31.         for(int i=0; i<len; i++){
    
32.                 for(int j=i; j>=0; j--){
    
33. 
    
34.                         string temp = s.substr(j, i-j+1);
    
35.                         if(record.find(temp) != record.end()){
    
36.                                 res[j][i] = record[temp].size();
    
37.                                 continue;
    
38.                         }
    
39.                         string ans = temp;
    
40.                         for(int k=j; k<i; k++){
    
41.                                
    
42.                                 string str1 = s.substr(j, k-j+1);
    
43.                                 string str2 = s.substr(k+1, i-k);
    
44.                                 if(res[j][i] > res[j][k] + res[k+1][i]){
    
45.                                         res[j][i] = res[j][k]+res[k+1][i];
    
46.                                         ans = record[str1] + record[str2];
    
47.                                 }
    
48. 
    
49.                                 if(checkRepeating(s, j, k, k+1, i) == true && res[j][i] > 2+getLength(k-j+1, i-k)+res[j][k]){
    
50.                                         res[j][i] = 2+getLength(k-j+1, i-k)+res[j][k];
    
51.                                         ans = to_string((i-j+1)/(k-j+1)) + '[' + record[str1] +']';
    
52.                                 }
    
53.                         }
    
54.                         record[temp] = ans;
    
55.                 }
    
56. 
    
57.         }
    
58. 
    
59.         return record[s];
    
60. }

复制代码

第三轮那个跟我一样，原来只是个warm up啊。。怪不得我HC挂了

最后一轮竟然考gpu算法。玩游戏的知道关了阴影特效会流畅很多就知道这个复杂度挺高的了。

chestnut9919 发表于 2016-11-18 04:52
第三轮那个跟我一样，原来只是个warm up啊。。怪不得我HC挂了

T T那我凶多吉少了。。。是个亚裔姐姐。。。

SidneyFan 发表于 2016-11-18 06:04
T T那我凶多吉少了。。。是个亚裔姐姐。。。

我的是个非洲小哥 你起码还问到了followup 我写完根本没时间了 还是很有希望的

第三轮的dp思路能不能分享下? 这题想了好几天了... 没有头绪呀

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

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

chestnut9919 发表于 2016-11-18 06:09
我的是个非洲小哥 你起码还问到了followup 我写完根本没时间了 还是很有希望的

我看到你的帖子了！rotation多好啊！！！

SidneyFan 发表于 2016-11-18 06:28
我看到你的帖子了！rotation多好啊！！！

好啥啊这都是HC挂了的被扔过去，还是祝你过HC。

加油小可爱～哈哈哈