- A: the distance from the beginning to the start of the cycle
- B: the distance slow pointer moved the start of the cycle
- L: the length of the cycle
So the slow pointer has moved A+B, therefore the fast pointer 2A+2B. Since the fast pointer have moved L more steps, we have A+B+L=2A+2B –> L=A+B. Since L=A+B, the slow pointer has moved B, the rest of the cycle(back to the starting point) is A, the same as the distance from head to the start of the cycle.
The use of dummy is optional. If we do
fast = head, we need to verify that
head != null.
Keep a tail pointer when we need the end node.
Request types: User register, user login, user query, user info update.
Assume DAU is 100 million.
User register, user login, and user info update altogether: 0.5/user/day, QPS ~100
User query: 100/user/day, QPS~100,000
Which implementation is better?
A, because B,C,D will easily cause data corruption(mismatch) in case of one operation falls. Case A usually does not cause dirty data, unless setUser() was invoked after the marked place in getUser(), which causes an older version of user been stored in cache.
To avoid the inconsistency issues, which may occur here and there in a concurrent system, we should set a cache timeout, so we can make sure that all data will eventually be the same.
After a user logged in:
- The server creates a session table(session_key, user_id, expire_time)
- Return session_key as cookie
- User browser stores the session_key
- Every request the user sent will take along with it all cookies from this site(so don’t make too many cookies)
- If the server sees the session_key in the cookie is effective, log in the user
Where should we put the sessions? cache? database?
Both. In case we lost all session tables in cache, a great number of users will try to log in at the same time, causing problems.
One-way or two-way. Usually in NoSQL database as it’s simple.
- SQL: ~1k QPS
- NoSQL: ~10k QPS
- In-memory NoSQL(Redis / Memcached): ~100k QPS
- Your news feed consists of the timelines of all your friends or users that you are following
- Core algorithm: merge k sorted array/list/any
- Daily active users(DAU), monthly active users(MAU), query per second(QPS). Peak value and growth expectation
- Number of reads and writes
Get the first N tweets from K(all of your) following users, merge them, and then take the first N tweets.
Problem: Long waiting period. It takes K times blocking (阻塞型) DB read request to load the news feed.
Solution: Cache, for both timeline and news feed:
- Cache timeline: cache the most recent n tweets for each user (DB read –> cache read)
- Cache news feed: If read within x seconds from the last time, read from cache. If not, only merge the K tweets after a certain timestamp (such as since the last update)
Store a news feed list in the database for each user. When a user publishes a new tweet, do a fanout to push the tweet to all the news feed lists of his/her followers. The fanout is performed asynchronously in another task.
Problem: Delayed display for some users. If we have a star user who has 100 million followers, the fanout will have 100 million write operations, which could take hours and is unacceptable for those unlucky followers.
Solution: Rank users by active level; find star users(who have a lot of followers) and use pull model for them.
|DB read||K (num of following)||1|
|DB write||1||K (num of follower)|
|Demand for resources||expensive (memory)||cheap (disk)|
|Delay||low||high (to hear from stars)|
|Active level||users post frequently||users post unfrequently|
Firstly, read and follow the steps on this official instruction from CloudFlare. Do not change the auto-generated DNS rules unless you know what you are doing.
Several things you may need to change if your site is not working properly after you completed all the steps. Be aware, it takes a long time for the newly updated DNS to be effective, be patient and do not worry and change things randomly. I waited for about 24 hours.
- You need a
CNAMEfile in your repo root, containing only one line:
www.yourdomain.com. It decides which domain will response by default. Personally, I prefer the one with
- Configure your DNS in CloudFlare:
The first rule enables
yourdomain.comand the second enables
- Configure your Page Rules to allow Https connections
To deploy on Github, we need to install git deployer and modify the _config.yml file in root:
You have to add your local ssh key to your github account, otherwise you won’t be able to display the site, find instruction here
Clone the new theme under themes directory
Should be the most straight forward solution.
As long as we realize this question is best resolved using stacks, we should be fine. So we need to be clear about when to use stack: When we scan from left to right and always need to look back.
How to convert standard arithmetic expressions to Reverse Polish Notation(RPN), aka postfix notation?