how to design a online judgement system like leetcode

– 1. user table for service
– 2. problem service, might be problem and solution and user’s solution
– 3. slave worker
– 4. socket for when the code compile finish, we will need to notice user, benchmark setting for runtime
API building.
–5. submit code is post operation, dispatch jobs for workers and notice
web socket consistant connenction

– core service: what users can do in the website?
submit code, get result, profile, problem, solution, and submission as well.

distribute system for worker? like even loop and thread pool stuff. Load balance..

Dockerize MySQL server for REST API

  1. Dockerize MySQL server
    A. launch a docker in local
    B. Hosting the MySQL server in Docker container in IMAGE
    C. Listening to the host port of MySQL server in local by whatever like Springboot
    Rest API or Django Rest API

Command:

1
2
3
4
5
6
docker run -d -p 3306:3306 --name=mysql-server --env="MYSQL_ROOT_PASSWORD=123456" mysql
# This runs on a detached mode
# Open port 3306:3306
# Name of the server: mysql-server
# root password: 123456
# Container is created from mysql image

Notes: Check what other app is listening to the port on 3306
Command:

1
2
3
-p 12345:3306
# This is one method to check for the port on MAC OS
netstat -vanp tcp | grep 3306

– If you cannot connect to MySQL from another docker and got this error:

to load authentication plugin 'caching_sha2_password'. ```
1
2
3
4
Then you can add the parameter below when running the container.
It is because the newer version of MySQL uses caching_sha2_password instead of mysql_native_password

``` mysqld --default-authentication-plugin=mysql_native_password

– you can access the MySQL through your host

1
2
3
4
5
6
# Through Host 
mysql -host 127.0.0.1 -P 3306 -protocol=tcp -u root -p

# Through container
Docker exec -ti mysql-server bash
mysql -u root -p

Create user and database for connection

1
2
3
4
5
CREATE DATABASE databaseName;
CREATE USER 'dnguyen'@'localhost' IDENITIFIED BY '123456';
GRANT ALL PRIVALEGES ON databaseName.* TO 'dnguyen'@'localhost';
FLUSH PRIVALEGES;
QUIT

If you are using Django, here is what you need to put in the settings.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DATABASES = {
      'default': {
        'ENGINE': 'django.db.backends.mysql',
        'NAME': 'databaseName',
        'USER': 'dnguyen', # or root
        'PASSWORD': '123456',
        'HOST': '127.0.0.1',
        'PORT': '3306', # or 12345
        'OPTIONS': {
            # Tell MySQLdb to connect with 'utf8mb4' character set
            'charset': 'utf8mb4',
        },
    }
}

That is that.

//Resources for mySQL and docker commands to practice.
//With Docker-composer set up docker-compose1.yml

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

services:
  mysql:
    image: mysql:5.6
    ports:
      - "3306:3306"
    environment:
      MYSQL_DATABASE: findeasily
      MYSQL_ROOT_PASSWORD: 88888888
    volumes:
      - mysql_data:/var/lib/mysql/data
  redis:
    image: 'redis:5.0-alpine'
    command: redis-server --requirepass 88888888
    ports:
      - '6379:6379'

volumes:
  mysql_data:

or docker-compose2.yml
‘’’
version: ‘2’

services:

mysql:
image: mariadb:10.1.19
ports:

  - 8083:3306
volumes:
  - ./mysql:/var/lib/mysql
environment:
  MYSQL_ROOT_PASSWORD: wp

1
2

