---
# DSA - Phạm Thị Diễm Quỳnh - 21020087
## [BT2](https://www.hackerrank.com/domains/java?filters%5Bsubdomains%5D%5B%5D=java-introduction)
### 1. [Welcome to Java!](https://www.hackerrank.com/challenges/welcome-to-java/problem?isFullScreen=true)

public class Solution {

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

### 2. [ Java Stdin and Stdout I](https://www.hackerrank.com/challenges/java-stdin-and-stdout-1/problem?isFullScreen=true)

import java.util.*;

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);
    }
}

### 3. [Java If-Else](https://www.hackerrank.com/challenges/java-if-else/problem?isFullScreen=true)

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 == 1 || (N % 2 == 0 && 6 <= N && N <= 20)) 
        {
            System.out.print("Weird");
        }
        else 
             System.out.print("Not Weird");
        scanner.close();
    }
}

### 4. [Java Stdin and Stdout II](https://www.hackerrank.com/challenges/java-stdin-stdout/problem?isFullScreen=true)

import java.util.Scanner;

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();
        
        System.out.println("String: " + s);
        System.out.println("Double: " + d);
        System.out.println("Int: " + i);
    }
}

### 5. [Java Output Formatting](https://www.hackerrank.com/challenges/java-output-formatting/problem?isFullScreen=true)

import java.util.Scanner;

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();
                while(s1.length() < 15) s1 += ' ';
                int x = sc.nextInt();
                String s2 = new String(); 
                while(x > 0)
                {
                    s2 = x % 10 + s2;
                    x = x / 10;
                }
                while(s2.length() < 3) s2 = '0' + s2;
                System.out.printf(s1);
                System.out.println(s2);
            }
            System.out.println("================================");

    }
}

### 6. [Java Loops I](https://www.hackerrank.com/challenges/java-loops-i/problem?isFullScreen=true)

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)
        {
            String ans = new String();
            
            ans = N + " x " + i;
            ans += " = ";
            ans += N * i;
            System.out.println(ans);
        }
        bufferedReader.close();
    }
}

### 7. [Java Loops II](https://www.hackerrank.com/challenges/java-loops/problem?isFullScreen=true)

import java.util.*;
import java.io.*;

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 cur = a;
            int cur2 = 1;
            for(int j = 0; j < n; ++j)
            {
                cur += cur2 * b;
                cur2 *= 2;
                System.out.print(cur);
                System.out.printf(" ");
            }
            System.out.println();
        }
        in.close();
    }
}

### 8. [Java Datatypes](https://www.hackerrank.com/challenges/java-datatypes/problem?isFullScreen=true)

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 >= -(1 << 15) && x <= (1 << 15) - 1) System.out.println("* short");
                if(x >= -(1 << 31) && x <= (1 << 31) - 1) System.out.println("* int");
                if(x >= -(1L << 63) && x <= (1L << 63) - 1) System.out.println("* long");
            }
            catch(Exception e)
            {
                System.out.println(sc.next()+" can't be fitted anywhere.");
            }

        }
    }
}

### 9. [Java End-of-file](https://www.hackerrank.com/challenges/java-end-of-file/problem?isFullScreen=true)

public class Solution {

    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int id = 0;
       while(sc.hasNext())
       {
           ++id;
           System.out.println(id + " " + sc.nextLine());
       }
    }
}

### 10. [Java Static Initializer Block](https://www.hackerrank.com/challenges/java-static-initializer-block/problem?isFullScreen=true)

public class Solution {
static Scanner scan = new Scanner(System.in);
static int B;
static int H;
static boolean flag;

static{
B = scan.nextInt();
H = scan.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);
}
}

public static void main(String[] args){
		if(flag){
			int area=B*H;
			System.out.print(area);
		}
		
	}//end of main

}//end of class

### 11. [Java Int to String](https://www.hackerrank.com/challenges/java-int-to-string/problem?isFullScreen=true)

import java.util.*;
import java.security.*;
public class Solution {
 public static void main(String[] args) {

  DoNotTerminate.forbidExit();

  try {
   Scanner in = new Scanner(System.in);
   int n = in .nextInt();
   in.close();
   //String s=???; Complete this line below
   String s = Integer.toString(n);

   
   if (n == Integer.parseInt(s)) {
    System.out.println("Good job");
   } else {
    System.out.println("Wrong answer.");
   }
  } catch (DoNotTerminate.ExitTrappedException e) {
   System.out.println("Unsuccessful Termination!!");
  }
 }
}

//The following class will prevent you from terminating the code using exit(0)!
class DoNotTerminate {

 public static class ExitTrappedException extends SecurityException {

  private static final long serialVersionUID = 1;
 }

 public static void forbidExit() {
  final SecurityManager securityManager = new SecurityManager() {
   @Override
   public void checkPermission(Permission permission) {
    if (permission.getName().contains("exitVM")) {
     throw new ExitTrappedException();
    }
   }
  };
  System.setSecurityManager(securityManager);
 }
}

