一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 1746|回复: 6
收起左侧

Google 前端 onsite

[复制链接] |试试Instant~ |关注本帖
AD0103 发表于 2016-10-8 06:54:40 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

第一轮:算法.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

第二轮:

第一题:上了一段写的很烂的代码,让你简化,把一些写的烂的地方变成可以理解的。这个就是考大家平时写代码的习惯,比如不该用 loop 的时候别用 loop,可以用 if else 的时候别用 swift。. 1point 3acres 璁哄潧
第二题:求两个 string 的 common prefix(从头开始比较即可)
follow up:怎么优化(用二分法). 鍥磋鎴戜滑@1point 3 acres
. more info on 1point3acres.com
第三轮:

考察简单的用 JS 处理数据的思路。说给一个网页,跟一个 getHash 函数,求返回页面里所的 img,要求用 hash 去重。就用简单的 DOM API,中间需要用到 promise(或者 callback)来获取 image data 给 getHash 用来计算 hash。用什么不重要,主要看你习不习惯 JS 里面的 async flow control。
. 1point3acres.com/bbs
第四轮:
.1point3acres缃
要求实现 querySelectorAll。没思路,没答好,感觉应该看看 jQuery 源代码就没问题。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. visit 1point3acres.com for more.第五轮:

Decode string,输入 2[ab]2[c3[d]],要求输出 ababcdddcddd。只考虑重复的部分是 letter 的情况。但是就像大家已经看到的,[ ] 是可以套多层的。用 stack 或者 recursion 都可以做。懒得设计 stack 怎么存了,就用了 recursion。

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

谢谢大家,求米!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

