---
# System prepended metadata

title: Bài tập CTDL-GT

---


# Bài tập CTDL-GT

## 1. [BT2](https://www.hackerrank.com/domains/java?filters%5Bsubdomains%5D%5B%5D=java-introduction)

### Bài 1: [Welcome to Java!](https://www.hackerrank.com/challenges/welcome-to-java/problem?isFullScreen=true)
```java
public class Solution {

    public static void main(String[] args) {
        System.out.println("Hello, World.");
        System.out.println("Hello, Java.");
    }
}
```

### Bài 2: [Java Stdin and Stdout I](https://www.hackerrank.com/challenges/java-stdin-and-stdout-1/problem) 
```java
public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();

        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}
```

### Bài 3: [Java If-Else](https://www.hackerrank.com/challenges/java-if-else/problem) 
```java
public class Solution {

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int N = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        
        if(N % 2 != 0)
            System.out.println("Weird");
        else {
            if(2 <= N && N <= 5) {
                System.out.println("Not Weird");
            }
            else {
                if(6 <= N && N <= 20) {
                    System.out.println("Weird");
                }
                else
                    System.out.println("Not Weird");
            }
        }
        scanner.close();
    }
}
```

### Bài 4: [Java Stdin and Stdout II](https://www.hackerrank.com/challenges/java-stdin-stdout/problem) 
```java
public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int i = scan.nextInt();
        double d = scan.nextDouble();
        String s = scan.nextLine();
        s = scan.nextLine();
        // Write your code here.

        System.out.println("String: " + s);
        System.out.println("Double: " + d);
        System.out.println("Int: " + i);
    }
}
```

### Bài 5: [Java Output Formatting](https://www.hackerrank.com/challenges/java-output-formatting/problem) 
```java
public class Solution {

    public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            System.out.println("================================");
            for(int i=0;i<3;i++){
                String s1=sc.next();
                int x=sc.nextInt();
                System.out.printf("%-15s%03d\n", s1, x);
            }
            sc.close();
            System.out.println("================================");

    }
}

```

### Bài 6: [Java Loops I](https://www.hackerrank.com/challenges/java-loops-i/problem) 
```java
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine().trim());
        for(int i = 1; i <= 10; i++)
            System.out.printf("%d x %d = %d\n", N, i, N * i);
        bufferedReader.close();
    }
}
```

### Bài 7: [Java Loops II](https://www.hackerrank.com/challenges/java-loops/problem) 
```java
class Solution{
    public static void main(String []argh){
        Scanner in = new Scanner(System.in);
        int t=in.nextInt();
        for(int i=0;i<t;i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int n = in.nextInt();
            int temp = 1;
            for(int j = 1; j <= n; j++)
            {
                a += b * temp;
                System.out.print(a + " ");
                temp *= 2;
            }
            System.out.println();
        }
        in.close();
    }
}
```

### Bài 8: [Java Datatypes](https://www.hackerrank.com/challenges/java-datatypes/problem) 
```java
class Solution{
    public static void main(String []argh)
    {



        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();

        for(int i=0;i<t;i++)
        {

            try
            {
                long x=sc.nextLong();
                System.out.println(x+" can be fitted in:");
                if(x>=-128 && x<=127)System.out.println("* byte");
                if(x>=Short.MIN_VALUE && x<=Short.MAX_VALUE)System.out.println("* short");
                if(x>=Integer.MIN_VALUE && x<=Integer.MAX_VALUE)System.out.println("* int");
                if(x>=Long.MIN_VALUE && x<=Long.MAX_VALUE)System.out.println("* long");
                //Complete the code
            }
            catch(Exception e)
            {
                System.out.println(sc.next()+" can't be fitted anywhere.");
            }

        }
    }
}


```

### Bài 9: [Java End-of-file](https://www.hackerrank.com/challenges/java-end-of-file/problem) 
```java
public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int cnt = 0;
        while(sc.hasNext())
        {
            ++cnt;
            String s = sc.nextLine();
            System.out.println(cnt + " " + s);
        }
    }
}
```

### Bài 10: [Java Static Initializer Block](https://www.hackerrank.com/challenges/java-static-initializer-block/problem) 
```java
public static Scanner sc = new Scanner(System.in);
public static int B;
public static int H;
public static boolean flag;

static {
    B = sc.nextInt();
    H = sc.nextInt();
    try {
        if(B > 0 && H > 0)
            flag = true;
        else
        {
            flag = false;
            throw new Exception("Breadth and height must be positive");
        }
    }
    catch(Exception e) {
        System.out.println(e);
    }
}
```

### Bài 11: [Java Int to String](hackerrank.com/challenges/java-int-to-string/problem) 
```java
    String s = "" + n;

```

### Bài 12: [Java Date and Time](https://www.hackerrank.com/challenges/java-date-and-time/problem) 
```java
class Result {

    public static String findDay(int month, int day, int year) {
        
        Calendar cal = Calendar.getInstance();
        cal.set(year, month - 1, day);
        int dayOfWeek = cal.get(Calendar.DAY_OF_WEEK);
        // return "" + dayOfWeek;
        if(dayOfWeek == 1)
            return "SUNDAY";
        if(dayOfWeek == 2)
            return "MONDAY";
        if(dayOfWeek == 3)
            return "TUESDAY";
        if(dayOfWeek == 4)
            return "WEDNESDAY";
        if(dayOfWeek == 5)
            return "THURSDAY";
        if(dayOfWeek == 6)
            return "FRIDAY";
        return "SATURDAY";
    }

}
```

### Bài 13: [Java Currency Formatter](https://www.hackerrank.com/challenges/java-currency-formatter/problem) 
```java
public class Solution {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double payment = scanner.nextDouble();
        scanner.close();
        
        // Write your code here.
        NumberFormat f1 = NumberFormat.getCurrencyInstance(Locale.US);
        NumberFormat f2 = NumberFormat.getCurrencyInstance(new Locale("en", "IN"));
        NumberFormat f3 = NumberFormat.getCurrencyInstance(Locale.CHINA);
        NumberFormat f4 = NumberFormat.getCurrencyInstance(Locale.FRANCE);

        String us = f1.format(payment);
        String india = f2.format(payment);
        String china = f3.format(payment);
        String france = f4.format(payment); 
        
        System.out.println("US: " + us);
        System.out.println("India: " + india);
        System.out.println("China: " + china);
        System.out.println("France: " + france);
    }
}
```

## 2. [BT3](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=warmup)

### Bài 1: [Solve Me First](https://www.hackerrank.com/challenges/solve-me-first/problem) 
```java
public class Solution {



    static int solveMeFirst(int a, int b) {
      // Hint: Type return a+b; below
      return a + b;
      
	}

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a;
        a = in.nextInt();
        int b;
        b = in.nextInt();
        int sum;
        sum = solveMeFirst(a, b);
        System.out.println(sum);
	}
}
```

### Bài 2: [Simple Array Sum](https://www.hackerrank.com/challenges/simple-array-sum/problem) 
```java
public static int simpleArraySum(List<Integer> ar) {
    int sum = 0;
    for(int i = 0; i < ar.size(); i++)
        sum += ar.get(i);
    return sum;
}
```

