Drawbridge SDE/Hadoop 电面

其实我申请的是sde，不过hr说我们觉得这个hadoop挺适合你的……经验啥的不要紧……面试官是提前告知的，天竺老哥。面之前看了下他的领英就觉得没有任何交集，希望他到时候只问算法题就好，不要蛋疼。
先吐槽codepair，在mac上打电话无法开启外接摄像头和话筒，折腾了几分钟没修好，只能用手机打电话。听得出来面试官有点不爽……劝大家如果用这个工具面试要提前测试。上来先问了下职业规划啥的……

题目：给了一个JSON，还有两个字符串列表primaryKeys和secondaryKeys，要求返回JSON中第一个属于primaryKeys的key对应的value（以字符串形式），如果没有，那就第一个属于secondaryKeys的，再没有就返回空字符串。这些keys有可能是嵌套在某个object里的。举例，给了如下JSON：

{
    "firstName": "John&quo

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

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

他存心想让我自己搞清楚，还是他水平问题。现在想想当时写的还是可以优化的，没有必要把JSON转化成unordered_map，直接每发现一个key就在两个列表里面找，既省时间又省空间。

答完题之后我随便问了问他的日常工作，好像也涉及广告投放什么的。问了问工作环境如何，答曰很适合新人学习。本来还想调戏一下，问他有什么理由放弃大公司加入他们，最终没有问。哈哈，一场双方印象都不好的面试，就当是多刷了一题吧。地里这个公司的面经也少，顺便作点微小的贡献。

好吧，我就再写一遍代码。以下是测试通过的。不过我按照面试中的输入格式，把JSON中的空格和换行都除去了。

1. #include <iostream>
   
2. #include <string>
   
3. #include <unordered_set>
   
4. #include <cctype>
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8.     unordered_set<string> primaryKeys, secondaryKeys;
   
9.     string primaryValue = "", secondaryValue = "";
   
10.     int findMatchingBracket(string s, int pos, string brackets) {
    
11.         int cnt = 0, n = s.length();
    
12.         for (int j = pos; j < n; j++) {
    
13.             if (s[j] == brackets[0]) cnt++;
    
14.             if (s[j] == brackets[1]) cnt--;
    
15.             if (cnt == 0) return j;
    
16.         }
    
17.     }
    
18.     int findMatchingQuotation(string s, int pos) {
    
19.         int n = s.length();
    
20.         for (int j = pos + 1; j < n; j++)
    
21.             if (s[j] == '"' && s[j - 1] != '\\') return j;
    
22.     }
    
23.     void findKey(string obj) {
    
24.         int n = obj.length();
    
25.         for (int i = 0; i < n; i++) {
    
26.             if (obj[i] != '"') continue;
    
27.             int endOfKey = findMatchingQuotation(obj, i);
    
28.             int startOfValue = endOfKey + 2, endOfValue;
    
29.             string key = obj.substr(i + 1, endOfKey - i - 1), value;
    
30. 
    
31.             // value is an object
    
32.             if (obj[startOfValue] == '{')
    
33.                 endOfValue = findMatchingBracket(obj, startOfValue, "{}");
    
34.             // value is an array
    
35.             if (obj[startOfValue] == '[')
    
36.                 endOfValue = findMatchingBracket(obj, startOfValue, "[]");
    
37.             // value is a number
    
38.             if (isdigit(obj[startOfValue]))
    
39.                 endOfValue = obj.find_first_not_of("0123456789.", startOfValue + 1) - 1;
    
40.             // value is a string
    
41.             if (obj[startOfValue] == '"')
    
42.                 endOfValue = findMatchingQuotation(obj, startOfValue);
    
43.             value = obj.substr(startOfValue, endOfValue - startOfValue + 1);
    
44. 
    
45.             if (primaryKeys.count(key)) {
    
46.                 primaryValue = value;
    
47.                 return;
    
48.             }
    
49.             if (secondaryValue == "" && secondaryKeys.count(key))
    
50.                 secondaryValue = value;
    
51.             if (value[0] == '{') findKey(value);
    
52.             if (primaryValue != "") return;
    
53.             i = endOfValue;
    
54.         }
    
55.     }
    
56. public:
    
57.     string getValue(string obj, unordered_set<string> primary, unordered_set<string> secondary) {
    
58.         primaryKeys = primary;
    
59.         secondaryKeys = secondary;
    
60.         findKey(obj);
    
61.         return primaryValue != "" ? primaryValue : secondaryValue;
    
62.     }
    
63. };
    
64. 
    
65. int main() {
    
66.     Solution sol;
    
67.     string s = "{\"firstName\":\"John\",\"lastName\":\"Smith\",\"sex\":\"male\",\"age\":25,\"address\":{\"streetAddress\":\"212ndStreet\",\"city\":\"NewYork\",\"state\":\"NY\",\"postalCode\":\"10021\"},\"phoneNumber\":[{\"type\":\"home\",\"number\":\"212555-1234\"},{\"type\":\"fax\",\"number\":\"646555-4567\"}]}";
    
68.     cout << sol.getValue(s, {"streetAddress"}, {"age"}) << endl;
    
69.     return 0;
    
70. }

复制代码

lyh2017 发表于 2018-1-23 05:36
谢谢楼主啊，能不能问一下你的面试官叫什么名字啊

你搜nandish加公司名就能搜到。

谢谢楼主啊，能不能问一下你的面试官叫什么名字啊

好的好的，谢谢楼主。。。。。

请问楼主这题对于string的解析，是完全自己手动写递归还是可以用json的包？另外的话，“第一个属于primaryKeys的key对应的value”，是不是意味着每一层的keys是有先后关系的？比方说在你的例子里，firstname就比lastname的顺序要先

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

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

Spinoza 发表于 2018-1-26 21:41
我是自己手写的。我之前完全不熟JSON，也不知道有没有包……看面试官的意思，就是要考我自己写递归的。第 ...

感觉纯手写递归好难！很复杂的字符串

Avogadro 发表于 2018-1-27 03:04
感觉纯手写递归好难！很复杂的字符串

没想象中那么难的，分类讨论一下就好，只有数组、对象、数字、字符串四种情况。

楼主是先用递归转化成Map<String, Object>的嵌套？是用LinkedHashMap去维持先后关系？

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

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