Facebook Interview Question Software Engineer / Developers
Country: India
it seems that according to your input, logical, it can't generate the output sample.
.
Since balance 3 has nothing on it it is already perfectly balanced, and weighs a total of 10 pounds.
why the output is "3:0 0", not "3: 5 5"
.
Balance 1 has balance three on its right side, which weighs 10 pounds, so we just put 10 pounds on its left side. Balance 1 weighs a total of 30 pounds.
why balance 1 weights a total of "30" pounds, not "20"? do you mean left weights 10 and right weights 10 as well? if Yes, why the output is not "3:10 10"?
so,my rough idea is
1. data struct
struct node
{
int leftWeight; // raw data (read from file) on the left of balance
int righWeightt; // raw data on the right of balance
int leftAdd; // weighs added to the left by calc
int rightAdd; // weighs added to the right by calc
int left; // point to the index of balance which is read from file
int right; // point tot he index of balance which is read from file too
};
2. read from file by 2 lines every time, and add to a vector from index 1, e.g.
0 1
0 2
vector<node*> v;
node* n = new node();
n.leftweight = 0;
n.rightweight = 0;
n.left = 1
n.right = 2;
v.add(n);
......
3. for-loop vector from tail to head, and calc the leftadd and rightadd in every node
3. output the vector element one by one.
this solution does not handle many balances, as the question description said: "<balances> is a space-delimited list of the other balance that are on that side of this balance.
<balances> may contain zero or more elements.". I think that the better way to solve this question, would be use a B-Tree structure.
Ye, I received a link from my friend, saying this is the facebook programming challenge. So I had a try. I finished it and submitted it and had extra 30 mins. Then I looked for the 2nd question, but I found that I could only solve 1 question with my account. I realized this is the only chance. so I submitted a resume to facebook immediately. A week later, I got contacted by facebook recruiter saying I solved one challenge and glad to talk to me. It was unexpected, I have to say I had luck this time. Hope I will do well in the interview next week. Good luck to everybody here, including myself. : )
public class BalanceProblem {
public class Balance {
Integer id;
Balance leftBalance;
Balance rightBalance;
Integer leftBalanceId;
Integer rightBalanceId;
Integer leftWeight;
Integer rightWeight;
Integer totalWeight;
public Balance(Integer id) {
this.id = id;
}
}
Map<Integer, Balance> balances;
Map<Integer, Pair<Integer>> balanced;
public Map<Integer, Pair<Integer>> getBalanced() {
return balanced;
}
public BalanceProblem(String file) throws IOException {
File f = new File(file);
BufferedReader reader = new BufferedReader(new FileReader(f));
String line = reader.readLine();
balances = new HashMap<Integer, BalanceProblem.Balance>(
Integer.parseInt(line));
boolean balanceProcessed = false;
Integer i = 0;
Balance b = null;
while ((line = reader.readLine()) != null) {
String[] split = line.split(" ");
if (!balanceProcessed) {
b = new Balance(i);
b.leftWeight = Integer.parseInt(split[0]);
if (split.length == 2) {
b.leftBalanceId = Integer.parseInt(split[1]);
}
balanceProcessed = true;
} else {
b.rightWeight = Integer.parseInt(split[0]);
if (split.length == 2) {
b.rightBalanceId = Integer.parseInt(split[1]);
}
balances.put(b.id, b);
balanceProcessed = false;
++i;
}
}
initializeWeightsAndBalance();
}
private int getBalanceWeight(Balance b, int weight) {
if (b.leftBalance != null) {
if (b.leftBalance.totalWeight == null) {
weight += getBalanceWeight(b.leftBalance, weight);
} else {
weight += b.leftBalance.totalWeight;
}
}
if (b.rightBalance != null) {
if (b.rightBalance.totalWeight == null) {
weight += getBalanceWeight(b.rightBalance, weight);
} else {
weight += b.rightBalance.totalWeight;
}
}
weight += b.leftWeight + b.rightWeight;
return weight;
}
private int getBalanceWeight(Balance b) {
if (b.totalWeight == null) {
return getBalanceWeight(b, 10);
} else {
return b.totalWeight;
}
}
private void balanceLeaf(Balance b) {
int rightBalanceWeight = 0;
int leftBalanceWeight = 0;
if (b.leftWeight != b.rightWeight) {
if (b.leftWeight > b.rightWeight) {
rightBalanceWeight = b.leftWeight - b.rightWeight;
b.rightWeight += rightBalanceWeight;
} else {
leftBalanceWeight = b.rightWeight - b.leftWeight;
b.leftWeight += leftBalanceWeight;
}
}
balanced.put(b.id, new Pair<Integer>(leftBalanceWeight,
rightBalanceWeight));
}
private void balanceNode(Balance b) {
int rightBalanceWeight = 0;
int leftBalanceWeight = 0;
int leftWeight = b.leftWeight;
if (b.leftBalance != null) {
if (!balanced.containsKey(b.leftBalanceId)) {
balanceNode(b.leftBalance);
}
leftWeight += getBalanceWeight(b.leftBalance);
}
int rightWeight = b.rightWeight;
if (b.rightBalance != null) {
if (!balanced.containsKey(b.rightBalanceId)) {
balanceNode(b.rightBalance);
}
rightWeight += getBalanceWeight(b.rightBalance);
}
if (leftWeight != rightWeight) {
if (leftWeight > rightWeight) {
rightBalanceWeight = leftWeight - rightWeight;
b.rightWeight += rightBalanceWeight;
} else {
leftBalanceWeight = rightWeight - leftWeight;
b.leftWeight += leftBalanceWeight;
}
}
balanced.put(b.id, new Pair<Integer>(leftBalanceWeight, rightBalanceWeight));
}
private void initializeWeightsAndBalance() {
ArrayList<Balance> leafBalances = new ArrayList<BalanceProblem.Balance>();
ArrayList<Balance> nodeBalances = new ArrayList<BalanceProblem.Balance>();
for (Balance b : balances.values()) {
if (b.leftBalanceId == null && b.rightBalanceId == null) {
leafBalances.add(b);
} else {
if (b.leftBalanceId != null) {
b.leftBalance = balances.get(b.leftBalanceId);
}
if (b.rightBalanceId != null) {
b.rightBalance = balances.get(b.rightBalanceId);
}
nodeBalances.add(b);
}
}
balanced = new HashMap<Integer, Pair<Integer>>();
for (Balance b : leafBalances) {
balanceLeaf(b);
b.totalWeight = getBalanceWeight(b);
}
for (Balance b : nodeBalances) {
if (!balanced.containsKey(b.id)) {
balanceNode(b);
}
}
}
public static void main(String[] args) throws IOException {
String file = "balance.text";
BalanceProblem bp = new BalanceProblem(file);
Map<Integer, Pair<Integer>> balanced = bp.getBalanced();
for (Integer i : balanced.keySet()) {
System.out.println(String.format("%s : %s", i, balanced.get(i)));
}
}
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<assert.h>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int inf=1000000000;
const double pi=acos(-1.0);
#define eps (1e-15)
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define see(x)(cerr<<"[line:"<<__LINE__<<" "<<#x<<" "<<x<<endl)
#define se(x) cerr<<x<<" "
template<class T>T& ls(T& a,T b)
{ if(b<a) a=b; return a;}
template<class T>T& gs(T& a,T b)
{ if(b>a) a=b; return a;}
inline int to_i(const string& s)
{int n;sscanf(s.c_str(),"%d",&n);return n;}
inline string to_s(int n)
{char buf[32];sprintf(buf,"%d",n);return string(buf);}
const int maxn =1000;
int n,m;
struct node
{
vector<int> l,r;
int la,ra;
int sum,add;
node(){};
void init()
{
l.clear();
r.clear();
la=ra=0;
sum=10;
add=0;
}
}tr[maxn];
int cur=0;
char ch[1000];
int get(int rt)
{
int i,j,k;
for(i=0; i<tr[rt].l.size(); i++)
{
k=get(tr[rt].l[i]);
tr[rt].la+=k;
}
for(i=0; i<tr[rt].r.size(); i++)
{
k=get(tr[rt].r[i]);
tr[rt].ra+=k;
}
tr[rt].add=tr[rt].la-tr[rt].ra;
return tr[rt].sum+=max(tr[rt].la,tr[rt].ra)*2;
}
int main()
{
freopen("in.txt","r",stdin);
int i,j,k,t,x,y;
cur=1;
scanf("%d",&n);
getchar();
string s;
for(i=1; i<=n; i++)
{
tr[i].init();
stringstream in;
cin.getline(ch,1000);
in<<ch;
in>>x;
tr[i].la=x;
while(in>>x)
{
x++;
tr[i].l.push_back(x);
}
in.clear();
cin.getline(ch,1000);
in<<ch;
in>>x;
tr[i].ra=x;
while(in>>x)
{
x++;
tr[i].r.push_back(x);
}
}
get(1);
for(i=1; i<=n; i++)
{
if(tr[i].add<0)
printf("%d:%d %d\n",i-1,-tr[i].add,0);
else
printf("%d:%d %d\n",i-1,0,tr[i].add);
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct stacklist
{
struct slinkedlist *val;
struct stacklist *next;
}stack;
typedef struct slinkedlist
{
int b;
int w;
int awr;
int awl;
int wl;
int wr;
stack *rnext;
stack *lnext;
}slist;
int pop(stack **head)
{
stack *temp;
temp=(*head);
(*head)=temp->next;
free(temp);
}
int sfree(stack **head)
{
if((*head)!=NULL)
{
stack *temp=(*head)->next;
free((*head));
sfree(&temp);
}
return 0;
}
int push(stack **head,slist *data)
{
stack *temp=(stack *)malloc(sizeof(stack));
temp->val=data;
temp->next=(*head);
(*head)=temp;
}
int sum(slist *num)
{
stack *temp;
if(num->b==1) return num->w;
while(num->rnext!=NULL)
{
num->wr+=sum(num->rnext->val);
num->rnext=num->rnext->next;
}
while(num->lnext!=NULL)
{
num->wl+=sum(num->lnext->val);
num->lnext=num->lnext->next;
}
if(num->wr>num->wl)
{
num->awr=0;
num->awl=num->wr-num->wl;
num->w=10+2*(num->wr);
}
else
{
num->awl=0;
num->awr=num->wl-num->wr;
num->w=10+2*(num->wl);
}
num->b=1;
return num->w;
}
int main()
{
int i,j,k;
int n;
char c;
int temp;
slist *num;
scanf("%d",&n);
num=(slist *)malloc(n*sizeof(slist));
for(i=0;i<n;i++)
{
num[i].rnext=NULL;
num[i].lnext=NULL;
num[i].b=0;
scanf("%d",&(num[i].wl));
scanf("%c",&c);
while(c!='\n')
{
scanf("%d",&temp);
push(&(num[i].lnext),&num[temp]);
scanf("%c",&c);
}
scanf("%d",&(num[i].wr));
scanf("%c",&c);
while(c!='\n')
{
scanf("%d",&temp);
push(&(num[i].rnext),&num[temp]);
scanf("%c",&c);
}
}
for(i=0;i<n;i++)
{
sum(&num[i]);
}
for(i=0;i<n;i++)
{
printf("%d: %d %d\n",i,num[i].awl,num[i].awr);
}
for(i=0;i<n;i++);
{
sfree(&(num[i].rnext));
sfree(&(num[i].lnext));
}
free(num);
return 0;
}
#include<iostream>
#include<stack>
#include<vector>
#include<string.h>
using namespace std;
class balances
{
public:
int lweight;
int rweight;
vector<int> lchild;
vector<int> rchild;
int total;
balances()
{
lweight = rweight = total = -1;
}
};
class output
{
public:
int lweight;
int rweight;
output()
{
lweight = rweight = -1;
}
};
int main()
{
stack<int> st;
int num;
cin>>num;
balances balance[num];
output out[num];
cin.ignore();
for(int i=0;i<num;i++)
{
int w = 0;
string str;
getline(cin, str);
const char* s = str.c_str();
char* line = const_cast <char*>(s);
char* tok = strtok(line, " ");
balance[i].lweight = atoi(tok);
tok = strtok(NULL, " ");
while(tok!=NULL)
{
balance[i].lchild.push_back(atoi(tok));
tok = strtok(NULL, " ");
}
getline(cin, str);
s = str.c_str();
line = const_cast<char*>(s);
tok = strtok(line, " ");
balance[i].rweight = atoi(tok);
tok = strtok(NULL, " ");
while(tok!=NULL)
{
balance[i].rchild.push_back(atoi(tok));
tok = strtok(NULL, " ");
}
if((balance[i].lchild.size() == 0) && (balance[i].rchild.size() == 0))
{
if(balance[i].lweight == balance[i].rweight)
{
balance[i].total = balance[i].lweight + balance[i].rweight + 10;
out[i].lweight = out[i].rweight = 0;
}
else
{
if(balance[i].lweight > balance[i].rweight)
{
out[i].lweight = 0;
out[i].rweight = balance[i].lweight - balance[i].rweight;
balance[i].total = balance[i].lweight + balance[i].rweight + 10 + out[i].rweight;
}
else
{
out[i].rweight = 0;
out[i].lweight = balance[i].rweight - balance[i].lweight;
balance[i].total = balance[i].lweight + balance[i].rweight + 10 + out[i].lweight;
}
}
}
}
int i=0;
while(i<num)
{
int flag = 0;
int diff = 0;
if(balance[i].total != -1)
{
if(st.size()!=0)
{
i = st.top();
st.pop();
}
else
i++;
continue;
}
for(int j = 0;j<balance[i].lchild.size();j++)
{
Sorry for the above post. Submitted by mistake.
Here is the code I wrote for it. I did not try and cleanup or improve it so might have redundant stuff. But it works.
#include<iostream>
#include<stack>
#include<vector>
#include<string.h>
using namespace std;
class balances
{
public:
int lweight;
int rweight;
vector<int> lchild;
vector<int> rchild;
int total;
balances()
{
lweight = rweight = total = -1;
}
};
class output
{
public:
int lweight;
int rweight;
output()
{
lweight = rweight = -1;
}
};
int main()
{
stack<int> st;
int num;
cin>>num;
balances balance[num];
output out[num];
cin.ignore();
for(int i=0;i<num;i++)
{
int w = 0;
string str;
getline(cin, str);
const char* s = str.c_str();
char* line = const_cast <char*>(s);
char* tok = strtok(line, " ");
balance[i].lweight = atoi(tok);
tok = strtok(NULL, " ");
while(tok!=NULL)
{
balance[i].lchild.push_back(atoi(tok));
tok = strtok(NULL, " ");
}
getline(cin, str);
s = str.c_str();
line = const_cast<char*>(s);
tok = strtok(line, " ");
balance[i].rweight = atoi(tok);
tok = strtok(NULL, " ");
while(tok!=NULL)
{
balance[i].rchild.push_back(atoi(tok));
tok = strtok(NULL, " ");
}
if((balance[i].lchild.size() == 0) && (balance[i].rchild.size() == 0))
{
if(balance[i].lweight == balance[i].rweight)
{
balance[i].total = balance[i].lweight + balance[i].rweight + 10;
out[i].lweight = out[i].rweight = 0;
}
else
{
if(balance[i].lweight > balance[i].rweight)
{
out[i].lweight = 0;
out[i].rweight = balance[i].lweight - balance[i].rweight;
balance[i].total = balance[i].lweight + balance[i].rweight + 10 + out[i].rweight;
}
else
{
out[i].rweight = 0;
out[i].lweight = balance[i].rweight - balance[i].lweight;
balance[i].total = balance[i].lweight + balance[i].rweight + 10 + out[i].lweight;
}
}
}
}
int i=0;
while(i<num)
{
int flag = 0;
int diff = 0;
if(balance[i].total != -1)
{
if(st.size()!=0)
{
i = st.top();
st.pop();
}
else
i++;
continue;
}
for(int j = 0;j<balance[i].lchild.size();j++)
{
if(balance[balance[i].lchild[j]].total != -1)
continue;
st.push(i);
i = balance[i].lchild[j];
flag = 1;
break;
}
if(flag)
continue;
for(int j = 0;j<balance[i].rchild.size();j++)
{
if(balance[balance[i].rchild[j]].total != -1)
continue;
st.push(i);
i = balance[i].rchild[j];
flag = 1;
break;
}
if(flag)
continue;
int l=balance[i].lweight,r=balance[i].rweight;
for(int j=0;j<balance[i].lchild.size();j++)
l += balance[balance[i].lchild[j]].total;
for(int j=0;j<balance[i].rchild.size();j++)
r += balance[balance[i].rchild[j]].total;
diff = r-l;
balance[i].total = l + r + 10 + abs(diff);
if(diff>0)
{
out[i].lweight = abs(diff);
out[i].rweight = 0;
}
else
{ out[i].rweight = abs(diff);
out[i].lweight = 0;
}
}
int first;
for(int i=0;i<num;i++)
{
if(first)
cout<<endl;
cout<<i<<": "<< out[i].lweight<<" "<<out[i].rweight;
first = 1;
}
return 0;
}
Its a simple recursive DFS like soln
Store set of left balances, right balances
initialize each one to isBalanced = false
for(int i=0;i<N;i++) {
if(b[i].isBalanced==false)
getBalance(b, i, N);
}
void getBalance(balance b[], int k, int N) {
l_e = b[k].lef_edges;
r_e = b[k].right_edges;
for(all left_edges) if(not balanced) getBalanced(left_edge)
for(all right_edges) if(not balanced) getBalance(right edge)
// balance the kth balance
compute extra weight to be added for balancing
}
Here is my recursive implementation . ( pseudo code )
I am assuming input is stored in file.
No NULL checking.
struct node {
int rw; // right side weight
int lw; // left side weight
struct node * lb //Balance on left side
struct node * rb // Balace on right side
int cbr // Counter balance needed on right.
int cbl // counter balance needed on left.
}
// I will compute cbl and cbr for each node.
int main(){
int totalbal;
int temp=0;
struct node * T;
File * fp=fopen ( "input.txt",r);
fscanf(fp,"%d\n",&totalbal);
T= ( stuct node *) malloc ( sizeof (struct node) * totoalbal);
//Now I have all the empty nodes.
node=0;
while( feof(fp)){
int wl,wr,bl=0,br=0;
fscanf(fp,"%d %d\n",wl,bl );
fscanf(fp,"%d %d\n",wr,br );
T[node].lw = wl
T[node].rw = wr
T[node].lb = bl==0 ? NULL : node[bl]
T[node].rb = br==0 ? NULL : node[br]
T[node].cbr = T[node].cbl = 0;
node++;
}
// Now I will have all the nodes initialized and configured.
Balance(T);
PrintOutput(T);
}
// Computes balance for each node and returns total weight on that node after counter balancing.
int Balance ( struct node * T)
{
if ( T->lb != NULL )
T->lw += Balance( T->lb);
if ( T->lb != NULL )
T->rw += Balance( T->rb);
if (T->lw > T->rw )
T->cbr = T->lw - T->rw
else if (T->rw > T->lw )
T->cbl = T->rw - T->lw
else
T-> cbl = T->cbr = 0 //unnecessary
return 10 + T->cbl + T->cbr + T->rw + T->lw; // 10 for balance weight
}
PrintOutput ( stuct node * T) {
for ( i =0; i<totalbal ; i++ )
print ( " %d : %d %d\n", i , T[i]->cbl,T[i]->cbr);
}
#include<iostream>
#include<vector.h>
#include<string.h>
#include<stdio.h>
#include<queue.h>
using namespace std;
struct node
{
int lw;
int rw;
vector<int> l;
vector<int> r;
}*start;
int main()
{
char s[100];
vector<int> v;
start=NULL;
node *temp;
int n,lw,rw,k,num,c,l;
cin>>n;
node **isset=new node*[n];
for(int i=0;i<n;i++)
isset[i]=NULL;
for(int i=0;i<n;i++)
{
for(int j=0;j<2;j++)
{
gets(s);
k=0;
v.clear();
while(k!=strlen(s) && s[k]!=' ')
{
v.push_back(s[k]-'0');
k++;
}
num=0;
c=1;
l=k-1;
while(l>=0)
{
num+=(v[l]*c);
c*=10;
l--;
}
lw=num;
if(start==NULL)
{
start=new node;
isset[0]=start;
}
if(isset[i]==NULL)
{
temp=new node;
isset[i]=temp;
}
if(j)
(isset[i])->rw=lw;
else
(isset[i])->lw=lw;
if(k!=strlen(s))
{
while(k!=strlen(s))
{
k++;
v.clear();
while(k!=strlen(s) && s[k]!=' ')
{
v.push_back(s[k]-'0');
k++;
}
num=0;
c=1;
l=v.size()-1;
while(l>=0)
{
num+=(v[l]*c);
c*=10;
l--;
}
if(isset[num]==NULL)
{
temp=new node;
isset[num]=temp;
}
if(j==0)
((isset[i])->l).push_back(num);
else
((isset[i])->r).push_back(num);
}
}
}
}
v.clear();
int x,y,z;
queue<int> q;
temp=start;
q.push(0);
while(!q.empty())
{
x=q.front();
q.pop();
v.push_back(x);
y=0;
while(y!=((isset[x])->l).size())
{
q.push((isset[x]->l)[y]);
y++;
}
y=0;
while(y!=((isset[x])->r).size())
{
q.push((isset[x]->r)[y]);
y++;
}
}
int **ans=new int*[n];
for(int i=0;i<n;i++)
{
ans[i]=new int[2];
for(int j=0;j<2;j++)
ans[i][j]=0;
}
y=n-1;
int *tw=new int[n];
while(y>=0)
{
lw=(isset[v[y]]->lw);
z=0;
while(z!=(((isset[v[y]])->l).size()))
{
lw+=(tw[(isset[v[y]]->l)[z]]);
z++;
}
z=0;
rw=(isset[v[y]]->rw);
while(z!=(((isset[v[y]])->r).size()))
{
rw+=(tw[(isset[v[y]]->r)[z]]);
z++;
}
if(lw>rw)
{
ans[v[y]][1]=(lw-rw);
isset[v[y]]->rw=lw;
rw=lw;
}
else if(rw>lw)
{
ans[v[y]][0]=(rw-lw);
isset[v[y]]->lw=rw;
lw=rw;
}
tw[v[y]]=lw+rw+10;
y--;
}
for(int i=0;i<n;i++)
{
cout<<i<<": "<<ans[i][0]<<" "<<ans[i][1]<<endl;
}
}
#include<iostream>
#include<vector>
#include<malloc.h>
#include<stdio.h>
using namespace std;
struct node
{
int nodenum;
int left;
int right;
vector<int> leftbal;
vector<int> rightbal;
int total;
};
int main()
{
struct node *arr[10];
int N;
int l=1;
int level[100]={0};
char str[100];
int result=0;
cin>>N;
for(int i=0;i<N;i++)
{
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
p->nodenum=i;
p->total=0;
arr[i]=p;
fflush(stdin);
for(int j=0;j<2;j++)
{
fflush(stdin);
gets(str);
fflush(stdin);
int flag=0;
int number=0;
for(int k=0;k<strlen(str);k++)
{
if(str[k]==' ' && flag==0)
{
if(j==0)
{
p->left=number;
}
else
{
p->right=number;
}
number=0;
flag=1;
continue;
}
else if(str[k]==' ' && flag==1)
{
if(j==0)
{
p->leftbal.push_back(number);
}
else
{
p->rightbal.push_back(number);
}
level[l]=number;
l++;
number=0;
continue;
}
number=number*10+(str[k]-'0');
}
if(flag==0)
{
if(j==0)
{
p->left=number;
}
else
{
p->right=number;
}
}
else
{
if(j==0)
{
p->leftbal.push_back(number);
}
else
{
p->rightbal.push_back(number);
}
level[l]=number;
l++;
}
}
}
for(int i=N-1;i>=0;i--)
{
int balance=level[i];
struct node *p=arr[balance];
int wl=p->left;
int wr=p->right;
int index=-1;
for(int j=0;j<p->leftbal.size();j++)
{
index=p->leftbal[j];
wl=wl+arr[index]->total;
}
for(int j=0;j<p->rightbal.size();j++)
{
index=p->rightbal[j];
wr=wr+arr[index]->total;
}
p->left=wl;
p->right=wr;
if(wl>wr)
{
result=result+(wl-wr);
p->total=2*wl + 10;
}
else
{
result=result+(wr-wl);
p->total=2*wr +10;
}
}
for(int i=0;i<N;i++)
{
struct node *p;
p=arr[i];
if((p->left)>(p->right))
cout<<p->nodenum<<": "<<0<<" "<<(p->left)-(p->right)<<"\n";
else
cout<<p->nodenum<<": "<<(p->right)-(p->left)<<" "<<0<<"\n";
}
}
#include<iostream>
#include<vector>
#include<malloc.h>
#include<stdio.h>
#include<queue>
#include<stack>
using namespace std;
struct node
{
int nodenum;
int left;
int right;
vector<int> leftbal;
vector<int> rightbal;
int total;
};
int main()
{
struct node *arr[10];
int N;
char str[100];
int result=0;
cin>>N;
for(int i=0;i<N;i++)
{
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
p->nodenum=i;
p->total=0;
arr[i]=p;
fflush(stdin);
for(int j=0;j<2;j++)
{
fflush(stdin);
gets(str);
fflush(stdin);
int flag=0;
int number=0;
for(int k=0;k<strlen(str);k++)
{
if(str[k]==' ' && flag==0)
{
if(j==0)
{
p->left=number;
}
else
{
p->right=number;
}
number=0;
flag=1;
continue;
}
else if(str[k]==' ' && flag==1)
{
if(j==0)
{
p->leftbal.push_back(number);
}
else
{
p->rightbal.push_back(number);
}
number=0;
continue;
}
number=number*10+(str[k]-'0');
}
if(flag==0)
{
if(j==0)
{
p->left=number;
}
else
{
p->right=number;
}
}
else
{
if(j==0)
{
p->leftbal.push_back(number);
}
else
{
p->rightbal.push_back(number);
}
}
}
}
int start=0;
for(int i=0;i<N;i++)
{
struct node *p;
p=arr[i];
for(int j=0;j<p->leftbal.size();j++)
{
if(p->leftbal[j]==start)
start=i;
}
for(int j=0;j<p->rightbal.size();j++)
{
if(p->rightbal[j]==start)
start=i;
}
}
queue <int> myqueue;
stack <int> final;
myqueue.push(start);
while(!myqueue.empty())
{
int id=myqueue.front();
myqueue.pop();
final.push(id);
struct node *p;
p=arr[id];
for(int j=0;j<p->leftbal.size();j++)
{
myqueue.push(p->leftbal[j]);
}
for(int j=0;j<p->rightbal.size();j++)
{
myqueue.push(p->rightbal[j]);
}
}
while(!final.empty())
{
int balance=final.top();
final.pop();
cout<<"balance is"<<balance<<endl;
struct node *p=arr[balance];
int wl=p->left;
int wr=p->right;
int index=-1;
for(int j=0;j<p->leftbal.size();j++)
{
index=p->leftbal[j];
wl=wl+arr[index]->total;
}
for(int j=0;j<p->rightbal.size();j++)
{
index=p->rightbal[j];
wr=wr+arr[index]->total;
}
p->left=wl;
p->right=wr;
if(wl>wr)
{
result=result+(wl-wr);
p->total=2*wl + 10;
}
else
{
result=result+(wr-wl);
p->total=2*wr +10;
}
}
for(int i=0;i<N;i++)
{
struct node *p;
p=arr[i];
if((p->left)>(p->right))
cout<<p->nodenum<<": "<<0<<" "<<(p->left)-(p->right)<<"\n";
else
cout<<p->nodenum<<": "<<(p->right)-(p->left)<<" "<<0<<"\n";
}
cout<<result;
}
//taking input fronm a txt file named fb.txt
#include<stdio.h>
typedef struct node{
int weight;
int name;
int lw;
int rw;
struct node*left;
struct node*right;
}*NODEPTR;
NODEPTR ptree;
void inorder(NODEPTR p);
void print_bal(NODEPTR p);
void main()
{
ptree=0;
//input
int N;
FILE *f;
int i,b,wl,wr,bl,br,t;
f=fopen("fb.txt","r");
fscanf(f,"%d",&N);
NODEPTR bal[N];
for(i=0;i<N;i++)
{
bal[i]=(NODEPTR*)malloc(sizeof(struct node));
bal[i]->name=i;
bal[i]->left=0;
bal[i]->right=0;
bal[i]->weight=10;
bal[i]->lw=0;
bal[i]->rw=0;
}
//create tree
for(i=0;i<N;i++)
{
//if no balance then enter sothing above N
fscanf(f,"%d",&wl);
fscanf(f,"%d",&bl);
fscanf(f,"%d",&wr);
fscanf(f,"%d",&br);
if(bl<=N)
{
if(ptree==0)
ptree=bal[i];
bal[i]->left=bal[bl];
}
if(br<=N)
{
if(ptree==0)
ptree=bal[i];
bal[i]->right=bal[br];
}
bal[i]->lw=wl;
bal[i]->rw=wr;
//bal[i]->weight+=wl+wr;
}
print_bal(ptree);
inorder(ptree);
}
void inorder(NODEPTR p)
{
if(p!=0)
{
inorder(p->left);
printf("%d ->",p->weight);
inorder(p->right);
}
}
void print_bal(NODEPTR p)
{
int l,r;
if(p!=0)
{
print_bal(p->right);
print_bal(p->left);
if(p->left==0&&p->right==0) // printf("NOTHING TO ADD on :%c: w=%d\n",p->name,p->weight);
{
if(p->lw==0&&p->rw==0)
;//do nothing
else if(p->lw!=0&&p->rw==0)
{
printf("node :%d: add to R: %d \n",p->name,p->lw);
// p->weight=p->weight+p->lw;
p->rw+=p->lw;
}
else if(p->rw!=0&&p->lw==0)
{
printf("node :%d: add to L: %d \n",p->name,p->rw);
// p->weight=p->weight+p->rw;
p->lw+=p->rw;
}
else if(p->rw!=0&&p->lw!=0)
{
if(p->lw!=p->rw)
{
if(p->lw < p->rw)
{
printf("node :%d: add to L :%d\n",p->name,p->rw-p->lw);
// p->weight=p->weight+(p->rw-p->lw);
p->lw+=(p->rw-p->lw);
}
else
{
printf("node :%d: add to R :%d\n",p->name,p->lw-p->rw);
// p->weight=p->weight+(p->lw-p->rw);
p->rw+=(p->lw-p->rw);
}
}
}
p->weight+=(p->lw+p->rw); //updqte whole weight
}
else if(p->left==0&&p->right!=0)
{
l=p->lw;
r=p->rw+p->right->weight;
if(l!=r)
{
if(l>r)
{
printf("node :%d: add to R :%d\n",p->name,l-r);
p->rw+=l-r;
}
else
{
printf("node :%d: add to L :%d\n",p->name,r-l);
p->lw+=r-l;
}
}
p->weight+=p->rw+p->lw+p->right->weight;
}
else if(p->left!=0&&p->right==0)
{
l=p->lw+p->left->weight;
r=p->rw;
if(l!=r)
{
if(l>r)
{
printf("node :%d: add to R :%d\n",p->name,l-r);
p->rw+=l-r;
}
else
{
printf("node :%d: add to L :%d\n",p->name,r-l);
p->lw+=r-l;
}
}
p->weight+=p->rw+p->lw+p->left->weight;
}
else if(p->left!=0&&p->right!=0)
{
l=p->right->weight;
r=p->left->weight;
l=l+p->lw;
r=r+p->rw;
if(l!=r)
{
if(l>r)
{
printf("node :%d: add to R :%d\n",p->name,l-r);
p->rw+=(l-r);
}
else
{
printf("node :%d: add to L :%d\n",p->name,r-l);
p->lw+=(r-l);
}
}
p->weight+=p->rw+p->lw+p->right->weight+p->left->weight;
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class balance {
int wl;// left weight
int wr;// right weight
int wt;// total weight
int init_wl;
int init_wr;
int[] left_bal;
int[] right_bal;
}
public class Main {
public static int n;
public static balance[] bal;
public static int[] flag;
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
bal = new balance[n];
flag = new int[n];
for (int i = 0; i < n; ++i) {
flag[i] = 0;
/**
* indicates that the balance ith total weight is not calculated
*/
}
for (int i = 0; i < n; ++i) {
// adding left balance part
st = new StringTokenizer(br.readLine());
bal[i] = new balance();
bal[i].init_wl = Integer.parseInt(st.nextToken());
bal[i].left_bal = new int[st.countTokens()];
int c1 = st.countTokens();
for (int j = 0; j < c1; ++j) {
bal[i].left_bal[j] = Integer.parseInt(st.nextToken());
}
// adding right balance part
st = new StringTokenizer(br.readLine());
bal[i].init_wr = Integer.parseInt(st.nextToken());
bal[i].right_bal = new int[st.countTokens()];
int c2 = st.countTokens();
for (int j = 0; j < c2; ++j) {
bal[i].right_bal[j] = Integer.parseInt(st.nextToken());
}
}
// Algo for balancing
for (int i = 0; i < n; ++i) {
find_balance(i);
}
//print result
for(int i=0;i<n;++i)
{
if(bal[i].wl>bal[i].wr)
{
System.out.println(i+": "+"0"+" "+diff(bal[i].wl,bal[i].wr));
}
else
{
System.out.println(i+": "+diff(bal[i].wl,bal[i].wr)+" "+"0");
}
}
}
public static void find_balance(int id) {
bal[id].wt=0;
// make sure weight of all left and right balances are found
// left
bal[id].wl=0;
bal[id].wl=bal[id].init_wl;
for (int j = 0; j < bal[id].left_bal.length; ++j) {
if (flag[bal[id].left_bal[j]] == 0) {
//System.out.println("find "+bal[id].left_bal[j]);
find_balance(bal[id].left_bal[j]);
}
bal[id].wl+=bal[bal[id].left_bal[j]].wt;
//System.out.println("bal_wL "+"("+id+")"+"="+bal[id].wl);
}
// right
bal[id].wr=0;
bal[id].wr=bal[id].init_wr;
for (int k = 0; k < bal[id].right_bal.length; ++k) {
if (flag[bal[id].right_bal[k]] == 0) {
//System.out.println("find "+bal[id].right_bal[k]);
find_balance(bal[id].right_bal[k]);
}
bal[id].wr+=bal[bal[id].right_bal[k]].wt;
//System.out.println("bal_wR "+"("+id+")"+"="+bal[id].wr);
}
//find the weight of current balance
bal[id].wt=bal[id].wl+bal[id].wr+10+diff(bal[id].wl,bal[id].wr);
//System.out.println("bal_wT "+"("+id+")"+"="+bal[id].wt);
//set flag
flag[id]=1;
//System.out.println("EXIT("+id+")");
return;
}
public static int diff(int a,int b)
{
if(a>b)
return (a-b);
else
return (b-a);
}
}
//C# : It Works
using System;
class Balance
{
public int weightLeft;
public int weightRight;
public Balance leftBalance;
public Balance rightBalance;
public int totalWeight;
public Balance()
{
totalWeight = 10;
weightLeft = 0;
weightRight = 0;
}
public void addWeightLeft(int _value)
{
weightLeft = _value;
totalWeight = totalWeight + weightLeft;
}
public void addWeightRight(int _value)
{
weightRight = _value;
totalWeight = totalWeight + weightRight;
}
public void addLeftBalance(Balance _balance)
{
leftBalance = _balance;
weightLeft += _balance.totalWeight;
totalWeight += _balance.totalWeight;
}
public void addRightBalance(Balance _balance)
{
rightBalance = _balance;
weightRight += _balance.totalWeight;
totalWeight += _balance.totalWeight;
}
public void addLeftBalanceExtra()
{
if (leftBalance != null)
{
weightLeft += leftBalance.weightLeft;
weightRight += leftBalance.weightRight;
}
}
public void addRightBalanceExtra()
{
if (rightBalance != null)
{
weightLeft += rightBalance.weightLeft;
weightRight += rightBalance.weightRight;
}
}
}
class Program
{
static void Main(string[] args)
{
int N = Convert.ToInt32(Console.ReadLine());
Balance[] balance = new Balance[N];
for (int i = 0; i < N; i++)
{
balance[i] = new Balance();
}
for (int i = 0; i < N; i++)
{
string Line1 = Console.ReadLine();
string Line2 = Console.ReadLine();
string[] parts1 = Line1.Split(' ');
string[] parts2 = Line2.Split(' ');
balance[i].addWeightLeft(Convert.ToInt32(parts1[0]));
if (parts1.Length > 1)
{
for (int j = 1; j < parts1.Length; j++)
{
balance[i].addLeftBalance(balance[Convert.ToInt32(parts1[j])]);
}
}
balance[i].addWeightRight(Convert.ToInt32(parts2[0]));
if (parts2.Length > 1)
{
for (int j = 1; j < parts2.Length; j++)
{
balance[i].addRightBalance(balance[Convert.ToInt32(parts2[j])]);
}
}
}
for (int i = 0; i < N; i++)
{
balance[i].addLeftBalanceExtra();
balance[i].addRightBalanceExtra();
}
for (int i = 0; i < N; i++)
{
balance[i].addLeftBalanceExtra();
balance[i].addRightBalanceExtra();
}
for (int i = 0; i < N; i++)
{
if (balance[i].weightLeft < balance[i].weightRight)
{
Console.WriteLine(i + " : " + (balance[i].weightRight - balance[i].weightLeft) + " 0 ");
}
if (balance[i].weightLeft > balance[i].weightRight)
{
Console.WriteLine(i + " : 0 " + (balance[i].weightLeft - balance[i].weightRight));
}
if (balance[i].weightLeft == balance[i].weightRight)
{
Console.WriteLine(i + " : 0 0");
}
}
Console.Read();
}
}
I have passed this question in Facebook Programming Puzzle.
Code is attached below:
package PhoneInterview;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class Balance {
// property of the balance
public boolean balanced = false;// balance is balanced or not
public int nodeID;//balance id
public Balance[] leftChild = null;// array of balances in left side of this balance
public Balance[] rightChild = null;// array of balances in right side of this balance
public int balanceWeight = 10;// self weight
public int leftWeight = 0;// total weight of left side of this balance
public int rightWeight = 0;// total weight of right side of this balance
public int adding = 0;// how many additional weights should be added in order to balance this balance
// recursive balancing method
public static int balancing(Balance node) {
// check whether it has left children or right children
if (node.leftChild != null) {
for (int i = 0; i < node.leftChild.length; i++)
node.leftWeight += balancing(node.leftChild[i]);
}
if (node.rightChild != null) {
for (int i = 0; i < node.rightChild.length; i++) {
node.rightWeight += balancing(node.rightChild[i]);
}
}
// left children and right children is balanced, now balance itself
node.adding = Math.abs(node.leftWeight - node.rightWeight);
//mark balanced for this balance
node.balanced = true;
return node.balanceWeight + node.leftWeight + node.rightWeight
+ node.adding;
}
public static void main(String[] args) {
int N = 0;
Balance[] Balances;
BufferedReader br;
try {
// load file
br = new BufferedReader(new FileReader("input00.txt"));
// first line
String string = br.readLine();
N = Integer.parseInt(string);
// init balances array
Balances = new Balance[N];
int i = 0;
for (int k = 0; k < N; k++) {
Balances[k] = new Balance();
Balances[k].nodeID = k;
}
/*
* read data per line. Two lines is a loop
*/
while ((string = br.readLine()) != null) {
// init left side
String[] strs = string.split(" ");
Balances[i].leftWeight = Integer.parseInt(strs[0]);
/*
* if length > 1, it has balances in the left
*
*/
if (strs.length != 1)
Balances[i].leftChild = new Balance[strs.length - 1];
for (int j = 1; j < strs.length; j++) {
Balances[i].leftChild[j - 1] = Balances[Integer
.parseInt(strs[j])];
}
// init right side
string = br.readLine();
String[] strs1 = string.split(" ");
Balances[i].rightWeight = Integer.parseInt(strs1[0]);
// the same as left side
if (strs1.length != 1)
Balances[i].rightChild = new Balance[strs1.length - 1];
for (int j = 1; j < strs1.length; j++) {
Balances[i].rightChild[j - 1] = Balances[Integer
.parseInt(strs1[j])];
}
i++;
}
// start balancing
for (i = 0; i < Balances.length; i++) {
if (!Balances[i].balanced)
Balance.balancing(Balances[i]);
}
//output
for (int m = 0; m < Balances.length; m++) {
if (Balances[m].leftWeight < Balances[m].rightWeight)
System.out.println(m + ": " + Balances[m].adding + " 0");
else if (Balances[m].leftWeight >= Balances[m].rightWeight)
System.out.println(m + ": 0 " + Balances[m].adding);
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Here is my code !! I don't know but they say its not right !! :(
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/************************************************************************************************
* Author : Pkya
* Problem Statement -
Lalu owns a shop that sells weighing scales (see figure alongside) and weights. All the scales in his shop weigh the same – ten kilograms. They are of high quality and are well calibrated such that when equal weights are placed on both sides, they balance correctly. During his free time, Lalu imagines a grand tower made of many scales placed on one another as well as weights placed on some of them. He imagines the challenge it would pose to balance the entire tower! Your aim is to write a program to help Lalu balance any tower configuration by adding minimum weights on some scales. The balancing is always done by adding additional weights on lower scales and not by adding additional scales.
* Wed Jun 26 23:58:41 IST 2013
*************************************************************************************************/
struct Node /*Node As in Scale and Weight in every Pan*/
{
int left_pan_weight;
int right_pan_weight;
int added_left_pan;
int added_right_pan;
struct Node* left_scale;
struct Node* right_scale;
};
/*Global Declaration*/
static FILE *fr;
int no_of_scales;
char read_line[5];
char write_line[100];
struct Node *root = 0;
/*Function to balance each pan of scale and return total weight - recursive call*/
int balance_and_return_total_wt(struct Node* node)
{
if(node->left_scale != NULL)
node->left_pan_weight+=balance_and_return_total_wt(node->left_scale);
if(node->right_scale != NULL)
node->right_pan_weight+=balance_and_return_total_wt(node->right_scale);
if(node->left_pan_weight == node->right_pan_weight)
return(node->left_pan_weight+node->right_pan_weight+10);
else
{
if(node->left_pan_weight > node->right_pan_weight)
{
node->added_right_pan = node->left_pan_weight - node->right_pan_weight;
node->right_pan_weight += node->added_right_pan;
}
else
{
node->added_left_pan = node->right_pan_weight - node->left_pan_weight;
node->left_pan_weight += node->added_left_pan;
}
return(node->left_pan_weight+node->right_pan_weight+10);
}
}
/*Main Function*/
int main(int argc, char *argv[])
{
int c,i;
FILE *fw;
fr = fopen (argv[1], "r");
if (fr==NULL)
{
perror ("Error opening file");
return 1;
}
else
{
fw = fopen (argv[2],"w");
if (fw==NULL)
{
perror ("Error opening file");
return 1;
}
while(!feof(fr))
{
memset(read_line,'\0',sizeof read_line);
fgets(read_line,sizeof read_line,fr);
/*To handle E as End of Test Case*/
if(read_line[0]=='E')
{
memset(read_line,'\0',sizeof read_line);
fgets(read_line,sizeof read_line,fr);
}
no_of_scales=read_line[0] - '0';
struct Node* Array = (struct Node*) malloc(no_of_scales*sizeof(struct Node));
for(i=0;i<no_of_scales;i++)
{
memset(read_line,'\0',sizeof read_line);
fgets(read_line,sizeof read_line,fr);
Array[i].left_pan_weight = read_line[0] - '0';
Array[i].added_left_pan = 0;
if(read_line[2]!='\0')
{
Array[i].left_scale=&Array[read_line[2] - '0'];
}
else
{
Array[i].left_scale=NULL;
}
memset(read_line,'\0',sizeof read_line);
fgets(read_line,sizeof read_line,fr);
Array[i].right_pan_weight = read_line[0] - '0';
Array[i].added_right_pan = 0;
if(read_line[2]!='\0')
{
Array[i].right_scale=&Array[read_line[2] - '0'];
}
else
{
Array[i].right_scale=NULL;
}
}
root=&Array[0];
balance_and_return_total_wt(root);
for(i=0;i<no_of_scales;i++)
{
memset(write_line,'\0',sizeof write_line);
fprintf(fw,"%d %d %d\n",i,Array[i].added_left_pan,Array[i].added_right_pan);
}
/*Free Allocated Memory*/
free(Array);
}
}
/* close the files */
fclose(fr);
fclose(fw);
return 0;
}
The same question was posed as a problem in a coding competition organized at my workplace. Here is the working solution I submitted
#include<stdio.h>
#include<string.h>
#define LEFT 0
#define RIGHT 1
#define TOTAL 2
#define WEIGHT_OF_BALANCE 10
int tobeadded[50][2];
int actual_weights_kept[50][2];
int scales_dependency_left[50][50];
int scales_dependency_right[50][50];
int balance(int balance_number);
int countspaces(char *p)
{
int count=0, i;
int len=strlen(p);
for(i=0;i<len; i++)
{
if(p[i]==' ')
{
count++;
p[i]='\0';
}
}
return count;
}
void reset()
{
int i, j, k;
for(i=0; i<50;i++)
{
for(j=0;j<50; j++)
{
scales_dependency_left[i][j]=0;
scales_dependency_right[i][j]=0;
}
for(k=0;k<2;k++)
{
tobeadded[i][j]=0;
actual_weights_kept[i][j]=0;
}
}
}
int main(int argc, char *argv[])
{
char str[250];
int i, j, leftcount, rightcount, n;
int ns;
char *p;
FILE *fp=fopen(argv[1], "r");
FILE *of=fopen(argv[2], "w");
while(memcmp(fgets(str, 250, fp), "E", 1)!=0)
{
reset();
n=atoi(str);
for(i=0;i<2*n;i++)
{
fgets(str, 250, fp);
ns=countspaces(str);
if(i%2==0)
{
actual_weights_kept[i/2][LEFT]=atoi(str);
scales_dependency_left[i/2][0]=ns;
p=str + strlen(str)+1;
for(j=1; j<=ns; j++)
{
scales_dependency_left[i/2][j]=atoi(p);
p=p + strlen(p)+1;
}
}
else
{
actual_weights_kept[i/2][RIGHT]=atoi(str);
scales_dependency_right[i/2][0]=ns;
p=str+strlen(str)+1;
for(j=1;j<=ns; j++)
{
scales_dependency_right[i/2][j]=atoi(p);
p=p+strlen(p)+1;
}
}
}
for(i=0;i<n;i++)
balance(i);
for(i=0;i<n;i++)
fprintf(of, "%d: %d %d\n", i, tobeadded[i][0], tobeadded[i][1]);
}
fclose(fp);
fclose(of);
return 0;
}
int balance(int balance_number)
{
int i, j;
int lweight=actual_weights_kept[balance_number][LEFT], rweight=actual_weights_kept[balance_number][RIGHT];
for(i=1; i<=scales_dependency_left[balance_number][0]; i++)
{
lweight=lweight+balance(scales_dependency_left[balance_number][i]);
}
for(j=1; j<=scales_dependency_right[balance_number][0]; j++)
{
rweight=rweight+balance(scales_dependency_right[balance_number][j]);
}
if(lweight>rweight)
{
tobeadded[balance_number][LEFT]=0;
tobeadded[balance_number][RIGHT]=lweight-rweight;
rweight=lweight;
}
else
{
tobeadded[balance_number][LEFT]=rweight-lweight;
tobeadded[balance_number][RIGHT]=0;
lweight=rweight;
}
return lweight+rweight+WEIGHT_OF_BALANCE;
}
Input test case file name and output file name to be passed as command line arguments.
End of Input indicated by 'E' in the input file.
So the above input will look like
4
0 1
0 2
0
0 3
3
0
0
0
E
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include <sstream>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> II;
typedef vector<II> VII;
typedef vector<VII> VVII;
typedef vector<VI> VVI;
#define INF 2000000000
#define INFLL (1LL<<62)
#define FI first
#define SE second
#define PB push_back
#define SS ({int x;scanf("%d\n", &x);x;})
#define SSL ({LL x;scanf("%lld", &x);x;})
#define rep(i,n) for(i=0;i<(n);i++)
#define _mp make_pair
vector<int> l[1000] ,r[1000];
II w[1000];
int fun(int n){
int l1,r1,i;
l1=r1=0;
l1+=l[n][0];
r1+=r[n][0];
rep(i,(int)l[n].size()-1){
l1+=fun(l[n][i+1]);
}
rep(i,(int)r[n].size()-1){
r1+=fun(r[n][i+1]);
}
if(l1>r1){
w[n]=_mp(0,l1-r1);
}
else{
w[n]=_mp(r1-l1,0);
}
return 2*max(l1,r1)+10;
}
int main(){
int n=SS,a,b,i,j,k;
rep(i,n){
stringstream s;
string ss;
getline(cin,ss);
cout<<"left "<<ss<<endl;
s<<ss;
cout<<ss<<endl;
while(s>>a){
l[i].PB(a);
}
stringstream p;
getline(cin,ss);
p<<ss;
cout<<"rigft "<<ss<<endl;
while(p>>a){
r[i].PB(a);
}
}
fun(0);
rep(i,n){
cout<<w[i].FI<<" "<<w[i].SE<<endl;
}
return 0;
}
Here is implementation written using Objective-C:
@import Foundation;
@interface Balance : NSObject
- (instancetype)initWithIndex:(NSUInteger)index;
@property(nonatomic) NSUInteger index;
@property(nonatomic, strong) NSMutableArray* leftBalances;
@property(nonatomic, strong) NSMutableArray* rightBalances;
@property(nonatomic) NSUInteger leftWeight;
@property(nonatomic) NSUInteger rightWeight;
- (void)fillWithScanner:(NSScanner*)scanner balances:(NSArray*)balances;
@property(nonatomic) NSUInteger addedLeftWeight;
@property(nonatomic) NSUInteger addedRightWeight;
@end
@implementation Balance
- (instancetype)initWithIndex:(NSUInteger)index {
self = [super init];
if (self) {
_index = index;
_leftBalances = [NSMutableArray array];
_rightBalances = [NSMutableArray array];
}
return self;
}
- (void)fillWithScanner:(NSScanner*)scanner balances:(NSArray*)balances {
NSCharacterSet* newLineCharacterSet = [NSCharacterSet newlineCharacterSet];
NSString* leftPartString;
NSString* rightPartString;
if (NO == [scanner scanUpToCharactersFromSet:newLineCharacterSet
intoString:&leftPartString] ||
NO == [scanner scanUpToCharactersFromSet:newLineCharacterSet
intoString:&rightPartString]) {
return;
}
NSUInteger weight = 0;
[self fillSideBalances:self.leftBalances weight:&weight
fromString:leftPartString balances:balances];
self.leftWeight = weight;
weight = 0;
[self fillSideBalances:self.rightBalances weight:&weight
fromString:rightPartString balances:balances];
self.rightWeight = weight;
}
- (void)fillSideBalances:(NSMutableArray*)sideBalances
weight:(NSUInteger*)sideWeight
fromString:(NSString*)string
balances:(NSArray*)balances {
NSArray* components = [string componentsSeparatedByString:@" "];
*sideWeight = [[components firstObject] integerValue];
for (NSUInteger i = 1; i < [components count]; ++i) {
NSInteger index = [components[i] integerValue];
[sideBalances addObject:balances[index]];
}
}
- (NSUInteger)leftSideWeight {
return self.leftWeight + self.addedLeftWeight +
[[self.leftBalances valueForKeyPath:@"@sum.weight"] unsignedIntegerValue];
}
- (NSUInteger)rightSideWeight {
return self.rightWeight + self.addedRightWeight +
[[self.rightBalances valueForKeyPath:@"@sum.weight"] unsignedIntegerValue];
}
- (NSUInteger)weight {
return 10 + self.leftSideWeight + self.rightSideWeight;
}
@end
void balanceBalance(Balance* balance, NSArray* balances) {
for (Balance* leftBalance in balance.leftBalances) {
balanceBalance(leftBalance, balances);
}
for (Balance* rightBalance in balance.rightBalances) {
balanceBalance(rightBalance, balances);
}
NSUInteger leftSideWeight = balance.leftSideWeight;
NSUInteger rightSideWeight = balance.rightSideWeight;
if (leftSideWeight == rightSideWeight) {
return;
}
if (leftSideWeight > rightSideWeight) {
balance.addedRightWeight = leftSideWeight - rightSideWeight;
} else {
balance.addedLeftWeight = rightSideWeight - leftSideWeight;
}
}
int main() {
@autoreleasepool {
NSArray* arguments = [[NSProcessInfo processInfo] arguments];
NSString* inputPath = arguments[1];
NSString* outputPath = arguments[2];
NSError* error;
NSString* string = [NSString stringWithContentsOfFile:inputPath
encoding:NSASCIIStringEncoding
error:&error];
if (!string) {
NSLog(@"Error reading %@: %@",
inputPath, [error localizedFailureReason]);
return -1;
}
NSScanner* scanner = [NSScanner scannerWithString:string];
NSInteger numberOfBalances;
[scanner scanInteger:&numberOfBalances];
NSMutableArray* balances = [NSMutableArray
arrayWithCapacity:numberOfBalances];
for (NSUInteger index = 0; index < numberOfBalances; ++index) {
Balance* balance = [[Balance alloc] initWithIndex:index];
[balances addObject:balance];
}
for (Balance* balance in balances) {
[balance fillWithScanner:scanner balances:balances];
}
// Balance each item in the collection to make sure all balances,
// even unrelated ones, get balanced!
for (Balance* balance in balances) {
balanceBalance(balance, balances);
}
NSMutableString* resultString = [NSMutableString string];
for (Balance* balance in balances) {
[resultString appendFormat:@"%lu: %lu %lu\n",
(unsigned long)balance.index,
(unsigned long)balance.addedLeftWeight,
(unsigned long)balance.addedRightWeight];
}
if (![resultString writeToFile:outputPath
atomically:YES
encoding:NSASCIIStringEncoding
error:&error]) {
NSLog(@"Failed to save output to %@, error: %@",
outputPath, [error localizedFailureReason]);
return -1;
}
}
return 0;
}
recursively balance each node of the balance.
I may have made the wrong assumption that root is balances[0] , but I can always find the root of the tree and then send that node into the function.
Algo:
--Go to the root and start balancing its left and right nodes.
--Whenever you add a wt to balance a "particular balance" add that addition to the ans
--Keep balancing the left side and right side
-- compare the total weight after balancing them on the left and right
-- do the balancing at this level and add the "additional weight" to ans
-- Set the totalweight for the node
Since we are starting at root, it will recursively balance all the balances
import java.io.*;
import java.util.*;
class blnode{
public int Weight;
public ArrayList<balance> balances= new ArrayList<>();
public int totalWeight;
}
class balance{
public int index;
public static int Weight=10;
public blnode left;
public blnode right;
public int totalWt(){
if (left!=null && right!=null)
{return left.totalWeight +right.totalWeight +Weight;}
else if(left!=null && right==null){ return left.totalWeight+Weight;}
else if(left==null && right!=null){return right.totalWeight + Weight;}
else {return Weight;}
}
}
public class zzzBalances {
public static int [] ans;
public static void FindWeightAdded(balance bl, int N){
ans= new int[2*N];
FindWeight(bl.left);
FindWeight(bl.right);
BalanceThis(bl);
for (int i=0;i<ans.length; i=i+2){
System.out.println(i+": "+ans[i]+" "+ans[i+1]);
}
}
public static void main(String [] args)throws IOException{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
int i=0;
balance bl;
balance[] balances= new balance[N];
for(int j=0;j<N;j++){
balances[j]= new balance();
balances[j].index=j;
balances[j].left=new blnode();
balances[j].right= new blnode();
}
while(i!=N){
//read left balance node
bl=balances[i];
String line=br.readLine();
String [] temp=line.split(" ");
bl.left.Weight=Integer.parseInt(temp[0]);
if(temp.length >1){
for (int k=1;k<temp.length;k++){
bl.left.balances.add(balances[Integer.parseInt(temp[k])]);
}
}
line=br.readLine();
temp=line.split(" ");
bl.right.Weight=Integer.parseInt(temp[0]);
if(temp.length >1){
for (int k=1;k<temp.length;k++){
bl.right.balances.add(balances[Integer.parseInt(temp[k])]);
}
}
i++;
}
FindWeightAdded(balances[0],N);
}
public static void BalanceThis(balance bl){
if(bl.left.totalWeight > bl.right.totalWeight){
int diff=bl.left.totalWeight- bl.right.totalWeight;
ans[(2*bl.index) +1]=diff;
bl.right.totalWeight=bl.left.totalWeight;
}
else if(bl.left.totalWeight < bl.right.totalWeight){
int diff=bl.right.totalWeight -bl.left.totalWeight;
ans[2*bl.index]= diff;
bl.left.totalWeight=bl.right.totalWeight;
}
}
public static void FindWeight(blnode bn){
int totalweight=bn.Weight;
for(balance bl:bn.balances){
FindWeight(bl.left);
FindWeight(bl.right);
BalanceThis(bl);
totalweight+=bl.totalWt();
}
bn.totalWeight=totalweight;
}
}
binary tree, recurssion.
- Frank January 16, 2012In each recursive step, balance subnodes (sub balances) before balancing current node.
struct Node{
int leftWeight
int rightWeight
Node[] leftNodes;
Node[] rightNodes;
}