算法群模拟面试记录

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法群模拟面试记录，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3550字，纯文字阅读大概需要6分钟。

内容图文

第一场：2018年12月30日（周日），北京时间早上五点。

写在最前面：好不容易五点爬了起来围观mock，结果早上周赛睡过去了，唉。orz。

面试官：wisdompeak，同学：littleRainRain

第一题：有个花圃矩阵 grid，size 是n * m，花圃上面的一个点，坐标是(x, y)上面可能有花，可能没有花（没有花的话，矩阵上的值为0）。如果一个Q(x,y)上有花的话，grid[x][y] = W， W代表这朵花的香气，随着距离这朵花越来越远，花的香气会逐渐减弱，减弱的关系和两个点的曼哈顿距离成正比，比如在点 P(x1, y1)，能闻到在点Q的花的香味是 f = W / (abs(x- x1) + abs(y-y1))。输入一个P点的坐标(px, py)，求在这个P点，能闻到花的香味最重的点坐标。

题解：直接二维矩阵遍历就行。只有一点需要注意的就是曼哈顿距离为0的时候，0不能做除数，怎么处理要问面试官，不要自己yy。

follow-up，能不能让算法更快一点？（其实我觉得这个问法不是特别的优秀，第一次听到了比较容易懵逼，如果我是面试者的话下面不知道该怎么接。直接问具体条件有什么变化，还是新增了什么条件么）

我第一次听到follow-up有点懵逼，我还以为难道bfs能解...但是迅速的否认了自己的想法，想象一下如果有个点距离给出的P点非常非常远，但是它的W非常非常大，这个点也有可能是candidate。

后来面试官解释了一下，假设这个花圃上面就几朵花呢？然后调用query方法N次，如何加速这个算法（言下之意是这个矩阵是一个稀疏矩阵）

ok，那我们开始预处理下矩阵，把有花的坐标点给存下来，存成一个数组，假设叫flowerCoor，然后每次query的时候就从flowerCoor里面取花的坐标，然后计算。

 

第二题：leetcode 837 New 21 Game

https://leetcode.com/problems/new-21-game/description/

面试官化简了一下这个题，他的问题是桌面上有10张扑克牌，代表[1, 10]这个区间的数字，玩家一开始有个基础分数 score， 游戏开始，score 代表现在点数，如果 score < 17， 那么庄家随机翻一张牌，累加score；如果 score 在[17, 21] 这个区间中，就代表庄家win；如果 score > 21 就代表玩家win。求玩家 win 的概率。

前面怎么讨论的我有点记不清了，但是妹子说了一句“这个题有点递归的意思”，然后就开始递归做。递归可以做。（不知道如果递归写全对的话，下面follow-up会不会扩大规模考 dp。不过想不到 dp不知道是 hired 还是 weak hired 了）

lc递归会超时，我加了记忆化递归也超时了 :( ，lc给的是 dp 解法。

mock的时候群里小伙伴有人说这题和 688 很像：https://leetcode.com/problems/knight-probability-in-chessboard/description/

 

第三题：leetcode 636 Exclusive Time of Functions

https://leetcode.com/problems/exclusive-time-of-functions/description/

第三题有点类似资源抢占调度的一道题。

 task 1:  start,  0

 task 2:  start,  2

 task 2:  end,  3

 task 1:  end,  4

 task 2:  start, 6

 task 2:  end,  7

start, end just mean get schecduled, like process to CPU, only one cpu, so if task2 started, task 1 paused。

要求返回每个task占用cpu的时间。返回map也好，数组也好，都行。

用stack解，我还没仔细想。我估计应该是用一个变量或者pair存某个任务被中断的时间？

 

第四题：leetcode 528. Random Pick with Weight

https://leetcode.com/problems/random-pick-with-weight/description/

群主给的就是有 N 个人种，每个人种的占比，实现一个算法，这个算法每次都会返回一个人种，在调用K（K是一个很大的数）次的情况下，所有的返回值的比例满足人种的占比。

given possibility like

chinese  22%

american:  5%

indian: 21%

...

各个概率之和保证为1，随机选一个,要求符合概率,如按22.333% sample chinese..

 

妹子一开始想的有点类似于基数了，就是比如说chinese占了22%，American占了 5%，那我搞一个 100 个人的数组，前 22 个元素 代表 chinese， 23 ～ 28 个元素代表 american。然后 1 ～ 100 内随机一个随机数，求得。然后面试官反问，如果占比不是整数呢，比如 22.345676798878888%这种，那是不是要开一个巨大的数组存这些数。于是这个思路走进死胡同了。群里有小伙伴说，如果有个 0 ～ 1 的随机数发生器就好了。我们可以这么思考，就是我们把概率数组求前缀和，然后随机一个 0 ～ 1 的数，在前缀和数组中二分这个数字就可以了。

题解：前缀和 + 二分。

 

内容总结

以上是互联网集市为您收集整理的算法群模拟面试记录全部内容，希望文章能够帮你解决算法群模拟面试记录所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---