CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Directi Interview Question for Software Engineers


Team: Media.net
Country: India
Interview Type: Phone Interview



Comment hidden because of low score. Click to expand.
2
of 2 vote

foreach node in the branch which is no more than K deep, get:
W - max weight collected one way from the root to this node (this is a sum of the parent W and the weight of the edge taken)
D - depth traversed to this node
E - an incident edge with maximum value (edge to the parent or a child)
M - maximum collectible weight if jumping back and forth along the edge E
M = W + V * (K - D)

Maximum of M is the answer.

For example for K = 5, the maximum M is in the left most leaf, M = 29 + 24 * 3 = 101. Note that the leaves are not pictured by the author..

- JB February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
well thats a simple recursion code // {{{ int maxedge(struct node *root,int c,int k) { if(root==NULL) return 0; if(c==k) return 0; int left edge=0; int right edge=0; if(root->left) left edge=(root->left->wt);//edge to the left node if(root->right) right edge=(root->right->wt);//edge to the right node int l=0,r=0; if(root->left) l= maxedge(root->left,c+1,k); if(root->right) r=maxedge(root->right,c+1,k); return max( left edge+l,right edge+r); } - sid February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

well thats a simple recursion code //

int maxedge(struct node *root,int c,int k)
{
 if(root==NULL)
 return 0;
if(c==k)
return 0;
int left edge=0;
int right edge=0;
if(root->left)
left edge=(root->left->wt);//edge to the left node
if(root->right)
right edge=(root->right->wt);//edge to the right node 
int l=0,r=0;
if(root->left)
l= maxedge(root->left,c+1,k);
if(root->right)
r=maxedge(root->right,c+1,k);
return max( left edge+l,right edge+r);
}

- Anonymous February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are missing this part - "You can traverse in any direction either from parent to child or child to parent. You can visit a node multiple times".

- cold February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that we are given the adjacency list of the tree which contains the link to the parent. If not, we can easily build it in linear time.
We can use dynamic programming to solve this problem (in fact, my solution will work in a general graph, not only on a tree). So, our DP state will be:
DP[i][j]: max weigth we can achieve if we are on node i with j jumps left

Now the code in C++11 (I am coding my solution directly here to train for an interview, so it may contain some bugs/typos):

int root;
int weight[MAX_N]; // weight of each node
vector <int> g[MAX_N]; // adjacency list
int dp[MAX_N][MAX_K]; // initialized with -1

int solve(int node, int jumps){
	if(jumps == 0)
		return weight[node];
	if(dp[node][jumps] == -1){
		dp[node][jumps] = weight[node];
		for(int v : g[node])
			dp[node][jumps] = max(dp[node][jumps], solve(v, jumps - 1));
	}
	return dp[node][jumps];
}

We can now analize the complexity of this solution: O((V + E) * K).

We may be able to improve this solution using bottom-up construction and some dynamic programming optimization (divide and conquer optimization I think, but I haven't study it yet).

- Anonymous February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not correct. I didn't read the question right and assumed that the weights were on the nodes instead of edges.

Assuming we can collect the weigth of an edge multiple times:
We can adapt the solution easily and even improve it with the following observation:
- If we reach the maximum edge, we can just use that edge on all the jumps left.

If can only collect the weigth of each edge once, then the problem gets much more difficult and we need a much clever DP or a brute force with some heuristics and optimizations.

- Anonymous February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

recursive function

Maxi(node,k){
	if(k==0 || node ==NULL)
		return 0;
	max = 0;
	max = node.parents weight + Maxi(node.parent,k-1);
	for each(child of node)
		max  = maximum(max, child's weight +Maxi(child,k-1));
       return max;

}

}

- bhanu July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this problem can be turned in to unbounded knapsack problem and we can apply that concept here.

Store each edge weights as values and how many steps it took to reach those edges as their weights. store these values and weights in arrays. Now we need to maximise the value for a given weight, assuming we're given infinite set of each of these values.

Lemme know if this is right way to solve this problem.

- Sharath May 09, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More