### 12. [Java Date and Tim](https://www.hackerrank.com/challenges/java-date-and-time/problem?isFullScreen=true)

class Result {
    public static String findDay(int month, int day, int year) {
       Calendar calendar = new GregorianCalendar(year, month-1, day);
       return calendar.getDisplayName(calendar.DAY_OF_WEEK, calendar.LONG, Locale.US).toUpperCase();
    }

}

### 13. [Java Currency Formatter](https://www.hackerrank.com/challenges/java-currency-formatter/problem?isFullScreen=true&h_r=next-challenge&h_v=zen)

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.
        String us = NumberFormat.getCurrencyInstance(Locale.US).format(payment);
        String india = NumberFormat.getCurrencyInstance(new Locale ("en", "IN")).format(payment);
        String china = NumberFormat.getCurrencyInstance(Locale.CHINA).format(payment);
        String france = NumberFormat.getCurrencyInstance(Locale.FRANCE).format(payment);
        
        System.out.println("US: " + us);
        System.out.println("India: " + india);
        System.out.println("China: " + china);
        System.out.println("France: " + france);
    }
}

## [BT3](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=warmup)
### 1. [Solve Me First](https://www.hackerrank.com/challenges/solve-me-first/problem?isFullScreen=true)

public class Solution {
    static int solveMeFirst(int a, int b) {
        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);
	}
}

### 2. [Simple Array Sum](https://www.hackerrank.com/challenges/simple-array-sum/copy-from/289149402)

class Result {
    public static int simpleArraySum(List<Integer> ar) {
        int sum = 0;
        for (int i = 0; i < ar.size(); ++i) {
            sum += ar.get(i);
        }
        return sum;
    }
}

### 3. [Compare the Triplets](hackerrank.com/challenges/compare-the-triplets/problem?isFullScreen=true)

class Result {
    public static List<Integer> compareTriplets(List<Integer> a, List<Integer> b) {
        List <Integer> score = new ArrayList<Integer>();
        int alice = 0;
        int bob = 0;
            for (int i = 0; i < a.size(); i++) {
                if(a.get(i)>b.get(i)){
                    alice++;
                } else if(a.get(i)<b.get(i)){
                    bob++;
                } else {
                continue;
                }
            }
        score.add(alice);
        score.add(bob);
        return score;
    }

}

### 4. [A Very Big Sum](https://www.hackerrank.com/challenges/a-very-big-sum/problem?isFullScreen=true)

class Result {
    public static long aVeryBigSum(List<Long> ar) {
        long sum = 0;
        for (int  i = 0; i < ar.size(); ++i) {
            sum += ar.get(i);
        }
        return sum;
    }

}

### 5. [Diagonal Difference](https://www.hackerrank.com/challenges/diagonal-difference/problem?isFullScreen=true)

class Result {
    public static int diagonalDifference(List<List<Integer>> arr) {
    int len = arr.size();
    int left =0;
    int right =0;
    int j = 0, k = len - 1;
    for (int i = 0; i < len; i++) {
        left += arr.get(i).get(j);
        right += arr.get(i).get(k);
        j++;
        k--;
    }
    return Math.abs(left - right);
    }
}

### 6. [Staircase](https://www.hackerrank.com/challenges/staircase/problem?isFullScreen=true)

class Result {
    public static void staircase(int n) {
    for (int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n - i; ++j) {
            System.out.print(' ');
        }
        for(int j = 1; j <= i; ++j) {
            System.out.print('#');
        }
        System.out.println();
    }
}

### 7. [Plus Minus](https://www.hackerrank.com/challenges/plus-minus/problem?isFullScreen=true)

class Result {
   public static void plusMinus(List<Integer> arr) {
    double count = 0;
    double count1 = 0;
    double count2 = 0;
    for(int i=0; i < arr.size(); i++){
        if(arr.get(i) < 0){
            count++;
        }
        else if(arr.get(i) > 0){
            count1++;
        }
        else if(arr.get(i)==0){
             count2++;
        }
    }
    System.out.format("%.6f",count1 / arr.size());
    System.out.println();
    System.out.format("%.6f",count / arr.size());
    System.out.println();
    System.out.format("%.6f",count2 / arr.size());
    }
}

### 8. [Mini-Max Sum](https://www.hackerrank.com/challenges/mini-max-sum/problem?isFullScreen=true)

class Result {
    public static void miniMaxSum(List<Integer> arr) {
        long sum =0;
        
        for(Integer elemt : arr) sum += elemt;
        
        long min = sum, max = 0;
        
        for(Integer elemt : arr){
            max = Math.max(max,sum-elemt);
            min = Math.min(min,sum-elemt);
        }
        
        System.out.print(min+" "+max);
    }

}

