My Notes some of this and some of that

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

Spring Rest API - Add Basic Authentication

This guide explains the steps needed to secure Spring REST APIs with basic authentication. Once done, the clients would need to send Base64 encoded credentials with each request, using HTTP [Authorization] header.

  • Add dependency in POM for spring security
<dependency>
  <groupId>org.springframework.security</groupId>
  <artifactId>spring-security-config</artifactId>
  <version>4.1.1.RELEASE</version>
</dependency>
<dependency>
  <groupId>org.springframework.security</groupId>
  <artifactId>spring-security-web</artifactId>
  <version>4.1.1.RELEASE</version>
</dependency>
  • Configure users with username, password and roles. Also define http urls which needs authentication along with the roles to whom urls would be accessible.
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.http.HttpMethod;
import org.springframework.security.config.annotation.authentication.builders.AuthenticationManagerBuilder;
import org.springframework.security.config.annotation.web.builders.HttpSecurity;
import org.springframework.security.config.annotation.web.builders.WebSecurity;
import org.springframework.security.config.annotation.web.configuration.EnableWebSecurity;
import org.springframework.security.config.annotation.web.configuration.WebSecurityConfigurerAdapter;
import org.springframework.security.config.http.SessionCreationPolicy;

@Configuration
@EnableWebSecurity
public class SecurityConfiguration extends WebSecurityConfigurerAdapter {

    public static String REALM = "REALM";

    @Autowired
    public void configureGlobalSecurity(AuthenticationManagerBuilder auth) throws Exception {
        auth.inMemoryAuthentication().withUser("abc").password("abc123").roles("USER");
        auth.inMemoryAuthentication().withUser("xyz").password("xyz123").roles("USER");
    }

    @Override
    protected void configure(HttpSecurity http) throws Exception {

        http.csrf().disable()
                .authorizeRequests()
                .antMatchers("/labels.json").hasRole("USER")
                .and().httpBasic().realmName(REALM).authenticationEntryPoint(getBasicAuthEntryPoint())
                .and().sessionManagement().sessionCreationPolicy(SessionCreationPolicy.STATELESS);
    }

    @Bean
    public CustomBasicAuthenticationEntryPoint getBasicAuthEntryPoint() {
        return new CustomBasicAuthenticationEntryPoint();
    }

    @Override
    public void configure(WebSecurity web) throws Exception {
        web.ignoring().antMatchers(HttpMethod.OPTIONS, "/**");
    }
}
  • Configure BasicAuthenticationEntryPoint to return response in case of invalid/missing credentials. Since its a REST API, it makes sense to return some response and not redirect user to any login page.
import org.springframework.security.core.AuthenticationException;
import org.springframework.security.web.authentication.www.BasicAuthenticationEntryPoint;

import javax.servlet.ServletException;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.io.IOException;
import java.io.PrintWriter;

import static SecurityConfiguration.REALM;

public class CustomBasicAuthenticationEntryPoint extends BasicAuthenticationEntryPoint {

    @Override
    public void commence(final HttpServletRequest request,
                         final HttpServletResponse response,
                         final AuthenticationException authException) throws IOException, ServletException {
        response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);
        response.addHeader("WWW-Authenticate", "Basic realm=" + getRealmName() + "");

        PrintWriter writer = response.getWriter();
        writer.println("HTTP Status 401 : " + authException.getMessage());
    }

    @Override
    public void afterPropertiesSet() throws Exception {
        setRealmName(REALM);
        super.afterPropertiesSet();
    }
}
  • Enable spring security in web.xml. This can also be done by just creating a new class extending AbstractSecurityWebApplicationInitializer but I have faced issues with jetty using java config so I prefer xml config.
<filter>
    <filter-name>springSecurityFilterChain</filter-name>
    <filter-class>org.springframework.web.filter.DelegatingFilterProxy
    </filter-class>
</filter>
<filter-mapping>
    <filter-name>springSecurityFilterChain</filter-name>
    <url-pattern>/*</url-pattern>
</filter-mapping>