### Bài 3: [Compare the Triplet](https://www.hackerrank.com/challenges/compare-the-triplets/problem) 
```java
public static List<Integer> compareTriplets(List<Integer> a, List<Integer> b) {
        int Alice = 0;
        int Bob = 0;
        for(int i = 0; i < 3; i++)
        {
            int f1 = a.get(i);
            int f2 = b.get(i);
            if(f1 > f2)
                Alice++;
            else if(f1 < f2)     
                Bob++;
        }
        List<Integer> ans = new ArrayList<>();
        ans.add(Alice);
        ans.add(Bob);
        return ans;
    }
}
```

### Bài 4: [A Very Big Sum](https://www.hackerrank.com/challenges/a-very-big-sum/problem) 
```java
public static long aVeryBigSum(List<Long> ar) {
    long ans = 0;
    for(int i = 0; i < ar.size(); i++)
        ans += ar.get(i);
    return ans;
}

```

### Bài 5: [Diagonal Difference](https://www.hackerrank.com/challenges/diagonal-difference/problem) 
```java
public static int diagonalDifference(List<List<Integer>> arr) {
// Write your code here
    int f1 = 0;
    int f2 = 0;
    int n = arr.size();
    for(int i = 0; i < n; i++) {
        f1 += arr.get(i).get(i);
        f2 += arr.get(i).get(n - i - 1);
    }
    return Math.abs(f1 - f2);

}
```

### Bài 6: [Plus Minus](https://www.hackerrank.com/challenges/plus-minus/problem) 
```java
public static void plusMinus(List<Integer> arr) {
// Write your code here
    int positive = 0;
    int negative = 0;
    int zero = 0;
    int n = arr.size();
    for(int i = 0; i < n; i++)
    {
        int temp = arr.get(i);
        if(temp > 0)
            positive++;
        else if(temp == 0)
            zero++;
        else
            negative++;
    }
    double raPos = (double) positive / n;
    double raNeg = (double) negative / n;
    double raZe = (double) zero / n;
    System.out.printf("%.6f\n%.6f\n%.6f", raPos, raNeg, raZe);
}
```

### Bài 7: [Staircase](https://www.hackerrank.com/challenges/staircase/problem) 
```java
public static void staircase(int n) {
    String ans = "";
    String temp = "" + n;
    temp += "s\n";
    temp = "%" + temp;

    for(int i = 1; i <= n; i++) {
        ans += "#";
        System.out.printf(temp, ans);
    }

}
```

### Bài 8: [Mini-Max Sum](https://www.hackerrank.com/challenges/mini-max-sum/problem) 
```java
public static void miniMaxSum(List<Integer> arr) {
// Write your code here
    Collections.sort(arr);
    long sum = 0;
    for(int x : arr)
        sum += x;
    System.out.printf("%d %d", sum - arr.get(arr.size() - 1), sum - arr.get(0));
}
```

### Bài 9: [Birthday Cake Candles](https://www.hackerrank.com/challenges/birthday-cake-candles/problem) 
```java
public static int birthdayCakeCandles(List<Integer> candles) {
    int cnt = 0;
    int max = 0;
    for(int x : candles)
        if(x > max) {
            max = x;
            cnt = 1;
        }
        else if(x == max)
            ++cnt;
    return cnt;
}
```

### Bài 10: [Time Conversion](https://www.hackerrank.com/challenges/time-conversion/problem) 
```java
public static String timeConversion(String s) {
    int hour = Integer.valueOf(s.substring(0, 2));

    if (s.contains("AM")) {
        if (hour == 12) {
            hour = 0;
        }
    } else {
        if (hour != 12) {
            hour += 12;
        }

    }

    return String.format("%02d%s", hour, s.substring(2, s.length() - 2));
}
```

## 3. [BT4](https://docs.google.com/document/d/1RgwRO_6J3RXtw3Zj4mIfEAJ3Q2HorNfQ3qx6_ge5tgs/edit)

### Bài 2: [Array - DS](https://www.hackerrank.com/challenges/arrays-ds)

```java
public static List<Integer> reverseArray(List<Integer> a) {
    List<Integer> b = new ArrayList<>();
    for(int i = (int) a.size() - 1; i >= 0; i--) {
        b.add(a.get(i));
    }
    return b;
}
```

### Bài 3: [2D Array - DS](https://www.hackerrank.com/challenges/2d-array)
```java
public static int hourglassSum(List<List<Integer>> arr) {
    int[][] a = new int[6][6];
    for(int i = 0; i < 6; i++)
        for(int j = 0;j < 6; j++)
            a[i][j] = arr.get(i).get(j);
    int maxx = Integer.MIN_VALUE;
    for(int i = 0; i <= 3; i++)
        for(int j = 0; j <= 3; j++){
            int sum = a[i][j] + a[i][j + 1] + a[i][j + 2] +
            a[i + 1][j + 1] + a[i + 2][j] + a[i + 2][j + 1] + a[i + 2][j + 2];
            if(maxx < sum)
                maxx = sum;
        }
    return maxx;
}
```

### Bài 4: [Sherlock and Array](https://www.hackerrank.com/challenges/sherlock-and-array)
```java
public static String balancedSums(List<Integer> arr) {
    int n = arr.size();
    int[] f = new int[n + 1];
    for(int i = 1; i <= n; i++)
        f[i] = f[i - 1] + arr.get(i - 1);
    for(int i = 1; i <= n ; i++)
        if(f[i - 1] - f[0] == f[n] - f[i])
            return "YES";
    return "NO";
}
```

### Bài 5: [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers)
```java
public static List<Integer> closestNumbers(List<Integer> arr) {
    Collections.sort(arr);
    List<Integer> answer = new ArrayList<>();
    int minn = Integer.MAX_VALUE;
    for (int i = 1; i < arr.size(); i++) {
        if (minn > arr.get(i) - arr.get(i - 1)) {
            minn = arr.get(i) - arr.get(i - 1);
            answer.removeAll(answer);
            answer.add(arr.get(i - 1));
            answer.add(arr.get(i));
        } else if(minn == arr.get(i) - arr.get(i - 1)) {
            answer.add(arr.get(i - 1));
            answer.add(arr.get(i));
        }
    }
    return answer;     
}
```

### Bài 6: [Pairs](https://www.hackerrank.com/challenges/pairs)
```java
public static int pairs(int k, List<Integer> arr) {
    int ans = 0;
    HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
    Collections.sort(arr);
    mp.put(arr.get(0), 1);
    for (int i = 1; i < arr.size(); i++) {
        if (mp.get(arr.get(i) - k) != null) {
            ans += mp.get(arr.get(i) - k);
        }
        if (mp.get(arr.get(i)) == null) {
            mp.put(arr.get(i), 1);
        } else {
            mp.put(arr.get(i), mp.get(arr.get(i)) + 1);
        }
    }
    return ans;
}
```

### Bài 7: ThreeSum
```java
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    private static boolean containsDuplicates(long[] a) {
        for (int i = 1; i < a.length; i++)
            if (a[i] == a[i-1]) return true;
        return false;
    }

    private static long count(long[] a) {
        int n = a.length;
        Arrays.sort(a);

        if (containsDuplicates(a)) {
            throw new IllegalArgumentException("array contains duplicate integers");
        }

        long count = 0;
        for (int i = 0; i < n; i++) {
            int k = n - 1;
            for (int j = i + 1; j < n; j++) {
                while (k >= 0 && a[k] > -(a[i] + a[j])) {
                    k--;
                }
                if(k < 0) {
                    break;
                }
                if (k > j && a[i] + a[j] == -a[k]) {
                    count++;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        System.out.println(count(a));
    }
}
```