qingmo 发表于 2016-11-12 05:07:43 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
再次谢谢楼主的经验贴,在这贴一下当时准备面试的时候准备的第四轮的代码
(假定只存在tagName, ID, class三种情况,因为45分钟如果能把特殊情况都考虑进去的话我觉得有点假。。。)
比如如果是selector_str   = 'div#main p p.red span'
因为浏览器解析selector是从右到左的,所以我的思路是先找到最右的selector,找出所有满足的结果-即先找出所有的span元素. 1point3acres.com/bbs
然后根据浏览器解析的原则进行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.     //check if the selector is valid
  5.     if (typeof selector !== 'string') return [];

  6.     selector = selector.split(' '); //[#main, li.selected a]

  7.     fns = {
  8.         id: function (sel) {. more info on 1point3acres.com
  9.             return document.getElementById(sel); //return an Element Object
  10.         }, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.         get: function (c_or_e, sel, par) {
  12.             par = par || document;
  13.             var i, len, temp,. 鍥磋鎴戜滑@1point 3 acres
  14.                 arr = [],
  15.                 get_what = (c_or_e === 'class') ? 'getElementsByClassName' : 'getElementsByTagName';-google 1point3acres
  16.             //parent - node, nodeList, dom

  17.             if (par.length > 1) {
  18.                 i = 0;
  19.                 len = par.length;
  20.                 while (i < len) {
  21.                     temp = par[i++][get_what](sel);
  22.                     Array.prototype.push.apply(arr, Array.prototype.slice.call(temp)); //because temp is an object
  23.                 }
  24.             } else {
  25.                 arr = par[get_what](sel); //?.鏈枃鍘熷垱鑷1point3acres璁哄潧
  26.             }

  27.             return arr;
  28.         },. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.         eleFilter: function(c_or_e, sel, arr){
  30.             if(arr === null || arr.length === 0) return arr;
  31.             var i,ele,.1point3acres缃
  32.                 isClass,
  33.                 len = arr.length,
  34.                 res = [];
  35. . 1point3acres.com/bbs
  36.             isClass = c_or_e === 'class' ? true : false

  37.             for(i = 0; i < len; i++){
  38.                 ele = arr[i];
  39.                 if((isClass&&ele.className.indexOf(sel) !== -1) || (!isClass && ele.nodeName === sel.toUpperCase()))
  40.                     res.push(ele);
  41.             }

  42.             return res;
  43.         },.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.         eleValid: function(sel, node){
  45.             if(sel === null || sel.length === 0) return true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  46. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  47.             if(sel.indexOf('#') > -1){
  48.                 sel = sel.split('#');
  49.                 if(fns.id(sel[1]) !== node) return false;
  50.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
  51.             }else if(sel.indexOf('.') > -1){.1point3acres缃
  52.                 sel = sel.split('.');
  53.                 var i = 1, len = sel.length;
  54.                 for(i; i < len; i++){
  55.                     if(node.className.indexOf(sel[i]) === -1) return false;
  56.                 }
  57.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
  58.             }else{
  59.                 return node.nodeName === sel.toUpperCase();. Waral 鍗氬鏈夋洿澶氭枃绔,
  60.             }

  61.             return true;
  62.         }
  63.     };

  64.     getBySingleSelector = function(sel){. Waral 鍗氬鏈夋洿澶氭枃绔,
  65.         var res = [], rep, i, len;
  66.         if(sel === null || sel.length === 0 || typeof sel !== 'string') return [];
  67.         if(sel.indexOf('#') > -1){
  68.             sel = sel.split('#');
  69.             rep = fns.id(sel[1]);. 1point3acres.com/bbs
  70.             if(sel[0].length > 0 && rep.nodeName !== sel[0].toUpperCase()) rep = null;
  71.             res.push(rep);. From 1point 3acres bbs
  72.         }else if(sel.indexOf('.') > -1){
  73.             sel = sel.split('.');
  74.             len = sel.length; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  75.             res = fns.get('class',sel[1]);
  76.             for(i = 2; i < len; i++){. more info on 1point3acres.com
  77.                 res = fns.eleFilter('class',sel[i],res);
  78.                 if(res.length === 0) break;
  79.             }
  80.             if(res.length > 0 && sel[0].length > 0){
  81.                 res = fns.eleFilter('tag',sel[0],res);
  82.             }
  83.         }else{
  84.             res = fns.get('tag', sel);
  85.         }
  86. . more info on 1point3acres.com

  87.         return res;
  88.     };



  89.     function dfs(node, curNode, res, selectors, index){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  90.         if(index === -1){
  91.             if(curNode !== document && res.indexOf(node) === -1) res.push(node);
  92.             return;
  93.         }

  94.         if(curNode === document) return;

  95.         var sel = selectors[index];. more info on 1point3acres.com
  96.         if(fns.eleValid(sel, curNode)){
  97.             dfs(node, curNode.parentNode, res, selectors, index-1);
  98.         }else{
    . 1point 3acres 璁哄潧
  99.             dfs(node, curNode.parentNode, res, selectors, index);
  100.         }
  101.     }

  102.     function genFinalRes(input,selector){
  103.         if(selector.length < 2) return input; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  104.         var res = [];
  105.         for(var i = 0; i < input.length; i++){. 1point 3acres 璁哄潧
  106.             var node = input[i];
  107.             dfs(node, node.parentNode, res, selector,selector.length-2);
  108.         }

  109.         return res;
    . more info on 1point3acres.com

  110.     }


  111.     res = genFinalRes(getBySingleSelector(selector[selector.length-1]),selector);. from: 1point3acres.com/bbs
  112. . from: 1point3acres.com/bbs
  113.     return res;

  114. };
复制代码
. more info on 1point3acres.com


参考了https://code.tutsplus.com/tutorials/building-a-simple-css-selector-engine--net-16389
https://github.com/jquery/sizzle. more info on 1point3acres.com
回复 支持 1 反对 0

使用道具 举报

伤的彻底 发表于 2016-10-8 09:47:46 | 显示全部楼层
关注一亩三分地微博:
Warald
第一题WIFI覆盖是半径吗?如果是一个圆的话求one pass的思路!
回复 支持 反对

使用道具 举报

qingmo 发表于 2016-10-8 10:34:01 | 显示全部楼层
谢谢楼主,实在是太有用啦~~~楼主早点有好消息哈~~
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-10-8 13:57:50 | 显示全部楼层
伤的彻底 发表于 2016-10-8 09:47
第一题WIFI覆盖是半径吗?如果是一个圆的话求one pass的思路!

lz说了是1D的
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| AD0103 发表于 2016-11-12 11:19:31 | 显示全部楼层
qingmo 发表于 2016-11-12 05:07
再次谢谢楼主的经验贴,在这贴一下当时准备面试的时候准备的第四轮的代码
(假定只存在tagName, ID, class ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
赞一个!
回复 支持 反对

使用道具 举报

Will5 发表于 2016-11-16 04:53:47 | 显示全部楼层
谢谢分享,赞。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-2-24 06:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表