### 9. [Birthday Cake Candles](https://www.hackerrank.com/challenges/birthday-cake-candles/problem?isFullScreen=true)

class Result {
    public static int birthdayCakeCandles(List<Integer> candles) {
        Integer[] arr = candles.toArray(new Integer[candles.size()]);
        // find highest
        int high = 0;
        int highCounts = 0;
    
        for(int i = 0; i < arr.length ; i++) {
            if(arr[i] > high)
                high = arr[i];    
        }
    
        for(int a : arr) {
            if(a == high)
                highCounts++;  
        }
        return highCounts;
    }

}

### 10. [Time Conversion](https://www.hackerrank.com/challenges/time-conversion/problem?isFullScreen=true)

class Result {
    public static String timeConversion(String s) {
        Integer hora = Integer.parseInt(s.substring(0,2));

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

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

## [BT4](https://docs.google.com/document/d/1RgwRO_6J3RXtw3Zj4mIfEAJ3Q2HorNfQ3qx6_ge5tgs/edit)
### 2. [Arrays - DS](https://www.hackerrank.com/challenges/arrays-ds/problem)

class Result {
    public static List<Integer> reverseArray(List<Integer> a) {
        List<Integer> newArr = new ArrayList<>();
        for (Integer val : a) {
            newArr.add(0, val);
        }
        return newArr;
    }

}

### 3. [2D Array - DS](https://www.hackerrank.com/challenges/2d-array/problem)

class Result {
    public static int hourglassSum(List<List<Integer>> arr) {
        int top1, top2, top3, center, bottom1, bottom2, bottom3, sum = -63; //(7*-9=-63): min value
         for(int i = 0; i < arr.size()-2; ++i)
         {
             for(int j = 0; j < arr.get(i).size()-2; ++j)
             {
                 top1 = arr.get(i).get(j);
                 top2 = arr.get(i).get(j+1);
                 top3 = arr.get(i).get(j+2);
                 center = arr.get(i+1).get(j+1);
                 bottom1 = arr.get(i+2).get(j);
                 bottom2 = arr.get(i+2).get(j+1);
                 bottom3 = arr.get(i+2).get(j+2);
                 int tempSum = sum;
                 sum = top1+top2+top3+center+bottom1+bottom2+bottom3;
                 if(tempSum > sum)
                 {
                     sum = tempSum;
                 }
             }
         }
         return sum;

    }

}

### 4. [Sherlock and Array](https://www.hackerrank.com/challenges/sherlock-and-array/problem)

class Result {
    public static String balancedSums(List<Integer> arr) {
        int leftSum = 0;
        int sum = 0;
        // find the sum of all list elements
        for (Integer i : arr) {
            sum += i;
        }
        // equation is 2*leftSum = sum - j
        for (Integer j : arr) {
            if (2 * leftSum == sum - j) {
                return "YES";
            }
         leftSum += j;
        }
        return "NO";
    }

}

### 5. [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers/problem)

class Result {
    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;     
    }

}

### 6. [Pairs](https://www.hackerrank.com/challenges/pairs/problem)

class Result {
    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;
    }

}

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

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));
    }
}

## [Bài tập Linked List](https://docs.google.com/document/d/1uDeCCEFVt2tHRsqInU5MSh-YTb-cpNRWTuKBMhbYrdE/edit)
### 1. [Print the Elements of a Linked List](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list/problem)

    static void printLinkedList(SinglyLinkedListNode head) {
        SinglyLinkedListNode cur = head;
        while (head != null) {
            System.out.println(head.data);
            head = head.next;
        }
    }

### 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)

    static SinglyLinkedListNode insertNodeAtTail(SinglyLinkedListNode head, int data) {
        SinglyLinkedListNode node = new SinglyLinkedListNode(data);
        if (head == null) {
            head = node;
        }
        else {
            SinglyLinkedListNode temp = head;
            while(temp.next != null) {
            temp = temp.next;
            }
            temp.next = node;
        }
        return head;
    }

### 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)

    static SinglyLinkedListNode insertNodeAtHead(SinglyLinkedListNode llist, int data) {
        SinglyLinkedListNode newNode = new SinglyLinkedListNode(data);
        newNode.next = llist;
        llist = newNode;
        return llist;
    }

### 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)

    public static SinglyLinkedListNode insertNodeAtPosition(SinglyLinkedListNode llist, int data, int position) {
       SinglyLinkedListNode node = new SinglyLinkedListNode(data);
        SinglyLinkedListNode tmp = llist;
        if(position == 0) {
            node.next = llist;
            llist = node;
        }
        else {
            for (int i = 0; i < position - 1; i++) {
                tmp = tmp.next;
            }
            node.next = tmp.next;
            tmp.next = node;
        }

        return llist;
    }

