Ước chung lớn nhất và bội số chung nhỏ nhất của mảng số nguyên

Chào mừng các bạn đã quay trở lại với thachleblog. Để “đổi gió” cho blog, thỉnh thoảng mình sẽ có những bài code challenge về các giải thuật đơn giản. Để bắt đầu cho phần giải thuật này, bài viết hôm nay mình sẽ trình bày giải thuật tìm ước chung lớn nhất và bội số chung nhỏ nhất cho mảng các số nguyên.

Yêu cầu

Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của mảng các số nguyên.

– Ước chung lớn nhất: gcd (greatest common divisor) là số nguyên x lớn nhất sao cho các phần tử của mảng đều chia hết cho x

– Bội số chung nhỏ nhất: lcm (least common multiple) là số nguyên x nhỏ nhất sao cho x chia hết cho tất cả các phần tử của mảng

Input

a[] = {12, 8, 16}

Output

gcd(a): 4

lcm(a): 48

Giải thuật

– Tìm gcd

+ Đầu tiên mình sẽ tìm a[i] là phần tử nhỏ nhất mảng

+ Tiếp theo thực hiện kiểm tra các phần tử trong mảng có chia hết cho a[i] hay không, nếu chia hết thì a[i] là phần tử cần tìm

+ Nếu không, mình sẽ cho a[i] giảm dần về 1, nếu có giá trị nào mà tất cả phần tử trong mảng đều chia hết thì đó là giá trị cần tìm

– Tìm lcm

+ Đầu tiên mình sẽ tìm a[i] là phần tử lớn nhất nhất mảng

+ Tiếp theo thực hiện kiểm tra a[i] có chia hết cho các phần tử trong mảng không, nếu chia hết thì a[i] là phần tử cần tìm

+ Nếu không, mình sẽ cho a[i] tăng dần đến cấp số cộng, nếu có giá trị nào mà tất cả phần tử trong mảng đều chia hết thì đó là giá trị cần tìm

Code minh họa

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
 
public class Solution {
 
    static int max(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }
 
    static int min(int[] a) {
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        return min;
    }
 
    static int lcm(int[] a) {
        int max = max(a);
        int result = max(a);
        int k = 1;
        boolean flag = true;
        int length = a.length;
        do {
            for (int i = 0; i < a.length; i++) {
                if (result % a[i] != 0) {
                    k++;
                    result = max * k;
                } else if (i == length - 1) {
                    flag = false;
                    break;
                }
            }
        } while (flag);
 
        return result;
    }
 
