# 美团 2020 年实习生招聘

# 笔试

# 双行道

时间限制:C/C++语言 1000MS;其他语言 3000MS

内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述: 有一个 2*n 的网格,有一个人位于(1,1)的位置,即左上角,他希望从左上角走到右下角,即(2,n)的位置。在每一次,他可以进行三种操作中的一种:

1. 向右走一格,即从(x,y)到(x,y+1);

2. 向上右方走一格,即,如果他在(2,y)的位置可以走到(1,y+1);

3. 向下右方走一格,即,如果他在(1,y)的位置可以走到(2,y+1);

问题当然不会这么简单,在这 2*n 的格子中,有一部分格子上有障碍物,他不能停在障碍物上,当然也不能走出网格,请问他有多少种不同的路线可以到达(2,n)。

输入

输入第一行仅包含一个正整数 n,表示网格的长度。(1<=n<=50)

接下来有 2 行,每行有 n 个字符,“X”代表障碍物,“.”代表可以停留。

输出

如果没有可以到达的路线则输出-1,否则输出方案数量。

样例输入

5
..X.X
XX...

样例输出

2

# 最好一样

时间限制:C/C++语言 1000MS;其他语言 3000MS

内存限制:C/C++语言 131072KB;其他语言 655360KB

题目描述: 给出一个序列包含 n 个正整数的序列 A,然后给出一个正整数 x,你可以对序列进行任意次操作的,每次操作你可以选择序列中的一个数字,让其与 x 做按位或运算。你的目的是让这个序列中的众数出现的次数最多。

请问众数最多出现多少次。

输入

输入第一行仅包含两个正整数 n 和 x,表示给出的序列的长度和给定的正整数。(1<=n<=100000,1<=x<=1000)

接下来一行有 n 个正整数,即这个序列,中间用空格隔开。(1<=a_i<=1000)

输出

输出仅包含一个正整数,表示众数最多出现的次数。

样例输入

5 2
3 1 3 2 5

样例输出

3

提示

样例解释

例如如果序列中所有数字都不修改时,众数为 3,3 出现的次数为 2,如果我们把两个 3 都做如题操作,序列会变为 1,1,1,2,5,此时众数为 1,出现次数为 3,所以我们选择后者方案,输出众数出现的次数,即 3。

# 整除的数组

时间限制:C/C++语言 3000MS;其他语言 5000MS

内存限制:C/C++语言 131072KB;其他语言 655360KB

题目描述: 小美曾经有一个特殊的数组,这个数组的长度为 n。但是她在打恐怖游戏的时候被吓得忘记了这个数组长什么样了。不过她还记得这个数组满足一些条件。

首先这个数组的每个数的范围都在 L 和 R 之间。包括端点。

除此之外,这个数组满足数组中的所有元素的和是 k 的倍数。

但是这样的数组太多了,小美想知道有多少个这样的数组。你只需要告诉她在模 1e9+7 意义下的答案就行了。

输入

一行四个整数 n,k,L,R

(1≤n≤1e5 1≤k≤10 1≤L≤R≤1e9)

输出

输出一个数表示满足条件的数组的个数。

样例输入

9 1 1 3

样例输出

19683

# 物资采购

时间限制:C/C++语言 2000MS;其他语言 4000MS

内存限制:C/C++语言 131072KB;其他语言 655360KB

题目描述: 某公司要建厂投产一种产品,已知该产品共需要 k 种不同的原材料才能生产,而在这个工厂周围有 n 个可供建厂的地址,同时这 n 个位置都生产该产品所需 k 种原材料中的一种,在这 n 个位置间存在一些通行的道路,我们可以视这些道路的长度都为 1,保证这些位置之间两两都是连通的。

很显然工厂面临一个很严峻的问题,就是原料采集,我们定义采集一种原材料的花费为工厂所在位置到最近的一个该材料的采集点的距离,在一个位置建厂的成本为 k 种原材料的采集花费之和。

请你对每一个位置都求出其建厂的花费。

输入

输入第一行有三个正整数 n,m,k,分别代表可供选择的建厂地址数量,编号为从 1 到 n,这些地址之间的道路数量,生产所需的原材料数量,编号为 1 到 k。(1<=n,m,<=50000,1<=k<=100)

输入第二行包含 n 个正整数,第 i 个正整数 a_i 表示第 i 个地址是第 a_i 种原料的采集点。(1<=a_i<=k)

接下来有 m 行,每行有两个正整数 u,v,表示 u 号位置和 v 号位置之间有一条连接的路径,可能存在重边或自环(如样例所示)。

