一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1273|回复: 6
收起左侧

Google 前端 onsite

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

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

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

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

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

第一轮:算法. 1point 3acres 璁哄潧

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

第二轮:

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

第三轮:. 1point 3acres 璁哄潧

考察简单的用 JS 处理数据的思路。说给一个网页,跟一个 getHash 函数,求返回页面里所的 img,要求用 hash 去重。就用简单的 DOM API,中间需要用到 promise(或者 callback)来获取 image data 给 getHash 用来计算 hash。用什么不重要,主要看你习不习惯 JS 里面的 async flow control。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第四轮:
. visit 1point3acres.com for more.
要求实现 querySelectorAll。没思路,没答好,感觉应该看看 jQuery 源代码就没问题。

第五轮:

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

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

谢谢大家,求米!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

qingmo 发表于 2016-11-12 05:07:43 | 显示全部楼层
再次谢谢楼主的经验贴,在这贴一下当时准备面试的时候准备的第四轮的代码.鐣欏璁哄潧-涓浜-涓夊垎鍦
(假定只存在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.     //check if the selector is valid
  5.     if (typeof selector !== 'string') return [];

  6. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.     selector = selector.split(' '); //[#main, li.selected a]

  8.     fns = {
  9.         id: function (sel) {
  10.             return document.getElementById(sel); //return an Element Object-google 1point3acres
  11.         },.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.         get: function (c_or_e, sel, par) {
  13.             par = par || document;
  14.             var i, len, temp,
  15.                 arr = [],
  16.                 get_what = (c_or_e === 'class') ? 'getElementsByClassName' : 'getElementsByTagName';
  17.             //parent - node, nodeList, dom

  18.             if (par.length > 1) {
  19.                 i = 0;
    -google 1point3acres
  20.                 len = par.length;
  21.                 while (i < len) {
  22.                     temp = par[i++][get_what](sel);
  23.                     Array.prototype.push.apply(arr, Array.prototype.slice.call(temp)); //because temp is an object
  24.                 }
  25.             } else {
  26.                 arr = par[get_what](sel); //?
  27.             }

  28.             return arr;
  29.         },
  30.         eleFilter: function(c_or_e, sel, arr){
  31.             if(arr === null || arr.length === 0) return arr;
  32.             var i,ele,
  33.                 isClass,. 鍥磋鎴戜滑@1point 3 acres
  34.                 len = arr.length,
  35.                 res = [];
  36. . Waral 鍗氬鏈夋洿澶氭枃绔,
  37.             isClass = c_or_e === 'class' ? true : false

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

  43.             return res;
  44.         },
  45.         eleValid: function(sel, node){
  46.             if(sel === null || sel.length === 0) return true;. 1point 3acres 璁哄潧

  47.             if(sel.indexOf('#') > -1){
  48.                 sel = sel.split('#');
  49.                 if(fns.id(sel[1]) !== node) return false;. From 1point 3acres bbs
  50.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
  51.             }else if(sel.indexOf('.') > -1){
  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.                 }-google 1point3acres
  57.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
  58.             }else{
  59.                 return node.nodeName === sel.toUpperCase();
  60.             }

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

  64.     getBySingleSelector = function(sel){
  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]);
  70.             if(sel[0].length > 0 && rep.nodeName !== sel[0].toUpperCase()) rep = null;
  71.             res.push(rep);
  72.         }else if(sel.indexOf('.') > -1){
  73.             sel = sel.split('.');.1point3acres缃
  74.             len = sel.length;
  75.             res = fns.get('class',sel[1]); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  76.             for(i = 2; i < len; i++){
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  85.         }

  86. . 1point3acres.com/bbs
  87.         return res;
  88.     };.1point3acres缃

  89. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  90. . Waral 鍗氬鏈夋洿澶氭枃绔,
  91.     function dfs(node, curNode, res, selectors, index){
  92.         if(index === -1){
  93.             if(curNode !== document && res.indexOf(node) === -1) res.push(node);. 1point3acres.com/bbs
  94.             return;
  95.         }
  96. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  97.         if(curNode === document) return;

  98.         var sel = selectors[index];
  99.         if(fns.eleValid(sel, curNode)){
  100.             dfs(node, curNode.parentNode, res, selectors, index-1);
  101.         }else{
  102.             dfs(node, curNode.parentNode, res, selectors, index);
  103.         }
  104.     }

  105.     function genFinalRes(input,selector){
  106.         if(selector.length < 2) return input;
  107.         var res = [];.1point3acres缃
  108.         for(var i = 0; i < input.length; i++){
  109.             var node = input[i];
    . 鍥磋鎴戜滑@1point 3 acres
  110.             dfs(node, node.parentNode, res, selector,selector.length-2);
  111.         }

  112.         return res;

  113.     }


  114.     res = genFinalRes(getBySingleSelector(selector[selector.length-1]),selector);
  115. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  116.     return res;

  117. };
复制代码
. 1point 3acres 璁哄潧


参考了https://code.tutsplus.com/tutorials/building-a-simple-css-selector-engine--net-16389. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
https://github.com/jquery/sizzle
回复 支持 1 反对 0

使用道具 举报

伤的彻底 发表于 2016-10-8 09:47:46 | 显示全部楼层
第一题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的思路!
. more info on 1point3acres.com
lz说了是1D的
回复 支持 反对

使用道具 举报

 楼主| AD0103 发表于 2016-11-12 11:19:31 | 显示全部楼层
qingmo 发表于 2016-11-12 05:07. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
再次谢谢楼主的经验贴,在这贴一下当时准备面试的时候准备的第四轮的代码. Waral 鍗氬鏈夋洿澶氭枃绔,
(假定只存在tagName, ID, class ...

赞一个!
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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