骨骼面经

Job Hunting Interview
, , , , ,
1

一：鲜花和雕像
在2D的矩阵上，某些坐标有鲜花（F），某些坐标又雕像(S)。其余的坐标是空白的（O）
例：
OOFOO
OOSOO
FFOFF
SOOOF
OFOOO

雕像会挡住这个方向的鲜花, 问：在每一个空白位置上，朝四个方向看，一共能看到几朵鲜花。
在这个例子里：在左下角的空白，朝上被雕像挡住，朝右右1朵鲜花，一共1朵
在正中间的空白，上0，左2，右2，下0，一共4朵
输出一个2d矩阵

follow up:

  1. 写test case，conrer case.
  2. 如果矩阵很大，不能一次性读入内存怎么办。假设矩阵是稀疏的（鲜花和雕像很少）

二.自行车
2D平面上，有m个人（P），n辆自行车(B)，还有空白（O）满足以下条件
1.m < n
2.不存在两个人，到同一辆自行车距离相等, 距离用abs(x1-x2) + abs(y1-y2)定义
3.每个人尽量找离自己最近的自行车，一旦某辆自行车被占，其他人只能找别的自行车。

例
OPOBOOP
OOOOOOO
OOOOOOO
OOOOOOO
BOOBOOB

红色的人找到第一行的自行车，距离最近。
蓝色的人离第一行自行车最近，但自行车已经被红色人占有，所以他只能找离他第二近的，右下角的自行车。

问：把人和自行车配对，输出vector<pair<int, int>>每个人对应的自行车. {i, j} 是人i对应自行车j

其他几轮都是地里的面经高频题，我就不重复啦，祝大家好运~都能收到offer

2

应该是的 好眼力！

3

可以搞几个priority_queue<距离，人，车>
然后遍历m个人，n辆车，把m*n个 距离，人，车放入其中。
每次取出距离最小的，看看这个人是否已经分配了自行车
如果没有分配，则可以把这个人和这辆车输出

4

已加， 求问自行车分配问题的思路？

5

谢谢楼主。请问楼主在哪个Office面的 还有 楼主的第一题follow up大概怎么答得能说一下吗？加

6

求问：怎么编辑帖子 设置积分可见 谢谢~

7

在总部面得，第一题我是用range存储可以看见的花
比如说底四行，第2-4列向 左右都是只能看到一朵花。
row：4
start:2
end:4
flower:1
这样
可以节省存储空间。

看面试官的意思 应该还有其他方法，但是面到最后没时间了

8

谢谢楼主耐心解答 一会用电脑给 手机app给不了

9

感觉第一轮就是LC bomb enemy ？

10

楼主的第二个解法很赞