Saturday, January 28, 2017

Power Set Algorithm - Iterative

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.

Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set {a, b, c}, the binary string 101 would represent {a, c}.

Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!

Here is the algorithm:

public static <E> List<List<E>> powerSet(final List<E> list) {
  final List<List<E>> result = new ArrayList<>();
  final int numSubSets = 1 << list.size(); // 2^n
  for (int i = 0; i < numSubSets; i++) {
    final List<E> subSet = new ArrayList<>();
    int index = 0;
    for (int j = i; j > 0; j >>= 1) { // keep shifting right
      if ((j & 1) == 1) { // check last bit
        subSet.add(list.get(index));
      }
      index++;
    }
    result.add(subSet);
  }
  return result;
}

Sunday, January 22, 2017

Java 8: Top N elements from a stream

This post shows how you can sort a stream in reverse order and then select the top N elements.

This is quite common in financial systems.

For example, let's say that you have a list of currency exchange rate movements and you want to see the top 5 largest movements. You can do this using Java 8 Streams as shown below:

import static java.util.Comparator.*;
import static java.util.stream.Collectors.*;

// list of currency exchange rate percentage moves
final List<Currency> currencies = Arrays.asList(
    new Currency("EUR/USD", 0.37),
    new Currency("USD/JPY", -0.21),
    new Currency("GBP/USD", 0.27),
    new Currency("AUD/USD", -0.08),
    new Currency("USD/CAD", 0.02),
    new Currency("USD/CHF", -0.46),
    new Currency("EUR/JPY", 0.16),
    new Currency("EUR/GBP", 0.13),
    new Currency("USD/HKD", 0.0),
    new Currency("EUR/CHF", 0.05),
    new Currency("USD/KRW", -0.71)
    );

currencies.stream()
  .sorted(comparing(Currency::getMove, comparing(Math::abs)).reversed())
  .limit(5)
  .collect(toList());

The result is:

Currency [ccy=USD/KRW, move=-0.71]
Currency [ccy=USD/CHF, move=-0.46]
Currency [ccy=EUR/USD, move=0.37]
Currency [ccy=GBP/USD, move=0.27]
Currency [ccy=USD/JPY, move=-0.21]

The two argument Comparator.comparing method easily allows us to compare currency moves on absolute value.

Sunday, January 01, 2017

fahd.blog in 2016

Happy 2017, everyone!

I'd like to wish everyone a great start to an even greater new year!

In keeping with tradition, here's one last look back at fahd.blog in 2016.

During 2016, I posted 20 new entries on fahd.blog. I am also thrilled that I have more readers from all over the world! Thanks for reading and especially for giving feedback.

Top 5 posts of 2016:

I'm going to be writing a lot more this year, so stay tuned for more great techie tips, tricks and hacks! :)

Related posts:

Tuesday, December 27, 2016

Stacks and Queues

This post shows you how to implement a Stack and a Queue in Java. It might be handy in interviews ;)

Implementing a Stack:

A stack uses LIFO (last-in first-out) ordering. Think of a stack of dinner plates. It provides constant time adds and removes. Sample code:

public class Stack<E> {
  private static class StackItem<E> {
    final E data;
    StackItem<E> next;

    public StackItem(final E data) {
      this.data = data;
    }
  }

  private StackItem<E> top;

  public boolean isEmpty() {
    return top == null;
  }

  public void push(final E e) {
    final StackItem<E> toAdd = new StackItem<>(e);
    toAdd.next = top;
    top = toAdd;
  }

  public E pop() {
    if (isEmpty()) {
      throw new NoSuchElementException("Stack is empty");
    }
    final E data = top.data;
    top = top.next;
    return data;
  }

  public E peek() {
    if (isEmpty()) {
      throw new NoSuchElementException("Stack is empty");
    }
    return top.data;
  }
}
Implementing a Queue:

A queue uses FIFO (first-in first-out) ordering. Sample code:

public class Queue<E> {
  private static class QueueItem<E> {
    final E data;
    QueueItem<E> next;

    public QueueItem(final E data) {
      this.data = data;
    }
  }

  private QueueItem<E> first;
  private QueueItem<E> last;

  public boolean isEmpty() {
    return first == null;
  }

  public void add(final E e) {
    final QueueItem<E> toAdd = new QueueItem<>(e);
    if (last != null) {
      last.next = toAdd;
    }
    last = toAdd;
    if (first == null) {
      first = last;
    }
  }

  public E remove() {
    if (isEmpty()) {
      throw new NoSuchElementException("Queue is empty");
    }
    final E data = first.data;
    first = first.next;
    if (first == null) {
      last = null;
    }
    return data;
  }

  public E peek() {
    if (isEmpty()) {
      throw new NoSuchElementException("Queue is empty");
    }
    return first.data;
  }
}

Saturday, December 24, 2016

Shell Scripting: Parsing options using getopt and getopts

This post shows how you can parse shell options using getopts and getopt.

Using getopts:

getopts is a bash built-in command. I find it a lot easier to use than getopt.

Here is an example of using getopts:

# options a and b are followed by a colon because they require arguments
while getopts "ha:b:" opt; do
  case "$opt" in
    h)
      echo "help"
     ;;
    a)
      option_a=$OPTARG
      ;;
    b)
      option_b=$OPTARG
      ;;
  esac
done
shift $((OPTIND-1))

echo "option_a: $option_a"
echo "option_b: $option_b"

# read positional parameters
echo "Param 1: $1"
echo "Param 2: $2"

Running it:

$ myscript.sh -a foo -b bar hello world
option_a: foo
option_b: bar
Param 1: hello
Param 2: world
Using getopt:

getopt supports long options and that's the only time I use it.

Here is an example of using getopt:

options=$(getopt -n "$0" -o ha:b: -l "help,alpha:,bravo:"  -- "$@")
(( $? != 0 )) && echo "Incorrect options provided" >&2 && exit 1
eval set -- "$options"

while true; do
  case "$1" in
    -h|--help)
        echo "help"
        ;;
    -a|--alpha)
        shift
        option_a="$1"
        ;;
    -b|--bravo)
        shift
        option_b="$1"
        ;;
    --)
        shift
        break
        ;;
  esac
  shift
done

echo "option_a: $option_a"
echo "option_b: $option_b"

# read positional parameters
echo "Param 1: $1"
echo "Param 2: $2"

Running it:

$ myscript.sh --alpha foo --bravo bar hello world
option_a: foo
option_b: bar
Param 1: hello
Param 2: world