古狗电面跪经

好想混进狗家啊。
2周前在linkedin联系的HR。约了个电面。tag底下刷了2周，写了能有67十道吧。
SETI职位。英语说的别好的一个外国人面的。

第一题测试

Calculate(String"2", String "+", String"3") return 5

你会怎么测试这个函数？

我列个能想到的情况：

我就说 如果说 如果输入是"" "" &q

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

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

left">然后第三题他有说 TreeNode Snipit

我就说 前缀树，然后觉得也不太对，也不太会写就。那么地了。

第三题 主要是难在 他的那些[marks] 文本符号是互相交错的.。

提了两个问题，然后就结束了。

第三题代码都不会写。估计onsite的机会都没有了，好难过

第三题将文本“分开”的方法，比较系统的知识应该是在"Programming Languages and Compilers"这类课程里前几章关于"Lexer/Parser"的部分。

只是要做题目的话，可以用一个stack去hack出来（stack=递归，是处理树状结构的很好的方法）， 例如楼上提到的类似题目LeetCode 591，Discuss里给出的答案：
https://discuss.leetcode.com/topic/91300/java-solution-use-startswith-and-indexof

更通用一点的方法是写一个简单的“递归下降语法解析器”(recursive descent parser)——这个并不难写，而且可以解决几乎所有类似的题目，建议搜索并学习一下..

实践中需要解析文本的时候一般是用"parser generator"工具，比如flex+bison / JavaCC / Antlr之类的。这道题目非常适合词法和语法混合的LL(k)的parser generator，例如Antlr，语法部分几行代码就可以表达出来了。

会给你第二轮电面的。好好准备

第三题 recursive descend parser

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. using namespace std;
   
5. 
   
6. struct TreeNode {
   
7.     string tag;
   
8.     string text;
   
9.     vector<TreeNode*> children;
   
10.     TreeNode(string tag_, string text_) {
    
11.         tag = tag_;
    
12.         text = text_;
    
13.     }
    
14. };
    
15. 
    
16. TreeNode* parse(string& html, int& i) {
    
17.     if(html[i] == '[') {
    
18.         i++; // skip '['
    
19.         int j = html.find(']', i);
    
20.         string tag = html.substr(i, j-i);
    
21.         i = j + 1;
    
22.         
    
23.         int start = i;
    
24.         TreeNode* root = new TreeNode(tag, "");
    
25.         while(html.substr(i,2) != "[/") {
    
26.             auto child = parse(html, i);
    
27.             if(child) root->children.push_back(child);
    
28.         }
    
29.         root->text = html.substr(start, i-start);
    
30.         i += 2;
    
31.         i = html.find(']', i);
    
32.         i++;// skip ']'
    
33.         return root;
    
34.     }
    
35.     else {
    
36.         while(i < html.length() && html[i] != '[') i++; // scan all text content
    
37.         return nullptr;
    
38.     }
    
39. }
    
40. 
    
41. TreeNode* parseHtml(string& html) {
    
42.     TreeNode* root = new TreeNode("","");
    
43.     for(int i = 0; i < html.length(); ) {
    
44.         auto tmp = parse(html, i);
    
45.         if(tmp) root->children.push_back(tmp);
    
46.     }
    
47.     return root;
    
48. }
    
49. 
    
50. void printTree(TreeNode* root) {
    
51.     queue<TreeNode*> q;
    
52.     q.push(root);
    
53.     while(!q.empty()) {
    
54.         int qsize = q.size();
    
55.         while(qsize-- > 0) {
    
56.             auto top = q.front();
    
57.             q.pop();
    
58.             cout << "tag:" << top->tag << " text:" << top->text << "    ";
    
59.             for(auto c : top->children) q.push(c);
    
60.         }
    
61.         cout << endl;
    
62.     }
    
63. }
    
64. 
    
65. int main(int argc, const char * argv[]) {
    
66.     // insert code here...
    
67.     string html = "[text] Hello [/text] [bold]![/bold] [mark]word[/mark]";
    
68.     printTree(parseHtml(html));
    
69.     cout << endl;
    
70.     html = "[text] Hello [/text] [bold]abc[tiny] maketiny [/tiny]123[/bold] [mark]word[/mark]";
    
71.     printTree(parseHtml(html));
    
72.     return 0;
    
73. }
    

复制代码

胖迪加油

第三题都没看懂什么意思 是说给定  [text] Hello [/text] [bold]![/bold] [mark]word[mark]  最后让你提取出 Hello (并且标记其为text属性) 提取出"!"(标记其为bold属性) 以及提取"word"(标记其为mark属性)？

2011051305 发表于 2017-8-5 01:27
第三题都没看懂什么意思 是说给定  [text] Hello [/text] ![/bold] [mark]word[mark]  最后让你提取出 Hell ...

设计一个数据结构 分别储存文本和标记。

FightForTomo 发表于 2017-8-5 05:06
设计一个数据结构 分别储存文本和标记。

那么看起来是利扣 无玖腰 的变体？

2011051305 发表于 2017-8-5 10:12
那么看起来是利扣 无玖腰 的变体？

没做过，不知道。

谢谢分享

brn 发表于 2017-8-7 10:48
第三题就是设计一个类似于 TreeNode 的结构呗
另外你说的是 snippet 吧？

你嗦的对。