## 4. [BT linked-list](https://docs.google.com/document/d/1uDeCCEFVt2tHRsqInU5MSh-YTb-cpNRWTuKBMhbYrdE/edit)

### Bài 1: [Print the Elements of a Linked List](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list/problem)
```java
static void printLinkedList(SinglyLinkedListNode head) {
    while (head.next != null) {
        System.out.println(head.data);
        head = head.next;
    }
    System.out.println(head.data);
}
```

### Bài 2: [Insert a Node at the Tail of a Linked List](https://www.hackerrank.com/challenges/insert-a-node-at-the-tail-of-a-linked-list/problem)
```java
static SinglyLinkedListNode insertNodeAtTail(SinglyLinkedListNode head, int data) {
    if (head == null) {
        head = new SinglyLinkedListNode(data);
    } else {
        SinglyLinkedListNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new SinglyLinkedListNode(data);
    }
    return head;
}
```

### Bài 3: [Insert a node at the head of a linked list](https://www.hackerrank.com/challenges/insert-a-node-at-the-head-of-a-linked-list/problem)
```java
static SinglyLinkedListNode insertNodeAtHead(SinglyLinkedListNode llist, int data) {
    if (llist == null) {
        llist = new SinglyLinkedListNode(data);
    } else {
        SinglyLinkedListNode tmp = new SinglyLinkedListNode(data);
        tmp.next = llist;
        llist = tmp;
    }
    return llist;
}
```

### Bài 4: [Insert a node at a specific position in a linked list](https://www.hackerrank.com/challenges/insert-a-node-at-a-specific-position-in-a-linked-list/problem)
```java
public static SinglyLinkedListNode insertNodeAtPosition(SinglyLinkedListNode llist, int data, int position) {
    SinglyLinkedListNode head = llist;
    for (int i = 0; i < position - 1; i++) {
        head = head.next;
    }
    SinglyLinkedListNode tmp = head.next;
    head.next = new SinglyLinkedListNode(data);
    head.next.next = tmp;
    return llist;
}
```

### Bài 5: [Delete a Node](https://www.hackerrank.com/challenges/delete-a-node-from-a-linked-list/problem)
```java
public static SinglyLinkedListNode deleteNode(SinglyLinkedListNode llist, int position) {
    if (position == 0) {
        return llist.next;
    }
    SinglyLinkedListNode temp = llist;

    for (int i = 0; i < position - 1; i++) {
        temp = temp.next;
    }
    SinglyLinkedListNode tmp = temp.next.next;
    temp.next = new SinglyLinkedListNode(0);
    temp.next = tmp;
    return llist;
}
```

### Bài 6: [Print in Reverse](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list-in-reverse/problem)
```java
public static void reversePrint(SinglyLinkedListNode llist) {
    SinglyLinkedListNode tmp = llist;
    List<Integer> ans = new ArrayList<Integer>();
    while (tmp.next != null) {
        ans.add(tmp.data);
        tmp = tmp.next;
    }
    ans.add(tmp.data);
    Collections.reverse(ans);
    for (int i : ans) {
        System.out.println(i);
    }
}
```

### Bài 7: [Reverse a linked list](https://www.hackerrank.com/challenges/reverse-a-linked-list)
```java
public static SinglyLinkedListNode reverse(SinglyLinkedListNode llist) {
    SinglyLinkedListNode tmp = llist;
    List<Integer> ans = new ArrayList<Integer>();
    while (tmp.next != null) {
        ans.add(tmp.data);
        tmp = tmp.next;
    }
    ans.add(tmp.data);
    Collections.reverse(ans);
    SinglyLinkedListNode res = llist;
    for (int i : ans) {
        res.data = i;
        res = res.next;
    }
    return llist;
}
```

### Bài 8: [Compare two linked lists](https://www.hackerrank.com/challenges/compare-two-linked-lists/problem)
```java
static boolean compareLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    SinglyLinkedListNode tmp1 = head1, tmp2 = head2;
    while (tmp1 != null && tmp2 != null) {
        if (tmp1.data != tmp2.data) { 
            return false;
        }
        tmp1 = tmp1.next;
        tmp2 = tmp2.next;
    }
    if (tmp1 != null || tmp2 != null) {
        return false;
    }
    return true;

}
```

### Bài 9: [Merge two sorted linked lists](https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists/problem)
```java
static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    SinglyLinkedListNode tmp = new SinglyLinkedListNode(0);
    SinglyLinkedListNode cur = tmp;
    while (head1 != null && head2 != null) {
        if (head1.data <= head2.data) {
            if ( cur.data == 0) {
                cur.data = head1.data;
            } else {
                cur.next = new SinglyLinkedListNode(head1.data);
                cur = cur.next;
            }
            head1 = head1.next;
        } else {
            if (cur.data == 0) {
                cur.data = head2.data;
            } else {
                cur.next = new SinglyLinkedListNode(head2.data);
                cur = cur.next;
            }
            head2 = head2.next;
        }
    }
    while (head1 != null) {
        cur.next = new SinglyLinkedListNode(head1.data);
        cur = cur.next;
        head1 = head1.next;
    }

    while (head2 != null) {
        cur.next = new SinglyLinkedListNode(head2.data);
        cur = cur.next;
        head2 = head2.next;
    }
    return tmp;

}
```

### Bài 10: [Get Node Value](https://www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem)
```java
public static int getNode(SinglyLinkedListNode llist, int positionFromTail) {
// Write your code here
    int cnt = 0;
    SinglyLinkedListNode tmp = llist;
    while (tmp != null) {
        ++cnt;
        tmp = tmp.next;
    }
    tmp = llist;
    cnt -= positionFromTail;
    for (int i = 0; i < cnt - 1; i++) {
        tmp = tmp.next;
    }
    return tmp.data;
}
```

## 5. [BT5](https://docs.google.com/document/d/1L6IC7R0TYiSZOYG2wXhCMah4WD4VSnSLdfLf1ilcvfs/edit)

### Bài 2: [Java List](https://www.hackerrank.com/challenges/java-list/problem)
```java
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    ArrayList<Integer> arr = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
        int x = sc.nextInt();
        arr.add(x);
    }

    int Q = sc.nextInt();
    while (Q-- != 0) {
        String s = sc.next();
        if (s.equals("Insert")) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            arr.add(x, y);
        } else {
            int x = sc.nextInt();
            arr.remove(x);
        }
    }
    for (int x : arr) {
        System.out.print(x + " ");
    }
}
```

### Bài 3: [Java Arraylist](https://www.hackerrank.com/challenges/java-arraylist/problem)
```java
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    ArrayList< ArrayList <Integer> > arr = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
        ArrayList<Integer> tmp = new ArrayList<>();
        int d = sc.nextInt();
        while (d-- != 0) {
            int x = sc.nextInt();
            tmp.add(x);
        }
        arr.add(tmp);
    }
    int q = sc.nextInt();
    while (q-- != 0) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        x--;
        y--;
        if (x >= arr.size()) {
            System.out.println("ERROR!");
            continue ;
        }
        if (y >= arr.get(x).size()) {
            System.out.println("ERROR!");
            continue ;
        }

        System.out.println(arr.get(x).get(y));
    }
}
```

