微软电面

azure stream analytical组，hiring manager简单聊后，上了一道coding题：

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

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

楼主最后想了两种方法：
方法1：从后往前找头，先扫找到X记录下来，然后通过X的index往前找，直到page的index没前项，即为头page；（稍微紧张了下，没有在此基础上直接用hashmap存，而选择了扫pages）；不太满意
方法2：花了点时间，想出了另一种方法，直接用indegree思路，用hashmap标识next出现数字或者X的page是否可能头page。比如：next带数字的，直接将其index添加hashmap标识false，或者已在hashmap将其值改为false（不可能头page），然后在hashmap里面查找当前page的index是否在其中，如果没有将自己index加入hashmap并暂时标记为true；最后遍历hashmap里面为true的page即为所有头page。

manager挑了几个case，最后觉得work，然后我白板实现了code。（应该不是和她心目中的解法一致，估计她想的是第一种解法用hashmap倒着搜索，像union-find找根）。

下午接到拒信，可能嫌弃background不是很strong，毕竟是转行。anyway，个人还是比较满意自己短时间想出另外一个approach。

可以请教一下这题的输入和输出嘛？已经加米咯~~~

golittleflag 发表于 2019-9-22 16:50
可以请教一下这题的输入和输出嘛？已经加米咯~~~

你可以假设输入是一个定义好的list of page（vector of page），返回list of page index（head page index）。

page class在完成主代码后你可以自己定义（包括两个成员：int idx，和 string next）。

我感觉这题是个BFS,
首先循环所有pages，建立一个page, prepage的map，同时把所有next page是x的加进queue.
然后就是BFS，一旦当前元素没有在map里，也就是当前元素没有previous page，就加入答案list，否则就把previous page加入queue。

另一个做法可能是UnionFind，但是还没太像仔细，感觉不会比BFS更简单，而且都是 O(n)

想了想UnionFind的解法大概应该是这样，建一个UnionFind class,里面放个数组长度就是page总数的数组father[n + 1]（下标处理无所谓了，个人偏好），初始值就是下标本身，或者-1之类不可能出现的page number，建立一个listx，用来存所有next是x的page。然后遍历一遍pages，遍历的过程update数组的值为他的previous page number. 比如遍历到(page 2, next page 4)， 就把father[4] = 2，便利的同时把所有next是x的加进listx。遍历结束后，对每一个listx里的page number进行 findfather运算，findfather 这个recursive结束的条件就是father[n] == -1或则father[n] == n, 如果father[n] == -1就把father[n] = n。 左中每一个listx里的pagenumber找出来的father就是答案。
时间空间复杂度好像都是O(n)，跟BFS相同，但是细节处理好像略为麻烦一点。