Algorithms

This section is about solving simple algorithms, coding challenges, puzzles, katas and dojo material in Java.

Sum a Collection

Given an array of integers, find the sum of its elements.

import java.util.List;

public class CollectionAdder {

    public int sum(List<Integer> numbers) {
        return numbers.stream().reduce(0, Integer::sum);
    }
}

Biggest Number

Messages with random data are coming! But we just care about numbers! Your task is to implement a function which removes all non numeric data and return just the biggest number messages = "hi", "2", "@#$%", "32" result = 32

import java.util.List;

public class BiggestNumberFinder {

  private String regex = "-?[0-9]+.?[0-9]+";

  public double find(List<String> numbers) {
    return numbers.stream()
        .filter(it -> it.matches(regex))
        .map(it -> Double.parseDouble(it))
        .max(Double::compare)
        .get();
  }
}

Given a collection with numbers: 34 , 31, 34, 56, 12, 35, 24, 34, 69, 18 Write a function that finds most popular number in the array, in this case 34 because it is the number that appears most often.

import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class PopularFinder {

  public int find(List<Integer> numbers) {
    return numbers.stream()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
        .entrySet()
        .stream()
        .max(Comparator.comparing(Map.Entry::getValue))
        .get()
        .getKey();
  }
}

Common Elements in two Collections

I have two arrays with integers. I want to return elements in common.

Example

first = [1,2,3,4,5]
second = [1,3,5,7,9]
result = [1,3,5]

Solution

import java.util.List;
import java.util.stream.Collectors;

public class CommonElements {

  public List<Integer> find(List<Integer> first, List<Integer> second) {
    return first.stream().filter(it -> second.contains(it)).collect(Collectors.toList());
  }
}

Number Counter

Given an integer collection, return an array with three elements: how many of them are positive, how many negative and how many are zeros.

Sample Input

[-4, 3, -9, 0, 4, 1]

Expected Output

[3, 2, 1]

Solution

import java.util.Arrays;

public class NumbersCounter {

    public int[] count(int[] numbers) {
        return new int[]{
                (int)Arrays.stream(numbers).filter(n -> n > 0).count(),
                (int)Arrays.stream(numbers).filter(n -> n < 0).count(),
                (int)Arrays.stream(numbers).filter(n -> n == 0).count()
        };
    }
}

Characters Counter

Create two functions one for counting vowels and another for counting consonants. Given a string, when that string is josdem, then counting vowels should be 2 and consonants 4.

Solution

import java.util.Arrays;
import java.util.List;

public class CharactersCounter {
  private List<Character> vowels = Arrays.asList('a', 'e', 'i', 'o', 'u');
  private List<Character> consonants =
      Arrays.asList(
          'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'r', 'p', 'q', 's', 't', 'v', 'w',
          'x', 'y', 'z');

  public int countVowels(String keyword) {
    return (int) keyword.chars().filter(ch -> vowels.contains((char) ch)).count();
  }

  public int countConsonants(String keyword) {
    return (int) keyword.chars().filter(ch -> consonants.contains((char) ch)).count();
  }
}

Birthday Cake Candles

It is your birthday! And you want to make it special, so you want to keep only biggest candles in the cake Your task is to create a function that removes all small candles and just keep the biggest ones.

Sample Input

[3,2,1,3]

Sample Output

[3,3]

Solution

import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

public class CandleCounter {

  public List<Integer> count(List<Integer> candles) {
    Optional<Integer> biggest = candles.stream().max(Integer::compare);
    return candles.stream().filter(it -> it == biggest.get()).collect(Collectors.toList());
  }
}

String Compressor

Given a String “aaabbbbcc” when we call compress method then we have a compressed string like: “a3b4c2”

Sample Input

String = "aaabbbbcc"

Sample Output

"a3b4c2"

Solution

import java.util.Map;
import java.util.stream.Collectors;

public class StringCompressor {

  public String compress(String keyword) {
    Map<Object, Long> map =
        keyword
            .chars()
            .mapToObj(it -> (char) it)
            .collect(Collectors.groupingBy(it -> it, Collectors.counting()));
    StringBuilder sb = new StringBuilder();
    map.forEach(
        (k, v) -> {
          sb.append(k);
          sb.append(v);
        });
    return sb.toString();
  }
}