### Bài 4: [Balanced Brackets](https://www.hackerrank.com/challenges/balanced-brackets)
```java
public static String isBalanced(String s) {
    Stack <Character> st = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
            st.push(s.charAt(i));
            continue ;
        }
        if (st.empty()) {
            return "NO";
        }
        if (st.peek() == '{' && s.charAt(i) != '}') {
            return "NO";
        }
        if (st.peek() == '(' && s.charAt(i) != ')') {
            return "NO";
        }
        if (st.peek() == '[' && s.charAt(i) != ']') {
            return "NO";
        }
        st.pop();
    }
    if (!st.empty()) {
        return "NO";
    }
    return "YES";
}
```

### Bài 5: [Equal Stacks](https://www.hackerrank.com/challenges/equal-stacks)
```java
public static int getSum(List<Integer> d) {
    int sum = 0;
    for (int x : d) {
        sum += x;
    }
    return sum;
}
public static int getLastElement(List<Integer> d) {
    int size = d.size();
    return d.get(size - 1);
}
public static List<Integer> removeLastElement(List<Integer> d) {
    int size = d.size();
    d.remove(size - 1);
    return d;
}
public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
    Collections.reverse(h1);
    Collections.reverse(h2);
    Collections.reverse(h3);
    while (h1.size() != 0 && h2.size() != 0 && h3.size() != 0) {
        int x = getSum(h1);
        int y = getSum(h2);
        int z = getSum(h3);
        int minn = Math.min(x, Math.min(y, z));
        while (x > minn) {
            x -= getLastElement(h1);
            h1 = removeLastElement(h1);
        }
        while (y > minn) {
            y -= getLastElement(h2);
            h2 = removeLastElement(h2);
        }
        while (z > minn) {
            z -= getLastElement(h3);
            h3 = removeLastElement(h3);
        }
        if (x == minn && y == minn & z == minn) {
            return x;
        }
    }
    return 0;
}
```

### Bài 6: [Simple Text Editor](https://www.hackerrank.com/challenges/simple-text-editor)
```java
import java.io.*;
import java.util.*;

public class Solution {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                if (st.hasMoreTokens()) {
                    str = st.nextToken("\n");
                } else {
                    str = br.readLine();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        Stack<String> stack = new Stack<>();
        String s = "";
        int Q = sc.nextInt();
        while (Q-- != 0) {
            int query = sc.nextInt();
            switch (query) {
                case 1: {
                    stack.push(s);
                    String temp = sc.next();
                    s += temp;
                    break;
                }

                case 2: {
                    int n = s.length() - sc.nextInt();
                    stack.push(s);
                    s = s.substring(0, n);
                    break;
                }

                case 3: {
                    int k = sc.nextInt();
                    System.out.print(s.charAt(k - 1) + "\n");
                    break;
                }

                case 4: {
                    s = stack.pop();
                    break;
                }
            }
        }
    }
}

```

### Bài 7: [Queue Using Two Stacks](https://www.hackerrank.com/challenges/queue-using-two-stacks)
```java
public class Solution {

    private static void move(Stack<Integer> src, Stack<Integer> des) {
        while (!src.isEmpty()) {
            des.push(src.pop());
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int query = sc.nextInt();

        Stack<Integer> input = new Stack<>();
        Stack<Integer> output = new Stack<>();

        while (query-- > 0) {
            int type = sc.nextInt();
            if (type == 1) {
               input.push(sc.nextInt());
               continue;
            }

            if (output.isEmpty()) {
                move(input, output);
            }
            
            if (type == 2) {
                output.pop();
                continue;
            }

            System.out.print(output.peek() + "\n");
        }

        sc.close();
    }
}
```


## 6. [BT6](https://docs.google.com/document/d/1dkLn_S_Wd8qCnB_aoQHVef9Yciy1cdRXvIvRRHJuIQY/edit)

### Bài 2: [Intro to Tutorial Challenges](https://www.hackerrank.com/challenges/tutorial-intro)
```java
public static int introTutorial(int V, List<Integer> arr) {
    int r = arr.size() - 1;
    int l = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int k = arr.get(mid);
        if (k == V) {
            return mid;
        }
        if (k > V) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }        
    }
    return -1;
}
```

### Bài 3: [Insertion Sort - Part 1](https://www.hackerrank.com/challenges/insertionsort1)
```java
public static void insertionSort1(int n, List<Integer> arr) {
    for (int i = n - 2; i >= 0; i--) {
        int a = arr.get(i);
        int b = arr.get(i + 1);

        if (a > b) {
            arr.set(i + 1, a);

            for (Integer p : arr) {
                System.out.print(p + " ");
            }

            System.out.println();

            arr.set(i, b);
        }
    }

     for (Integer p : arr) {
        System.out.print(p + " ");
    }
}
```

### Bài 4: [Insertion Sort - Part 2](https://www.hackerrank.com/challenges/insertionsort2)
```java
public static void insertionSort2(int n, List<Integer> arr) {
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            int a = arr.get(j);
            int b = arr.get(j + 1);
            if (a > b) {
                arr.set(j, b);
                arr.set(j + 1, a);
            }
        }

        for (int j = 0; j < n; j++) {
            System.out.print(arr.get(j) + " ");
        }
        System.out.println();
    }
}

```

### Bài 5: [Correctness Invariant](https://www.hackerrank.com/challenges/correctness-invariant)
```java
public class Solution {

    public static void insertionSort(int[] A){
        for (int i = 1; i < A.length; i++){
            int value = A[i];
            int j = i - 1;
            while (j >= 0 && A[j] > value){
                A[j + 1] = A[j];
                A[j] = value;
                j = j - 1;
            }
        }
        printArray(A);
    }
    

    static void printArray(int[] ar) {
        for (int n: ar){
            System.out.print(n+" ");
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ar = new int[n];
        for (int i = 0; i < n; i++){
            ar[i] = in.nextInt();
        }
        insertionSort(ar);
    }
}
```

### Bài 6: [Counting Sort 1](https://www.hackerrank.com/challenges/countingsort1)
```java
public static List<Integer> countingSort(List<Integer> arr) {
    int[] cnt = new int[100];
    
    for (Integer p : arr) {
        cnt[p]++;
    }
    List<Integer> ans = new ArrayList<>();
    
    for (int i = 0; i < 100; i++) {
        ans.add(cnt[i]);
    }
    return ans;
}
```

### Bài 7: 
Trong hai thuật toán sắp xếp Chọn (Insertion sort) và Chèn/Xen vào (Selection Sort), dữ liệu đầu vào không nên lưu trong LinkedList (danh sách liên kết). Bởi vì việc update trong LinkedList rất phức tạp.


## 7. [BT7](https://docs.google.com/document/d/1KndwwmFgUGY6Smj7b1L75YPX0sB2hgbWRWmqdRh5kXQ/edit)

### Bài 2: [Computing the GCD](https://www.hackerrank.com/challenges/functional-programming-warmups-in-recursion---gcd)
```java
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    while (b != 0) {
        int c = a % b;
        a = b;
        b = c;
    }
    System.out.print(a);
}
```

### Bài 3: [Java Sort](https://www.hackerrank.com/challenges/java-sort)
```java
private static class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student x, Student y) {
        if (Double.compare(x.getCgpa(), y.getCgpa()) == 0) {
            if (x.getFname().equals(y.getFname())) {
                return Integer.compare(x.getId(), y.getId());
            }
            return x.getFname().compareTo(y.getFname());
        }
        return -Double.compare(x.getCgpa(), y.getCgpa());
    }
}
```

