import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence/0
//Description: Given an array of integers, find the length of the longest sub-sequence
//such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

public class LongestConsecutiveSubSequence {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int testCases = scanner.nextInt();
        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(getLengthOfLongestConsecutiveSubSequence(arr));
        }
    }

    //Logic: is to add all array elements to map
    //Then iterate array, and for any element, increment by 1 and find in map, decrement by 1 and find in map
    //increment counter if found, and remove entry from hashmap if found
    //keep track of max count and return once all elements are iterated
    public static int getLengthOfLongestConsecutiveSubSequence(int[] arr) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int count = 0, maxCount = 0, key = 0;

        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], 1);
        }

        for (int i = 0; i < arr.length; i++) {
            key = arr[i];
            count = 1;
            map.remove(key);

            //keep on adding 1 to key and incrementing counter if found
            while (true) {
                ++key;
                if (map.containsKey(key)) {
                    count++;
                    map.remove(key);
                } else {
                    break;
                }
            }

            key = arr[i];
            //keep on subtracting 1 from key and incrementing counter if found
            while (true) {
                --key;
                if (map.containsKey(key)) {
                    count++;
                    map.remove(key);
                } else {
                    break;
                }
            }

            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/array-subset-of-another-array/0
//Description: Given 2 array, check whether arr2[] is a subset of arr1[] or not
public class ArraySubset {

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

        for (int i = 0; i < testCases; i++) {
            int arr1Length = scanner.nextInt();
            int arr2Length = scanner.nextInt();

            int[] arr1 = new int[arr1Length];
            int[] arr2 = new int[arr2Length];

            for (int j = 0; j < arr1Length; j++) {
                arr1[j] = scanner.nextInt();
            }
            for (int j = 0; j < arr2Length; j++) {
                arr2[j] = scanner.nextInt();
            }

            System.out.println(isSubset(arr1, arr2));
        }
    }

    //Logic: put first array arr1 in map. Then iterate arr2 and for each element check if it is present in map.
    //if even a single element is not present then return No, else Yes
    public static String isSubset(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr1.length; i++) {
            map.put(arr1[i], 1);
        }

        for (int i = 0; i < arr2.length; i++) {
            if (!map.containsKey(arr2[i])) {
                return "No";
            }
        }

        return "Yes";
    }
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/remove-duplicates/0
//Description: Given a string, remove duplicates from it.
public class RemoveDuplicateCharacters {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int testCases = scanner.nextInt();
        scanner.nextLine();

        for (int i = 0; i < testCases; i++) {
            System.out.println(removeDuplicates(scanner.nextLine()));
        }
    }

    //Logic: uses hashing or hashmap to find if character is repeating.
    //instead of hashmap, any array of size 256 can also be used
    public static String removeDuplicates(String str) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();

        char[] chars = str.toCharArray();
        int length = chars.length;

        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < length; i++) {
            if (!map.containsKey(chars[i])) {
                builder.append(chars[i]);
                map.put(chars[i], 1);
            }
        }

        return builder.toString();
    }
}

import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/longest-common-substring/0
//Description: Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

public class LongestCommonSubstring {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int len1 = scanner.nextInt();
            int len2 = scanner.nextInt();

            String str1 = scanner.next();
            String str2 = scanner.next();

            System.out.println(getLongestCommonSubstringLength(str1, str2));
        }

    }

    //Logic: Length of the common string can maximum be length of the shortest string among two strings.
    //So, first find shortest among 2 strings. Start with finding the shorter string in the longer string and if not found then find the longest substring (all) of the shorter string in the longer string. Repeat this until all substrings are covered.
    public static int getLongestCommonSubstringLength(String str1, String str2) {
        int length1 = str1.length();
        int length2 = str2.length();

        String shortString = length1 > length2 ? str2 : str1;
        String longString = length1 > length2 ? str1 : str2;

        int shortStringLength = shortString.length();
        int maxLength = shortStringLength;

        while (maxLength > 0) {

            for (int i = 0; i + maxLength - 1 < shortStringLength; i++) {
                if (longString.contains(shortString.substring(i, i + maxLength))) {
                    System.out.println(shortString.substring(i, i + maxLength));
                    return maxLength;
                }
            }

            maxLength--;
        }

        return 0;
    }

}

import java.util.concurrent.CountDownLatch;

public class TestCountDownLatch {

    public static void main(String[] args) {
        CountDownLatch latch = new CountDownLatch(3);
        Thread cacheService = new Thread(new Service(latch), "Cache Service");
        Thread namingService = new Thread(new Service(latch), "Naming Service");
        Thread validationService = new Thread(new Service(latch), "Validation Service");

        cacheService.start();
        namingService.start();
        validationService.start();

        try {
            latch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("All services are up!");
    }
}

class Service implements Runnable {

    private CountDownLatch latch;

    public Service(CountDownLatch latch) {
        this.latch = latch;
    }

    @Override
    public void run() {
        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println(Thread.currentThread().getName() + " is up!");
        latch.countDown();
    }
}