Kotlin Coding Test Course, Understanding Friend Relationships

Problem Description

There are N students who are friends with each other. The friendships are given in pairs,
and if student A is friends with student B, then A is a friend of B and B is a friend of A.
Now, you need to implement a function to identify all friends of friends for a specific student and
return the count of those friends.

For example, if the friendships are given as follows:

(1, 2)
(1, 3)
(2, 4)
(3, 5)

Student 1’s friends are 2 and 3, and their friends are 4 and 5.
Therefore, the total number of friends of friends for student 1 is 4.

Input Format

friends: List>, target: Int

– friends: A list of tuples representing friendships,
– target: The student whose friends of friends you want to find

Output Format

– An integer representing the number of friends of friends

Problem Solving Process

To understand friendships, we can apply graph theory.
Each student becomes a node, and friendships are represented as edges.
This allows us to explore the given student and their friends’ friends.

1. Constructing the Graph

First, we need to convert the friendships into a graph format.
Let’s create a map with each student as keys and their friends as values.


fun buildGraph(friends: List>): Map> {
    val graph = mutableMapOf>()
    for ((a, b) in friends) {
        graph.computeIfAbsent(a) { mutableListOf() }.add(b)
        graph.computeIfAbsent(b) { mutableListOf() }.add(a)
    }
    return graph
}

2. Finding Friends of Friends

Once the graph is constructed, we need to find the friends of a specific student and
obtain the list of their friends’ friends.
Care must be taken to ensure that the friends list does not contain duplicates.


fun findFriendsOfFriends(friends: List>, target: Int): Int {
    val graph = buildGraph(friends)
    val directFriends = graph[target] ?: return 0
    val friendsOfFriends = mutableSetOf()
    
    for (friend in directFriends) {
        val friendsOfCurrentFriend = graph[friend]
        if (friendsOfCurrentFriend != null) {
            for (fof in friendsOfCurrentFriend) {
                if (fof != target && !directFriends.contains(fof)) {
                    friendsOfFriends.add(fof)
                }
            }
        }
    }
    return friendsOfFriends.size
}

3. Complete Code

Now, let’s organize the complete code.


fun main() {
    val friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5))
    val targetStudent = 1
    val result = findFriendsOfFriends(friendsList, targetStudent)
    println("Number of friends of friends for student $targetStudent: $result")
}

Complexity Analysis

The time complexity of this algorithm is O(N + M).
Here, N is the number of students, and M is the number of friendships.
The space complexity is also O(N + M).
This is because each student and friendship is stored in graph form.

Example and Test Cases

Let’s verify that the function works correctly with various examples.

Example 1:

Input:


                    friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5))
                    targetStudent = 1

Output: “Number of friends of friends for student 1: 2”

Example 2:

Input:


                    friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 3))
                    targetStudent = 1

Output: “Number of friends of friends for student 1: 0”

Example 3:

Input:


                    friendsList = listOf(Pair(1, 2), Pair(3, 4), Pair(4, 5))
                    targetStudent = 1