### 5. [Delete a Node](https://www.hackerrank.com/challenges/delete-a-node-from-a-linked-list/problem)

    public static SinglyLinkedListNode deleteNode(SinglyLinkedListNode llist, int position) {
    if (llist == null) return llist;
    if(position == 0) return llist.next;
    SinglyLinkedListNode tmp = llist;
    for (int i = 1; i < position; ++i) {
        tmp = tmp.next;
    }
    SinglyLinkedListNode anotherTmp = tmp.next;
    anotherTmp = anotherTmp.next;
    tmp.next = anotherTmp;
    return llist;
    }

### 6. [Print in Reverse](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list-in-reverse/problem)

    public static void reversePrint(SinglyLinkedListNode llist) {
        int[] ans = new int[1000];
        int id = 0;
        while(llist != null) {
            ans[id++] = llist.data;
            llist = llist.next;
        }
        for (int i = id - 1; i >= 0; --i) {
            System.out.println(ans[i]);
        }
    }

### 7. [Reverse a linked list](https://www.hackerrank.com/challenges/reverse-a-linked-list/problem)

    public static SinglyLinkedListNode reverse(SinglyLinkedListNode llist) {
        int[] ans = new int[1000];
        if (llist == null) {
            return llist;
        }
        int id = 0;
        while(llist != null) {
            ans[id++] = llist.data;
            llist = llist.next;
        }
        SinglyLinkedListNode ret = new SinglyLinkedListNode(ans[id - 1]);
        SinglyLinkedListNode head = ret;
        for (int i = id - 2; i >= 0; --i) {
            ret.next = new SinglyLinkedListNode(ans[i]);
            ret = ret.next;
        }
        return head;
    }

### 8. [Compare two linked lists](https://www.hackerrank.com/challenges/compare-two-linked-lists/problem)

    static boolean compareLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        boolean ans = true;
        while (head1 != null && head2 != null) {
            if (head1.data != head2.data) {
                    ans = false;
                    break;
                }
            head1 = head1.next;
            head2 = head2.next;
        }
        if(head1 != null || head2 != null) {
            ans = false;
        }
        return ans;
    }

### 9. [Merge two sorted linked lists](hackerrank.com/challenges/merge-two-sorted-linked-lists/problem)

    static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        SinglyLinkedList llist3 = new SinglyLinkedList();
        SinglyLinkedListNode tempA = head1;
        SinglyLinkedListNode tempB = head2;

        while(tempA != null && tempB != null) {
            if(tempA.data < tempB.data){
                llist3.insertNode(tempA.data);
                tempA = tempA.next;
            }
            else {
                llist3.insertNode(tempB.data);
                tempB = tempB.next;
            }
         }
         if(tempA != null) {
             while(tempA != null) {
                llist3.insertNode(tempA.data);
                tempA = tempA.next;
            }
        }
        if(tempB != null) {
            while(tempB != null) {
                llist3.insertNode(tempB.data);
                tempB = tempB.next;
            }
        }
        return llist3.head;
    }

### 10. [Get Node Value](https://www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem)

public static int getNode(SinglyLinkedListNode llist, int positionFromTail) {
    SinglyLinkedListNode tmp = llist;
    int sizeofList = 0;
    while(tmp.next != null) {
            tmp = tmp.next;
            sizeofList++;
            }
    int pos = sizeofList - positionFromTail;
    
    while (llist != null && pos != 0)  {
        llist = llist.next;
        pos--;
    }
    return llist.data;
}

## [BT5](https://docs.google.com/document/d/1L6IC7R0TYiSZOYG2wXhCMah4WD4VSnSLdfLf1ilcvfs/edit)
### 2. [Java List](https://www.hackerrank.com/challenges/java-list/problem)

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        
        int len = scanner.nextInt();
        
        for (int i = 0; i < len; i++) {
            list.add(scanner.nextInt());
        }

        int num = scanner.nextInt();
        
        for (int i = 0; i < num; i++) {
            String op = scanner.next().toLowerCase();
            if (op.equals("insert")){
                list.add(scanner.nextInt(), scanner.nextInt());
            } 
            if (op.equals("delete")){
                list.remove(scanner.nextInt());
            }
        }
        
        scanner.close();
        for (int i = 0; i < list.size(); ++i) {
            System.out.print(list.get(i) + " ");
        }
    }
}

### 3. [Java Arraylist](https://www.hackerrank.com/challenges/java-arraylist/problem)

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();

        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> line = new ArrayList<Integer>();
            int d = scanner.nextInt();
            for (int j = 0; j < d; j++) {
            line.add(scanner.nextInt());
            }
            arr.add(line);
        }

        int q = scanner.nextInt();
        for (int i = 0; i < q; i++) {
            try {
                System.out.println(arr.get(scanner.nextInt() - 1).get(scanner.nextInt() - 1));
            } catch(Exception e) {
                System.out.println("ERROR!");
            }
        }
        scanner.close();
    }
}

### 4. [Balanced Brackets](https://www.hackerrank.com/challenges/balanced-brackets/problem)

