C’est quoi le CodinGame?

Bonjour les développeurs,

Durant le processus de recrutement, plusieurs entreprises d’IT (généralement des ESN, grandes entreprises de développement) vous envoient comme première étape du processus de recrutement le CodinGame. Si vous êtes familiarisé avec des sites de genre HackerRank, LeetCode, Codeforces…, le test CodinGame ne sera pas difficile normalement pour vous :).

Nous ne sommes pas ici pour juger le test en matière de questions posées. L’idée consiste à faire connaître ce test aux développeurs qui ne le connaissent pas et d’essayer par la suite de simplifier la compréhension des exercices de type « problème algorithmique » qui ont un poids énorme au niveau de l’évaluation finale attribuée.

Dans cet article, nous allons essayer de résoudre en Swift, deux problèmes de ce test en suivant l’approche TDD.

Problème: Trouver le noeud terminal

L’objectif de ce problème est de trouver le noeud terminal d’un réseau simple.

Dans ce réseau:

• Chaque nœud a seulement un successeur.
• Le dernier nœud ne possède aucun successeur.
• Le réseau est unidirectionnel.

Dans l’exemple c-dessus, le noeud terminal en partant par exemple du noeud 8 est le 7.

Dans l’exercice, on nous demande d’implémenter une méthode qui renvoie le dernier nœud de ce réseau à partir d’un nœud initial startNodeId en suivant les liens unidirectionnels du réseau.

findNetworkEndPoint(startNodeId, fromIds, toIds) -> Int

Notre réseau est unidirectionnel, chaque élément du tableau formIds doit avoir un successeur dans le tableau toIds, cela se traduit par la relation fromIds[i] → toIds[i]. De ce fait, ces deux tableaux doivent avoir la même longueur.

Selon le schéma ci-dessus le contenu des deux tableaux est le suivant:

let fromIds = [2,5,3,8,14,10]
let toIds = [3,3,14,10,7,7]

En suivant l’approche TDD (Test-driven development), nous commençons par écrire nos tests puis nous développons notre algorithme avec un minimum de codes pour réussir nos tests.

Côté CodinGame, on suppose que la saisie est correcte. Alors, nous ne pouvons pas tomber sur un cas où nous cherchons un élément qui n’existe pas dans le tableau fromIds.

Tout d’abord, nous voulons commencer par tester ces deux cas,

• Les deux tableaux fromIds et toIds sont vides.
• Le tableau fromIds contient un seul élément et le tableau toIds est vide.

Voici à quoi resemble notre playground dans un premier lieu :

import UIKit
import XCTest

final class SimpleNetworkTests: XCTestCase {
    override func setUp() {
        super.setUp()
    }
    
    override func tearDown() {
        super.tearDown()
    }
    
    func testEmptyToIdsArrayShouldReturnStartNode() {
        // Given
        let fromIds = [2]
        let toIds = [Int]()
        let sut = SimpleNetwork()

        // THEN
        XCTAssertEqual(
            sut.findNetworkEndPoint(
                2,
                fromIds,
                toIds
            ),
            2
        )
        
    }
    
    func testEmptyFromIdsAndToIdsArraysShouldReturnStartNode() {
        // Given
        let fromIds = [Int]()
        let toIds = [Int]()
        let sut = SimpleNetwork()

        // THEN
        XCTAssertEqual(
            sut.findNetworkEndPoint(
                2,
                fromIds,
                toIds
            ),
            2
        )
        
    }
    
}

final class SimpleNetwork {
    
    init() {}
    
    func findNetworkEndPoint(
        _ startNodeId: Int,
        _ fromIds: [Int],
        _ toIds: [Int]
    ) -> Int {
        return startNodeId
    }
}

SimpleNetworkTests.defaultTestSuite.run()

Si nous réalisons les deux tests, les tests passeront, étant donné que notre algorithme renvoie toujours startNodeId.

Examinons maintenant le cas où nous avons deux tableaux fromIds et toIds qui ne sont pas vides, écrivons notre test.

