CareerCup

Traverse the graph with DFS\BFS
For each node check its degree (get the neighbors, if it is its own neighbor, i.e. cycle, add another one)

My finding..

1) the number of subtrees of a node is called degree of the node.
2) The degree of a tree is the maximum degree of a node in the tree.
3) A binary tree is degree 2.

then i would to this

1) review all subtree of each node with BFS
2) have one variable to keep updating max num of subtree
3) once complete to review all nodes, then return max num which would be *degree* of the graph or tree

@ shivamdurani220 - BTW, are you sure if these are really interview questions from Google interview? recently you uploaded many and looks like some of them are exactly same as one in leetcode.. i'm not trying to be rude but just wondering...

struct AdjList{
    unordered_map<int,vector<int> > nodes;

    void insert(int i, int j){
        nodes[i].push_back(j);
        nodes[j].push_back(i);
    }

    vector<int> &getAllNeighbors(int n){
        return nodes[n];
    }
};


int findNodeWithDegree(int n, AdjList &adjList){
    unordered_map<int,int> counts;

    auto bfs = [&](int node){
        deque<int> q;
        counts[node] = 0;
        q.push_back(node);

        while(!q.empty()){
            auto front = q.front();
            q.pop_front();
            for(auto &other : adjList.getAllNeighbors(front)){
                if(counts.find(other) == counts.end()){
                    q.push_back(other);
                }
                counts[other]++;
            }
        }
    };

    for(auto &a : adjList.nodes){
        if(counts.find(a.first) == counts.end()){
            bfs(a.first);
        }
    }

    for(auto &p  : counts){
        if(p.second == n){
            return p.first;
        }
    }

    return -1;
}

int main() {
    AdjList adj;
    adj.insert(0,1);
    adj.insert(0,2);
    adj.insert(0,3);
    adj.insert(1,2);
    adj.insert(1,4);
    adj.insert(1,5);
    adj.insert(4,5);
    adj.insert(2,4);
    adj.insert(2,5);
    adj.insert(2,3);
    adj.nodes[6] = vector<int>();

    cout << findNodeWithDegree(5,adj) << endl;
    return 0;
}

Though the code to calculate vertex degree depends on the implementation of Graph data structure, here is a simple method to calculate a degree of a vertex.

We return TRUE if any of the vertex has a degree equal to N.

public static int degree(Graph G, int v)
{
  int degree = 0;
  for (int w : G.adj(v)) degree++;
  return degree;
}

we can make a adjency list and then we can count for each node and say how many nodes have n degree.

amazing