class Result {
public static String closingPair(String bracket) {
        switch (bracket) {            
            case "}":
                return "{";
                                
            case "]":
                return "[";
                                
            case ")":
                return "(";
        }
        
        return "";
    }

    public static String isBalanced(String s) {      
        Stack<String> stack = new Stack<String>();
        for(int i = 0; i < s.length(); i++) {
            String chrString = Character.toString(s.charAt(i));
            if(!stack.isEmpty()) {
                String peekedString = stack.peek();
                if(peekedString.equalsIgnoreCase(closingPair(chrString))) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(chrString);
        }
        
        return stack.isEmpty() ? "YES" : "NO";
    }
}

### 5. [Equal Stacks](https://www.hackerrank.com/challenges/equal-stacks/problem)

class Result {
   public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
       int size1 = h1.size();
       int size2 = h2.size();
       int size3 = h3.size();
       int sum1 = 0, sum2 = 0, sum3 = 0;
       int count1 = 0, count2 = 0, count3 = 0;
       for (int i = 0; i < size1; i++) {
            sum1 = sum1 + h1.get(i);
            }
        for (int i = 0; i < size2; i++) {
            sum2 = sum2 + h2.get(i);
        }
        for (int i = 0; i < size3; i++) {
            sum3= sum3 + h3.get(i);
        }
        if (sum1 == sum2 && sum2 == sum3) {
            return sum1;
        }
        while(!(sum1 == sum2 && sum2 == sum3)) {
            if(sum1 >= sum2 && sum1 >= sum3) {
                sum1 = sum1 - h1.get(count1);
                count1++;
            } else if (sum2 >= sum1 && sum2 >= sum3) {
                sum2 = sum2 - h2.get(count2);
                count2++;
                } else {
                    sum3 = sum3 - h3.get(count3);
                    count3++;
                }
        }
        if(size1 == 0 || size2 == 0 || size3 == 0) {
            return 0;
        } else {
            return sum2;
        }
   }
}

### 6. [Simple Text Editor](https://www.hackerrank.com/challenges/simple-text-editor/problem)

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int ops = Integer.parseInt(br.readLine());
        Stack<StringBuilder> st = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ops; i++) {
            String z[] = br.readLine().split(" "); 
            if(z[0].equals("1")) {
                st.add(new StringBuilder(sb.toString()));
                sb.append(z[1]);
            }
            if(z[0].equals("2")) {
                st.add(new StringBuilder(sb.toString()));
                sb.delete(sb.length() - Integer.parseInt(z[1]), sb.length());
            }
            if(z[0].equals("3")) {
                System.out.println(sb.charAt(Integer.parseInt(z[1]) - 1));
            }
            if(z[0].equals("4")) {
                sb = st.pop();
            }
        }
    }
}

### 7. [Queue Using Two Stacks](https://www.hackerrank.com/challenges/queue-using-two-stacks/problem)

import java.util.*;

public class Solution {
    
    private static class StackQueue<T> {
        
        private Stack<T> stack = new Stack<>(), auxStack = new Stack<>();
        
        void enqueue(T elem) {
            stack.push(elem);
        }
        
        T dequeue() {
            if (auxStack.isEmpty()) {
                if (stack.isEmpty()) {
                    System.out.println("Queue underflow");
                    return null;
                }
                while (!stack.isEmpty()) {
                    auxStack.push(stack.pop());
                }
            }
            return auxStack.pop();
        }
        
        T peek() {
            if (auxStack.isEmpty()) {
                if (stack.isEmpty()) {
                    System.out.println("Queue underflow");
                    return null;
                }
                while (!stack.isEmpty()) {
                    auxStack.push(stack.pop());
                }
            }
            return auxStack.peek();
        }
        
    }
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        scan.nextLine();    // Gets rid of the newline char
        List<String> queries = new ArrayList<>(q);
        
        // Query gathering
        for (int i = 0; i < q; i++) {
            queries.add(scan.nextLine());
        }
        scan.close();
        
        // Query handling
        int type, val;
        StackQueue<Integer> queue = new StackQueue<>();
        
        for (String query : queries) {
            type = query.charAt(0);
            if (type == '1') {
                val = Integer.parseInt(query.substring(2));
                queue.enqueue(val);
            }
            else if (type == '2') {
                queue.dequeue();
            }
            else {
                System.out.println(queue.peek());
            }
        }
    }
}

## [BT6](https://docs.google.com/document/d/1dkLn_S_Wd8qCnB_aoQHVef9Yciy1cdRXvIvRRHJuIQY/edit)
### 2. [Intro to Tutorial Challenges](https://www.hackerrank.com/challenges/tutorial-intro/problem)

class Result {
    public static int introTutorial(int V, List<Integer> arr) {
    // Write your code here
        int result = 0;
        int l = 0;
        int r = arr.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr.get(mid) == V) {
                return mid;
            }
            if (arr.get(mid) < V) {
                l = mid + 1;
                result = mid;
            } else {
                r = mid - 1;
                result = mid;
            }
        }

        return result;
    }

}