### Bài 4: [Quicksort 1 - Partition](https://www.hackerrank.com/challenges/quicksort1)
```java
public static List<Integer> quickSort(List<Integer> arr) {
    int pivot = arr.get(0);
    List<Integer> right = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    for (int i = 1; i < arr.size(); i++) {
        if (arr.get(i) > pivot) {
            right.add(arr.get(i));
        } else {
            ans.add(arr.get(i));
        }
    }
    ans.add(pivot);
    for (int x : right) {
        ans.add(x);
    }
    return ans;
}
```

### Bài 5: [Quicksort In-Place](https://www.hackerrank.com/challenges/quicksort3)
```java
public class Solution {
    
    public static void Quicksort(List<Integer> arr, int low, int high) {
        if(low >= high)
            return ;
        int i = low;
        for(int j = low; j < high; j++) {
            if(arr.get(j) <= arr.get(high)) {
                Collections.swap(arr, i, j);
                i++;
            }
        }
        Collections.swap(arr, i, high);
        for(int x : arr)
            System.out.print(x + " ");
        System.out.println();
        Quicksort(arr, low, i - 1);
        Quicksort(arr, i + 1, high);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> arr = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            arr.add(x);
        }
        Solution.Quicksort(arr, 0, arr.size() - 1);
    }
}
```

### Bài 6: [Find the Median](https://www.hackerrank.com/challenges/find-the-median)
```java
class Result {

    private static void shuffle(List<Integer> arr, int left, int right) {
        Random rand = new Random();
        for (int i = left; i <= right; i++) {
            int pos = rand.nextInt(right - left + 1) + left;
            int a = arr.get(i);
            arr.set(i, arr.get(pos));
            arr.set(pos, a);
        }
    }

    public static int findMedian(List<Integer> arr, int median, int low, int high) {
        shuffle(arr, low, high);
        int patrition = arr.get(high);
        if (median == 1 && arr.size() == 1) {
            return patrition;
        }
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr.get(j) <= patrition) {
               Collections.swap(arr, i, j);
               i++;
            }
        }

        Collections.swap(arr, i, high);


        int left = i - low + 1;

        if (median > left) {
            return findMedian(arr, median - left, i + 1, high);
        }

        if (median < left) {
            return findMedian(arr, median, low, i - 1);
        }

        return patrition;
    }
}
```

## 8. [BT8](https://docs.google.com/document/d/1UVgzgppsNKqBvgIuoZ0rryy9a7vwi8CnH_8osfYnDVk/edit)

### Bài 2: [Java String Reverse](https://www.hackerrank.com/challenges/java-string-reverse/problem)
```java
public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String A = sc.next();

    StringBuilder tmp = new StringBuilder();
    tmp.append(A);
    tmp.reverse();
    String B = String.valueOf(tmp);
    if (A.equals(B)) {
        System.out.println("Yes");
    } else {
        System.out.println("No");
    }
    sc.close();
}
```

### Bài 3: [Jesse and Cookies](https://www.hackerrank.com/challenges/jesse-and-cookies/problem)
```java
public static int cookies(int k, List<Integer> A) {
    Queue<Integer> q = new PriorityQueue<>(A);
    int cnt = 0;
    while (q.size() >= 2 && q.peek() < k) {
        int a = q.poll();
        int b = q.poll();
        cnt++;
        q.add(a + 2 * b);
    }
    
    if (q.peek() < k) {
        return -1;
    }
    
    return cnt;
}
```

### Bài 4: [Java Priority Queue](https://www.hackerrank.com/challenges/java-priority-queue/problem)
```java
class Student {
    int id;
    String name;
    double cgpa;
    
    public Student(int id, String name, double cgpa) {
        this.id = id;
        this.name = name;
        this.cgpa = cgpa;
    }
    
    public int getId() {
        return id;
    }
    
    public String getName() {
        return name;
    }
    
    public double getCgpa() {
        return cgpa;
    }
    
    
}


class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student x, Student y) {
        int a = Double.compare(x.getCgpa(), y.getCgpa());
        // System.err.println("Compare: " + x.getCgpa() + " " + y.getCgpa() + " " + a);
        if (a == 0) {
            int b = x.getName().compareTo(y.getName());
            if (b == 0)  {
                return Integer.compare(x.getId(), y.getId());
            }
            return b;
        }
        return -a;
    }
}

class Priorities {
    public List<Student> getStudents(List<String> event) {
        Comparator cmp = new StudentComparator();
        Queue<Student> q = new PriorityQueue<>(10, cmp);
        for (String p : event) {
            StringTokenizer st = new StringTokenizer(p);
            String type = st.nextToken();
            if (type.equals("SERVED")) {
                q.poll();
                continue;
            }
            String name = st.nextToken();
            double cgpa = Double.parseDouble(st.nextToken());
            int id = Integer.parseInt(st.nextToken());
            // System.err.println(id + " " + name + " " + cgpa);
            q.add(new Student(id, name, cgpa));
        }
        List<Student> tmp = new ArrayList<>();
        while(!q.isEmpty()) {
            tmp.add(q.poll());
        }
        return tmp;
    }
}
```

### Bài 5: [Counting Sort 2](https://www.hackerrank.com/challenges/countingsort2)
```java
public static List<Integer> countingSort(List<Integer> arr) {
    int cnt[] = new int[100];

    for (Integer p : arr) {
        cnt[p]++;
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        while (cnt[i]-- > 0) {
            ans.add(i);
        }
    }
    return ans;
}
```

### Bài 6: [Find the Running Median](https://www.hackerrank.com/challenges/find-the-running-median)
```java
public static List<Double> runningMedian(List<Integer> a) {
    int n = a.size();
    Queue<Integer> max = new PriorityQueue<>(n / 2 + 1, Collections.reverseOrder());
    Queue<Integer> min = new PriorityQueue<>(n / 2 + 1);
    List<Double> ans = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        int x = a.get(i - 1);
        if (!min.isEmpty() && x > min.peek()) {
            min.add(x);
        } else {
            max.add(x);
        }
        while (max.size() - min.size() > 1) {
            int k = max.poll();
            min.add(k);
        }
        
        while (min.size() - max.size() >= 1) {
            int k = min.poll();
            max.add(k);
        }

        if (i % 2 == 0) {
            ans.add((double) (max.peek() + min.peek()) / 2);
        } else {
            ans.add((double) max.peek());
        }
    }
    return ans;
}
```

## 9. [BT9](https://docs.google.com/document/d/1Hbt-7VW7wEVPQVrkawt9fvdcciIyIFTot7dfV19sIP4/edit)

### Bài 2: [Java Map](https://www.hackerrank.com/challenges/phone-book)
```java
class Solution {
    public static void main(String []args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        Map<String, Integer> map = new HashMap<>();
        for (int i=0;i<n;i++) {
            String name = in.nextLine();
            int phone = in.nextInt();
            map.put(name, phone);
            in.nextLine();
        }
        while (in.hasNext()) {
            String s=in.nextLine();
            if (map.containsKey(s)) {
                System.out.println(s + "=" + map.get(s));
            } else {
                System.out.println("Not found");
            }
        }
    }
}
```

