Possible Solution
FbUnfriend
1
2
3
4
5
6
7
8
9
10
11
12
13 | bool FbUnfriend(Fb fb, char *name1, char *name2) {
int id1 = nameToId(fb, name1);
int id2 = nameToId(fb, name2);
assert(id1 != id2);
if (fb->friends[id1][id2]) {
fb->friends[id1][id2] = false;
fb->friends[id2][id1] = false;
return true;
} else {
return false;
}
}
|
FbMutualFriends
1
2
3
4
5
6
7
8
9
10
11
12 | List FbMutualFriends(Fb fb, char *name1, char *name2) {
int id1 = nameToId(fb, name1);
int id2 = nameToId(fb, name2);
List l = ListNew();
for (int id = 0; id < fb->numPeople; id++) {
if (fb->friends[id1][id] && fb->friends[id2][id]) {
ListAppend(l, fb->names[id]);
}
}
return l;
}
|
FbFriendRecs1
Using a helper function that counts mutual friends
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | static int numMutualFriends(Fb fb, int id1, int id2);
void FbFriendRecs1(Fb fb, char *name) {
int myId = nameToId(fb, name);
// Collect mutual friend counts
int *counts = calloc(fb->numPeople, sizeof(int));
assert(counts != NULL);
for (int id = 0; id < fb->numPeople; id++) {
counts[id] = numMutualFriends(fb, myId, id);
}
counts[myId] = 0;
// Print friend recommendations
printf("%s's friend recommendations\n", name);
for (int i = fb->numPeople - 2; i > 0; i--) {
for (int id = 0; id < fb->numPeople; id++) {
if (counts[id] == i && !fb->friends[myId][id]) {
printf("\t%-20s%4d mutual friends\n",
fb->names[id], i);
}
}
}
free(counts);
}
static int numMutualFriends(Fb fb, int id1, int id2) {
int count = 0;
for (int id = 0; id < fb->numPeople; id++) {
if (fb->friends[id1][id] && fb->friends[id2][id]) {
count++;
}
}
return count;
}
|
Using a more direct method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | void FbFriendRecs1(Fb fb, char *name) {
int id1 = nameToId(fb, name);
// Collect mutual friend counts
int *counts = calloc(fb->numPeople, sizeof(int));
assert(counts != NULL); // lazy error checking
for (int id2 = 0; id2 < fb->numPeople; id2++) {
if (fb->friends[id1][id2]) {
for (int id3 = 0; id3 < fb->numPeople; id3++) {
if (fb->friends[id2][id3] && !fb->friends[id1][id3] && id1 != id3) {
counts[id3]++;
}
}
}
}
// Print friend recommendations
printf("%s's friend recommendations\n", name);
for (int i = fb->numPeople - 2; i > 0; i--) {
for (int id = 0; id < fb->numPeople; id++) {
if (counts[id] == i) {
printf("\t%-20s%4d mutual friends\n",
fb->names[id], i);
}
}
}
free(counts);
}
|
Complexity Analysis
Note: The correct answer will differ depending on the implementation. These answers are for the above implementations.
===============
FbUnfriend
===============
- Worst case time complexity: O(log n)
===============
FbMutualFriends
===============
- Worst case time complexity: O(n)
===============
FbFriendRecs1
===============
- Worst case time complexity: O(n^2)