面试官是个老印, 不给题目, 全程口述. 遇到这种面试官一定要问清楚问题是干啥的, 如果盲目去写很可能答非所问.
一个白板题，参考这个仓库的题，一样的
一个面试官口述题: 亚马逊有很多的服务, 每个服务之间存在依赖关系, 当我们将其中的一些服务停机后, 求哪些服务会被影响.
Clarify question: 一定一定先进行这一步, 把问题的条件问清楚.让面试官给个例子, 面试官没准备, 现场画了个图. 问完这个问题后就确认是拓扑排序问题了.
是否可能是非法的, 比如存在环的情况 → 输入一定合法
是否可以自定义输入的格式 → 可以, 我们将输入定义为一个hashmap, key是服务名称, value是依赖他们的服务列表.
Ideas: 写代码之前要做的, 讲清楚自己的思路, 因为亚麻的代码不能run, 直接写代码的话, 如果面试官不认可你的代码, 直接凉凉. 所以在写代码前先讲清楚如何去做.
统计每个服务的入度
将入度为0的服务加入到队列中
初始化一个受影响服务集合, 一开始被停机的服务会被加入进去.
访问队列, 每次弹出队首
访问依赖服务列表, 如果当前服务在受影响服务集合中, 那么将依赖服务也加入到集合中. 同时更新依赖服务的入度, 如果入度变成0, 加入到队列中
当队列为空, 返回受影响的服务集合.
分析 Time/space complexity:
Dry run: 因为代码不能执行, 所以需要手动去跑样例, 这一步需要多练