ARTS Week1

1. leetcode-200

the problem: https://leetcode.com/problems/number-of-islands/

I solved it using one of union-find algorithms, namely quick-find. I have learned about this kind of algorithm when I first read Algorithms, 4th. And I have collected and read several articles about union-find algorithms. I wrote the first version. However, I forget that the input is a 2D matrix of char and I used grid[i][j]==1. Then the count is always the count of the lands(I once set the initial count as m*n and I realized its problem after I read others' implementations for number-of-islands problem. Besides, the implementations of others have wrong method of find method.)

union-find algorithms articles:

1. https://senlinzhan.github.io/2015/01/14/unionfind%E7%AE%97%E6%B3%95/

2.

https://blog.csdn.net/dm_vincent/article/details/7655764

3. https://blog.csdn.net/yaokai_assultmaster/article/details/78888846

4.

有一种算法叫做“Union-Find”？ - Sea_Sky - 博客园

My answer for the problem: number of islands

class Solution {

public int numIslands(char[][] grid) {

    //动态规划
    //最长公共子串？
    //连通性问题？ yes!


    int m=grid.length;
    if(m==0){
        return 0;
    }
    int n=grid[0].length;
     if(n==0){
        return 0;
    }
    UF uf = new UF(n * m);

    int count=0;
    for (int i = 0; i < m; i++) {           
  for (int j = 0; j < n; j++) {                
    if (grid[i][j]=='1') count++;  
    //初始化count值的时候，我们假设每块陆地起初都是孤立的，所以有多少块陆地，就有多少个连通分量
  }       
}  

    uf.setCount(count);

    //注意char=='1'的写法
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]=='1'){         

  if (i < m - 1 && grid[i + 1][j] == '1') { //右边相邻                

    uf.union(i*n+j, (i+1)*n+j);           
  }            
  if (j < n - 1 && grid[i][j + 1] == '1') { //下边相邻                            
    uf.union(i*n+j, i*n+j+1);           
  }       

            }
        }
    }

    return uf.count();
}

}

class UF{ private int count; private int[] ids = null;

    public UF(int num){

    ids=new int[num];
    for(int i=0;i<num;i++){
        ids[i]=i;
    }   
    }

    public void setCount(int total) {
    count = total;
}

    public int count(){
        return count;
    }

       private int find(int p) {
    while(p!=ids[p]){
        p=ids[p];
    }

           return p;
}



public void union(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    if (root_a != root_b) {
        ids[root_a] = root_b;
        count --;
    }
}


}

2. Review for The Chapter 4 Design of Kafka Documentation

Chinese Translation:

4.1 Motivation

4.1 动力

We designed Kafka to be able to act as a unified platform for handling all the real-time data feeds a large company might have. To do this we had to think through a fairly broad set of use cases.

设计Kafka是为了让他能够成为处理各类实时数据流的统一平台。

It would have to have high-throughput to support high volume event streams such as real-time log aggregation.

它必须支持高通量，以支持庞大的事件流比如实时数据收集。

It would need to deal gracefully with large data backlogs to be able to support periodic data loads from offline systems.

需要能很好地应对数据滞后，以应对离线系统周期性地数据加载。

It also meant the system would have to handle low-latency delivery to handle more traditional messaging use-cases.

需要低延时以应对传统的消息系统用法。

We wanted to support partitioned, distributed, real-time processing of these feeds to create new, derived feeds. This motivated our partitioning and consumer model.

支持分片、分布式、实时处理流以创建新的流，这使我们做了分片和消费者模型。

Finally in cases where the stream is fed into other data systems for serving, we knew the system would have to be able to guarantee fault-tolerance in the presence of machine failures.

这些信息流要输入其他数据系统，那么我们要做到很好的错误容忍。

Supporting these uses led us to a design with a number of unique elements, more akin to a database log than a traditional messaging system. We will outline some elements of the design in the following sections.

这些需求使得我们的设计用一些独特地元素，更类似于数据库地日志，而不是传统的消息系统。

3. tips

Jenkins can be configured to automatically make a package using new tag in the git repository.

4. share

Bad Practice I Have Seen (or Participated in) in the software engineering

1. Maps as the input param;

2. One class has too many lines of code;

3. Redundant implicit sessions in Scala, connections are not closed properly as a result;

4. Dao layer and model class is intertwined, coupled;

5. Write your own code instead of using famous frameworks;