### Bài 3: [Java HashSet](https://www.hackerrank.com/challenges/java-hashset)
```java
HashSet<String> hashSet = new HashSet<>();  
for (int i = 0; i < t; i++) {
    hashSet.add(pair_left[i] + " " + pair_right[i]);
    System.out.println(hashSet.size());
}
```

### Bài 4: [Tree: Inorder Traversal](https://www.hackerrank.com/challenges/tree-inorder-traversal)
```java
public static void inOrder(Node root) {
    if (root.left != null) {
        inOrder(root.left);
    }
    System.out.print(root.data + " ");

    if (root.right != null) {
        inOrder(root.right);
    }
}
```

### Bài 5: [Tree: Preorder Traversal](https://www.hackerrank.com/challenges/tree-preorder-traversal)
```java
public static void preOrder(Node root) {
    System.out.print(root.data + " ");

    if (root.left != null) {
        preOrder(root.left);
    }


    if (root.right != null) {
        preOrder(root.right);
    }
}
```

### Bài 6: [Tree: Level Order Traversal](https://www.hackerrank.com/challenges/tree-level-order-traversal)
```java
public static void levelOrder(Node root) {
    Queue<Node> pq = new LinkedList<>();
    pq.add(root);

    while (!pq.isEmpty()) {
        Node p = pq.poll();
        System.out.print(p.data + " ");
        if (p.left != null) {
          pq.add(p.left); 
        }
        if (p.right != null) {
          pq.add(p.right);
        }
    }
}
```

### Bài 7: [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers)
```java
static List<Integer> tmp = new ArrayList<>();
private static void mergeSort(List<Integer> arr, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = low + (high - low) / 2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    tmp.clear();
    int i = low;
    int j = mid + 1;
    while (i <= mid && j <= high) {
        int a = arr.get(i);
        int b = arr.get(j);
        if (a <= b) {
            tmp.add(a);
            i++;
            continue;
        }
        tmp.add(b);
        j++;
    }

    while (i <= mid) {
        tmp.add(arr.get(i++));
    }

    while (j <= high) {
        tmp.add(arr.get(j++));
    }
    int pos = 0;
    for (int k : tmp) {
        arr.set(pos + low, k);
        pos++;
    }

}
public static List<Integer> closestNumbers(List<Integer> arr) {
    mergeSort(arr, 0, arr.size() - 1);
    List<Integer> answer = new ArrayList<>();
    int minn = Integer.MAX_VALUE;
    for (int i = 1; i < arr.size(); i++) {
        if (minn > arr.get(i) - arr.get(i - 1)) {
            minn = arr.get(i) - arr.get(i - 1);
            answer.removeAll(answer);
            answer.add(arr.get(i - 1));
            answer.add(arr.get(i));
        }
        else if (minn == arr.get(i) - arr.get(i - 1)) {
            answer.add(arr.get(i - 1));
            answer.add(arr.get(i));
        }
    }
    return answer;
}
```


## 10. [BT10](https://docs.google.com/document/d/1xHE6AQypBX5E16t6hjAJ4yxA5WGc9apgu1bholitmgI/edit)

### Bài 2: [Tree: Height of a Binary Tree](https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree) 
```java
public static int height(Node root) {
      int ans = 0;
      if (root.left != null) {
          ans = Math.max(ans, height(root.left) + 1);
      }

      if (root.right != null) {
          ans = Math.max(ans, height(root.right) + 1);
      }

      return ans;
}
```

### Bài 3: [Binary Search Tree : Insertion](https://www.hackerrank.com/challenges/binary-search-tree-insertion) 
```java
public static Node insert(Node root,int data) {
    if (root == null) {
        return new Node(data);
    }

    Node cur = root;

    if (data < cur.data) {
        cur.left = insert(cur.left, data);
    } else {
        cur.right = insert(cur.right, data);
    }

    return cur;
}
```

### Bài 4: [Binary Search Tree : Lowest Common Ancestor](https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor) 
```java
private static List<Integer> findAncestor(Node root, int v) {
    List<Integer> ancestor = new ArrayList<>();
    Node p = root;
    while (p.data != v) {
          ancestor.add(p.data);
          if(v < p.data) {
              p = p.left;
          } else {
              p = p.right;
          }
    }
    ancestor.add(v);
    return ancestor;
}
public static Node lca(Node root, int v1, int v2) {
    // Write your code here.

      List<Integer> ancestor1 = findAncestor(root, v1);
      List<Integer> ancestor2 = findAncestor(root, v2);

      int length = Math.min(ancestor1.size(), ancestor2.size());
      int LCA = root.data;
      for (int i = length - 1; i >= 0; i--) {
          int a = ancestor1.get(i);
          int b = ancestor2.get(i);
          if (a == b) {
              LCA = a;
              break;
          }
      }

      return new Node(LCA);

}
```

### Bài 5: [Is This a Binary Search Tree?](https://www.hackerrank.com/challenges/is-binary-search-tree) 
```java
List<Integer> list = new ArrayList();
void inOrder(Node root) {
    if (root.left != null) {
        inOrder(root.left);
    }

    list.add(root.data);

    if (root.right != null) {
        inOrder(root.right);
    }
}
boolean checkBST(Node root) {
    inOrder(root);
    System.err.println(list);
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i - 1) >= list.get(i)) {
            return false;
        }
    }

    return true;
}
```

### Bài 6: [Self Balancing Tree](https://www.hackerrank.com/challenges/self-balancing-tree) 
```java
private static Node leftRotation(Node root) {
    Node nRoot = root.right;
    Node tmp = root;
    tmp.right = nRoot.left;
    nRoot.left = tmp;
    return nRoot;
}

private static Node rightRotation(Node root) {
    Node nRoot = root.left;
    Node tmp = root;
    tmp.left = nRoot.right;
    nRoot.right = tmp;
    return nRoot;
}

private static int getHeight(Node root) {
    if (root == null) {
        return -1;
    }

    return root.ht;
}

private static int setHeight(Node root) {
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

private static Node update(Node root) {
    if (root == null) {
        return root;
    }
    if (root.left != null) {
        root.left.ht = setHeight(root.left); 
    }

    if (root.right != null) {
        root.right.ht = setHeight(root.right); 
    }

    root.ht = setHeight(root);
    return root;
}
static Node insert(Node root,int val)
{
    if (root == null) {
        root = new Node();
        root.val = val;
        root.ht = setHeight(root);
        return root;
    }

    Node cur = root;

    if (root.val > val) {
        cur.left = insert(cur.left, val);
    } else {
        cur.right = insert(cur.right, val);
    }

    int balance = getHeight(cur.left) - getHeight(cur.right);

    if (balance < -1) { //Right
        if (getHeight(cur.right.left) > getHeight(cur.right.right)) { //Left
            cur.right = rightRotation(cur.right);
            update(cur.right);
        }

        cur = leftRotation(cur);
    }

    if (balance > 1) { //Left
        if (getHeight(cur.left.right) > getHeight(cur.left.left)) {//Right
            cur.left = leftRotation(cur.left);
            update(cur.left);
        }

        cur = rightRotation(cur);
    }
    update(cur);
    return cur;

}
```

## 11. [BT11](https://docs.google.com/document/d/1j5jlpHyo9YmT8oX9WWHI3KNeeZdkogY7O6-U5Xv46lc/edit)

