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:
- postTweet(userId, tweetId): Compose a new tweet.
- 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.
- follow(followerId, followeeId): Follower follows a followee.
- unfollow(followerId, followeeId): Follower unfollows a followee.
123456789101112131415161718192021222324 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 -> .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 -> ,// since user 1 is no longer following user 2.twitter.getNewsFeed(1);
leetcode Count of Range Sum
Given an integer array
nums, return the number of range sums that lie in
S(i, j)is defined as the sum of the elements in
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Given nums =
[-2, 5, -1], lower =
-2, upper =
The three ranges are :
[0, 2]and their respective sums are:
-2, -1, 2.
Given an Iterator class interface with methods:
hasNext(), design and implement a PeekingIterator that support the
peek()operation — it essentially peek() at the element that will be returned by the next call to next()
Here is an example. Assume that the iterator is initialized to the beginning of the list:
[1, 2, 3].
next()gets you 1, the first element in the list.
Now you call
peek()and it returns 2, the next element. Calling
next()after that still return 2.
next()the final time and it returns 3, the last element. Calling
hasNext()after that should return false.
- Think of “looking ahead”. You want to cache the next element.
- Is one variable sufficient? Why or why not?
- Test your design with call order of
- For a clean implementation, check out Google’s guava library source code.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
本文简单介绍Binary indexed tree (Fenwick tree)
leetcode Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
The graph contains
nnodes which are labeled from
n - 1. You will be given the number
nand a list of undirected
edges(each edge is a pair of labels).
You can assume that no duplicate edges will appear in
edges. Since all edges are undirected,
[0, 1]is the same as
[1, 0]and thus will not appear together in
n = 4,
edges = [[1, 0], [1, 2], [1, 3]]Python
12345 0|1/ \2 3
leetcode Range Sum Query – Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
sumRange(0, 2) -> 8
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
- 146 LRU Cache
- 150 Evaluate Reverse Polish Notation
- 155 Min Stack
- 187 Repeated DNA Sequences
- 208 Implement Trie (Prefix Tree)
- 211 Add and Search Word – Data structure design
- 218 The Skyline Problem
- 232 Implement Queue using Stacks
- 239 Sliding Window Maximum
- 341 Flatten Nested List Iterator
- 352 Data Stream as Disjoint Intervals
- 432 All O’one Data Structure