    static int gcd(int[] a) {
        int result = min(a);
        int length = a.length;
        boolean flag = true;
        do {
            for (int i = 0; i < length; i++) {
                if (a[i] % result != 0) {
                    result--;
                } else if (i == length - 1) {
                    flag = false;
                    break;
                }
            }
        } while (flag);
        return result;
    }

 

Kết

Giải thuật tìm ước chung lớn nhất và bội số chung nhỏ nhất của mảng các số nguyên là 1 phần của bài Between Two Sets trên hackerrank, nếu có hứng thú, các bạn có thể làm tiếp tục để hoàn thành. Sẽ có các test case để đánh giá giải thuật của bạn. Hiện tại thì mình đang luyện để tăng khả năng phản xạ cho giải thuật, hehe.

Đó là phần trình bày của mình về cách ước số chung lớn nhất và bội số chung nhỏ nhất của mảng các số nguyên. Các bạn có giải thuật nào hay hơn, độ phức tạp nhỏ hơn hay có góp ý cho bài của mình thì chia sẻ để chúng ta cùng trao đổi nhé.

Hẹn gặp lại các bạn ở các bài sau. Thanks.

Load balancing với nginx

Chào mừng các bạn đã quay trở lại với thachleblog. Bài viết hôm nay mình sẽ cùng các bạn tìm hiểu về cơ chế cân bằng tải (mình sẽ gọi đúng tên là load balancing) được sử dụng dưới backend.

Một ứng dụng có nhiều user chắc chắn sẽ phải sử dụng đến phương pháp này. Thông thường, việc tự xây dựng một server backend thì quá tốn kém và phức tạp nên phần lớn sẽ sử dụng các service có sẵn như AWS, Google Cloud, Microsoft Azure…

Tuy nhiên, việc hiểu về cơ chế load balancing sẽ cho chúng ta cái nhìn tổng quan hơn về hệ thống backend cũng như có thể hiểu được nguyên nhân của một vài lỗi “hư cấu”. Vậy các lỗi hư cấu đó là gì? Cơ chế balancing như thế nào? Chúng ta cùng bắt đầu nhé.

Giới thiệu

Load balancing là cơ chế phân chia request cho server. Một ứng dụng lớn, có nhiều user, thường sẽ được deploy trên các server khác nhau. Lúc này, ứng dụng sẽ gồm nhiều bản, gọi là instance chạy song song, xử lý độc lập nhưng dùng chung database.

Hình minh họa cơ chế load balancing

Hình minh họa cơ chế load balancing

Mục đích

Sử dụng load balancing với mục đích cân bằng tải và tăng khả năng chịu tải của server trong hệ thống phân tán. Ví dụ nếu một server có khả năng chịu tải 1000 user cùng lúc nhưng nếu có 2 instance thì sẽ tăng khả năng chịu tải lên 2000 user. Bình thường, tùy cơ chế mà ta cấu hình, số request sẽ được “chia” cho 2 instance để giảm tải cho từng server. Hệ thống sẽ xử lý nhanh hơn.

Ngoài ra, load balancing sẽ giảm thiểu khả năng xảy ra lỗi hay nói cách khác là tăng mức độ tin cậy của ứng dụng. Ví dụ, vì lí do gì đó (rất ít xảy ra) mà một server bị lỗi, hệ thống sẽ có cơ chế kiểm tra và chuyển request sang server đang hoạt động để xử lý.

Cơ chế

Tùy vào hệ thống balacing mà sẽ có cơ chế để balancer (nơi tiếp nhận request), xác định server nào sẽ nhận và xử lý request. Hôm nay, mình chỉ giới thiệu sơ lược về các cơ chế phân chia request của nginx balancer, hệ thống server được sử dụng cũng khá rộng rãi, các bạn có thể đọc thêm và nginx tại đây.

Ví dụ về cấu hình đơn giản của nginx cho việc load balancing:

http {
   upstream myapp1 {
       server srv1.thachleblog.com;
       server srv2.thachleblog.com;
       server srv3.thachleblog.com;
   }
   server {
       listen 80;
          }
}

Dựa vào cấu hình ta có thể thấy, có 3 instance của thachleblog.com được chạy trên 3 con server srv1, srv2, serv3. Để xác định được server nào sẽ tiếp nhận request thì có các cơ chế sau:

Round-robin: cơ chế phân chia request cho server dựa vào thuật toán round – robin. Các bạn muốn biết chi tiết về round robin có thể đọc thêm tại đây. Ở ví dụ trên, khi không cấu hình gì thêm, balancer sẽ mặc định sử dụng cơ chế round – robin

Least-connected: request sẽ được chuyển đến cho server đang có ít request đang active nhất

upstream myapp1 {
       least_conn;
       server srv1.thachleblog.com;
       server srv2.thachleblog.com;
       server srv3.thachleblog.com;
   }

ip-hash: cơ chế phân chia request dựa vào ip của client, đảm bảo rằng với cùng 1 ip, sẽ được xử lý trên cùng 1 server. Trừ trường hợp có lỗi xảy ra.

upstream myapp1 {
   ip_hash;
   server srv1.thachleblog.com;
   server srv2.thachleblog.com;
   server srv3.thachleblog.com;
}

weighted-load: ta có thể tự phân chia request dựa vào sức tải của từng server.

  upstream myapp1 {
       server srv1.thachleblog.com weight=3;
       server srv2.thachleblog.com weight=2;
       server srv3.thachleblog.com;
   }

Ví dụ với cấu hình trên, 6 request đến sẽ được chia lần lượt srv1 3 request, srv2 2 request và srv3 1 request.

Kết

Vừa rồi là phần giới thiệu của mình về load balancing cũng như cơ chế phân chia request của nginx balancer. Việc hiểu cơ chế này sẽ giúp các bạn có cái nhìn tổng quan hơn về hệ thống. Ví dụ trường hợp lỗi chỉ xuất hiện “chập chờn” trên môi trường live thì các bạn có thể nghĩ đến khả năng do cấu hình hoặc cache trên các server khác nhau dẫn đến kết quả không đồng nhất …

Mọi thắc mắc hay góp ý vui lòng comment bên dưới, mình sẽ follow nhé. Chào các bạn và hẹn gặp lại các bạn ở các bài viết sau.

Tham khảo thêm:

http://tutorials.jenkov.com/software-architecture/load-balancing.html

https://nginx.org/en/docs/http/load_balancing.html