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

Sunday, November 06, 2016

Detecting a Loop in a Linked List

In a previous post, I wrote about how you can detect a loop in a linked list using Floyd's Hare and Tortoise algorithm. You have two iterators - the hare and the tortoise - one of them runs faster than the other and, if the list has a loop, they will eventually collide. Here is a recap of the algorithm:

public static boolean hasLoop(final Node head) {
  Node tortoise = head;
  Node hare = head;
  while (hare != null && hare.next != null) {
    tortoise = tortoise.next;
    hare = hare.next.next;
    if (hare == tortoise) { // collision
      return true;
    }
  }
  return false;
}
How do you find the start of the loop?

Now, let's make this problem more interesting by finding the node at the beginning of the loop.

Consider the following illustration of a linked list with a loop. We need to find the start of the loop, which is 3.

0 - 1 - 2 - 3
           / \
         10   4
          |   |
          9   5
          |   |
          8   6
           \ /
            7

We know that the hare runs twice as fast as the tortoise. Let's say that the tortoise enters the loop after k steps. Then the hare has taken 2k steps in total and is, therefore, k steps ahead of the tortoise within the loop. This means that hare and tortoise are LOOP_SIZE - k nodes away from each other. Since hare moves two nodes for each node that tortoise moves, they move one node closer to each on each turn and will meet after LOOP_SIZE - k turns, and both will be k nodes from the start of the loop at that point. The start of the loop is also k nodes from the beginning of the list.

In my example, the tortoise enters the loop (node 3) after 3 steps. At that stage, the hare has taken 6 steps in total and is at node 6. They collide at node 8 after 5 steps (LOOP_SIZE = 8, k = 3, LOOP_SIZE - k = 5). The start of the loop is 3 nodes away from the point of collision and also 3 nodes away from the head of the list.

So, if we keep the hare where it is (at the point of collision) and move the tortoise back to the beginning of the list, and then move each of them one step at a time, they will collide at the start of the loop!

Here is the algorithm:

public static Node findLoopStart(final Node head) {
  Node tortoise = head;
  Node hare = head;

  boolean hasLoop = false;
  while (hare != null && hare.next != null) {
    tortoise = tortoise.next;
    hare = hare.next.next;
    if (hare == tortoise) {
      hasLoop = true;
      break;
    }
  }

  if (hasLoop) {
    tortoise = head;
    while (tortoise != hare) {
      tortoise = tortoise.next;
      hare = hare.next;
    }
    return tortoise;
  }

  return null;
}

Sunday, October 30, 2016

Java 8: Updates to Map

In Java 8, the Map interface has been updated to include several new, convenient methods. Some of the important changes are outlined below:

1. computeIfAbsent

computeIfAbsent is particularly useful when implementing the caching pattern. For example, previously, you would do this:

private final Map<String, Data> map = new HashMap<>();

public Data getData(final String key) {
  Data data = map.get(key); // look in cache
  if (data == null) { // data is not in cache
    data = computeData(key); // perform an (expensive) operation
    map.put(key, data); // put data in cache
  }
  return data; // return data
}

You can now write this method more concisely as follows:

public Data getData(final String key) {
  return map.computeIfAbsent(key, this::computeData);
}

You can also use computeIfAbsent when implementing a "multi-map" (Map<K, Collection<V>>):

 map.computeIfAbsent(key, k -> new ArrayList<V>()).add(v);
2. putIfAbsent

putIfAbsent puts a value in the map, if the key is not already present. For example, instead of this:

final Map<String, String> map = new HashMap<>();
final String v = map.get(k);
if (v == null) {
  map.put(k, newValue);
}

you can write:

final Map<String, String> map = new HashMap<>();
map.putIfAbsent(k, newValue);
3. getOrDefault

getOrDefault returns a default value, if a specified key is not found in the map. Previously, you would do this:

final Map<String, String> map = new HashMap<>();
return map.containsKey(key) ? map.get(key) : "foo";

Now you can write:

final Map<String, String> map = new HashMap<>();
return map.getOrDefault(key, "foo");
4. Performance

The implementation of HashMap has been updated so that when buckets become too big (see the "TREEIFY_THRESHOLD" setting) they are transformed from lists (with O(n) retrieval) into trees (with faster O(log(n)) retrieval). This improves performance when hashCode() methods return values that are poorly distributed, or when many keys share the same hashCode, so long as they are also Comparable.