Google 前端 onsite

看见地里面gg前端的很少，特来贡献，希望能帮助大家，壮大前端队伍。求米~
共5轮，1轮纯算法，4轮JavaScript

第一轮：算法

给出 wifi 发射点的覆盖距离，和一些 1D 的房子坐标，求需最少要几个 wifi 发射点（one pass 就能解出来）
follow up：给出最多可以安装的发射点的数量，求发射点最覆盖距离（用房子总长除以发射点数量得到最大覆盖距离，用二分法套到第一个解写出来的函数里不断尝试从1到最大覆盖）

第二轮：

第一题：上了一段写的很烂的代码，让你简化，把一些

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

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

都可以做。懒得设计 stack 怎么存了，就用了 recursion。

感觉谷歌对细节的要求很高。出题做起来很容易在小地方犯错误导致出不来。偏算法。面试官不太爱说话，场面有时候会很尴尬……也不知道是对了还是错了。还没出结果，答案不能用来参考嘿嘿

谢谢大家，求米！

再次谢谢楼主的经验贴，在这贴一下当时准备面试的时候准备的第四轮的代码
（假定只存在tagName, ID, class三种情况，因为45分钟如果能把特殊情况都考虑进去的话我觉得有点假。。。）
比如如果是selector_str   = 'div#main p p.red span'
因为浏览器解析selector是从右到左的，所以我的思路是先找到最右的selector，找出所有满足的结果－即先找出所有的span元素
然后根据浏览器解析的原则进行dfs，找出满足条件的元素，即他们的parent element能满足前一个selector － 看找出的span元素的父节点是否有满足p.class 的，如果有，继续向上dfs
最后返回dfs后的元素

1. var SELECTOR = function (selector, node) {
   
2.     node = node || document;
   
3.     var fns, getBySingleSelector, res;
   
4. 
   
5.     //check if the selector is valid
   
6.     if (typeof selector !== 'string') return [];
   
7. 
   
8.     selector = selector.split(' '); //[#main, li.selected a]
   
9. 
   
10.     fns = {
    
11.         id: function (sel) {
    
12.             return document.getElementById(sel); //return an Element Object
    
13.         },
    
14.         get: function (c_or_e, sel, par) {
    
15.             par = par || document;
    
16.             var i, len, temp,
    
17.                 arr = [],
    
18.                 get_what = (c_or_e === 'class') ? 'getElementsByClassName' : 'getElementsByTagName';
    
19.             //parent - node, nodeList, dom
    
20. 
    
21.             if (par.length > 1) {
    
22.                 i = 0;
    
23.                 len = par.length;
    
24.                 while (i < len) {
    
25.                     temp = par[i++][get_what](sel);
    
26.                     Array.prototype.push.apply(arr, Array.prototype.slice.call(temp)); //because temp is an object
    
27.                 }
    
28.             } else {
    
29.                 arr = par[get_what](sel); //?
    
30.             }
    
31. 
    
32.             return arr;
    
33.         },
    
34.         eleFilter: function(c_or_e, sel, arr){
    
35.             if(arr === null || arr.length === 0) return arr;
    
36.             var i,ele,
    
37.                 isClass,
    
38.                 len = arr.length,
    
39.                 res = [];
    
40. 
    
41.             isClass = c_or_e === 'class' ? true : false
    
42. 
    
43.             for(i = 0; i < len; i++){
    
44.                 ele = arr[i];
    
45.                 if((isClass&&ele.className.indexOf(sel) !== -1) || (!isClass && ele.nodeName === sel.toUpperCase()))
    
46.                     res.push(ele);
    
47.             }
    
48. 
    
49.             return res;
    
50.         },
    
51.         eleValid: function(sel, node){
    
52.             if(sel === null || sel.length === 0) return true;
    
53. 
    
54.             if(sel.indexOf('#') > -1){
    
55.                 sel = sel.split('#');
    
56.                 if(fns.id(sel[1]) !== node) return false;
    
57.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
    
58.             }else if(sel.indexOf('.') > -1){
    
59.                 sel = sel.split('.');
    
60.                 var i = 1, len = sel.length;
    
61.                 for(i; i < len; i++){
    
62.                     if(node.className.indexOf(sel[i]) === -1) return false;
    
63.                 }
    
64.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
    
65.             }else{
    
66.                 return node.nodeName === sel.toUpperCase();
    
67.             }
    
68. 
    
69.             return true;
    
70.         }
    
71.     };
    
72. 
    
73.     getBySingleSelector = function(sel){
    
74.         var res = [], rep, i, len;
    
75.         if(sel === null || sel.length === 0 || typeof sel !== 'string') return [];
    
76.         if(sel.indexOf('#') > -1){
    
77.             sel = sel.split('#');
    
78.             rep = fns.id(sel[1]);
    
79.             if(sel[0].length > 0 && rep.nodeName !== sel[0].toUpperCase()) rep = null;
    
80.             res.push(rep);
    
81.         }else if(sel.indexOf('.') > -1){
    
82.             sel = sel.split('.');
    
83.             len = sel.length;
    
84.             res = fns.get('class',sel[1]);
    
85.             for(i = 2; i < len; i++){
    
86.                 res = fns.eleFilter('class',sel[i],res);
    
87.                 if(res.length === 0) break;
    
88.             }
    
89.             if(res.length > 0 && sel[0].length > 0){
    
90.                 res = fns.eleFilter('tag',sel[0],res);
    
91.             }
    
92.         }else{
    
93.             res = fns.get('tag', sel);
    
94.         }
    
95. 
    
96. 
    
97.         return res;
    
98.     };
    
99. 
    
100. 
     
101. 
     
102.     function dfs(node, curNode, res, selectors, index){
     
103.         if(index === -1){
     
104.             if(curNode !== document && res.indexOf(node) === -1) res.push(node);
     
105.             return;
     
106.         }
     
107. 
     
108.         if(curNode === document) return;
     
109. 
     
110.         var sel = selectors[index];
     
111.         if(fns.eleValid(sel, curNode)){
     
112.             dfs(node, curNode.parentNode, res, selectors, index-1);
     
113.         }else{
     
114.             dfs(node, curNode.parentNode, res, selectors, index);
     
115.         }
     
116.     }
     
117. 
     
118.     function genFinalRes(input,selector){
     
119.         if(selector.length < 2) return input;
     
120.         var res = [];
     
121.         for(var i = 0; i < input.length; i++){
     
122.             var node = input[i];
     
123.             dfs(node, node.parentNode, res, selector,selector.length-2);
     
124.         }
     
125. 
     
126.         return res;
     
127. 
     
128.     }
     
129. 
     
130. 
     
131.     res = genFinalRes(getBySingleSelector(selector[selector.length-1]),selector);
     
132. 
     
133.     return res;
     
134. 
     
135. };

