未分類

Design Twitter

Design, Go, HashTable, Heap, LeetCode

Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

  1. postTweet(userId, tweetId): Compose a new tweet.
  2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
  3. follow(followerId, followeeId): Follower follows a followee.
  4. unfollow(followerId, followeeId): Follower unfollows a followee.

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Twitter twitter = new Twitter();
// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);
// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);
// User 1 follows user 2.
twitter.follow(1, 2);
// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);
// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);
// User 1 unfollows user 2.
twitter.unfollow(1, 2);
// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);
提示 解題應用
HashTable HashMap

Default:

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
38
39
40
41
42
43
type Twitter struct {
    
}
/** Initialize your data structure here. */
func Constructor() Twitter {
    
}
/** Compose a new tweet. */
func (this *Twitter) PostTweet(userId int, tweetId int)  {
    
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
func (this *Twitter) GetNewsFeed(userId int) []int {
    
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Follow(followerId int, followeeId int)  {
    
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Unfollow(followerId int, followeeId int)  {
    
}
/**
 * Your Twitter object will be instantiated and called as such:
 * obj := Constructor();
 * obj.PostTweet(userId,tweetId);
 * param_2 := obj.GetNewsFeed(userId);
 * obj.Follow(followerId,followeeId);
 * obj.Unfollow(followerId,followeeId);
 */

解答思路:

因為曾經在產品開發上實作過類似的東西，所以很快就有了想法，總而言之就是利用兩個hashmap來分別儲存各自的文章與追隨的對象，並記得文章在發送出去之前要包含時間戳記(這邊以發文編號替代)，當需要取出個人的動態時報時，就從所有追隨的對象(包含自己)取出文章在依時間戳記做排序，最後只要取出最新的前十篇文章做回傳即可。

程式碼解說:

因為最後要在個人的動態時顯示最新的前十篇文章(包含有追隨對象的文章)，因此需要將每則tweet依時間戳記(這邊以發文編號替代)做排序，這邊就自行定義了tweet的結構陣列所要排序的規則

1
2
3
4
5
6
7
8
type Tweet struct {
	TweetId int
	Num     int
}
type TweetList []Tweet
func (t TweetList) Len() int           { return len(t) }
func (t TweetList) Less(i, j int) bool { return t[i].Num < t[j].Num }
func (t TweetList) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }

接著Twitter的結構則是要包含兩個hashmap來分別儲存各自的文章與追隨的對象，與一個計數器以作為每篇文章發表的時間戳記，並在建構函數上初始化分配這三個變數的儲存空間

1
2
3
4
5
6
7
8
type Twitter struct {
	Count      int
	NewsFeed   map[int][]Tweet
	FollowList map[int][]int
}
func Constructor() Twitter {
	return Twitter{0, make(map[int][]Tweet), make(map[int][]int)}
}

當需要發表文章的時候記得先將Twitter物件的計數器+1，並將記數器的值連同tweetId作為tweet一起儲存到自己id在hashmap所對應到的陣列之中

1
2
3
4
5
func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.Count++
	count := this.Count
	this.NewsFeed[userId] = append(this.NewsFeed[userId], Tweet{tweetId, count})
}

如思路所述當需要取出個人的動態時報時，就先從所有追隨的對象(包含自己)取出文章，這邊是先取出自己的文章，才將追隨對象的文章放在後頭再依時間戳記做排序，最後只要取出最新的前十篇文章的的TweetId放到結果陣列做回傳即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (this *Twitter) GetNewsFeed(userId int) []int {
	var list []Tweet
	var result []int
	list = append(list, this.NewsFeed[userId]...)
	for _, followee := range this.FollowList[userId] {
		for _, tweet := range this.NewsFeed[followee] {
			list = append(list, tweet)
		}
	}
	sort.Sort(sort.Reverse(TweetList(list)))
	for _, tweet := range list {
		result = append(result, tweet.TweetId)
	}
	if len(result) > 10 {
		return result[:10]
	}
	return result
}

如果想要追隨特定的對象，要先過濾掉自己追隨自己的情況，接著檢查自己已追隨的名單，確定此人是否已經有追隨，如果沒有追隨才將其加入自己的追隨清單之中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (this *Twitter) Follow(followerId int, followeeId int) {
	var exist bool
	if followerId != followeeId {
		for _, followee := range this.FollowList[followerId] {
			if followee == followeeId {
				exist = true
				break
			}
		}
		if !exist {
			this.FollowList[followerId] = append(this.FollowList[followerId], followeeId)
		}
	}
}

而如果不想要再追隨特定的對象，就從自己已追隨名單中找出對象的index位置，接著在重新組合追隨清單的陣列即可(跳過該元素)

1
2
3
4
5
6
7
func (this *Twitter) Unfollow(followerId int, followeeId int) {
	for index, followee := range this.FollowList[followerId] {
		if followee == followeeId {
			this.FollowList[followerId] = append(this.FollowList[followerId][:index], this.FollowList[followerId][index+1:]...)
		}
	}
}

完整程式碼:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
type Tweet struct {
	TweetId int
	Num     int
}
type TweetList []Tweet
func (t TweetList) Len() int           { return len(t) }
func (t TweetList) Less(i, j int) bool { return t[i].Num < t[j].Num }
func (t TweetList) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }
type Twitter struct {
	Count      int
	NewsFeed   map[int][]Tweet
	FollowList map[int][]int
}
func Constructor() Twitter {
	return Twitter{0, make(map[int][]Tweet), make(map[int][]int)}
}
func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.Count++
	count := this.Count
	this.NewsFeed[userId] = append(this.NewsFeed[userId], Tweet{tweetId, count})
}
func (this *Twitter) GetNewsFeed(userId int) []int {
	var list []Tweet
	var result []int
	list = append(list, this.NewsFeed[userId]...)
	for _, followee := range this.FollowList[userId] {
		for _, tweet := range this.NewsFeed[followee] {
			list = append(list, tweet)
		}
	}
	sort.Sort(sort.Reverse(TweetList(list)))
	for _, tweet := range list {
		result = append(result, tweet.TweetId)
	}
	if len(result) > 10 {
		return result[:10]
	}
	return result
}
func (this *Twitter) Follow(followerId int, followeeId int) {
	var exist bool
	if followerId != followeeId {
		for _, followee := range this.FollowList[followerId] {
			if followee == followeeId {
				exist = true
				break
			}
		}
		if !exist {
			this.FollowList[followerId] = append(this.FollowList[followerId], followeeId)
		}
	}
}
func (this *Twitter) Unfollow(followerId int, followeeId int) {
	for index, followee := range this.FollowList[followerId] {
		if followee == followeeId {
			this.FollowList[followerId] = append(this.FollowList[followerId][:index], this.FollowList[followerId][index+1:]...)
		}
	}
}

總結:

要簡單實作twitter所包含的功能(發表文章、追隨陌生人並使其文章出現在自己的動態時報上)，做法就是利用兩個hashmap來分別儲存各自的文章與追隨的對象，並記得文章在發送出去之前要包含時間戳記(這邊以發文編號替代)，當需要取出個人的動態時報時，就從所有追隨的對象(包含自己)取出文章在依時間戳記做排序，最後只要取出最新的前十篇文章做回傳即可。

分享到