10月23日onsite面试

报一个google onsite的面经， 攒攒攒攒攒人品，回报地里！
面的时间比较久远了，其中经历也有点小波折。
10月23号面的，一共四轮（虽然我也很好奇为什么我只有四轮，具体原因我也不太清楚）
第一轮
上来就是OOD的题目。让我设计一个手机的打字输入法，然后我蒙了一下就开始巴拉巴拉扯，说了下Trie树，然后写了一点interface，面试官问怎么样improve搜索的efficiency，然后我说就把可能的word都存起来，放在trie的node里边，然后他提了几个这样做的不足，然后我就说另外弄一个map存一下每个word的出现频率之类的提高效率。最后再用pointer来节省空间。

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

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

没有过，现在想想觉得要是大家觉得自己简历不够strong还是找人推比较合适。
下午recruiter打了电话 告诉我hiring committe通过了，接下来还有一大堆流程。然后组match，请问地里的各位，这一阶段是不是还有风险啊，比如说组没有match上还是有可能挂掉？
保佑正式 offer快快来，攒攒攒人品，希望大家也一帆风顺！

写了下sort array a*x^2 + bx + c的代码，这题代码量也不少啊。。。

1. public class SortSortedArray {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {-5, -3, -1, 0, 4, 9, 11, 13};
   
5.                 int[] res = sortSortedArray(arr, -1, 2, 0);
   
6.                 for (int i : res) {
   
7.                         System.out.print(i + " ");
   
8.                 }
   
9.         }
   
10.         public static int[] sortSortedArray(int[] arr, int a, int b, int c) {
    
11.                 int pivot = -b / (2 * a);
    
12.                 int[] res = new int[arr.length];
    
13.                 int index = findPivot(arr, pivot);
    
14.                 int left = index;
    
15.                 int right = index + 1;
    
16.                 boolean faceUp = true;
    
17.                 if (a < 0) {
    
18.                         faceUp = false;
    
19.                 }
    
20.                 int pos = 0;
    
21.                 if (faceUp) {
    
22.                         while (left >= 0 && right < arr.length) {
    
23.                                 if (getResult(arr[left], a, b, c) > getResult(arr[right], a, b, c)) {
    
24.                                         res[pos++] = getResult(arr[right], a, b, c);
    
25.                                         right++;
    
26.                                 } else {
    
27.                                         res[pos++] = getResult(arr[left], a, b, c);
    
28.                                         left--;
    
29.                                 }
    
30.                         }
    
31.                         while (left >= 0) {
    
32.                                 res[pos++] = getResult(arr[left], a, b, c);
    
33.                                 left--;
    
34.                         }
    
35.                         while (right < arr.length) {
    
36.                                 res[pos++] = getResult(arr[right], a, b, c);
    
37.                                 right++;
    
38.                         }
    
39.                 } else {
    
40.                         pos = res.length - 1;
    
41.                         while (left >= 0 && right < arr.length) {
    
42.                                 if (getResult(arr[left], a, b, c) > getResult(arr[right], a, b, c)) {
    
43.                                         res[pos--] = getResult(arr[left], a, b, c);
    
44.                                         left--;
    
45.                                 } else {
    
46.                                         res[pos--] = getResult(arr[right], a, b, c);
    
47.                                         right++;
    
48.                                 }
    
49.                         }
    
50.                         while (left >= 0) {
    
51.                                 res[pos--] = getResult(arr[left], a, b, c);
    
52.                                 left--;
    
53.                         }
    
54.                         while (right < arr.length) {
    
55.                                 res[pos--] = getResult(arr[right], a, b, c);
    
56.                                 right++;
    
57.                         }
    
58.                 }
    
59.                 return res;
    
60.         }
    
61. 
    
62.         private static int getResult(int i, int a, int b, int c) {
    
63.                 return a * i * i + b * i + c;
    
64.         }
    
65. 
    
66.         private static int findPivot(int[] arr, int pivot) {
    
67.                 int start = 0;
    
68.                 int end = arr.length - 1;
    
69.                 while (start + 1 < end) {
    
70.                         int mid = (end - start) / 2 + start;
    
71.                         if (arr[mid] == pivot) {
    
72.                                 return mid;
    
73.                         } else if (arr[mid] > pivot) {
    
74.                                 end = mid;
    
75.                         } else {
    
76.                                 start = mid;
    
77.                         }
    
78.                 }
    
79.                 if (arr[end] <= pivot) {
    
80.                         return end;
    
81.                 } else {
    
82.                         return start;
    
83.                 }
    
84.         }
    
85. }
    

复制代码

您好！
本帖隐藏的内容需要积分高于 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

谢谢LZ分享， 走迷宫那题能具体说下做法吗？

请问第三轮的哪个扫描线是只能两两overlap吗还是说会出现[1,10],[2,7],[3,11]这种？

宝贝忆彼岸 发表于 2015-11-18 10:31
请问第三轮的哪个扫描线是只能两两overlap吗还是说会出现[1,10],[2,7],[3,11]这种？

是都可以overlap哦，会出现[1,10],[2,7],[3,11]这样的情况

hhllryslh 发表于 2015-11-18 12:01
是都可以overlap哦，会出现[1,10],[2,7],[3,11]这样的情况

哦哦，感觉有点难，我只想到brute force。。。请问lz是怎么答的？

就是得自己建一个struct 里边有它端点数值 和bool表示它是否是start，然后放在priority queue里边一个一个pop出来 发现一个start就加一 发现一个end就减一 然后得维持一个pair里边存放的就是overlap的段

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

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

hhllryslh 发表于 2015-11-18 09:52
就是
得定义一个 Point struct
struct Point{

谢谢LZ 只要走到出口就行了吗？ 还是要求最短路径或者其他的什么？

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

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