输出

输出包含 n 行,每行一个正整数,第 i 行表示第个位置的建厂成本。

样例输入

5 5 3
1 1 2 3 1
1 4
2 4
3 4
4 5
4 3

样例输出

3 3 3 2 3

# 小仓的射击练习 1

时间限制:C/C++语言 1000MS;其他语言 3000MS

内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述: 小仓酷爱射击运动。今天的小仓会进行 N 轮射击,已知第 i 次射击,她击中靶心的概率是 a[i] -1 。

小仓想知道 N 轮射击后,偏离靶心次数为 0 ,1 ,2 次的概率分别是多少。

输入

第一行一个数 N,代表射击轮数。

第二行 N 个数 a[i],第 i 个数为 a[i]。

1≤N≤100,000

1≤a[i]<998244353

输出

不难证明答案可以表示成一个最简分数 p * q -1。

你需要输出三个 p * q -1 对 998244353 取模后的结果,以此来表示偏离靶心次数为 0 , 1 , 2 时的概率。

其中 q-1 是 q 在模意义下的逆元,满足 q-1* q = 1 mod 998244353。

例如 1/4, 可以写成 748683265,原因是 4 * 748683265 % 998244353 = 1,也有且仅有 x = 748683265,1 <= x < 998244353 满足乘积等于 1

样例输入

2
2 2

样例输出

748683265 499122177 748683265

# 一面

面试官没有让我自我介绍,直接开始问问题了:

  1. 你做前端比较擅长哪些方面?(CSS 动画,性能优化)
  2. 为什么选择用 CSS 做动画?为什么不用 JS 来做动画呢?(CSS 开启 GPU 硬件加速使用 GPU 渲染,帧率高 / JS 做动画灵活,但是容易引起频繁的回流(reflow)重绘(repaint),且使用 CPU 计算渲染,帧率只有 40 帧左右)
  3. 那如果让你用 JS 做一个动画,实现一个方块从 0px 移动到 100px 的位置,你会怎么做?(这种情况优先考虑使用 CSS,因为是简单动画)
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
    <style>
      #move {
        position: absolute;
        top: 0;
        left: 0;
        width: 100px;
        height: 100px;
        line-height: 100px;
        background: green;
        text-align: center;
      }
    </style>
  </head>
  <body>
    <div id="move">move</div>
    <script>
      var ele = document.getElementById('move')
      var left = 0
      var timer = setInterval(() => {
        if (left < 100) {
          ele.style.left = `${left}px`
          left++
        } else {
          clearTimeout(timer)
        }
      }, 10)
    </script>
  </body>
</html>