So when you luanch the docker: ``` docker-compose up

Access the mysql db with command:

1
mysql -p findeasily  --protocol=tcp -u root -p

for the first docker-compose1.yml.

And for second docker-compose2.yml, we can access the mysql database with
Command like:

1
2
docker-compose up
mysql -P 8083 --protocol=tcp -u root -p

– Running a Postgres using docker
Command lines:

laungch a docker container
1
2
# Create the docker container over a specific image
docker create -v /var/lib/postgresql/data --name postgres10.3-database alpine

if we already have the docker container running, then we can just launch an images and if there is not
local image it will pull from remote community server.

Let’s now run a specific process in the container. This is going to be postgres. Here are the operations are broken down:
We’re naming the container local-postgres10.3.
Set the password to “password” using the environment tag -e.
Set the port to 5432 so we can access it from Postico later using -p.
The –volumes-from tells the container to mount the /var/lib/postgresql/data volume from the postgres10.3-database container that we created in the previous step.

Lastly, use postgres:10.3 to launch the container.

1
docker run --name local-postgres10.3 -p 5432:5432 -e POSTGRES_PASSWORD=password -d --volumes-from postgres10.3-database postgres:10.3

this is running the images base on postgres in local, so since we do not have local-postgres10.3 images, it will just pull the image from remote and then we can run the image by the image id.

1
docker run dsf3edfdsfw

like that, so right now we running the postgres db in the docker, we can check by

ps ```
1
2
now when we access the db by psql command, we can take like:
 ``` docker exec -it cocky_varahamihira psql -U postgres

This is meaning that:

docker exec command psql in database name as cocky_varahamihira.

Notes: we don’t need to do like

1
2
3
4
5
6
7
8
docker run --name local-postgres10.3 -p 5432:5432 -e POSTGRES_PASSWORD=password -d --volumes-from postgres10.3-database postgres:10.3
>> Get into it
psql -h localhost -p 5432 -U postgres
>>
Password for user postgres:
psql (10.3 (Debian 10.3-1.pgdg90+1))
Type "help" for help.
postgres=#

Cauz it will run psql in local compouter instead of running in docker. so you will get in trouble of
install psql in your local computer, that will be not good I think.

Difference between patch and put in http request

One explaining:
HTTP PUT method only allows a complete replacement of a document. A PATCH request on the other hand, is used to make changes to part of the resource at a location.

Second Explaining:
PATCH is a method which enclosed entity contains a set of instructions describing how a resource currently residing on the origin server should be modified to produce a new version. patch : patch request says . only send the data which one you want to update and it won’t effecting or changing other data

Third explaining:
The main difference between the PUT and PATCH method is that the PUT method uses the request URI to supply a modified version of the requested resource which replaces the original version of the resource whereas the PATCH method supplies a set of instructions to modify the resource.

Medium:
a PUT request always contains a full resource. This is necessary because, a necessary quality of PUT requests is idempotence — the quality of producing the same result even if the same request is made multiple times.

We could simply choose to send the data we need and have our server code update resources appropriately, but then, we’d loose the idempotence and its benefits such as reliable caching of responses on the network and reliable updates of resources from retries when the original request fails.

EDIT: Responses to PUT requests are not cacheable. If a PUT request finds a response in a cache infrastructure, that response (cache entry) should be treated as stale.
Patch:
A PATCH request on the other hand, is used to make changes to part of the resource at a location. That is, it PATCHES the resource — changing its properties. It is used to make minor updates to resources and it’s not required to be idempotent.

If we continue with our example above, we could easily add a new window to the house on plot 1 without having to ship a whole new house. All we have to do is ship the window and PATCH up the old house with a new window. Below is an example of the payload we’d have to send.
put:

1
2
3
4
5
6
7
8
9
 {
  address: 'plot 1',
  owner: 'segun',
  type: 'duplex',
  color: 'green',
  rooms: '5',
  kitchens: '1',
  windows: 20
}

patch:

1
2
3
{
 windows: 21
}

Since PATCH is not idempotent, failed requests are not automatically re-attempted on the network. Also, if a PATCH request is made to a non-existent url e.g attempting to replace the front door of a non-existent building, it should simply fail without creating a new resource unlike PUT, which would create a new one using the payload. Come to think of it, it’ll be odd having a lone door at a house address

leetcode.975 Odd Even Jump

dynamic Programming

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
public int oddEvenJumps(int[] A) {
        int N = A.length;
        if (N <= 1) return N;
        boolean[] odd = new boolean[N];
        boolean[] even = new boolean[N];
        odd[N-1] = even[N-1] = true;

        TreeMap<Integer, Integer> vals = new TreeMap();
        vals.put(A[N-1], N-1);
        for (int i = N-2; i >= 0; --i) {
            int v = A[i];
            if (vals.containsKey(v)) {
                odd[i] = even[vals.get(v)];
                even[i] = odd[vals.get(v)];
            } else {
                Integer lower = vals.lowerKey(v);
                Integer higher = vals.higherKey(v);

                if (lower != null)
                    even[i] = odd[vals.get(lower)];
                if (higher != null) {
                    odd[i] = even[vals.get(higher)];
                }
            }
            vals.put(v, i);
        }

        int ans = 0;
        for (boolean b: odd)
            if (b) ans++;
        return ans;
    }

Leetcode Contest 147 Jul 27 2019

No.1 DP problem

1
2
3
4
5
6
7
8
9
10
11
12
13
public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }

No.2 Alphebatic

//Be careful to process from the

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
class Solution {
public:
    string alphabetBoardPath(string target) {
        int r = 0, c = 0;
        string moves = "";

        for (char letter : target) {
            int row = (letter - 'a') / 5, col = (letter - 'a') % 5;

            while (c > col) {
                moves += 'L';
                c--;
            }

            while (r > row) {
                moves += 'U';
                r--;
            }

            while (r < row) {
                moves += 'D';
                r++;
            }

            while (c < col) {
                moves += 'R';
                c++;
            }

            moves += '!';
        }

        return moves;
    }
};

No.3 Most number of Largest grid border

// accumulated grid solution 

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
int findLargestSquare(vector<vector<int>>& mat) 
    { 
    int max = 0; int m = mat.size() , n = mat[0].size();
    vector<vector<int>> hor(m,vector<int> (n,0)) , ver(m,vector<int> (n,0));
   
    for (int i=0; i<m; i++) { 
        for (int j=0; j<n; j++) { 
            if (mat[i][j] == 1) 
            { 
                hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;   // auxillary horizontal array
                ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;  // auxillary vertical array
            } 
        } 
    } 
        
    for (int i = m-1; i>=0; i--) { 
        for (int j = n-1; j>=0; j--) { 
            int small = min(hor[i][j], ver[i][j]);  // choose smallest of horizontal and vertical value
            while (small > max) { 
                if (ver[i][j-small+1] >= small &&  hor[i-small+1][j] >= small)  // check if square exists with 'small' length
                    max = small; 
                small--; 
            } 
        } 
    } 
    return max*max; 
}

leetcode.528 Random Pick with Weight

JS version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var solution = function(w){
	this.map = new Map();
	this.sum = 0;
	for(let i = 0; i < w.length; i++){
	this.sum += w[i];
	this.map.set(this.sum, i);
	this.keys = [...this.map.keys()].sort((a, b) => a-b);
	}
}

solution.prototype.pickIndex = function(){
	const r = parseInt(Math.random() * this.sum);
	for(const key of this.keys){
		if(r < key){
			return this.map.get(key);
		}
	}
}

Leetcode_Contest_146

1128. Number of Equivalent Domino Pairs

check a list of dominoes, to see the number of pairs.
Ex: Input: dominoes = [[1, 2], [2,1], [3, 4], [5, 6]];
Outout: 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
	int numEquivDominoPairs(vector<vector<int>>& dominoes){
		map<pair<int, int>, int> freq;
		long long total = 0;
		for(vector<int> domino: dominoes){
			if(domino[0] > domino[1]){
				swap(domino[0], domino[1]);
			}
			total += freq[make_pair(domino[0], domino[1])]++;
		} 
		return total;
	}
}

leetcode.1129 Shortest Path with Alternating Colors

BFS: 1 = red, 2 = blue, 0 = root-edge(special case)

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
public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges){
	List<Integer>[] res = new ArrayList[n], blues = new ArrayList[n];
	for(int[] e: red_edges){
		if(reds[e[0]]==null) reds[e[0]] = new ArrayList<>();
	reds[e[0]].add(e[1]);
 	}
 	for(int[] e: blue_edges){
	 	if(blues[e[0]]==null) blue[e[0]] = new ArrayList<>();
	 	blues[e[0]].add(e[1]);
 	}
 	Queue<int[]> q = new LinkedList<>();
 	int[] res = new int[n];
 	Arrays.fill(res, -1);
 	q.add(new int[]{0, 0});
 	int moves = 0;
 	Set<String> seen = new HashSet<>();
 	while(!q.isEmpty()){
 		int size = queue.size(){
 		for(int i = 0; i < size; i++){
 			int curr = q.remove();
 			String key = curr[0] + " " + curr[1];
 			if(seen.contains(key)) continue;
 			seen.add(key);
 			if(curr[1] == 2 || curr[1] == 0)
 				if(reds[curr[0]] != null){
 					for(int child: reds[curr[0]])
 						q.add(new int[]{child, 1});
 			} 
 			if(curr[1]==1 || curr[1] == 0)
 				if(blues[curr[0]] != null)
 					for(int child: blues[curr[0]])
 						q.add(new int[]{child, 2});
 		}
 		moves++;
 	}
 	return res;
 }
}

Leetcode popular answers. initialize all nodes as unreachable(-1)

leetcode.76 Minimum window string

This Pro, at the first time I think of two pointer construct slidding windows, using map
but I find that it is so hard to continue with keep track of the status of T string in the map.

the idea is constructed a window, using two pointer, begin & end, end go forward, when the windows first contain the target word, begin pointer start go right, and once the map[c] ==0, it means that this char is from T. so we make map[c]++, and invalid the counter for next window.
the core code:

1
2
3
4
5
6
7
8
9
10
11
12
13
string minWindow(string s, string t){
	vector<int> map(128, 0);
	for(auto c: t) map[c]++;
	int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
	while(end < s.size()){
		if(map[s[end++]]-- > 0) counter--; //this is hard to read, it means that every time it will //decrease
		while(counter==0){
			if(end-begin < d) d = end - (head = begin);
			if(map[s[begin++]]++==0) counter++; //invalid the counter
		}
	}
	return d==INT_MAX?"":s.substr(head, d);
}

// here is the template for most substr problem using sliding window solution:

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
int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 
                 
                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again
                
                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

//One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++>0) counter++; 
            while(counter>0) if(map[s[begin++]]-->1) counter--;
            d=max(d, end-begin); //while valid, update d
        }
        return d;
    }

Dry:Don't Repeat Yourself

Don’t repeat yourself (DRY, or sometimes do not repeat yourself) is a principle of software development aimed at reducing repetition of software patterns,[1] replacing it with abstractions or using data normalization to avoid redundancy.