复制代码

参考了https://code.tutsplus.com/tutorials/building-a-simple-css-selector-engine--net-16389
https://github.com/jquery/sizzle

第一题WIFI覆盖是半径吗？如果是一个圆的话求one pass的思路！

谢谢楼主，实在是太有用啦~~~楼主早点有好消息哈~~

伤的彻底 发表于 2016-10-8 09:47
第一题WIFI覆盖是半径吗？如果是一个圆的话求one pass的思路！

lz说了是1D的

qingmo 发表于 2016-11-12 05:07
再次谢谢楼主的经验贴，在这贴一下当时准备面试的时候准备的第四轮的代码
（假定只存在tagName, ID, class ...

赞一个！

谢谢分享，赞。。

算法必须用js写吗？

LZ 第一题的follow up能不能给出更多的detail 感谢

f1371342385 发表于 2017-4-9 07:18
LZ 第一题的follow up能不能给出更多的detail 感谢

我觉得follow up的意思是，已知房子的坐标[x1, x2, x3, ...xn]，然后和可以安装的最多的wifi 发射点数目max，求wifi发射点的最小覆盖距离 d。
思路是，1. 安装最多的WiFi发射点 max，能保证wifi发射点的覆盖距离d最小。
2. 然后安装max 个WiFi发射点情况下，当dmax = (xn - x1) / max时候，只有WiFi发射点均匀分布，就能覆盖所有的房子
3. 但是步骤2的dmax是最差情况，所有我们可以用二分法[1, dmax], 求得当前的d,只要d满足能够覆盖所有的房子，我们就寻找下一个更小的d，知道找到刚刚好覆盖所有房子的最小的覆盖距离。

这一题有个疑问就是，不断二分后，可能最终要迭代很多次后，比如wifi覆盖距离被缩短到[5.1， 5.11]类似这样的范围，这时候要找个方法来终止迭代