动画效果点击此处查看

  1. 你知道什么是点击穿透嘛?如何实现点击穿透?(听说过,CSRF 攻击通常会使用这种方式诱导用户点击链接到危险网站。当时不知道如何实现点击穿透,后来查了一下资料发现可以使用 CSS 的pointer-events: none;将遮罩层的元素指针事件禁用,就能实现点击穿透)
  2. 你说到 CSRF,那么可以讲一下 CSRF 的流程嘛?如何防范 CSRF(这个很多方法了(token,referer 验证,cookie samesite 等等))
  3. 编程题,水桶问题,一个水桶 5 升,一个水桶 3 升,只能倒空或倒满,问能否得到 n 升的水(返回 true or false)(DFS,容积做差)
  4. 编程题,一个有序数组,存在重复元素,给定一个target,如何找出其在数组中最左边的位置,不使用indexOf(二分法,设置返回条件递归)
  5. React/Vue 中的 key 值有什么作用,又有什么区别?(只答出 key 值相同的 DOM 会被复用,key 也参与 DOM Diff 当 key 和标签相同则 DOM 结点未发生变化)
  6. 你说你对性能优化比较了解,讲一下吧?(性能优化的 N 种方式

# 面试评价

基础不太好,算法和数据结构基础,最后留了一句继续加油吧。

# 二面

  1. 一面的面试官对你评价很高(???前天才说基础不好继续加油?),问一下你对 Webpack 方面的了解是你自己写过 Webpack 的插件吗还是学习过一些脚手架的?(主要是在深信服实习阶段学习到了代码打包压缩,多入口配置等,学习还是主要看文档)
  2. 那你描述一下浏览器从输入域名到页面加载的整个过程?(我回答这是老生常谈了,面试官立即就打断我了)
  3. 那我问你一下,浏览器是如何判断你输入的是域名还是 IP 地址又或者要搜索的内容的?(正则?)
  4. 我如果输入 meituan.com,如何能够重定向到 bj.meituan.com?服务器是如何知道用户所在地址的?(TCP 报文首部的源 IP?)
  5. 现在基本上都是内网地址,那服务器是如何知道真实的 IP 地址的?(NAT 地址转换技术,内网的报文发送至路由器会由路由器拆包并改为真实的 IP 地址,然后收到响应报文再根据路由表转发?)
  6. 那你在浏览器输入 meituan.com 为什么会变成 www.meituan.com?(这个是浏览器自动转换的吧?)
  7. 如果美团的网关挂了,会返回什么状态码?(我回答的 500,应该是 502 Bad Gateway)
  8. 如果浏览器返回的状态码是 302,是什么原因?(临时重定向,表示资源临时移动至别的位置)
  9. 那 302 和 301 有什么区别,为什么更建议临时重定向?(跟 SEO 相关,因为搜索引擎保存的可能是原本的资源地址,如果使用 301 进行永久重定向,可能出现 404 的情况。)
  10. 问一下你经常见的有哪些响应头或者请求头?(host,origin,referer 说了 3 个就被打断了)
  11. 那你知道 origin 字段在什么请求中会携带,什么请求中不会?前端手动设置 origin 字段会不会报错?(不会,没了解过)
  12. 知道 link 标签吧,一般用来做些什么?(favicon、css、dns 预解析等)
  13. Vue 中如果在某个点击函数中直接修改某个 data 的值,页面是否会重新渲染?(这个问题我有点没听懂,就讲了一下响应式的原理,不应该是在 data 中声明了的变量才会重新渲染嘛?面试官是把 Vue 和 React 弄混了?)
  14. 我看你简历上写了学过 TypeScript,看过 enum 编译后的代码吗?(看过,有印象,但是不太记得怎么写了)
  15. 如果让你用 JavaScript 实现一个 enum 你会怎么实现?(不会)
  16. location 对象知道吗?location = '/a.html'location.href = '/a.html'有什么区别?(不会,基本没用过 location 对象)
  17. SPA 为什么 URL 发生变化浏览器不刷新?(history.pushState)
  18. iframe 有一个很丑的边框,如何将他的边框取消掉?(我做项目的时候没遇到有边框啊,难道是手动设置border: none;?)
  19. 你应该知道原生的文件上传组件很丑,有什么办法美化一下嘛?(加一个容器,去掉原生的默认样式)
  20. 事件冒泡知道吧,怎么样获取到冒泡的标签呢?(e.target
  21. 那如何获取这个标签是第几个呢?(e.target.childNode?)
  22. 你知道 CSS 的pointer-events: none;属性的效果是什么嘛?(阻止默认的指针事件)
  23. 在 HTTP 的请求头里面可以自定义嘛?比如说设定一个aa: xxx的字段?(可以,我的项目里面用一个 aabbcc 字段携带 token 做用户登录态校验)
  24. 在响应头里面有一个 content-length,你知道当他设为 0 时,是请求体中的内容直接就发送不出来,还是发送出来了但是被浏览器截断了?(应该是后端直接就发送不出来?)
  25. 编程题,合并两个有序数组。
  26. 编程题,将一段文字中的含有某个字母的单词高亮。

# 面试评价

知识面挺广的,就是缺乏一些实际应用的经验(面试过程中一直安慰我说没有实际应用过应该不知道,没事的)

# 三面

三面应该是一个 leader 级别的人物面试我,问的问题都比较有深度,我提问给的回答也比较深入。

  1. 实现一个自己的排序算法,挂载到数组原型上(小问题)
  2. 考察this指向问题(连续两道this指向的题都答错了)
  3. C++ 与 JavaScript 区别(前者需要编译,后者即时执行)
  4. 同步和异步怎么理解?(这点没回答好)
  5. 求最大最长子序列(LeetCode 做过,但是当时没写完整说了思路,应该要用到 DFS)
  6. 未来职业规划?(打通后端,转向架构)
  7. 介绍项目(深信服、简历上的项目)
  8. 有没有别的公司在面试过程中?(老实交代已拿腾讯深信服海康威视 offer,还有阿里头条在走流程)
  9. 如果做一个方块一秒钟从左边移到右边,怎么做?(setInterval、setTimeout、requestAnimationFrame,还顺便提到了 CSS 做简单动画,性能更佳,以及 CSS 动画的一些基础操作)
  10. 你有什么想问我的?(TS、自动化测试是否落地?base 哪里?)

# 面试评价

要多了解计算机相关的知识,都是限制你上限的因素,职业发展尤其是前端很容易遇到瓶颈原地踏步。