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

面完很久了，今天来把题目贴一下，希望对后面面试的同学有帮助。

第一轮：
感觉是中国人，二话不说贴题，应该是挂在这轮了，还有15分钟贴上第三题 T_T 没写完，当时就感觉完蛋了
Q1: Assume you have a deck of cards. Each card has a number on it with no suit. We define “X of a kind” as X cards with same number on it (X >= 2). Determine if the deck can be fully divided into sets of “X of a kind”.

Example: 3, 5, 3, 5, 3 -> True

3, 3, 5, 3, 3 -> False

Q2: Define “Straight” as 5 cards with consecutive numbers. Determine if the deck can be fully divided into sets of “Straight”.

Example: 1, 2, 3, 4, 4, 5, 5, 6,

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

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

Copy with random pointer

[size=13.3333px]

[size=13.3333px]😂面试过程超搞笑，在学校图书馆面，第一轮的时候一个小哥过来说这屋子我预定了，你出去，阿三哥：求你别让我走..我在面试...

[size=13.3333px]第二轮的时候火警响了，好像今天学校火警演练，来了三拨人说你不要命了，赶紧出去，阿三哥：求你别让我走...我在面试...

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. }
     

复制代码

写了下第一轮第二问，楼主可以详细讲讲第三问怎么做吗？

1. public class Straight {
   
2.        
   
3.         static class Point {
   
4.                 int val;
   
5.                 int count;
   
6.                
   
7.                 public Point(int val, int count) {
   
8.                         this.val = val;
   
9.                         this.count = count;
   
10.                 }
    
11.         }
    
12.         public static boolean isExactXStraight(int[] nums, int x) {
    
13.                 if (nums == null || nums.length < x) {
    
14.                         return false;
    
15.                 }
    
16.                 PriorityQueue<Point> pq = new PriorityQueue<Point>(11, new Comparator<Point>() {
    
17.                         public int compare(Point p1, Point p2) {
    
18.                                 return p1.val - p2.val;
    
19.                         }
    
20.                 });
    
21.                 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    
22.                 for (int i : nums) {
    
23.                         if (map.containsKey(i)) {
    
24.                                 map.put(i, map.get(i) + 1);
    
25.                         } else {
    
26.                                 map.put(i, 1);
    
27.                         }
    
28.                 }
    
29.                 for (int key : map.keySet()) {
    
30.                         pq.offer(new Point(key, map.get(key)));
    
31.                 }
    
32.                 while (!pq.isEmpty()) {
    
33.                         List<Point> list = new ArrayList<Point>();
    
34.                         Point prev = pq.poll();
    
35.                         list.add(prev);
    
36.                         for (int i = 1; i < x; i++) {
    
37.                                 if (pq.isEmpty()) {
    
38.                                         return false;
    
39.                                 }
    
40.                                 Point cur = pq.poll();
    
41.                                 list.add(cur);
    
42.                                 if (cur.val != prev.val + 1) {
    
43.                                         return false;
    
44.                                 }
    
45.                                 prev = cur;
    
46.                         }
    
47.                         for (Point p : list) {
    
48.                                 p.count = p.count - 1;
    
49.                                 if (p.count != 0) {
    
50.                                         pq.offer(p);
    
51.                                 }
    
52.                         }
    
53.                 }
    
54.                
    
55.                 return true;
    
56.         }
    
57.        
    
58.         public static void main(String[] args) {
    
59.                 int[] nums = {1, 2, 3, 4, 4, 5, 5, 6, 7, 8};
    
60.                 boolean res = isExactXStraight(nums, 5);
    
61.                 System.out.println(res);
    
62.         }
    
63. }

复制代码

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

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

这印度朋友太倒霉了吧。。。

leixiang5 发表于 2015-12-19 06:30
这印度朋友太倒霉了吧。。。

这就是命... 面试官还问，要不先这样吧，火大不？ =_= 最后时间到了还多给了他几分钟～

bearcat001 发表于 2015-12-19 06:35
这就是命... 面试官还问，要不先这样吧，火大不？ =_= 最后时间到了还多给了他几分钟～

火警这么响。也能继续面啊。

maximum increasing subsequence是指longest increasing subsequence吗？In tree指的是tree的in-order traversal吗？

leixiang5 发表于 2015-12-19 06:40
火警这么响。也能继续面啊。

火警演练，声音不是很大，也没有响很久。如果是真的火警那就说啥也得撤了 － －

bearcat001 发表于 2015-12-19 06:42
火警演练，声音不是很大，也没有响很久。如果是真的火警那就说啥也得撤了 － －

你朋友还真硬。。
我倒是遇过面试官的building火警。。重新安排面试了。。

straight那个题怎么实现？

tanpf5 发表于 2015-12-19 09:23
straight那个题怎么实现？

你说的是哪一问？