GG电面GG，感觉有点奇怪

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

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

我最开始没注意到那个acyclic的条件耽误了一些时间，之后阐述思路写代码分析complexity都没问题。唯一一个bug就是bfs过程中设了visited nodes之后忘记update了，经面试官提醒才发现。follow up的回答也很顺利。结果今天接到电话说fail。我在LC上没找到这道题，我也不知道面试官是不是觉得这道题太简单而我速度太慢。大家有什么观点呢？欢迎讨论，谢谢！

acyclic connected undirected graph就是tree吧，可以把A所在节点当做root，然后遍历看哪个分支的节点最多。
不知道能不能重复走和占领别人的节点。

写了一个模拟答案，思路是按照二楼大神取 拥有最大儿子数目的子树 请各位看看有啥问题不
class GraphNode {
public:
    vector<GraphNode*> neighbors;
    int val;
    GraphNode(int val) {
        this->val = val;
    }  
};

GraphNode* chooseMaxNode(vector<GraphNode*> allNodes, GraphNode* a) {
    GraphNode* b;
    int maxChildren = 0;
    for (GraphNode* node : a->neighbors) {
        int curChildren = getChildrenNumber(node);
        if (curChildren > maxChildren) {
            maxChildren = curChildren;
            b = node;
        }
    }
    return b;
}

int getChildrenNumber(GraphNode* root) {
    if (!root) {
        return 0;
    }

    int res = 0;
    for (GraphNode* child : root->neighbors) {
        res += getChildrenNumber(child);
    }
    return res + 1;
}

sunsiyue618 发表于 2019-2-6 17:38
我和你的思路类似，有一点不同是，选子节点最多的节点而不是最深的节点。dfs从a开始，每个node记录自己下 ...

我觉得你的想法是对的，但是不用每个node都记录，只要记录所有a的子节点记录就可以了，因为下面的节点肯定不会比他们大。所以我觉得bfs更好。当时我也是这么做的，complexity是O(n) time & space，面试官也认可了

我的想法 既然已经说了是联通的无向图还没有环 那必然是一颗树
以a为根节点建立这棵树 找到最深的子树 选择子树节点(也就是a的子节点)为b

楼主bfs啥思路。。

这道题我也面到了，我的思路是用两个queue但是就面试官一上来就直接把我思路驳回说我的想法复杂度太高
扯了半天也不让我写代码  一直重复让我举例子给input和output（觉得我没理解题意但我明明已经理解了）
所以就很迷，我也想看看各位对这题的看法

ef50mm 发表于 2019-2-6 14:10
我的想法 既然已经说了是联通的无向图还没有环 那必然是一颗树
以a为根节点建立这棵树 找到最深的子树 选 ...

我和你的思路类似，有一点不同是，选子节点最多的节点而不是最深的节点。dfs从a开始，每个node记录自己下面有多少个子节点。算完之后b落在子节点最多的节点上。

我觉得应该选max(deepest, most neighbors)吧。求高人指点

求问一下楼主能share一下代码嘛？多谢多谢~

follow up 是什么思路？
假设图1就1个点被A占了，怎么在图2落点？