func testNoEmptyFromIdsAndToIdsArraysShouldReturnStartNode() {
        // Given
        let fromIds = [2,5,3,8,14,10]
        let toIds = [3,3,14,10,7,7]
        let sut = SimpleNetwork()

        // THEN
        XCTAssertEqual(
            sut.findNetworkEndPoint(
                2,
                fromIds,
                toIds
            ),
            7
        )
        
    }

En partant du noeud 2, on arrivera au noeud 7. Ce test ne passera pas vu que notre code de production ne gère pas encore ce cas.

Sur Playground, vous aurez sur votre console cet affichage.

Ajoutons le stricte minimum du code pour passer ce test.

func findNetworkEndPoint(
        _ startNodeId: Int,
        _ fromIds: [Int],
        _ toIds: [Int]
    ) -> Int {
        var copyStartNodeId = startNodeId
        while(fromIds.contains(copyStartNodeId)) {
            let startIdToIdIndex = fromIds.firstIndex(of: copyStartNodeId) ?? 0
            copyStartNodeId = toIds[startIdToIdIndex]
        }
        return copyStartNodeId
    }

L’idée est de déterminer ou se trouve le startNodeId dans le tableau fromIds, ensuite d’écraser le startNodeId par son successeur au niveau du tableau toIds.

Lançons les test maintenant 🙂 , on remarque que notre premier test est impacté pour ce nouveau code

Rappelons que dans notre premier test, on a le tableau fromIds qui contient seulement 2 et que le tableau toIds est vide. Vu que la première instruction dans notre code est fromIds.contains(copyStartNodeId), on entrera dans l’itération sauf que l’erreur provient de cette instruction copyStartNodeId = toIds[startIdToIdIndex] ou on cherche le successeur de 2 dans le tableau toIds déjà vide.

La solution simple pour s’assurer, est de vérifier que le tableau toIds n’est pas vide avant de remplacer le copyStartNodeId.

func findNetworkEndPoint(
        _ startNodeId: Int,
        _ fromIds: [Int],
        _ toIds: [Int]
    ) -> Int {
        var copyStartNodeId = startNodeId
        while(fromIds.contains(copyStartNodeId)) {
            if let startIdToIdIndex = fromIds.firstIndex(of: copyStartNodeId),
               toIds.contains(startIdToIdIndex) {
                copyStartNodeId = toIds[startIdToIdIndex]
            }
        }
        return copyStartNodeId
  }

Tout nos tests passent maintenant.

Passons maintenant au deuxième problème que nous avons choisi de te montrer, c’est la recherche d’un élément dans une arbre binaire ordonné ABR.

Problème: Trouver un élément dans une arbre binaire de recherche(ABR)

Un arbre binaire de recherche est composé de noeuds qui respectent les règles suivantes:

• Un noeud a une valeur de type entier.
• Un noeud n’a pas plus de deux enfants, appelés noeud droite et noeud gauche.
• La valeur de tout enfant du sous arbre gauche est inférieur à la valeur de son parent.
• La valeur de tout enfant du sous arbre droite est supérieur à la valeur de son parent.

La hauteur de l’arbre (la distance entre le noeud le plus éloigné et la racine) est comprise entre 0 et 100000 noeuds.

Le candidat doit développer une méthode find(_ v: Int) qui retourne le noeud tenant la valeur v s’il existe.

On nous propose une classe Node qui contient trois attributs.

class Node {
    var value: Int
    var left: Node?
    var right: Node?
    
    init(_ value: Int) {
        self.value = value
    }
    
    func find(_ v: Int) -> Node? {
        return nil
    }
}

Pareil au problème précédent, on commencera par écrire une classe de test qu’on l’appelle NodeTests

class NodeTests: XCTestCase {
    override func setUp() {
        super.setUp()
    }
    
    override func tearDown() {
        super.tearDown()
    }
}
// Lancement des tests
NodeTests.defaultTestSuite.run()