### 3. [Insertion Sort - Part 1](https://www.hackerrank.com/challenges/insertionsort1/problem)

class Result {
    public static void print(List<Integer> arr){
        for(int x: arr){
            System.out.print(x+" ");
        }
        System.out.println();
    }
    
    public static void insertionSort1(int n, List<Integer> arr) {
        int key = arr.get(arr.size() - 1);
        int j = arr.size() - 2;
        
        while(j >= 0 && arr.get(j) > key){
            arr.set(j + 1, arr.get(j));
            j--;
            print(arr);
        }
        
        arr.set(j + 1, key);
        print(arr);
    }

}

### 4. [Insertion Sort - Part 2](https://www.hackerrank.com/challenges/insertionsort2/problem)

class Result {

    public static void print(List<Integer> arr){
        for(int x: arr){
            System.out.print(x + " ");
        }
        System.out.println();
    }
    public static void insertionSort2(int n, List<Integer> arr) {
        for (int i = 1; i < arr.size(); i++) {
            int key = arr.get(i);
            int j = i - 1;
            
            while(j >= 0 && arr.get(j) > key) {
                arr.set(j + 1, arr.get(j));
                j--;
            }
            
            arr.set(j + 1, key);
            print(arr);
        }
    }
}

### 5. [Correctness Invariant](https://www.hackerrank.com/challenges/correctness-invariant/problem)

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];
                j = j - 1;
            }
            A[j + 1] = value;
        }

        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);
    }
}

### 6. [Counting Sort 1](https://www.hackerrank.com/challenges/countingsort1/problem)

class Result {
    public static List<Integer> countingSort(List<Integer> arr) {
        Integer[] answer = new Integer[100];
        Arrays.fill(answer, 0);
        for (int v: arr) {
            answer[v]++;
        }
        return Arrays.asList(answer);
    }

}

### 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 có nên lưu trong LinkedList (danh sách liên kết) không? Vì sao?

> Trả lời: 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.

## [BT7](https://docs.google.com/document/d/1KndwwmFgUGY6Smj7b1L75YPX0sB2hgbWRWmqdRh5kXQ/edit)
### 2. [Computing the GCD](https://www.hackerrank.com/challenges/functional-programming-warmups-in-recursion---gcd/problem)

public class Solution {
   
    public static int gcd(int A,int B){
        if(B == 0){
            return A;
        }
        return gcd(B, A % B);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        sc.close();
        System.out.println(gcd(A,B));      

    }
}

### 3. [Java Sort](https://www.hackerrank.com/challenges/java-sort/problem)

class Student{
    private int id;
    private String fname;
    private double cgpa;
    public Student(int id, String fname, double cgpa) {
        super();
        this.id = id;
        this.fname = fname;
        this.cgpa = cgpa;
    }
    public int getId() {
        return id;
    }
    public String getFname() {
        return fname;
    }
    public double getCgpa() {
        return cgpa;
    }
}

//Complete the code
public class Solution
{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int testCases = Integer.parseInt(in.nextLine());
        
        List<Student> studentList = new ArrayList<Student>();
        while(testCases>0){
            int id = in.nextInt();
            String fname = in.next();
            double cgpa = in.nextDouble();
            
            Student st = new Student(id, fname, cgpa);
            studentList.add(st);
            
            testCases--;
        }
        in.close();
        Comparator<Student> compare = (Student s1, Student s2)->{
            if (s1.getCgpa() == s2.getCgpa()) {
                return s1.getFname().compareTo(s2.getFname());
            } else {
                if(s1.getCgpa() - s2.getCgpa() < 0) {
                    return 1;
                } else {
                    return -1;
                }
            }
        };
        
        Collections.sort(studentList, compare);
          for(Student st: studentList){
            System.out.println(st.getFname());
        }
    }
}

### 4. [Quicksort 1 - Partition](https://www.hackerrank.com/challenges/quicksort1/problem)

class Result {

    public static List<Integer> quickSort(List<Integer> arr) {
        int pivot = arr.get(0);
        int low = 0; 
        int high = arr.size() - 1;
        while (low <= high) {
            while (low < arr.size() && arr.get(low) <= pivot) {
                ++low;
            }
            while (high >= 0 && arr.get(high) > pivot) {
                --high;
            }
            if (low <= high) {
                int tmp = arr.get(low);
                arr.set(low, arr.get(high));
                arr.set(high, tmp);
            }
        }
        arr.set(0, arr.get(high));
        arr.set(high, pivot);
        return arr;
    }

}

### 5. [Quicksort In-Place](https://www.hackerrank.com/challenges/quicksort3/problem)

