My Notes some of this and some of that

Array Subset of another array

Problem Statement: Given two arrays: arr1[0..m-1] of size m and arr2[0..n-1] of size n. Task is to check whether arr2[] is a subset of arr1[] or not. Both the arrays can be both unsorted or sorted. It may be assumed that elements in both array are distinct.

Reference URL: Array Subset

Example:

Input: arr1: 11 1 13 21 3 7 arr2: 11 3 7 1 Output: Yes

Input: arr1: 10 5 2 23 19 arr2: 19 5 3 Output: No

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

Remove Duplicate Characters

Problem Statement: Given a string, remove duplicates from it. Note that original order of characters must be kept same. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string.

Reference URL: Remove Duplicates

Example:

Input: “geeksforgeeks” Output: “geksfor”

Input: “geeks for geeks” Output: “geks for”

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

Longest Common Substring

Problem Statement: Given two strings X and Y, find the length of the longest common substring.

Reference URL: Longest Common Substring

Examples:

Input : X = “GeeksforGeeks”, Y = “GeeksQuiz”

Output : 5 The longest common substring is “Geeks” and is of length 5.

Input : X = “abcdxyz”, y = “xyzabcd”

Output : 4 The longest common substring is “abcd” and is of length 4.


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

}

Java Concurrency - CountDownLatch

  • CountDownLatch is a very interesting class from java concurrent package. It allows one thread to wait for one or more threads to complete before it starts processing.

  • This can be super useful on java server side. The usage is pretty simple. You can initialize CountDownLatch with initial count and then decrement it in threads using countDown(). This will decrement the count by 1. Finally you can use await() in the thread which needs to await other threads processing before it starts its processing. It will wait until count becomes 0.

  • Below is the example of CountDownLatch. We have initialized the count at 3 and decrement the count in 3 other threads. The main thread will wait for all 3 threads to complete before it starts processing.

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

Output:

Validation Service is up!
Cache Service is up!
Naming Service is up!
All services are up!

Code highlighting in Jekyll blog using highlight.js

Adding code block in Jekyll blog should be easy. And though highlighting in markdown using back-ticks ``` worked but it didnt work as well as it should. The formatted java code was getting messed up as the lines were getting wrapped. I needed well formatted code with scrolling which should be easy to read.

This is where highlight.js came to rescue. There were other options and hacks but this was the clear winner because it was easy to integrate, supported many languages and comes with color themes.

  • Only 1 step is needed. Add highlight js and css of the color scheme you want in the header page. Either you can add cdn url as shown below or copy it in your project and give local path. This will find and all highlight the code inside of <pre><code> tags
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.11.0/styles/default.min.css">
<script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.11.0/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
  • highlight.js provide many color schemes and all you have to do is choose the right css and refer its path.

  • here is the list of cdn links of all color schemes

  • here is github link of all color schemes

  • here is the demo for all supported languages and schemes