Directi Interview Question
Software Engineer / DevelopersCountry: India
read the question properly. how can you implement the tree there can be many child to a parent and you are given the index of the array so by that how will you add the node to the tree?
I didn't understand your question. Implementing a tree given an edge list should not be difficult.
The solution seems to be right but everytime calling the function S() on child node of an edge will not have a time complexity of O(1) making the total time complexity higher.
It won't be called every time. The calculation will be done once for the entire tree and the sum values stored in a new tree structured analogously to the original input.
What ever you suppose, they is the only problem..!!!
you write the algorithm for that only, not for that we after that, after that can be done by anyone who know something about programming. give us algorithm in support of your suppose, i have posted O(N^2) solution. as according to problem specification (10 sec, of time), it require N^2 time.
@sonesh: The problem does not require O(n^2) time. This solution is correct.
Looking at the constraints, O(n^2) would potentially time out, as there are up to 100 test cases. You have to read 100 (number of test cases) * 1000 (size of each test case) lines from input...that's why they didn't go for bigger inputs here.
It seems that you have some questions about how this works, but I can't understand what specifically you want to know. Can you formulate your question more clearly?
We can do it like this..!!!
#include <iostream>
#include <cmath>
using namespace std;
int sum;
struct Node
{
int id;
Node *next;
};
struct node
{
int id;
int pid;
node *next;
};
class Queue
{
private:
node *head;
node *tail;
public:
Queue()
{
head = NULL;
tail = NULL;
}
void insert(int id,int pid)
{
node *temp = new node();
temp->id = id;
temp->pid = pid;
temp->next = NULL;
if(tail)
tail->next = temp;
tail = temp;
if(!head)
head = temp;
}
node* remove()
{
node *temp = new node();
temp = head;
head = head->next;
return temp;
}
void display()
{
node *temp = head;
if(temp)
{
cout<<"("<<temp->id<<","<<temp->pid<<") -> ";
temp = temp->next;
}
}
bool empty()
{
if(head)
return false;
else
return true;
}
};
class List
{
private:
Node *head;
int weight;
int id;
public:
List()
{
head = NULL;
weight = 0;
id = 0;
}
void setpar(int d,int w)
{
id = d;
weight = w;
}
void insert(int a)
{
Node *temp = new Node();
temp->id = a;
temp->next = head;
head = temp;
}
void cal_sum(int a, Queue *queue)
{
sum = sum + weight;
if(head)
{
Node *temp = head;
while(temp)
{
if(temp->id != a)
queue->insert(temp->id,id);
temp = temp->next;
}
}
}
};
int main()
{
Queue queue;
node *temp = new node();
int T,N,i,diff,sum1,sum2,w;
cin>>T;
while(T--)
{
cin>>N;
int A[N-1],B[N-1];
List list[N];
for(i=0;i<N;i++)
{
cin>>w;
list[i].setpar(i,w);
}
for(i=0;i<N-1;i++)
{
cin>>A[i]>>B[i];
list[A[i]].insert(B[i]);
list[B[i]].insert(A[i]);
}
diff = -1;
for(i=0;i<N-1;i++)
{
sum = 0;
queue.insert(A[i],B[i]);
while(!queue.empty())
{
temp = queue.remove();
list[temp->id].cal_sum(temp->pid,&queue);
}
sum1 = sum;
sum = 0;
queue.insert(B[i],A[i]);
while(!queue.empty())
{
temp = queue.remove();
list[temp->id].cal_sum(temp->pid,&queue);
}
sum2 = sum;
if(diff == -1)
diff = abs(sum1-sum2);
else if(diff > abs(sum1-sum2))
diff = abs(sum1-sum2);
}
cout<<diff<<endl;
}
}
here n = 1000 and t = 100, my algorithm takes n^2 time, so here the total it become 10^3*10^3*10^2 = 10^8, can be done in 1 sec. by 10^9 calculation/sec. machine.
Hi, Eugene. Thanks for the kick in the head. I see that it's a single problem now :-) In the 1st test case, removal of the edge 2,1 yields two subtrees of weight 15 and 8 respectively w/difference = 7. In the 2nd test case, removal of edge 3,1 yields subtrees of weight 14 and 27 w/difference = 13. So, now I at least understand the problem and what's being asked. Off to code it up. Thanks again - C
it is a BFS question
save the tree as a graph in 2-d matrix or adjacency list form.
calulatemindiff()
{
for each edge
{
apply bfs on left part and then on right par to calculate the sum of its both side tree
calculate the difference of these to sum.
update the global diff accordingly.
}
return globaldiff;
}
This soution is O(m*(m+n)) because you are doing m BFSes. Read my comment above for an O(m+n) solution.
You're basically iterating over all nodes for each edge. That's quadratic complexity instead of the linear complexity achieved by another solution here.
Let us define the notion of 'root' and 'parent' on the tree. Let the root of the tree be 'r'.
- anujkaliaiitd July 15, 2012Suppose that for every node 'x', we have computed the total weight of the subtree rooted at 'x' (this includes the weight of 'x'). Let us call this sum: S(x).
Then for every edge (u,v) in the tree, where 'u' is the parent of 'v', the sums of the 2 trees formed on removing edge (u,v) are S(v) and S(r) - S(v). In this way, we can iterate over all the edges and return the minimum possible difference.
Time complexity: O(N), space O(N).