Drawbridge SDE/Hadoop 电面

这题就是quantcast的OA，要求少了一点而已，本来应该用3小时写的，拿来面试有点过分了。。

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

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

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

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

请问楼主如何用递归得到这种mapping呢？

请问楼主 input 是一个JSON Format 的string 吗？ 会不会有特殊case 例如key 给你"phoneNumber" 要输出哪一个？已加大米～祝offer多多

好吧，我就再写一遍代码。以下是测试通过的。不过我按照面试中的输入格式，把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. }

复制代码

pkk5488 发表于 2018-1-28 00:04
有点好奇就像这样给你一个JSON格式的string，应该怎么提取出这种mapping呢？就是具体代码大概是怎样实现 ...

我贴在16楼了。求加大米……

chz 发表于 2018-1-28 04:19
请问楼主如何用递归得到这种mapping呢？

代码我贴在16楼了。求加大米……

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

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

Spinoza 发表于 2018-1-28 12:57
我贴在16楼了。求加大米……

感觉很强，学习了