一亩三分地论坛

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

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

Google 前端 onsite

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

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

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

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

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

第一轮:算法

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

第二轮:. Waral 鍗氬鏈夋洿澶氭枃绔,

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

第三轮:

考察简单的用 JS 处理数据的思路。说给一个网页,跟一个 getHash 函数,求返回页面里所的 img,要求用 hash 去重。就用简单的 DOM API,中间需要用到 promise(或者 callback)来获取 image data 给 getHash 用来计算 hash。用什么不重要,主要看你习不习惯 JS 里面的 async flow control。.鏈枃鍘熷垱鑷1point3acres璁哄潧

第四轮:.1point3acres缃
. From 1point 3acres bbs
要求实现 querySelectorAll。没思路,没答好,感觉应该看看 jQuery 源代码就没问题。

第五轮:

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

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

谢谢大家,求米!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

2

查看全部评分

本帖被以下淘专辑推荐:

qingmo 发表于 2016-11-12 05:07:43 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
再次谢谢楼主的经验贴,在这贴一下当时准备面试的时候准备的第四轮的代码
(假定只存在tagName, ID, class三种情况,因为45分钟如果能把特殊情况都考虑进去的话我觉得有点假。。。)
比如如果是selector_str   = 'div#main p p.red span'. 1point 3acres 璁哄潧
因为浏览器解析selector是从右到左的,所以我的思路是先找到最右的selector,找出所有满足的结果-即先找出所有的span元素
然后根据浏览器解析的原则进行dfs,找出满足条件的元素,即他们的parent element能满足前一个selector - 看找出的span元素的父节点是否有满足p.class 的,如果有,继续向上dfs
最后返回dfs后的元素

  1. var SELECTOR = function (selector, node) {. 1point 3acres 璁哄潧
  2.     node = node || document;
  3.     var fns, getBySingleSelector, res;

  4.     //check if the selector is valid. 鍥磋鎴戜滑@1point 3 acres
  5.     if (typeof selector !== 'string') return [];

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

  7.     fns = {
  8.         id: function (sel) {
  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,
  14.                 arr = [],
  15.                 get_what = (c_or_e === 'class') ? 'getElementsByClassName' : 'getElementsByTagName';. 鍥磋鎴戜滑@1point 3 acres
  16.             //parent - node, nodeList, dom.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17. . visit 1point3acres.com for more.
  18.             if (par.length > 1) {
  19.                 i = 0;
  20.                 len = par.length;-google 1point3acres
  21.                 while (i < len) {. 鍥磋鎴戜滑@1point 3 acres
  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. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.             return arr;.1point3acres缃
  30.         },
  31.         eleFilter: function(c_or_e, sel, arr){
    . from: 1point3acres.com/bbs
  32.             if(arr === null || arr.length === 0) return arr;. from: 1point3acres.com/bbs
  33.             var i,ele,
  34.                 isClass,
  35.                 len = arr.length,
  36.                 res = [];

  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);. visit 1point3acres.com for more.
  42.             }
  43. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.             return res;.1point3acres缃
  45.         },
  46.         eleValid: function(sel, node){
  47.             if(sel === null || sel.length === 0) return true;
  48. -google 1point3acres
  49.             if(sel.indexOf('#') > -1){
  50.                 sel = sel.split('#');
  51.                 if(fns.id(sel[1]) !== node) return false;
  52.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
  53.             }else if(sel.indexOf('.') > -1){
  54.                 sel = sel.split('.');
  55.                 var i = 1, len = sel.length;. 鍥磋鎴戜滑@1point 3 acres
  56.                 for(i; i < len; i++){
  57.                     if(node.className.indexOf(sel[i]) === -1) return false;
  58.                 }
  59.                 if(sel[0].length > 0 && node.nodeName !== sel[0].toUpperCase()) return false;
  60.             }else{
  61.                 return node.nodeName === sel.toUpperCase();
  62.             }

  63.             return true;
  64.         }
  65.     };

  66.     getBySingleSelector = function(sel){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  67.         var res = [], rep, i, len;
  68.         if(sel === null || sel.length === 0 || typeof sel !== 'string') return [];
  69.         if(sel.indexOf('#') > -1){
  70.             sel = sel.split('#');
  71.             rep = fns.id(sel[1]);
  72.             if(sel[0].length > 0 && rep.nodeName !== sel[0].toUpperCase()) rep = null;
  73.             res.push(rep);.1point3acres缃
  74.         }else if(sel.indexOf('.') > -1){
  75.             sel = sel.split('.');
  76.             len = sel.length;
  77.             res = fns.get('class',sel[1]);
  78.             for(i = 2; i < len; i++){
  79.                 res = fns.eleFilter('class',sel[i],res);
  80.                 if(res.length === 0) break;
  81.             }
  82.             if(res.length > 0 && sel[0].length > 0){
  83.                 res = fns.eleFilter('tag',sel[0],res);
  84.             }
  85.         }else{
  86.             res = fns.get('tag', sel);
  87.         }. visit 1point3acres.com for more.


  88.         return res;
  89.     };
  90. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


  91.     function dfs(node, curNode, res, selectors, index){
  92.         if(index === -1){. from: 1point3acres.com/bbs
  93.             if(curNode !== document && res.indexOf(node) === -1) res.push(node);
  94.             return;
  95.         }

  96.         if(curNode === document) return;.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

  104.     function genFinalRes(input,selector){
  105.         if(selector.length < 2) return input;
  106.         var res = [];
  107.         for(var i = 0; i < input.length; i++){. 1point 3acres 璁哄潧
  108.             var node = input[i];
  109.             dfs(node, node.parentNode, res, selector,selector.length-2);
  110.         }. Waral 鍗氬鏈夋洿澶氭枃绔,

  111.         return res;
  112. . from: 1point3acres.com/bbs
  113.     }

  114. . 鍥磋鎴戜滑@1point 3 acres
  115.     res = genFinalRes(getBySingleSelector(selector[selector.length-1]),selector);

  116.     return res;

  117. };
复制代码



参考了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 | 显示全部楼层
关注一亩三分地微博:
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.1point3acres缃
再次谢谢楼主的经验贴,在这贴一下当时准备面试的时候准备的第四轮的代码
(假定只存在tagName, ID, class ...
. 1point3acres.com/bbs
赞一个!
回复 支持 反对

使用道具 举报

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

使用道具 举报

zchang3 发表于 2017-3-15 09:06:33 | 显示全部楼层
算法必须用js写吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 12:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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