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;
}

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;
}

Power Set Algorithm

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}}.

The problem can be solved using recursion. We know that if the initial set is empty, then its power set is {{}} and if it has only one element {a} then its power set is {{}, {a}}.

Here is the algorithm:

public static <E extends Comparable<E>> List<List<E>> subsets(final List<E> list) {
  final List<List<E>> result = new ArrayList<>();

  // if the list is empty there is only one subset, which is the empty set
  if (list.isEmpty()) {
    result.add(Collections.emptyList());
    return result;
  }

  // otherwise, get the first element
  final E first = list.get(0);

  // find the subsets of the rest of the list
  final List<E> rest = list.subList(1, list.size());
  final List<List<E>> subsets = subsets(rest);
  result.addAll(subsets);

  // create new subsets by inserting the first element into each subset
  for (final List<E> subset : subsets) {
    final List<E> newSubset = new ArrayList<>(subset);
    newSubset.add(0, first);
    result.add(newSubset);
  }

  return result;
}

Power Set Algorithm

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}}. In an interview, I was asked to write an algorithm to find the power set of a given set.

The problem can be solved using recursion. We know that if the initial set has only one element {a} then its power set is {{}, {a}}.

Here is the algorithm:

public <E extends Comparable<E>> List<List<E>> powSet(List<E> list){

  List<List<E>> result = new ArrayList<List<E>>();
  if(list.isEmpty()){
    result.add(new ArrayList<E>());
    return result;
  }
  else if(list.size() == 1){
    List<E> empty = new ArrayList<E>() ;
    List<E> oneE = new ArrayList<E>(list) ;
    result.add(empty);
    result.add(oneE);
    return result;
  }
  else{
    E first = list.remove(0);
    List<List<E>> subsets = powSet(list);

    for(List<E> subset : subsets){
      result.add(subset);

      List<E> tmp = new ArrayList<E>(subset) ;
      tmp.add(first);
      Collections.sort(tmp);
      result.add(tmp);
    }
    return result;
  }
}

More Interview Posts

Tree Traversal

Given the following tree, how would you print out the nodes in the following order: 0, 1, 2, 3, 4, 5? (interview question)

     0
   /   \
  1     2
 / \   /
3   4 5

Breadth-first Traversal:
The problem can be solved with breadth-first (level-order) traversal, using an intermediate queue and iteration:

public void breadthFirstIterative(Node root){
  Queue<Node> q = new LinkedList<Node>();
  q.add(root);
  while(!q.isEmpty()){
    Node node = q.poll();
    System.out.println(node.data);
    if(node.left != null){
      q.add(node.left);
    }
    if(node.right != null){
      q.add(node.right);
    }
  }
}

You can also solve it using recursion, but this is not efficient and not recommended.

public void breadthFirstRecursive(Node root) {
  Map<Integer, List<Node>> map =
               new TreeMap<Integer, List<Node>>();
  breadthFirst2(root, map, 0);
  for (int i : map.keySet()) {
      List<Node> nodes = map.get(i);
      for(Node node : nodes){
          System.out.println(node);
      }
  }
}

private void breadthFirst2(Node node,
        Map<Integer, List<Node>> map,
                        int level) {
  List<Node> nodes = map.get(level);
  if (nodes == null) {
      nodes = new ArrayList<Node>();
      map.put(level, nodes);
  }
  nodes.add(node);
  if (node.left != null) {
      breadthFirst2(node.left, map, level + 1);
  }
  if (node.right != null) {
      breadthFirst2(node.right, map, level + 1);
  }
}

Depth-first Traversal:
Just for completeness, I will also show you the algorithm for depth-first traversal, which will not print out 0, 1, 2, 3, 4, 5 but will print out 0, 1, 3, 4, 2, 5. Here is the algorithm using a stack and iteration:

public void depthFirstIterative(Node root) {
    Stack<Node> s = new Stack<Node>();
    s.push(root);
    while (!s.isEmpty()) {
        Node node = s.pop();
        System.out.println(node);
        if (node.right != null) {
            s.push(node.right);
        }
        if (node.left != null) {
            s.push(node.left);
        }
    }
}

You can also solve it using recursion:

public void depthFirstRecursive(Node root) {
    System.out.println(root);
    if (root.left != null) {
        depthFirstRecursive(root.left);
    }
    if (root.right != null) {
        depthFirstRecursive(root.right);
    }
}

Detecting a Cycle in Linked List

How do you detect a cycle in a linked list? A cycle occurs if one node points back to a previous node in the list. You could solve this by using an intermediary data structure, but a more efficient algorithm is Floyd's "hare and tortoise" algorithm.

The idea is to have two iterators; the hare and the tortoise. The hare runs along the list faster than the tortoise and if the list has a cycle, the hare will eventually overtake the tortoise. The following code illustrates the algorithm:

public boolean hasCycle(Node root){
  Node tortoise = root;
  Node hare = tortoise.next;

  while (hare != tortoise) {
    // tortoise moves one place
    tortoise = tortoise.next;

    // hare moves two places
    hare = hare.next;
    if (hare != null) {
      hare = hare.next;
    }

    if (tortoise == null || hare == null) {
      // end of list, no cycles
      return false;
    }
  }
  return true;
}

(This is an interview question.)

Factorial Algorithm

The factorial of a number is the product of all positive integers less than or equal to it. e.g. the factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120.

While conducting a Java interview, I like to ask my candidates to write an algorithm to calculate the factorial of a number. This is one of my favourite questions because it gives me an insight into their thinking process. It is also one of the questions that I was asked at Merrill Lynch, in my first interview out of university. (I got it right)

I am surprised at how the majority of people cannot answer this question, or get anywhere close to it. C'mon, you can do it using recursion or loop-iteration; its not that difficult! If you can't count backwards, do it forwards - its the same thing.

Here is a simple solution: //loop public int factorial(int n) { int result = 1 ; for(int i = n ; i > 0 ; i--) { result = result * i ; } return result ; } //recursion public int recursiveFactorial(int n) { if (n == 0) return 1 ; else return n * recursiveFactorial(n-1) ; }