Facebook interview solution

facebook.cpp

//Solution à l'interview de Facebook
//Edmond La Chance UQAC 2012
//02:10 2012-05-24
//Énoncé : http://pastebin.com/4FNndtNV


#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

struct balance
{
	int leftSide;
	int rightSide;

	int leftBalancePtr;
	int rightBalancePtr;

	bool balanced;

	int weightAddedLeft;
	int weightAddedRight;

	int poidsBalanceGauche;
	int poidsBalanceDroite;
};

balance lesBalances[100];

//Fonction récursive qui va explorer l'arbre des balances et trouver les réponses
int weight(int noBalance)
{

	balance * courante = &lesBalances[noBalance];
	int finalWeight = 0;

	//Cas 0 (pour la récursivité : c'est balancé)
	if (courante->balanced)
		return 10 + courante->rightSide + courante->leftSide + courante->poidsBalanceGauche + courante->poidsBalanceDroite;

	//Cas 1 : Il y a 1 poids a gauche seulement
	if (courante->leftSide != 0 && courante->rightSide == 0) {
		courante->rightSide = courante->leftSide;
		courante->weightAddedRight = courante->leftSide;
		courante->balanced = true;
		return 10 + courante->rightSide + courante->leftSide + courante->poidsBalanceGauche + courante->poidsBalanceDroite;

	}
	//Cas 2 : Il y a un poids à droite seulement
	else if (courante->leftSide == 0 && courante->rightSide != 0) {
		courante->leftSide = courante->rightSide;
		courante->weightAddedLeft = courante->leftSide;
		courante->balanced = true;
		return 10 + courante->rightSide + courante->leftSide + courante->poidsBalanceGauche + courante->poidsBalanceDroite;
	}

	//Autre cas : Il n'y a pas de poids ni de balance
	else if (courante->leftSide == 0 && courante->rightSide == 0 && courante->leftBalancePtr == -1 && courante->rightBalancePtr == -1)
	{
		courante->balanced = true;
		return 10;
	}

	//Les balances

	//Aller chercher le poids de la balance gauche
	if (courante->leftBalancePtr == -1)
		courante->poidsBalanceGauche = 0;
	else courante->poidsBalanceGauche = weight( courante->leftBalancePtr);

	//Poids de la balance à droite
	if (courante->rightBalancePtr == -1)
		courante->poidsBalanceDroite = 0;
	else courante->poidsBalanceDroite = weight( courante->rightBalancePtr );


	//Il faut ajouter combien ?

	//Droit plus grand
	if (courante->poidsBalanceDroite + courante->rightSide > courante->poidsBalanceGauche + courante->leftSide)
	{
		courante->weightAddedLeft = courante->poidsBalanceDroite + courante->rightSide 
			- 
		courante->poidsBalanceGauche + courante->leftSide;

		courante->leftSide += courante->weightAddedLeft;

		courante->balanced = true;

		return 10 + courante->rightSide + courante->leftSide + courante->poidsBalanceGauche + courante->poidsBalanceDroite;
	}

	//Gauche plus grand
	else if (courante->poidsBalanceDroite + courante->rightSide < courante->poidsBalanceGauche + courante->leftSide)
	{
		courante->weightAddedRight = courante->poidsBalanceGauche + courante->leftSide
										- 
									 courante->poidsBalanceDroite + courante->rightSide;


		courante->rightSide += courante->weightAddedRight;

		courante->balanced = true;

		return 10 + courante->rightSide + courante->leftSide + courante->poidsBalanceGauche + courante->poidsBalanceDroite;
	}

	return -5;
}

int main(void)
{
	ifstream fichier;
	fichier.open("fichier.txt");

	int n;
	fichier >> n;

	char line[200];
	fichier.getline(line, 200);
	int b;
	char * ptr;

	for (int i =0; i < n ; i++)
	{
		balance * courante = &lesBalances[i];
		
		//Aucune balance au départ
		courante->leftBalancePtr = -1;
		courante->rightBalancePtr = -1;
	
		
		//Côté gauche
		fichier.getline(line, 200);

		//Si c'est une balance
		if ( strlen(line) > 1)
		{
			
			ptr = strtok(line, " ");
			ptr = strtok(NULL, " ");
			b = atoi(ptr);
			courante->leftBalancePtr = b;
		}

		//Sinon c'est un poids
		else courante->leftSide = atoi(line);

		//Côté droit
		fichier.getline(line, 200);

		//Si c'est une balance
		if ( strlen(line) > 1)
		{
			
			ptr = strtok(line, " ");
			ptr = strtok(NULL, " ");
			b = atoi(ptr);
			courante->rightBalancePtr = b;
		}

		//Sinon c'est un poids
		else courante->rightSide = atoi(line);

	}


	//Une fois que la structure de données est remplie, on s'occupe de remplir le tableau pour balancer les balances
	for (int i = 0; i < n ; i++)
	{
		weight(i);
	}

	//Imprimer les résultats

	for (int i = 0; i < n ; i++)
	{
		balance * courante = &lesBalances[i];
		printf("%d: %d %d\n", i, courante->weightAddedLeft, courante->weightAddedRight);
	}


	return 0;


}

fichier.txt

4
0 1
0 2
0
0 3
3
0
0
0