股沟店面过经，过了也然并卵

内推拿到面试，申请的是Early Career。上周参加了店面，一个衣着非常潮的三哥，体验还不错。上来简单寒暄、互相介绍下。全程没怎么打扰我给我压力，只在我stuck的时候给一点点提示。

这周HR回复说feedback不错，其实我答的比较一般，最后45分钟全用完了才刚好写完，没时间FUQ。不过可能沟通比较给力三哥放了我一马，在此感谢一下他。然而今天HR突然又说2022年的Early Career都取消了，推荐我去面其他的open position。感觉应该是大规模的招人全部取消了，现有的HC可能还有机会，但是一个萝卜一个坑了。
心情有点沉重，大龄转码，平日上班带娃刷题不易，好不容易走到这一步了经济又不好了，蓝瘦，香菇。下周要面香蕉厂，发个面筋攒人品，求大家赏点米抚慰下我的心灵。

题目是一道graph题，

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

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

不知道有没有蠡口原题，请各位刷题王看看。

1. public boolean must_succeed(int node){
   
2.         return dfs(node, new HashSet<Integer>());
   
3. }
   
4. 
   
5. private boolean dfs(int node, Set<Integer> visited){
   
6.         if(visited.contains(node)) return false; //cycle detected
   
7.         if(!adj.containsKey(node)){ //if leaf node
   
8.         return success_node(node);
   
9. }
   
10. 
    
11.         visited.add(node);
    
12.         for(int next : adj.get(node)){
    
13. if(!dfs(next, visited))) return false;
    
14. }
    
15. visited.remove(node);
    
16. return true;
    
17. }
    

复制代码

那就直接从没有out edge的 success Node 遍历呗？

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

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

只有祝福。
个人无法扭转局势，只能随波逐流。

这个有向图里面有没有环很重要，如果没有环的话，最终success的node的out degree一定是0。不然success的node还能往外走就不是一个“终点”了，不知道这样理解是否正确？

一个比较笨的办法是直接画图算out degree，in degree，然后DFS求每个node的情况，不知道这样是否可以？楼主讲一下思路？

匿名用户 发表于 2022-7-21 20:34
是的，我也是做到一半才发现有没有环很重要。

我最后实现的办法就是dfs，如果没有neighbor而且当前nod ...

谢谢楼主分享，刚才看了一下可能这道题有点像刷题网衣领兀鹫的升级版。

没看懂，为什么3，5，6是return true

JellyDG 发表于 2022-07-22 06:55:30
没看懂，为什么3，5，6是return true

6本身是success，而且不会再去其他node，所以true

5只能到6，所以true

3只能到5，所以最终也只能到6，所以true

reach 是什么意思？ 路过不行？ 必须最终卡在一个success node 然后不能再走了？

匿名用户 发表于 2022-7-22 14:05
reach 是什么意思？ 路过不行？ 必须最终卡在一个success node 然后不能再走了？

是的，我确认过success node必须是terminal node，也就是没有可以继续走下去的neighbor