Solution 1: accepted 3ms

1
2
3
4
5
6

public void deleteNode(ListNode node) {
    if (node != null && node.next != null) { // not necessary in the question's scope
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Solution 1: accepted 1ms

1. A: the distance from the beginning to the start of the cycle
2. B: the distance slow pointer moved the start of the cycle
3. 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public ListNode detectCycle(ListNode head) {
    ListNode dummy = new ListNode(0);  // no need to introduce dummy
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            ListNode start = dummy; // start with dummy
            while (slow != start) {
                slow = slow.next;
                start = start.next;
            }                
            return start;
        }
    }
    return null;
}

Without dummy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            ListNode start = head;
            while (slow != start) {
                slow = slow.next;
                start = start.next;
            }                
            return start;
        }
    }
    return null;
}

Solution 1: accepted

The use of dummy is optional. If we do fast = head, we need to verify that head != null.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean hasCycle(ListNode head) {
    ListNode dummy = new ListNode(1);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

Solution 1: accepted 1ms

Keep a tail pointer when we need the end node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public ListNode partition(ListNode head, int x) {
    ListNode leftHead = new ListNode(0);        
    ListNode left = leftHead;        
    ListNode rightHead = new ListNode(0);
    ListNode right = rightHead;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = null;
        if (head.val < x) {
            left.next = head;
            left = head;
        } else {
            right.next = head;
            right = head;
        }
        head = next;
    }
    left.next = rightHead.next; // left = leftHead if no elements were sorted to left
    return leftHead.next;
}

Senario

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

Service

User service

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

User getUser() {
  key = userId + salt;
  user = cache.get(key);
  if (user) 
    return user;
  user = database.get(userId); // mark
  cache.set(key, user);
  return user;
}
User setUser(User user) {
  key = user.id + salt;
  cache.delete(key); // order matters here
  database.set(user); 
}

Which implementation is better?
A. cache.delete(key); database.set(user);
B. database.set(user); cache.delete(key);
C. cache.set(key); database.set(user);
D. database.set(user); cache.set(key);

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.

Authentication service

After a user logged in:

1. The server creates a session table(session_key, user_id, expire_time)
2. Return session_key as cookie
3. User browser stores the session_key
4. Every request the user sent will take along with it all cookies from this site(so don’t make too many cookies)
5. 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.

Friendship service

One-way or two-way. Usually in NoSQL database as it’s simple.

Storgae

1. SQL: ~1k QPS
2. NoSQL: ~10k QPS
3. In-memory NoSQL(Redis / Memcached): ~100k QPS

News Feed System

Basics

1. Your news feed consists of the timelines of all your friends or users that you are following
2. Core algorithm: merge k sorted array/list/any
3. Daily active users(DAU), monthly active users(MAU), query per second(QPS). Peak value and growth expectation
4. Number of reads and writes
5. Examples:
   • Twitter
   • Facebook
   • 朋友圈

Pull model and Push model

Pull model

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:

1. Cache timeline: cache the most recent n tweets for each user (DB read –> cache read)
2. 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)

Push mode

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.

Comparison

First and foremost

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.

Not working?

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.

1. You need a CNAME file in your repo root, containing only one line: yourdomain.com OR www.yourdomain.com. It decides which domain will response by default. Personally, I prefer the one with www
2. Configure your DNS in CloudFlare:
   The first rule enables yourdomain.com and the second enables www.yourdomain.com
   
3. Configure your Page Rules to allow Https connections
   Order matters!
   

Reference

1. https://blog.cloudflare.com/secure-and-fast-github-pages-with-cloudflare/
2. https://www.jonathan-petitcolas.com/2017/01/13/using-https-with-custom-domain-name-on-github-pages.html

Install Hexo

1

npm install hexo-cli -g

Initialize the blog

1
2
3
4
5

hexo init blog
npm install
hexo g #generate
hexo s #server
hexo d #deploy

To deploy on Github, we need to install git deployer and modify the _config.yml file in root:

1

npm install hexo-deployer-git --save

1
2
3
4
5

#Configure _config.yml 
deploy:
  type: git
  repo: [email protected]:PhoenixPan/blog.git
  branch: master

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

Install themes

Clone the new theme under themes directory

1

git clone https://github.com/iissnan/hexo-theme-next.git themes/next

References

hexo-theme-next
手把手教你使用Hexo + Github Pages搭建个人独立博客

Solution 1: accepted 2ms

Should be the most straight forward solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode result = dummy;
        while (dummy.next != null) {
            if (dummy.next.val == val) {
                dummy.next = dummy.next.next;
            } else {
                dummy = dummy.next;
            }
        }
        return result.next;
    }
}

Solution 1: accepted: 12ms 86%

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String cur = tokens[i];  // without it its 14ms
             if (cur.equals("+")) {
                 stack.push(stack.pop() + stack.pop());
             } else if (cur.equals("-")) {
                 stack.push(-stack.pop() + stack.pop());
             } else if (cur.equals("*")) {
                 stack.push(stack.pop() * stack.pop());
             } else if (cur.equals("/")) {
                 int n2 = stack.pop();
                 int n1 = stack.pop();
                 stack.push(n1 / n2);
             } else {
                 stack.push(Integer.parseInt(cur));
             }   
        }
        return stack.pop();
    }
}

How to convert standard arithmetic expressions to Reverse Polish Notation(RPN), aka postfix notation?