import java.io.*; 
import java.util.*;

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])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        quickSort(arr, 0, arr.length-1);
        scanner.close();
    }

    static void quickSort(int[] arr, int low, int high) {

        if (low < high) {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }

}

    static int partition(int[] arr, int low, int high) {

        int pivot = arr[high];
        int j = low;
        for (int i = low; i < high; i++) {
            if (arr[i] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                j++;
            }
        }

        int temp = arr[j];
        arr[j] = arr[high];
        arr[high] = temp;

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        return j;
    }
}

### 6. [Find the Median](https://www.hackerrank.com/challenges/find-the-median/problem)

class Result {
    public static int findMedian(List<Integer> arr) {
        
        int index;
        int median = 0;
        Collections.sort(arr); 
        index = (arr.size() - 1) / 2;
        median = arr.get(index); 
        return median;
    }

}

## [BT8](https://docs.google.com/document/d/1UVgzgppsNKqBvgIuoZ0rryy9a7vwi8CnH_8osfYnDVk/edit)
### 2. [Java String Reverse](https://www.hackerrank.com/challenges/java-string-reverse/problem)

public class Solution {

    public static void main(String[] args) {
        String rev = "";
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        int length = A.length();

        for (int i = length - 1; i >= 0; i--)
            rev = rev + A.charAt(i);

        if (A.equals(rev))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

### 3. [Jesse and Cookies](https://www.hackerrank.com/challenges/jesse-and-cookies/problem)

class Result {
    public static int cookies(int k, List<Integer> A) {
        int count = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (Integer value: A) {
            pq.add(value);
        }
        
        if(pq.size() == 0 || pq.size() == 1)
            return -1;
        
        while (pq.size() > 1 && pq.peek() <= k) {
            count++;
            int temp = pq.poll() + (2 * pq.poll());
            pq.add(temp);
        }
        
        if(pq.size() < 2 &&  pq.peek() < k)
         return -1;
        
        return count;
    }

}

### 4. [Java Priority Queue](https://www.hackerrank.com/challenges/java-priority-queue/problem)

class Priorities {
    
    public List<Student> getStudents(List<String> events) {
        PriorityQueue<Student> q = new PriorityQueue<>();

        for (String event : events) {
            if (event.contains("ENTER")) {
                String[] student = event.split(" ");
                Student s = new Student(
                        student[1],
                        Double.parseDouble(student[2]),
                        Integer.parseInt(student[3]));
                q.add(s);
            }

            if (event.contains("SERVED")) {
                if (q.size() > 0) {
                    q.poll();
                }
            }
        }
        
        return q.stream().sorted().collect(Collectors.toList());
    }
}

class Student implements Comparable<Student>{
    
    private String name;
    private double cgpa;
    private int id;
    
    public Student(){}
    
    public Student(String name, double cgpa, int id) {
        this.id = id;
        this.name = name;
        this.cgpa = cgpa;
    }
    
    public int getId() {
        return this.id;
    }
    
    public String getName() {
        return this.name;
    }
    
    public double getCGPA() {
        return this.cgpa;
    }
    
    @Override
    public int compareTo(Student o) {
        if(this.cgpa == o.cgpa) {
            if(this.name.equals(o.name)) {
                return this.id - o.id;
            }else {
                return this.name.compareTo(o.name);
            }
        }else {
            return this.cgpa < o.cgpa ? 1 : -1;
        }
    }
    
}


public class Solution {
    private final static Scanner scan = new Scanner(System.in);
    private final static Priorities priorities = new Priorities();
    
    public static void main(String[] args) {
        int totalEvents = Integer.parseInt(scan.nextLine());    
        List<String> events = new ArrayList<>();
        
        while (totalEvents-- != 0) {
            String event = scan.nextLine();
            events.add(event);
        }
        
        List<Student> students = priorities.getStudents(events);
        
        if (students.isEmpty()) {
            System.out.println("EMPTY");
        } else {
            for (Student st: students) {
                System.out.println(st.getName());
            }
        }
    }
}

### 5. [Counting Sort 2](https://www.hackerrank.com/challenges/countingsort2/problem)

class Result {
    public static List<Integer> countingSort(List<Integer> arr) {
        int n = arr.size();
        
        int max = arr.get(0);
        for (int i = 1; i < n; i++)
            if(max < arr.get(i))
                max = arr.get(i);
        
        List<Integer> countSort = new ArrayList<Integer>();
        List<Integer> countingSort = Arrays.asList(new Integer[n]);
        
        for (int i = 0; i <= max; i++)
            countSort.add(0);
        
        for (int i = 0; i < n; i++)
            countSort.set(arr.get(i), countSort.get(arr.get(i)) + 1);
            
        for (int i = 1; i < countSort.size(); i++)
            countSort.set(i, countSort.get(i - 1) + countSort.get(i));
            
        for (int i = n - 1; i >= 0; i--) {
            countingSort.set(countSort.get(arr.get(i)) - 1, arr.get(i));
            countSort.set(arr.get(i), countSort.get(arr.get(i)) - 1);
        }

        return countingSort;
    }

}

### 6. [Find the Running Median](https://www.hackerrank.com/challenges/find-the-running-median/problem)

class Result {
    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;
    }
}

## [BT9](https://docs.google.com/document/d/1Hbt-7VW7wEVPQVrkawt9fvdcciIyIFTot7dfV19sIP4/edit)
### 2. [Java Map](https://www.hackerrank.com/challenges/phone-book/problem)

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");
            }
        }
    }
}

