This Week in Dev

Java, Unit Tests, CodeSignal

Up to level 40 this week on CodeSignal.com - that’s over 100 challenges solved in just a couple weeks

Evaluating Efficiency with Big-O Notation

Check out my recursive solution to this arcade problem, which made it possible for me solve a problem in *constant time* O(1), a whole world of improvement over my previous approach, which turned out to be a *factorial time* O(n!) solution. Big-O notation is a means of evaluating the computational efficiency of different algorithms.

My solution

boolean stringsRearrangement(String[] inputArray) {
    String[] sorted = Arrays.stream(inputArray).sorted().toArray(String[]::new);

    // test input that does not include duplicates
    if (inputArray.length == Arrays.stream(inputArray).distinct().count()
            && allStringsConform(sorted)) return true;

    // test starting with each individual input string
    for (String string : Arrays.stream(sorted).distinct().toArray(String[]::new)) {
        ArrayDeque<String> input = new ArrayDeque<>(Arrays.stream(sorted).collect(Collectors.toList()));
        input.remove(string);
        ArrayDeque<String> output = new ArrayDeque<>(Collections.singletonList(string));
        if (testPermutations(input, output)) return true;
    }

    return false;
}

private boolean testPermutations(ArrayDeque<String> input, ArrayDeque<String> output) {
    // base case
    if (input.isEmpty()) return true;

    List<String> validNextStrings = getMatches(output.getLast(), input);
    if (validNextStrings.isEmpty()) return false;

    for (String possible : validNextStrings) {
        ArrayDeque<String> newInput = input.clone();
        newInput.remove(possible);
        ArrayDeque<String> newOutput = output.clone();
        newOutput.add(possible);

        if (testPermutations(newInput, newOutput))
            return true;
    }

    return false;
}

private List<String> getMatches(String last, ArrayDeque<String> input) {
    return input.stream()
            .filter(prospect -> twoStringsVaryExactlyOnce(last, prospect))
            .collect(Collectors.toList());
}

private boolean allStringsConform(String[] strings) {
    return IntStream.range(0, strings.length - 1).allMatch(i -> twoStringsVaryExactlyOnce(strings[i], strings[i + 1]));
}

private static boolean twoStringsVaryExactlyOnce(String a, String b) {
    return 1 == IntStream.range(0, a.length()).filter(i -> a.charAt(i) != b.charAt(i)).count();
}

Untenable Bruteforce Solution - *Factorial Time* O(n!) This solution would take up to 5 minutes to complete the tests (an eternity in compute time)

import java.util.*;

class Example {
    boolean stringsRearrangement(String[] inputArray) {
        if (inputArray.length == Arrays.stream(inputArray).distinct().count()) {
            String[] sorted = Arrays.stream(inputArray).sorted().toArray(String[]::new);
            if (stringsConformToLowVarianceThreshold(sorted))
                return true;
        }

        Set<Map<Integer, Integer>> tested = new HashSet<>();
        long MaxPermutations = factorial(inputArray.length);

        Map<Integer, Integer> stringsMapping;
        Random rand = new Random();
        while (tested.size() < MaxPermutations) {
            do {
                stringsMapping = new HashMap<>();
                List<Integer> ints = new ArrayList<>();
                for (int i = 0; i < inputArray.length; i++) ints.add(i);
                for (int i = 0; i < inputArray.length; i++) {
                    int newMap = ints.get(rand.nextInt(ints.size()));
                    stringsMapping.put(i, newMap);
                    ints.remove(Integer.valueOf(newMap));
                }
            }
            while (tested.contains(stringsMapping));
            tested.add(stringsMapping);

            String[] toTest = new String[inputArray.length];
            for (int i = 0; i < inputArray.length; i++) {
                toTest[i] = inputArray[stringsMapping.get(i)];
            }
            if (stringsConformToLowVarianceThreshold(toTest)) {
                return true;
            }
        }

        return false;
    }

    private boolean stringsConformToLowVarianceThreshold(String[] sorted) {
        for (int i = 0; i < sorted.length - 1; i++) {
            if (moreThanOneVariance(sorted[i], sorted[i + 1])) return false;
        }
        return true;
    }

    private static long factorial(int number) {
        long result = 1;

        for (int factor = 2; factor <= number; factor++) {
            result *= factor;
        }

        return result;
    }

    private static boolean moreThanOneVariance(String a, String b) {
        int delta = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) delta++;
        }

        return delta != 1;
    }
}