Google 11月19号 实习面经 和 12月18号 旁观面经

隐隐野烟 发表于 2015-12-26 02:04
原数组先要sort吗？
比如原数组为[2,3,4,5,1]

面试时说可以认为是有序的

bearcat001 发表于 2015-12-26 14:10
面试时说可以认为是有序的

多谢，刚码完题目。

第一轮Q3怎么做？有efficient的解法吗？只想到递归。

fatalme 发表于 2015-12-27 01:36
第一轮Q3怎么做？有efficient的解法吗？只想到递归。

我也是用递归解的，暂时没有想到更好的办法

第一轮第三题 递归用backtrack可以的吧 然后把搜索过的子串记录下来

1. #include <iostream>
   
2. #include <map>
   
3. #include <vector>
   
4. #include <list>
   
5. #include <algorithm>
   
6. #include <sstream>
   
7. 
   
8. using namespace std;
   
9. 
   
10. bool can_divide_x_kind(std::vector<int> input)
    
11. {
    
12.     std::map<int, int> htable;
    
13.     for (int i = 0; i < input.size(); i++) {
    
14.         htable[input[i]] ++;
    
15.     }
    
16. 
    
17.     std::map<int, int>::iterator it = htable.begin();
    
18.     for (; it != htable.end(); it++) {
    
19.         if (it->second < 2) {
    
20.             return false;
    
21.         }
    
22.     }
    
23. }
    
24. 
    
25. bool can_divide_5straight(std::vector<int> input)
    
26. {
    
27.     std::map<int, int> htable;
    
28.     for (int i = 0; i < input.size(); i++) {
    
29.         htable[input[i]] ++;
    
30.     }
    
31. 
    
32.     while (htable.size() >= 5) {
    
33.         std::map<int, int>::iterator it = htable.begin();
    
34. 
    
35.         int val = it->first;
    
36.         it->second--;
    
37.         if (it->second == 0) {
    
38.             htable.erase(it++);
    
39.         } else {
    
40.             it++;
    
41.         }
    
42.         for (int i = 0; i < 4; i++) {
    
43.             int val1 = it->first;
    
44.             if (val1 = val + 1) {
    
45.                 it->second--;
    
46.                 if (it->second == 0) {
    
47.                     htable.erase(it++);
    
48.                 } else {
    
49.                     val = val1;
    
50.                     it++;
    
51.                 }
    
52.             } else {
    
53.                 return false;
    
54.             }
    
55.         }   
    
56.     }
    
57. 
    
58.     if (htable.size()) {
    
59.         return false;
    
60.     }
    
61.     return true;
    
62. }
    
63. 
    
64. string list_to_string(std::list<int> list)
    
65. {
    
66.     ostringstream oss;
    
67.     std::list<int>::iterator it = list.begin();
    
68.     for (; it != list.end(); it++) {
    
69.         oss << *it;
    
70.     }
    
71.     return oss.str();
    
72. }
    
73. 
    
74. int call = 0;
    
75. int ret = 0;
    
76. std::map<string, bool> memoized;
    
77. bool can_divide_x_straight(std::list<int> input)
    
78. {
    
79.     call++;
    
80.     string str = list_to_string(input);
    
81.     if (memoized.count(str)) {
    
82.         ret++;
    
83.         return memoized[str];
    
84.     }
    
85. 
    
86.     if (input.size() <= 2) {
    
87.         return false;
    
88.     }
    
89. 
    
90.     for (int i = 3; i <= input.size(); i++) {
    
91.         
    
92.         std::list<int> copy = input;
    
93.         std::list<int>::iterator it = copy.begin();
    
94.         std::list<int>::iterator it1;
    
95.         bool impossible = false;
    
96.         for (int j = 1; j <= i-1; j++) {
    
97.             it1 = it;
    
98.             while (*it1 == *it && it1 != copy.end()) {
    
99.                 it1++;
    
100.             }
     
101.             if (it1 == copy.end()) {
     
102.                 impossible = true;
     
103.                 break;
     
104.             }
     
105.             if (*it1 != *it + 1) {
     
106.                 impossible = true;
     
107.                 break;
     
108.             }
     
109.             copy.erase(it);
     
110.             it = it1;
     
111.         }
     
112.         if (impossible == true) {
     
113.             continue;
     
114.         }
     
115.         copy.erase(it);
     
116.         if (copy.size() == 0 || can_divide_x_straight(copy)) {
     
117.             string str = list_to_string(input);
     
118.             memoized[str] = true;
     
119.             return true;
     
120.         }
     
121.     }
     
122.     str = list_to_string(input);
     
123.     memoized[str] = false;
     
124.     return false;
     
125. }
     
126. 
     
127. bool comp(int i, int j) {
     
128.     return i<j;
     
129. }
     
130. 
     
131. int main(void)
     
132. {
     
133.     int vec[] = {
     
134.         1,1,2,2,3,3,4,4,5,5,5
     
135.     };
     
136. 
     
137.     std::vector<int> input(vec, vec + sizeof(vec)/sizeof(int));
     
138.     std::sort(input.begin(), input.end(), comp);   
     
139. 
     
140.     std::list<int> input1(vec, vec+ sizeof(vec)/sizeof(int));
     
141.     std::sort(input.begin(), input.end(), comp);
     
142. 
     
143.     if (can_divide_x_kind(input)) {
     
144.         cout << "1_good" <<endl;
     
145.     }
     
146. 
     
147.     if (can_divide_5straight(input)) {
     
148.         cout << "2_good" << endl;
     
149.     }
     
150. 
     
151.     if (can_divide_x_straight(input1)) {
     
152.         cout << "3_good" << " " << call << " " << ret << endl;
     
153.     } else {
     
154.         cout << call << " " << ret << endl;
     
155.     }
     
156.     return 0;
     
157. }
     

复制代码

deck的第三问是用back tracking吗

bobzhang2004 发表于 2016-1-15 00:10
deck的第三问是用back tracking吗

我是这么做的～ 我同学突然搞了个用堆解的，感觉也可以

楼主可以说一下怎么设计的pivot table吗？

bobzhang2004 发表于 2016-1-27 08:56
楼主可以说一下怎么设计的pivot table吗？

当时答的是用一个hashtable，key是两个字段名（用_分割），value是汇总信息