-
-
Save Jauny/2781340 to your computer and use it in GitHub Desktop.
Facebook interview solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 4 | |
| 0 1 | |
| 0 2 | |
| 0 | |
| 0 3 | |
| 3 | |
| 0 | |
| 0 | |
| 0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment