IAC Interview Question: given a tree, with a number a... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate) Hangzhou, Zhejiang (China)

given a tree, with a number assigned to each node, and a

  size N, find the maximum subtree such that: a. it contains N nodes, b. maximizes sum of nodes in the subtree
c++ programming

Interview Answer

1 Answer


DP on tree, M[a][k] = maximum{ M[a.left][i]+M[a.right][N-i-1]+(i==N?0:num[a]), i=0..N }

Interview Candidate on Apr 9, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.