### Bài 2: 

[Page1](https://i.imgur.com/TJmYNaD.jpg)
[Page2](https://i.imgur.com/sR5WFht.jpg)
[Page3](https://i.imgur.com/1U5WquV.jpg)
[Page4](https://i.imgur.com/bosuXNu.jpg)


### Bài 3: Vẽ

### Bài 4: [Pairs](https://www.hackerrank.com/challenges/pairs) 
```java
public static int pairs(int k, List<Integer> arr) {
    int ans = 0;
    HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
    Collections.sort(arr);
    mp.put(arr.get(0), 1);
    for (int i = 1; i < arr.size(); i++) {
        if (mp.get(arr.get(i) - k) != null) {
            ans += mp.get(arr.get(i) - k);
        }
        if (mp.get(arr.get(i)) == null) {
            mp.put(arr.get(i), 1);
        } else {
            mp.put(arr.get(i), mp.get(arr.get(i)) + 1);
        }
    }
    return ans;
}
```

### Bài 5: [Mising Numbers](https://www.hackerrank.com/challenges/missing-numbers) 

#### a. Hash Map: O($n \times \log$)
```java
public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    for (int a : arr) {
        if (!hashMap.containsKey(a)) {
            hashMap.put(a, 1);
        } else {
            hashMap.put(a, hashMap.get(a) + 1);
        }
    }

    List<Integer> ans = new ArrayList<>();
    for(int b : brr) {
        if(hashMap.get(b) == null || hashMap.get(b) == 0) {
            ans.add(b);
            hashMap.put(b, -1);
        } else {

            hashMap.put(b, hashMap.get(b) - 1);
        }
    }

    Collections.sort(ans);
    return ans;
}
```

#### b. Sorting: O($n \times \log(n)$)
```java
public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {
// Write your code here
    Collections.sort(arr);
    Collections.sort(brr);
    List<Integer> ans = new ArrayList<>();
    int a = 0;
    for (int b : brr) {
        if (!ans.isEmpty() && ans.get(ans.size() - 1) == b) {
            continue;
        }

        while(a < arr.size() && arr.get(a) < b) {
            a++;
        }

        if(a == arr.size() || arr.get(a) != b) {
            ans.add(b);
            continue;
        }

        a++;
    }
    return ans;
}
```

#### c. Counting Sort: O($n$)
```java
public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {

    List<Integer> ans = new ArrayList<>();
    int min = Collections.min(brr);
    for (int i = 0; i < arr.size(); i++) {
        arr.set(i, arr.get(i) - min);
    }
    for (int i = 0; i < brr.size(); i++) {
        brr.set(i, brr.get(i) - min);
    }
    int cnt[] = new int[101];
    for (int a : arr) {
        if (a < 0 || a > 100) {
            continue;
        }

        cnt[a]++;
    }
    boolean[] notHave = new boolean[101];
    for (int b : brr) {
        if (cnt[b] == 0) {
            notHave[b] = true;
        }    
        cnt[b]--;
    }
    for (int i = 0; i < 101; i++) {
        if (notHave[i]) {
            ans.add(i + min);
        }
    }
    return ans;
}
```

### Bài 6: [Find the Running Median](https://www.hackerrank.com/challenges/find-the-running-median) 
```java
class Pair implements Comparator<Pair>, Comparable<Pair> {
    public int value;
    public int pos;
    public Pair(){

    }

    public Pair(int value, int pos) {
        this.value = value;
        this.pos = pos;
    }

    @Override
    public int compare(Pair pair, Pair otherPair) {
        int a = Integer.compare(pair.value, otherPair.value);
        if (a == 0) {
            return Integer.compare(pair.pos, otherPair.pos);
        }
        return a;
    }

    @Override
    public int compareTo(Pair otherPair) {
        return compare(this, otherPair);
    }
}

class Result {

    public static List<Double> runningMedian(List<Integer> a) {
        Pair median = null;
        TreeSet<Pair> treeSet = new TreeSet<>();
        List<Double> ans = new ArrayList<>();
        for (int i = 1; i <= a.size(); i++) {
            int value = a.get(i - 1);
            Pair pair = new Pair(value, i);
            boolean toLeft = false;

            if (median == null) {
                median = pair;
            } else {
                toLeft = median.compareTo(pair) > 0;
            }

            treeSet.add(pair);

            int size = treeSet.size();

            if (size % 2 == 0) {
                Pair cur = null;
                if (toLeft) {
                    cur = treeSet.lower(median);
                } else {
                    cur = median;
                    median = treeSet.higher(median);
                }
                ans.add(1.0 * (median.value + cur.value) / 2);
            } else {
                if (toLeft) {
                    median = treeSet.lower(median);
                }
                ans.add(1.0 * median.value);
            }
        }
        return ans;
    }

}
```

## 12. [BT12](https://docs.google.com/document/d/1i9zGreLuArwE_oTD0GggaoBBgvT4M7PION6DgEGL9dI/edit)

### Bài 1: [Connected Cells in a Grid](https://www.hackerrank.com/challenges/connected-cell-in-a-grid) 
```java
class Result {
    private static int encode(int row, int col, int width) {
        return row * width + col;
    }
    
    private static int decodeRow(int code, int width) {
        return code / width;
    }
    
    private static int decodeCol(int code, int width) {
        return code % width;
    }
    
    private static int[][] value;
    private static boolean[][] visit;
    private static Queue<Integer> q = new LinkedList<>();
    private static int[] dx = new int[] {-1,  0, 0, 1, -1, -1, 1,  1};
    private static int[] dy = new int[] { 0, -1, 1, 0,  1, -1, 1, -1};
    private static int BFS(int start, int height, int width) {
        
        int size = height * width;
        
        
        q.add(start);
        int ans = 0;
        while (!q.isEmpty()) {
            
            int index = q.poll();
            int row = decodeRow(index, width);
            int col = decodeCol(index, width);
            
            if (visit[row][col]) {
                continue;
            }
            ans++;
            visit[row][col] = true;
            
            for (int k = 0; k < dx.length; k++) {
                int nRow = row + dx[k];
                int nCol = col + dy[k];
                
                if (nRow < 0 || nRow >= height) {
                    continue;
                }
                
                if (nCol < 0 || nCol >= width) {
                    continue;
                }
                
                if (visit[nRow][nCol]) {
                    continue;
                }
                
                if (value[nRow][nCol] == 0) {
                    continue;
                }
                
                q.add(encode(nRow, nCol, width));
            }
            
        }
        
        return ans;
    }
    public static int connectedCell(List<List<Integer>> matrix) {
        
        int height = matrix.size();
        int width = matrix.get(0).size();
        visit = new boolean[height][width];
        value = new int[height][width];
        for (int row = 0; row < height; row++) {
            for (int col = 0; col < width; col++) {
                value[row][col] = matrix.get(row).get(col);
            } 
        }
        int ans = 0;
        for (int row = 0; row < height; row++) {
            for (int col = 0; col < width; col++) {
                if (value[row][col] == 0) {
                    continue;
                }
                
                if (visit[row][col]) {
                    continue;
                }
                int index = encode(row, col, width);
                ans = Math.max(ans, BFS(index, height, width));
            } 
        }
        return ans;   
    }
}
```

### Bài 2: [Breadth First Search: Shortest Reach](https://www.hackerrank.com/challenges/bfsshortreach) 
```java
class Result {
    public static List<Integer> bfs(int n, int m, List<List<Integer>> edges, int s) {
        Integer[] f = new Integer[n];
        List[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (List<Integer> p : edges) {
            int u = p.get(0) - 1;
            int v = p.get(1) - 1;
            adj[u].add(v);
            adj[v].add(u);
        }
        Arrays.fill(f, -1);
        f[s - 1] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(s - 1);
        boolean[] inqueue = new boolean[n];
        while (!q.isEmpty()) {
            int u = q.poll();
            inqueue[u] = false;

            for (Object object : adj[u]) {
                int v = (Integer) object;
                if (f[v] == -1 || f[v] > f[u] + 6) {
                    f[v] = f[u] + 6;
                    if (!inqueue[v]) {
                        inqueue[v] = true;
                        q.add(v);
                    }
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (f[i] != 0) {
                ans.add(f[i]);
            }
        }
        return ans;
    }
}
```

## 13. [BT13](https://docs.google.com/document/d/1OfgrTdhYsVXJMdyC9yCIWiBXZ6_-dYCuQYtSXSZPVlU/edit)

### Bài 1: Vẽ

[Page1](https://i.imgur.com/DLCHlXa.jpg)
[Page2](https://i.imgur.com/NID97YC.jpg)
[Page3](https://i.imgur.com/hLK4nzi.jpg)


### Bài 2: [Prim's (MST) : Special Subtree](https://www.hackerrank.com/challenges/primsmstsub/problem)
```java
class Cost implements Comparable<Cost> {
    int cost;
    int v;
    
    public Cost() {
        
    }
    
    public Cost(int cost, int v) {
        this.cost = cost;
        this.v = v;
    }
    
    @Override
        public int compareTo(Cost c) {
        if (cost < c.cost) return -1;
        if (cost > c.cost) return 1;
        if (v < c.v) return -1;
        if (v > c.v) return 1;
        return 0;
    }
}

class Result {
    static PriorityQueue<Cost> pq = new PriorityQueue<>();
    public static int prims(int n, List<List<Integer>> edges, int start) {
        int[] f = new int[n];
        Arrays.fill(f, -1);
        
        f[start - 1] = 0;
        int[][] weight = new int[n][n];
        for(int i = 0; i < n; i++) {
            Arrays.fill(weight[i], -1);    
        }
        
        for(List<Integer> p : edges) {
            int u = p.get(0) - 1;
            int v = p.get(1) - 1;
            int w = p.get(2);
            if (weight[u][v] == -1 || weight[u][v] > w) {
                weight[u][v] = w;
                weight[v][u] = w;   
            }
        }
        int ans = 0;
        pq.add(new Cost(0, start - 1));
        while (!pq.isEmpty()) {
            Cost cur = pq.poll();
            int u = cur.v;
            int cost = cur.cost;
            if (f[u] != cost) {
                continue;
            }
            ans += f[u];
            f[u] = 0;
            
            for (int v = 0; v < n; v++) {
                if (weight[u][v] == -1) {
                    continue;
                }
                if (f[v] == -1 || f[v] > weight[u][v]) {
                    f[v] = weight[u][v];
                    pq.add(new Cost(f[v], v));
                }
            }
        }
        
        return ans;
    }
}
```

### Bài 3: [Dijkstra: Shortest Reach 2](https://www.hackerrank.com/challenges/dijkstrashortreach/problem)
```java
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

class Cost implements Comparable<Cost> {
        int cost;
        int v;
        
        public Cost() {
            
        }
        
        public Cost(int cost, int v) {
            this.cost = cost;
            this.v = v;
        }
        
        @Override
        public int compareTo(Cost c) {
            return Integer.compare(cost, c.cost);
        }

}

class Result {    
    static PriorityQueue<Cost> pq = new PriorityQueue<>();
    static List<Cost>[] adj;
    public static List<Integer> shortestReach(int n, int s) {
        int[] f = new int[n];
        Arrays.fill(f, -1);
        
        f[s - 1] = 0;

        pq.clear();
        
        for (int i = 0; i < n; i++) {
            Collections.sort(adj[i]);
        }
            
        pq.add(new Cost(0, s - 1));
        while (!pq.isEmpty()) {
            Cost cur = pq.poll();
            int u = cur.v;
            int cost = cur.cost;
            
            if (f[u] != cost) {
                continue;
            }
            
            for (Cost c : adj[u]) {
                int v = c.v;
                int w = c.cost;
                if (f[v] == -1 || f[v] > w + f[u]) {
                    f[v] = w + f[u];
                    pq.add(new Cost(f[v], v));
                    
                }
            }
        }
        
        List<Integer> ans = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (i + 1 != s) {
                ans.add(f[i]);
            }
        }
        return ans;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        int t = Integer.parseInt(st.nextToken());

        for (int tItr = 0; tItr < t; tItr++) {
            st = new StringTokenizer(bufferedReader.readLine());

            int n = Integer.parseInt(st.nextToken());

            int m = Integer.parseInt(st.nextToken());

            Result.adj = new List[n]; 
            for(int i = 0; i < n; i++) { 
                Result.adj[i] = new ArrayList<>();
            }

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(bufferedReader.readLine());
                int u = Integer.parseInt(st.nextToken()) - 1;
                int v = Integer.parseInt(st.nextToken()) - 1;
                int w = Integer.parseInt(st.nextToken());
                Result.adj[u].add(new Cost(w, v));
                Result.adj[v].add(new Cost(w, u));
            }

            int s = Integer.parseInt(bufferedReader.readLine().trim());

            List<Integer> result = Result.shortestReach(n, s);

            for (int i = 0; i < result.size(); i++) {
                bufferedWriter.write(String.valueOf(result.get(i)));

                if (i != result.size() - 1) {
                    bufferedWriter.write(" ");
                }
            }

            bufferedWriter.newLine();
        }

        bufferedReader.close();
        bufferedWriter.close();
    }
}
```

### Bài 4: [Kruskal (MST): Really Special Subtree](https://www.hackerrank.com/challenges/kruskalmstrsub/problem)
```java
class Edge implements Comparable<Edge>{
    public int u, v, w;
    public Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(w, other.w);
    }
    
}
class Result {
    static int root(int u, int[] par) {
        return (par[u] < 0) ? u : (par[u] = root(par[u], par));
    }
    
    static boolean merge(int u, int v, int[] par) {
        if ((u = root(u, par)) == (v = root(v, par))) {
            return false;
        }
        
        if (par[u] > par[v]) {
            int temp = u;
            u = v;
            v = temp;
        }
        
        par[u] += par[v];
        par[v] = u;
        
        return true;
    }
    public static int kruskals(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) {
        List<Edge> edges = new ArrayList<>();
        
        for (int i = 0; i < gFrom.size(); i++) {
            int u = gFrom.get(i);
            int v = gTo.get(i);
            int w = gWeight.get(i);
            edges.add(new Edge(u, v, w));
        }
        
        Collections.sort(edges);
        int[] par = new int[gNodes + 1];
        Arrays.fill(par, -1);
        int ans = 0;
        for (int i = 0; i < edges.size(); i++) {
            int u = edges.get(i).u;
            int v = edges.get(i).v;
            int w = edges.get(i).w;
            
            if (merge(u, v, par)) {
                ans += w;
            }
        }
        return ans;
    }
}
```