## Interview Question

**Country:**United States

I think this problem can be solved if we have a tree where no vertice has more than two edges, something like a link list perhaps. But a for a general tree it would depend on the kind of way the tree's edges and vertices are spread out. I can't be sure about it though. Please help if anyone ha a better answer

I solved this on interviewstreet.com using the following algo..

make a map of a node vs the no. of nodes connected to it..

iterate over the map

if for the ith node, the no. of nodes connected == even

-- then iterate over the nodes list connected to this node.

now for every connected jth node, again get the no. of nodes connected this jth node

if the no. of nodes connected to jth node == odd,

cut the edge ( increement the counter of cut edges )

Which company?

- Anonymous September 12, 2012