狗家SETI阳谷上门

这周面的狗家SETI, 阳谷县办公室。

第一轮 45mins: 蠡口散妖雾 +  test case。

第二轮 45mins:
第一题：
一个数组，只有RGB三色, arr={R,R,G,R,B,G,G,B,B...} 实现函数 query (index, targetColor) 返回离index最近的targetColor的距离。比如query(1,B)就是离arr[1]最近的B的距离是3。query会用很多次，要求是O(1).
Follow up: 2D array, 和上

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

angman。





补充内容 (2019-5-13 02:27):
觉得有用的，求加大米，加大米不会扣你自己大米的。谢谢啦！地里朋友们加油~

补充内容 (2019-5-19 04:47):
被HC给拒了，应该是第一轮第二轮都没答好。明年再战~

第二轮第一题，我来细说下解法：

一维：

解法1：
对于RGB三种颜色，针对每种颜色X，对数组进行两次扫描。第一次是从左往右扫描，可以得到某个位置i，左边离的最近的X的位置是多少-left[X][i]。从右往左扫描，可以得到right[X][i]。
当查询 query (index, targetColor)，返回 Math.min(index-left[targetColor][index], right[targetColor][index] - index)

解法2：
对于RGB三种颜色，针对每种颜色X，进行BFS。具体流程是：
1. 有一个二维数组minDis[X][i], 表示对于颜色X，在位置i查询的话，最近的点距离是多少。初始化无穷大。
2. 把当前颜色全部找出来，放入队列，队列里每个点存的信息是(Position, Step）。初始时加入点的Step都是0. 同时更新minDis[X][Position] = 0;
3. 取出队头里的一个元素，node =(Position, Step）, 判断结点Position +1, 和结点 Position - 1 是否没访问过，如果没有访问过，则加入队列中。加入的节点的Step = node.step + 1。同时更新minDis。

查询时，直接返回minDis[X][Position]。

二维：
解法：是一维的解法2一样，只是把Position的信息改成2维。拓展时，可以向4个方向拓展。

大雷若潘 发表于 2019-5-14 09:45
如果是往左右扫的话 时间就不是O(1)了吧  我以为要新建一个hash table什么的 这样query的时候时间是O(1). ...

我感觉楼主的意思是
初始颜色数组是固定的
所以从左到又扫一遍, 从右到左扫一遍之后你就知道每个位置最近的 RGB 在哪了, 把结果保存好.
然后每次 query 直接返回就行, 这就是 O(1)
不过如果初始数组是变动的我就没办法了.

2d 的同样, 对每个位置做 BFS 找到离当前最近的颜色快,
然后 query 的时候直接返回就好.

第一面的 hard 题 真心给跪......

大雷若潘 发表于 2019-5-14 08:45
求问楼主 第二轮要求O(1) 是时间和空间都是O(1)吗？ 求分享思路

第二轮第一题RGB那个吗？query不用空间的吧，initialize会用不少空间时间。讲真，我只会一维的，从左向右扫一遍，从右往左扫一遍，就知道离R最近的左右的G和B了，比较暴力。二维的我还是这样暴力扫，面试官说不行，提示是BFS。我想到了人和自行车那题，但还是不会，所以面试官才给第二题让我做[捂脸]。地里朋友们有思路的，求告诉我哈~

求问第三轮那题怎么解？

楼主可以回忆一下狗家BQ都问了什么？该怎么准备呢   谢谢啦

LZ的描述清晰具体，谢谢

厉害的面经！！

求问楼主 第二轮要求O(1) 是时间和空间都是O(1)吗？ 求分享思路

TTTWangTingting 发表于 2019-5-14 02:01
楼主可以回忆一下狗家BQ都问了什么？该怎么准备呢   谢谢啦

和亚麻的类似，就是如果和同事有不同意见怎么办，对现在老板有什么意见，做过的有挑战的项目是什么等等。不过比亚麻好一点，的确是要举例子，但不会往深处挖，不过例子也要详细合理。

shawnzhao 发表于 2019-5-13 22:23
求问第三轮那题怎么解？

我把第三轮的饭店书店什么的，看做第二轮第一问的RGB, 嘿嘿，然后题目就变一样了。感觉跟人和自行车那题类似。

zsz1990ustc 发表于 2019-5-14 09:32
第二轮第一题RGB那个吗？query不用空间的吧，initialize会用不少空间时间。讲真，我只会一维的，从左向右 ...

如果是往左右扫的话 时间就不是O(1)了吧  我以为要新建一个hash table什么的 这样query的时候时间是O(1).
看了你第一轮的题就吓尿了 上来就一道hard题 两周后要昂赛的我好方啊