Find longest non-repeating substring from a given string in Java

 

Approach

1. Traverse the string from position zero till end of length

2. maintain a hashmap of already visited characters

3. Maintain current substring with non-repeating characters with the help of a start and end index.

4. maintain the longest non-repeating substring in result variable

String getNonRepeatingSubstring(String input) { Map<Character, Integer> visited = new HashMap<>(); String result = ""; for (int start = 0, end = 0; end < input.length(); end++) { char currChar = input.charAt(end); if (visited.containsKey(currChar)) { start = Math.max(visited.get(currChar) + 1, start); } if (result.length() < end - start + 1) { result = input.substring(start, end + 1); } visited.put(currChar, end); } return result; }

Get distinct words from a given file in Java

 We will extract distinct words from a given file using Java.

Concepts

• Set data structure does not allow duplicate elements, so it can be used for filtering out duplicate words.

• Using regex we can split the given text file into words, Java provides StringTokenizer class that can help splitting each line of file.

• We need to close any input file so as to avoid file handle leaks inside Java program. try with resource takes care of automatically closing the underlying input stream once block of code is executed.

import java.io.*; import java.util.HashSet; import java.util.Set; import java.util.StringTokenizer; import java.util.logging.Level; import java.util.logging.Logger; public class DistinctWords { private static final Logger LOGGER = Logger.getLogger("DistinctWords"); public Set<String> getDistinctWords(String fileName) { Set<String> wordSet = new HashSet<>(); try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(fileName)))) { String line; while ((line = br.readLine()) != null) { StringTokenizer st = new StringTokenizer(line, " ,.;:\""); while (st.hasMoreTokens()) { wordSet.add(st.nextToken().toLowerCase()); } } } catch (IOException e) { LOGGER.log(Level.SEVERE, "IOException occurred", e); } return wordSet; } public static void main(String[] args) { DistinctWords distinctFileWords = new DistinctWords(); Set<String> wordList = distinctFileWords.getDistinctWords("<path-to-file>"); for (String str : wordList) { System.out.println(str); } } }

Create anagram buckets from a given input array of words

 Two strings are called anagrams if they contain same set of characters but in different order. For example,

• peek and keep are anagrams

• spar and rasp are anagrams

• listen and silent are anagrams

For more info:

https://en.wikipedia.org/wiki/Anagram

Here we get an input array of words that contains anagram string, and we need to create buckets for all the anagrams words.

Input:

{"akka", "akak", "baab", "baba", "bbaa"}

Output:

{
    [akka, akak],
    [baab, baba, bbaa]
}

Approach
Create a hashmap that will hold sorted word as the key and list of anagrams as the value. We will use this hashmap to store the results.
For each word in the input array, create a key by sorting the characters and put this word to that list whose key is the sorted word. for example [aakk → akka, akak] If it does not exist then create a new list with the sorted word as key in map.
In the end, traverse the values of hashmap and we get the desired result.

import java.util.*;

public class Anagrams {

    public static void main(String[] args) {
        String[] input = {"akka", "akak", "baab", "baba", "bbaa"};
        Map<String, List<String>> anagramsMap = anagramBuckets(input);
        System.out.println("anagramsMap = " + anagramsMap);
    }

    private static Map<String, List<String>> anagramBuckets(String[] input) {
        Map<String, List<String>> anagramsMap = new HashMap<>(100);
        for (String s : input) {
            char[] word = s.toCharArray();
            Arrays.sort(word);
            String key = String.valueOf(word);
            if (!anagramsMap.containsKey(key)) {
                anagramsMap.put(key, new ArrayList<>());
            }
            anagramsMap.get(key).add(s);
        }
        return anagramsMap;
    }
}

Reverse position of words in a string using recursion

 In this article, we will write a program to reverse position of words in a given string using recursive approach.

Sample input

I am the best of bests

Output

bests of best the am I

Recursive Approach

1. We will remove first word from the input string and append it at the end.

2. Repeat it till all the words are removed and input becomes empty.

public class ReverseWordsInString { public String reverse(String input) { if (input.isEmpty()) { return input; } String[] arr = input.split(" ", 2); String firstWord = arr[0]; String remainingSentence; if (arr.length == 2) remainingSentence = arr[1]; else remainingSentence = ""; return reverse(remainingSentence) + firstWord + " "; } }

1)Base condition in recursion, if the input is empty then we just return (unwind the stack in recursion)

2)We are splitting input string into two parts - first element of array will contain the first word, second element of array will contain the remaining sentence