On commencera par un simple test qui permet de vérifier si la recherche d’un élément non existant dans notre arbre avec un seul élément retournera nil.

func test_Search_No_Existing_Value_ON_MonoTree_Elements_ShouldReturnNil() {
     // GIVEN
     let root = Node(10)
        
     // THEN
     XCTAssertNil(root.find(3))
}

Ce test passera systématiquement vu que notre code de production retournera maintenant nil dans tout les cas 🙂 .

Passons à un deuxième TU.

func test_Search_Existing_Value_ON_MonoTree_Elements_ShouldNotReturnNil() {
    // GIVEN
    let root = Node(10)
        
    // THEN
    XCTAssertNotNil(root.find(10))
}

Ce test ne passera pas (phase rouge du TDD 🧪), essayons de passer ce test avec le minimum du code possible.

func find(_ v: Int) -> Node? {
     if value == v {
        return self
     }
     return nil
 }

Voila nos tests passent ✅

Passant ensuite au cas où notre arbre a un seul enfant droit (Une seule génération)

func test_Search_Existing_Value_ON_Tree_With_One_Right_Child_ShouldNotReturnNil() {
        // GIVEN
        let root = Node(10)

        let rightElementRoot = Node(14)

        root.right = rightElementRoot

        // THEN
        XCTAssertNotNil(root.find(14))
 }

Ce test ne passera pas aussi! vu que le noeud 14 existe et l’algorithme retourne nil

Ici la solution est simple, nous devons revenir a la condition:

💡 La valeur de tout enfant du sous-arbre droite est supérieure à la valeur de son parent.

Ce qui se traduit en code:

func find(_ v: Int) -> Node? {
        
     if value == v {
            return self
     }
        
     if v > value, let rightNode = right {
            return rightNode
     }
}

Nous faisons la même chose avec le côté gauche.

func test_Search_Existing_Value_ON_Tree_With_One_Left_Child_ShouldNotReturnNil() {
     // GIVEN
     let root = Node(10)

     let leftElementRoot = Node(7)

     root.left = leftElementRoot

     // THEN
     XCTAssertNotNil(root.find(7))
 }

💡La valeur de tout enfant du sous-arbre gauche est inférieure à la valeur de son parent.

func find(_ v: Int) -> Node? {
        
    if value == v {
            return self
     }
        
    if v > value, let rightNode = right {
            return rightNode
    }

    if v < value, let leftNode = left {
            return leftNode
    }
        
     return nil
}

Passons à la recherche dans une arbre à plusieurs générations ou niveaux.

func test_Search_Existing_Value_ON_Multi_levels_Tree_ShouldNotReturnNil() {
        // GIVEN
        let root = Node(10)

        let node7 = Node(7)
        let node14 = Node(14)

        root.left = node7
        root.right = node14

        let node4 = Node(4)
        let node9 = Node(9)

        node7.left = node4
        node7.right = node9

        let node1 = Node(1)
        let node5 = Node(5)

        node4.left = node1
        node4.right = node5

        // THEN
	let node = root.find(1)
        XCTAssertNotNil(root.find(1))
	XCTAssertEqual(node?.value, 1)
  }

Pour ce cas, nous allons utiliser la récursivité. On remarque bien que dans la recherche d’un nœud dans tout l’arbre, l’idée consiste à faire la recherche soit dans la génération gauche si la valeur est inférieure au nœud parent, ou la génération droite, si la valeur est supérieure au nœud parent et ainsi de suite jusqu’à nous tombons sur le critère d’arrêt if value == v { return self} ou bien return nil si le noeud n’existe pas.

Cherchant le noeud avec la valeur 1 par exemple:

func find(_ v: Int) -> Node? {
    if value == v {
            return self
    }
        
    if v > value,
       let rightNode = right {
            return rightNode.find(v)
    }

    if v < value,
       let leftNode = left {
            return leftNode.find(v)
    }
        
    return nil
  }