狗家new Gard店面

贡献一发面筋，白人大叔，没有问简历也没有让提问，开始直接做题，45分钟结束直接挂，面的太失败了。

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

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

希望高抬贵手吧


补充内容 (2018-10-17 05:37):
3. a{c, {a,b}} -> aca acb
更正为a{c{a,b}}

补充内容 (2018-10-22 07:57):
https://www.careercup.com/question?id=5717301963784192
类似的题目的解法 

补充内容 (2018-10-24 04:58):
接到电话 告诉我跪了。。

AaLlC 发表于 2018-10-17 05:59
对的 这个是面试官的第一问，就是第一种情况
你觉得好写吗？

我觉得超级难………………情况太多了……那再请问一下会不会出现{a,b}c{a,b}这样的情况呀……

LaSeineFirenze 发表于 2018-10-25 14:27
我试着写了下，感觉45分钟能把思路讲清就不错了，bug-free基本做不到，这还是用recursion，要是一开始就想 ...

刚才咋没贴出来……

1. 
   
2. vector<string> getNested(string s) {
   
3.     s += ',';
   
4.     vector<string> res, last{""}, cur, tmp;
   
5.      
   
6.     for (int i=0; i<s.size(); i++) {
   
7.         if (s[i] == ',') {
   
8.             for (int j=0; j<last.size(); j++)
   
9.                 res.push_back(last[j]);
   
10.             
    
11.             last = {""};
    
12.         } else {
    
13.             cur.clear();
    
14.             if (s[i] == '{') {
    
15.                 int count = 1;
    
16.                 int j = i+1;
    
17.                 while (j<s.size() && count>0) {
    
18.                     if (s[j]=='{') count++;
    
19.                     else if (s[j]=='}') count--;
    
20.                     j++;
    
21.                 };
    
22. //                cout << i << " " << j << endl;
    
23. //                cout << s.substr(i+1, j-i-2) << endl;
    
24.                 cur = getNested(s.substr(i+1, j-i-2));
    
25.                 i = j-1;
    
26.             } else
    
27.                 cur.push_back(string(1, s[i]));
    
28. 
    
29.             tmp.clear();
    
30.             for (int j=0; j<last.size(); j++) {
    
31.                 for (int k=0; k<cur.size(); k++) {
    
32.                     tmp.push_back(last[j] + cur[k]);
    
33. //                    cout << tmp.back() << " ";
    
34.                 }
    
35. //               cout << endl;
    
36.             }
    
37.             last = tmp;
    
38.         }
    
39.     }
    
40.     return res;
    
41. }
    
42. 
    
43. vector<string> expandS(string s) {
    
44.     vector<string> res = getNested(s);
    
45.     for (auto r : res)
    
46.         cout << r << " ";
    
47.     cout << endl;
    
48.     return res;
    
49. }
    
50. 
    
51. int main() {
    
52.     expandS("a,b,c");
    
53.     expandS("a{b,c}");
    
54.     expandS("{a,b}{c,d}");
    
55.     expandS("{a,b}{c,d},e");
    
56.     expandS("f{a,b}{c,d},e");     
    
57.     expandS("a{c{a,b}}");
    
58.     expandS("d{c,{a,b}}");   
    
59.     expandS("a{b,c}d");
    
60.     return 0;
    
61. }
    

复制代码

我试着写了下，感觉45分钟能把思路讲清就不错了，bug-free基本做不到，这还是用recursion，要是一开始就想着用stack写估计就凉凉了

1. // Nested
   
2. vector<string> getNested(string s) {
   
3.     s += ',';
   
4.     vector<string> res, last({""}), cur, tmp;
   
5.    
   
6.     for (int i=0; i<s.size(); i++) {
   
7.         if (s[i] == ',') {
   
8.             for (int j=0; j<last.size(); j++)
   
9.                 res.push_back(last[j]);
   
10.             
    
11.             last = {""};
    
12.         }
    
13.         else {
    
14.             cur.clear();
    
15.             if (s[i] == '{') {
    
16.                 int j = s.size()-1;
    
17.                 while (s[j] != '}') j--;
    
18.                 cur = getNested(s.substr(i+1, j-i-1));
    
19.                 i = j;
    
20.             }
    
21.             else
    
22.                 cur.push_back(string(1, s[i]));
    
23. 
    
24.             tmp.clear();
    
25.             for (int j=0; j<last.size(); j++)
    
26.                 for (int k=0; k<cur.size(); k++)
    
27.                     tmp.push_back(last[j] + cur[k]);
    
28.             
    
29.             last = tmp;
    
30.         }
    
31.     }
    
32.    
    
33.     return res;
    
34. }

复制代码

补充内容 (2018-10-25 14:38):
果然还是有bug......中间找大括号的地方写错了QAQ

感谢lz的分享！可以请问一下lz什么时候面的么？？

补充内容 (2018-10-17 05:21):
还有请问3那个例子里面，如果答案是aca和acb的话，为什么c和{a,b}之间会有","呢？请问是不是也可以理解为变成{ac,a{a,b}}=>ac,aa,ab呢？

笛卡尔乘积的话 ，3. a{c, {a,b}} -> aca acb 这个是怎么得到的呀？

SakuraBlossom 发表于 2018-10-17 05:15
感谢lz的分享！可以请问一下lz什么时候面的么？？

补充内容 (2018-10-17 05:21):

十分钟之前
就相当于nested的元素

补充内容 (2018-10-17 05:39):
你的理解没错

caragao 发表于 2018-10-17 05:26
笛卡尔乘积的话 ，3. a{c, {a,b}} -> aca acb 这个是怎么得到的呀？

 错啦 c 和 {a,b} 没有逗号

不好意思～
3. a{c, {a,b}} -> aca acb
更正为a{c{a,b}}

AaLlC 发表于 2018-10-17 05:35
十分钟之前
就相当于nested的元素

不好意思lz，想再请问一个问题……像c{a,b}d这样的情况，结果是不是就是cad,cbd呢？相当于括号里的每个元素都要加上前后的character？

SakuraBlossom 发表于 2018-10-17 05:46
不好意思lz，想再请问一个问题……像c{a,b}d这样的情况，结果是不是就是cad,cbd呢？相当于括号里的每个元 ...

对的 这个是面试官的第一问，就是第一种情况
你觉得好写吗？

SakuraBlossom 发表于 2018-10-17 06:04
我觉得超级难………………情况太多了……那再请问一下会不会出现{a,b}c{a,b}这样的情况呀……

会的呢 {}里都是有逗号分开的，可能有nested的，括弧外面就是直接连在一起的，就是直接乘开。
类似多项式展开。。