Sock Merchant

John works at a clothing store and he’s going through a pile of socks to find the number of matching pairs. Given a collection with socks’ colors 10, 20, 20, 10, 10, 30, 50, 10, 20 write a function to find out how many pairs you can get.

Sample Input

colors = [10, 20, 20, 10, 10, 30, 50, 10, 20]

Sample Output

3

Explanation

Sock Merchant

As you can see from the figure above, we can match three pairs of socks.

Solution

import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

class SockPairFinder {

  public Integer findPairsBy(List<Integer> colors) {
    Map<Integer, Long> map =
        colors.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    List<Long> values =
        map.entrySet().stream()
            .map(Map.Entry::getValue)
            .filter(it -> it / 2 > 0)
            .collect(Collectors.toList());
    Long result = values.stream().mapToLong(it -> it / 2).sum();
    return result.intValue();
  }
}

Smallest Biggest

Find smaller and biggest numbers in a collection, then return another collection with result. Given a collection like: 7, 5, 2, 4, 3, 9 when I call find method then I will get a collection with 2, 9 values.

Sample Input

numbers = [7, 5, 2, 4, 3, 9]

Sample Output

result = [2, 9]

Solution

import java.util.Arrays;
import java.util.List;

public class SmallerBiggestFinder {
  public List<Integer> find(List<Integer> numbers) {
    Integer smaller = numbers.stream().reduce((a, b) -> a < b ? a : b).get();
    Integer biggest = numbers.stream().reduce((a, b) -> a > b ? a : b).get();
    return Arrays.asList(smaller, biggest);
  }
}

Electronics Shop

Monica wants to buy exactly one keyboard and one USB drive from her favorite electronics store. The store sells N different brands of keyboards and M different brands of USB drives. Monica has exactly S dollars to spend, and she wants to spend as much of it as possible (i.e., the total cost of her purchase must be maximal). Given the amount of money Monica has to spend in electronics and the prices lists for the store’s keyboards and USB drives, find out the amount of money Monica will spend.

Sample Input

keyboards = [3, 1]
usbs = [5, 2, 8]
amount = 10

Sample Output

9

Explanation

She can buy the 2nd keyboard and the 3rd USB drive for a total cost of 8 + 1 = 9.

Solution

import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class ShopCalculator {

  public int compute(Integer amount, List<Integer> keyboards, List<Integer> usbs) {
    final List<Map.Entry<Integer, Integer>> pairs = new ArrayList<>();

    keyboards.forEach(
        k ->
            usbs.forEach(
                u -> {
                  pairs.add(new SimpleEntry<>(k, u));
                }));

    final List<Integer> prices =
        pairs.stream().map(entry -> entry.getKey() + entry.getValue()).collect(Collectors.toList());
    return prices.stream().filter(it -> it <= amount).max(Integer::compare).get();
  }
}

Square my List

Given a numeric list elements, square every element from the list and retrun the result in another collection.

Solution

import java.util.List;
import java.util.stream.Collectors;

public class SquareCalculator {
  public List<Integer> square(List<Integer> numbers) {
    return numbers.stream().map(it -> it * it).collect(Collectors.toList());
  }
}

Digital Adder

Given a numeric collection, when I call add method, then I will get a collection with every element summing its digits

Sample Input

numbers = [15, 20, 4, 8]

Sample Output

expectedCollection = [6, 2, 4, 8]

Solution

import java.util.List;
import java.util.stream.Collectors;

public class DigitalAdder {
  public List<Integer> add(List<Integer> numbers) {
    List<String> numbersAsString =
        numbers.stream().map(it -> String.valueOf(it)).collect(Collectors.toList());
    return numbersAsString.stream()
        .map(string -> string.chars().map(ch -> Integer.valueOf(Character.toString(ch))).sum())
        .collect(Collectors.toList());
  }
}

To browse the project go here, to download the project:

git clone git@github.com:josdem/algorithms-workshop.git
cd simple-algorithms

To run Java project code: Go to the kata directory and do

gradle test

Return to the main article

josdem  techtalks  algorithms  power set  palindrome