亞馬遜今年 Amazon China Code Challenge 的題目之一
藉由社交網路產生推薦課程清單
題目要求
推薦的課程要是 user 沒上過 的
社交網路朋友共同 上過愈多次的要排在愈前面
社交網路的定義是 三層以內 的直接朋友

Network.png

Suppose you are an engineer on the Amazon Student team.
Your team wants to launch a new feature called “Courses Your Social Network have Attended,”
that lists all courses that your social network are taking, sorted by popularity.

A social network is defined as all direct friends and all direct friends of direct friends.
People three levels deep are not part of the social circle, as illustrated below.

The recommendation logic is based on the following rules:

  • A user should only be recommended
    a course that their social network have attended
    but they have not attended
  • The recommendations priority is driven by
    how many people have attended the same course –
    if multiple people attended the same course,
    it should be higher in the recommendations than
    a course that only one person attended.

You are provided two library functions to help you

  • getDirectFriendsForUser
    – returns a list of customer IDs (strings that uniquely identify an Amazon user)
    representing the direct friends of an Amazon user
  • getAttendedCoursesForUser
    – returns a list of course IDs (strings that uniquely identify a course)
    for an Amazon user ordered by attendance time
    with newest course first in list
    and oldest course last in list

For this evaluation,
please write a function that provides a ranked (high to low)
list of courses (course IDs) for a provided user.

1
2
3
4
5
6
7
def getDirectFriendsForUser(user):
#  returns an array
#  e.g. ['friend1', 'friend2']
#
def getAttendedCoursesForUser(user):
#  returns an array
#  e.g. ['course1', 'course2']

我的解法
給大家參考

my solution here, FYI.:

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
# Complete the function below.
def getRankedCourses(user):
    friendsList = getFriends(user)
    coursesList = getRecommendedCoursesList(user, friendsList)
    scoreDict = getCoursesScoreDict(coursesList, friendsList)
    # 回傳前用 value 反向排序
    return sorted(scoreDict, key=scoreDict.get, reverse=True)
#
def getFriends(user):
    friends = getDirectFriendsForUser(user)
    for u in list(friends): # 這裡故意產生新的 list, 達到限制社交階層數
        friends += getDirectFriendsForUser(u)
    return friends
#
def getRecommendedCoursesList(user, friends):
    myAttendedcourses, othersAttendedCourses = set(), set()
    pullAttendedCoursesSet([user], myAttendedcourses)
    pullAttendedCoursesSet(getFriends(user), othersAttendedCourses)
    return list(othersAttendedCourses - myAttendedcourses)
    # 取回 課程 的集合, 並利用集合可以直接做減去, 把自己已經修過的去除
#
# 用 dictionary(a.k.a hash) 的特性做跑分
def getCoursesScoreDict(courses, friends):
    cs = {} # 好習慣帶你上天堂
    for u in friends:
        for c in getAttendedCoursesForUser(u):
            cs[c] = cs.get(c, 0) + 1
    return { c: cs[c] for c in courses }
# 回傳前特意利用 dictionary comprehension
# 用傳入課程清單的 key 值, 產生最後的推薦課程評分後的 dictionary
#
# 這裡用 python 函數會自動判斷而 pass by reference 的特性
def pullAttendedCoursesSet(friends, courses):
    for u in friends:
        for c in getAttendedCoursesForUser(u):
            courses.add(c)
#