3)Tail recursion - removes first word and appends it to the last

JUnit testcase

We will write a simple Junit based testcase to assert the correctness of our given program.

JUnit Test

import org.junit.Test;

import static org.hamcrest.CoreMatchers.equalTo;
import static org.junit.Assert.*;

public class ReverseWordsInStringTest {

    @Test
    public void reverse() {
        ReverseWordsInString utils = new ReverseWordsInString();
        assertThat(utils.reverse("I am the best of bests"), equalTo("bests of best the am I"));
    }
}

Find two numbers of which the product is maximum in an array

 We can easily find two number in an array whose product is maximum using the below approach:

1. Sort the input integer array in descending order

2. multiply first and second element of the array, the product will be maximum.Find product of max two elements of an integer array

   import java.util.Arrays;
   import java.util.Comparator;
   
   public class ArrayUtils {
   
       long productMinMax(Integer[] array) {
           Arrays.sort(array, Comparator.reverseOrder());
           int maxNumber = array[0];
           int secondMaxNumber = array[1];
           System.out.println("maxNumber = " + maxNumber);
           System.out.println("secondMaxNumber = " + secondMaxNumber);
           return secondMaxNumber * maxNumber;
       }
   
       public static void main(String[] args) {
           long product = new ArrayUtils().productMinMax(new Integer[]{10, 11, 13, 9, 2, 4});
           System.out.println("Product of min and max element = " + product);
       }
   }

   Program output

   maxNumber = 13
   secondMaxNumber = 11
   Product of min and max element = 143

JUnit vs. TestNG

 

1.

Junit  originally developed by kent beck and erich gamma . in 2013

testng, which was created by cedric beust

2.

groups

testng offers additional annotations to those available in junit. probably the most notable is the ability to run code before / after groups of test cases. also, single tests can belong to multiple groups and then run in different contexts (like slow or fast tests). it’s practically another layer in between a test case and a test suite:

1

@test(groups = { "sanity", "insanity" })

a similar feature exists in junit categories but lacks the @beforegroups / @aftergroups testng annotations that allow initializing the test / tearing it down. btw, looks like junit 5 is going to deprecate categories and introduce a new concept that will be called a tag:

1

@tag("sanity")

2

@tag("insanity")

3

void testsomething() {

4

  ...

5

}

but as it looks right now, no @beforetag / @aftertag annotations in sight.

3.parallelism

if you’d like to run the same test in parallel on multiple threads, testng has you covered with a simple to use annotation while junit doesn’t offer a simple way to do so out of the box. the testng implementation would look like:

1

@test(threadpoolsize = 3, invocationcount = 9)

2

public void testsomething() {

3

  ...

4

}

meaning, three threads and nine invocations of the same test. you can also run whole suites in parallel if you specify it in testng’s xml run configurations. while with junit you’d have to write a custom runner method, and feed the same testing parameters multiple times. which brings us to the next bullet point.

4.parameterized/data-driven testing

this is the problem of feeding different test inputs to the same test case, which both testng and junit solve, but use different approaches. the basic idea is the same, creating a 2d array, object[][] that includes the parameters.

however, in addition to supplying the parameters through the code, the testng @dataprovider can also support xml for feeding in data, csvs, or even plain text files.

a feature that exists in junit and misses on testng is the ability to use different combinations between several arguments. this provides a shortcut to long parameter list and explained in junit theories .

5.dependencies between groups/methods

since junit was built for unit tests, and testng had a wider array of tests in mind, they also differ in their approach to dependencies between tests.

testng allows you to declare dependencies between tests, and skip them if the dependency test didn’t pass:

1

@test(dependsonmethods = { "dependonsomething" })

2

public void testsomething() {

3

  ...

4

}

this functionality doesn’t exist in junit, but can be emulated using assumptions . a failed assumption results in an ignored test, which is skipped.

bottom line: different developers would have different expectations from their framework of choice. testng seems to provide greater flexibility out of the box compared to junit.

5. reporting on the results

test results interest a lot of people. it’s not just the developer who runs them. this is when reports come into play and both frameworks have an answer for this issue.

testng reports are generated by default to a test-output folder that includes html reports with all of the test data, passed/failed/skipped, how long did they run, which input was used and the complete test logs. in addition, it also exports everything to an xml file which can be used to construct your own report template.

on the junit front, all of this data is also available via xml, but there’s no out of the box report and you need to rely on plugins.

bottom line: testng provides out of the box reports, junit only exports it to xml