### 3. [Java HashSet](https://www.hackerrank.com/challenges/java-hashset/problem)

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());
}

### 4. [Tree: Inorder Traversal](https://www.hackerrank.com/challenges/tree-inorder-traversal/problem)

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);
    }
}

### 5. [Tree: Preorder Traversal](https://www.hackerrank.com/challenges/tree-preorder-traversal/problem)

    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);
        }
    }

### 6. [Tree: Level Order Traversal](https://www.hackerrank.com/challenges/tree-level-order-traversal/problem)

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);
        }
    }
}

### 7. [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers/problem)

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;
}

## [BT10](https://docs.google.com/document/d/1xHE6AQypBX5E16t6hjAJ4yxA5WGc9apgu1bholitmgI/edit)
### 2. [Tree: Height of a Binary Tree](https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem)

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;
}

### 3. [Binary Search Tree : Insertion](https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem)

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;
}

### 4. [Binary Search Tree : Lowest Common Ancestor](https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem)

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);

}

### 5. [Is This a Binary Search Tree?](https://www.hackerrank.com/challenges/is-binary-search-tree/problem)

    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;
    }

### 6. [Self Balancing Tree](https://www.hackerrank.com/challenges/self-balancing-tree/problem)

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;

}

## [BT11](https://docs.google.com/document/d/1j5jlpHyo9YmT8oX9WWHI3KNeeZdkogY7O6-U5Xv46lc/edit)
### 4. [Pairs](https://www.hackerrank.com/challenges/pairs/problem)

    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;
    }

### 5. [Mising Numbers](https://www.hackerrank.com/challenges/missing-numbers/problem)
a. Hash Map: $O(n\cdot log)$

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\cdot log)$

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)$

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;
}

### 6. [Find the Running Median](https://www.hackerrank.com/challenges/find-the-running-median/problem)

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;
    }

}

## [BT12](https://docs.google.com/document/d/1i9zGreLuArwE_oTD0GggaoBBgvT4M7PION6DgEGL9dI/edit)
### 1. [Connected Cells in a Grid](https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem)

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;
    }
    Prim's (MST) : Special Subtree
    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;   
    }
}

### 2. [Breadth First Search: Shortest Reach](https://www.hackerrank.com/challenges/bfsshortreach/problem)

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;
    }
}

## [BT13](https://docs.google.com/document/d/1i9zGreLuArwE_oTD0GggaoBBgvT)
### 2. [Prim's (MST) : Special Subtree](https://www.hackerrank.com/challenges/primsmstsub/problem)

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;
    }
}

### 3. [Dijkstra: Shortest Reach 2](https://www.hackerrank.com/challenges/dijkstrashortreach/problem)

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;
    }

}

### 4. [Kruskal (MST): Really Special Subtree](https://www.hackerrank.com/challenges/kruskalmstrsub/problem)

import java.util.*;

class DisjointSet {
    int[] lab;
    DisjointSet(int n) {
        lab = new int[n + 6];
        for (int i = 0; i <= n; ++i) {
            lab[i] = -1;
        }
    }
    
    int find(int x)
    {
        return lab[x] < 0 ? x : (lab[x] = find(lab[x]));
    }

    boolean join(int a, int b)
    {
        int x = find(a);
        int y = find(b);
        if (x == y)
            return false;
        if (lab[x] > lab[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        lab[x] += lab[y];
        lab[y] = x;
        return true;
    }
}
public class Solution {

    static void sortByColumn(int arr[][], int col) {  
        Arrays.sort(arr, new Comparator<int[]>() { 
          @Override               
          public int compare(final int[] entry1, final int[] entry2) { 
            if (entry1[col] > entry2[col]) 
                return 1; 
            else
                return -1; 
          } 
        });   
    } 

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

        int arr[][] = new int[m][3];

        for (int i = 0; i < m; i ++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int wt = sc.nextInt();
            arr[i][0] = u - 1;
            arr[i][1] = v - 1;
            arr[i][2] = wt;
        }

        sortByColumn(arr, 2);
        int totalWeight = 0;
        DisjointSet DSU = new DisjointSet(n);
        for (int i = 0; i < m; i++) {
            int u = arr[i][0];
            int v = arr[i][1];
            int wt = arr[i][2];
            if (DSU.join(u, v)) {
                totalWeight += wt;
            }
        }
        sc.close();
        System.out.println(totalWeight);
    }
}