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

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

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

Factorial Using Iteration, Recursion and Java 8 Streams

In this post, we will solve the classic school problem of calculating the factorial of a positive integer, using different Java algorithms.

Note: In all the algorithms below, we assume that the input is > 1.

1. Iterative Factorial

In this algorithm, we use a standard for-loop and increment the variables i and result at each iteration:

static int iterativeFactorial(final int n) {
  int result = 1;
  for (int i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

2. Recursive Factorial

Here is the recursive version (the function calls itself):

static int recursiveFactorial(final int n) {
  return n == 1 ? 1 : n * recursiveFactorial(n - 1);
}

Recursion lets you get rid of variables that are updated at each iteration. Typically, making a recursive function call is more expensive than iteration because each time the function is called, a new stack frame has to be created on the call stack to hold the state of each function call. Therefore, the memory consumed by the recursive function is proportional to the size of its input. You may even get a StackOverflowError with a large input.

3. Tail-recursive Factorial

Here's a tail-recursive definition of factorial. The recursive call is the last thing that happens in the function. In contrast, in our previous definition of factorial, the last thing was n multiplied by the result of the recursive call.

static int tailRecursiveFactorial(final int n) {
  return tailRecursiveFactorialHelper(n, 1);
}
private static int tailRecursiveFactorialHelper(final int n, final int acc) {
  return n == 1 ? acc : tailRecursiveFactorialHelper(n - 1, n * acc);
}

Tail-recursive functions can be optimised by the compiler in some programming languages. Instead of storing each intermediate result of the recursion onto different stack frames, a single stack frame can be reused instead, because there's no need to keep track of intermediate results. Unfortunately, Java does not support this kind of optimisation, but you might want to take this approach anyway, in case the compiler is optimised in the future. Other JVM languages (e.g. Scala) can optimise tail-recursion.

4. Stream Factorial

Finally, Java 8 streams provide a simple, declarative way of defining factorial:

static int streamFactorial(final int n) {
  return IntStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);
}

Java Bit Twiddling

This post explains some of the less commonly used operators in Java, namely the bitwise and bit shift operators and how they can be cleverly used to multiply or divide integers, test for evenness etc. The operators are shown in the table below:

Name	Description
~a (NOT)	Negates each bit. 0s becomes 1s and vice versa. ~a=(-a)-1
a & b (AND)	In each pair of corresponding bits, the result is 1 if the first bit is 1 AND the second bit is 1, 0 otherwise.
a | b (OR)	In each pair of corresponding bits, the result is 1 if the first bit is 1 OR the second bit is 1 OR both bits are 1, and otherwise the result is 0
a ^ b (XOR)	In each pair of corresponding bits, the result in each position is 1 if the two bits are different, and 0 if they are the same.
a << n (LEFT-SHIFT)	Shifts bit pattern to the left by n positions and places 0s on the right.
a >> n (RIGHT-SHIFT)	Shifts bit pattern to the right by n positions and places the sign-bit on the left, thus preserving the sign of the operand.
a >>> n (UNSIGNED-RIGHT-SHIFT)	Shifts bit pattern to the right by n positions and places 0s on the left.

Examples of bitwise and bit shift operators in action:

a = 3 (11)
b = 6 (110)

~a = -4 (11111111111111111111111111111100)
a & b = 2 (10)
a | b = 7 (111)
a ^ b = 5 (101)
a << 2 = 12 (1100)
b >> 1 = 3 (11)
b >>> 1 = 3 (11)

The code used to generate this is shown below:

final int a = 3; // 011
final int b = 6; // 110

System.out.printf("a = %s\t(%s)\n", a,
                 Integer.toBinaryString(a));
System.out.printf("b = %s\t(%s)\n", b,
                 Integer.toBinaryString(b));

/**
 * NOT
 */
int not = ~a;
System.out.printf("~a = %s\t(%s)\n", not,
                 Integer.toBinaryString(not));

/**
 * AND
 */
int and = a & b;
// 011
// 110
//----&
// 010
System.out.printf("a & b = %s\t(%s)\n", and,
                 Integer.toBinaryString(and));

/**
 * OR
 */
int or = a | b ;
// 011
// 110
//----|
// 111
System.out.printf("a | b = %s\t(%s)\n", or,
                 Integer.toBinaryString(or));

/**
 * XOR
 */
int xor = a ^ b ;
// 011
// 110
//----^
// 101
System.out.printf("a ^ b = %s\t(%s)\n", xor,
                 Integer.toBinaryString(xor));

/**
 * LEFT-SHIFT
 */
int lshift = a << 2;
// 00011
// ----- <<2
// 01100
System.out.printf("a << 2 = %s\t(%s)\n", lshift,
                 Integer.toBinaryString(lshift));

/**
 * RIGHT-SHIFT
 */
int rshift = b >> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >> 1 = %s\t(%s)\n", rshift,
                 Integer.toBinaryString(rshift));

/**
 * UNSIGNED-RIGHT-SHIFT
 */
int urshift = b >>> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >>> 1 = %s\t(%s)\n", urshift,
                 Integer.toBinaryString(urshift));

Usage of bit manipulation:
So, where do you use this? In the olden days, they were used for efficiency but most modern compilers today perform optimisations for you, so you don't have to worry about it. The bitwise and bit shift operators are not used very frequently in day-to-day programming, but here are a few scenarios where they can be used - mainly to impress you colleagues :)

1. Checking if an integer is even or odd
If an integer is odd, its rightmost bit will always be 1 and if it is even, it will always be 0. For example, 4 is 100 and 5 is 101.

public boolean isEven(int a){
    return a & 1 == 0;
}

2. Multiplying/Dividing by powers of two
Shifting to the left is just like multiplying by a power of two. For example 3 << 2 is 12. In general, a << n is a*(2^n). Keep in mind that a left shift can result in "overflow" which occurs when you exceed the limits of the range of the data type you are using and can cause unexpected behaviour.

A right shift is an integer division by a power of 2. Shifting right 1 position is the same as dividing by two. This approach is used in the Collections Framework, such as the Arrays class to find the middle element of an array. In general, a >> n is a/(2^n). Be careful, when right shifting negative integers. For example, 5 >> 1 gives 2, but -5 >> 1, gives -3.

3. Is an integer positive or negative?
Shift the integer right 31 places. The value of the far left bit is copied to the other bits. The far left bit is 1 when the value is negative and 0 otherwise.

public boolean isNegative(int a){
    return (a >> 31) != 0;
}

4. Negating an integer
You can use the NOT operator to determine the negative of any integer as shown in the snippet below. The basic idea is you invert all the bits and then add 1.

int num = 4;
int neg = ~num + 1; //-4

Note that you can also do the reverse and determine the positive of a negative integer by subtracting 1 and then inverting the bits.

5. Check if the nth bit is set
This is a more generalised version of the even/odd check. We move the 1 bit n places to the left and then apply the AND operation. If the nth bit was not set, this would result in 0.

public boolean isBitSet(int a, int n){
    return a & (1 << n) != 0;
}

6. Setting the nth bit

a | (1<<n)

7. Unsetting the nth bit

a & ~(1<<n)

8. Toggling the nth bit

a ^ (1<<n)

9. Unsetting the rightmost 1-bit

a & (a-1)

10. Checking if number is a power of 2
If the number is a power of 2, there will be only one 1-bit. If we unset this bit, we will get 0.

return (a & (a-1)) == 0;

11. Swapping values without a temporary variable
Swap two variables without a temporary variable using XOR:

x = x ^ y;
y = x ^ y;
x = x ^ y;

References:
Bit Twiddling Hacks
Java Ranch - Bit Shifting
Low Level Bit Hacks You Absolutely Must Know

Fixing a ConcurrentModificationException

Question:
The following code throws a ConcurrentModificationException. What additional code can you add between the <FIXME>...</FIXME> tags in order to prevent this exception from being thrown?

final List<String> list = new ArrayList<String>();
list.add("HELLO");
final Iterator<String> iter = list.iterator();
System.out.println(iter.next());
list.add("WORLD");
//<FIXME>

//</FIXME>
System.out.println(iter.next());

Solution:
In this example, a ConcurrentModificationException is thrown because the Iterator detects that the list over which it is iterating has been changed. If you look into the source code for these classes you will find that when an Iterator is created, it contains an int variable called expectedModCount which is initialised to the modCount of the backing list. Whenever the backing list is structurally modified (with an add or remove operation, for example) then the modCount is incremented. As a result, the iterator's expectedModCount no longer matches the list's modCount and the iterator throws a ConcurrentModificationException.

In order to prevent this exception from being thrown, we need to bring the expectedModCount of the iterator and the modCount of the list back in line with each other. Here are a couple of ways this can be done:

1. Reflection:
Reflection is the easiest way to change the internal counters of the iterator and list. In the fix below, I have set the expectedModCount of the iterator to the same value as the modCount of the list. The code no longer throws the ConcurrentModificationException.

final List<String> list = new ArrayList<String>();
list.add("HELLO");
final Iterator<String> iter = list.iterator();
System.out.println(iter.next());
list.add("WORLD");
//<FIXME>
/* Using Reflection */
try{
  //get the modCount of the List
  Class cls = Class.forName("java.util.AbstractList");
  Field f = cls.getDeclaredField("modCount");
  f.setAccessible(true);
  int modCount = f.getInt(list);

  //change the expectedModCount of the iterator
  //to match the modCount of the list
  cls = iter.getClass();
  f = cls.getDeclaredField("expectedModCount");
  f.setAccessible(true);
  f.setInt(iter, modCount);
}
catch(ClassNotFoundException e){
  e.printStackTrace();
}
catch(NoSuchFieldException e){
  e.printStackTrace();
}
catch(IllegalAccessException e){
  e.printStackTrace();
}
//</FIXME>
System.out.println(iter.next());

2. Integer Overflow:
Another approach is to keep modifying the list until the integer modCount overflows and reaches the same value as expectedModCount. At the moment, modCount=2 and expectedModCount=1. In the fix below, I repeatedly change the list (by calling trimToSize), forcing modCount to overflow and reach expectedModCount. This code took 38s to run on my machine.

final List<String> list = new ArrayList<String>();
list.add("HELLO");
final Iterator<String> iter = list.iterator();
System.out.println(iter.next());
list.add("WORLD");
//<FIXME>
for(int i = Integer.MIN_VALUE ; i < Integer.MAX_VALUE ; i++){
  ((ArrayList)list).trimToSize();
}
//</FIXME>
System.out.println(iter.next());

Brain Teaser: Find the ages

Question:
I was visiting a friend one evening and remembered that he had three daughters. I asked him how old they were. "The product of their ages is 72," he answered. Quizzically, I asked, "Is there anything else you can tell me?" "Yes," he replied, "the sum of their ages is equal to the number of my house." I stepped outside to see what the house number was. Upon returning inside, I said to my host, "I'm sorry, but I still can't figure out their ages." He responded apologetically, "I'm sorry, I forgot to mention that my oldest daughter likes strawberry shortcake." With this information, I was able to determine all of their ages. How old is each daughter?

Answer:
The first clue is that the product of their ages is 72. Therefore, the list of all possible sets of numbers whose product is 72 is:

72 1 1
36 2 1
24 3 1
18 4 1
18 2 2
12 3 2
12 6 1
9 8 1
9 4 2
8 3 3
6 6 2
6 4 3

The second clue involves the sums of their ages which are:

72 + 1 + 1 = 74
36 + 2 + 1 = 39
24 + 3 + 1 = 28
18 + 4 + 1 = 23
18 + 2 + 2 = 22
12 + 3 + 2 = 17
12 + 6 + 1 = 19
9 + 8 + 1 = 18
9 + 4 + 2 = 15
8 + 3 + 3 = 14
6 + 6 + 2 = 14
6 + 4 + 3 = 13

Out of all these sums, two of them are equal:

8 + 3 + 3 = 14
6 + 6 + 2 = 14

The final clue is that his "oldest" daughter likes cake, which means that we can eliminate the second one of the above. Therefore, his daughter's ages are:

8 + 3 + 3 = 14

More Interview Posts

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

Design Pattern Interview Questions

1. Explain the Flyweight, Builder, Mediator and Memento patterns.
2. Describe the decorator pattern and how it is used within the java.io package.

   Answer: Decorators are used to provide additional functionality to an object of some kind. The key to a decorator is that a decorator "wraps" the object decorated and looks to a client exactly the same as the object wrapped. This means that the decorator implements the same interface as the object it decorates. For example, a BufferedReader is just a decorator for a Reader.

3. Observer Pattern:
   • Draw the class diagram for the Observer Pattern.
   • What instance variables would you have in the Observable class?
   • What would happen if an Observer removes himself from the observers list when he is notified?
   • What is thread-safety and how can you make the Observer Pattern thread-safe?
4. Name your favourite design pattern.
5. Explain the Model-View-Controller (MVC) compound design pattern. What patterns is it composed of?

More Interview Posts

Java Interview Questions II

Here are a few more java questions I have been asked in interviews recently:

1. Garbage Collection:
   • How does Garbage Collection work?
   • Where does garbage collection start from?
   • When do static fields get garbage collected?
   • When does a thread get garbage collected?
2. What is a potential problem with the following code? How can it be resolved?

   public void swap(Account a, Account b){
    synchronized (a) {
     synchronized (b) {
      double d = a.getBalance();
      double e = b.getBalance();
      a.setBalance(e);
      b.setBalance(d);
     }
    }
   }
   

   Answer: A deadlock will occur if one thread calls swap(a,b) and another calls swap(b,a) at the same time. The easiest way to resolve this issue is to remove the two synchronized blocks and make the method synchronized instead.
3. How many occurences of "NO" does the following program print?

   
   public class Main {
   
     public static void test(String s, String t) {
       if (s == t) {
         System.out.println("YES");
       }
       else {
         System.out.println("NO");
       }
       if (s.equals(t)) {
         System.out.println("YES");
       }
       else {
         System.out.println("NO");
       }
     }
   
     public static void main(String[] args) {
       String s = new String("HELLO");
       String t = new String("HELLO");
       test(s, t); // no, yes
   
       s = "HELLO";
       t = "HELLO";
       test(s, t); // yes, yes
   
       s = s + "!";
       t = t + "!";
       test(s, t); // no, yes
   
       s = "HELLO" + "!";
       t = "HELLO" + "!";
       test(s, t); // yes, yes
     }
   }
   

4. What does the following code print?

   String s = "Welcome!";
   s.substring(3, 7);
   System.out.println(s);
   

   Answer: Welcome!
5. What are the possible outputs of the following program? What changes can you make to print out "HelloI HelloII HelloIII HelloIV" in order?

   public static void main(String[] args) {
    Thread t1 = new Thread(new Runnable(){
     public void run() {
      System.out.println("HelloI");
      System.out.println("HelloII");
     }
    });
    Thread t2 = new Thread(new Runnable(){
     public void run() {
      System.out.println("HelloIII");
      System.out.println("HelloIV");
     }
    });
    t1.start();
    t2.start();
   }
   

   Answer: Possible outputs are:

   HelloI HelloII HelloIII HelloIV
   HelloI HelloIII HelloIV HelloII
   HelloI HelloIII HelloII HelloIV
   HelloIII HelloIV HelloI HelloII
   HelloIII HelloI HelloII HelloIV
   HelloIII HelloI HelloIV HelloII
   

   To print them in order add t1.join() after t1.start().
6. You have a list of integers. Write an algorithm to find the maximum of the differences of each element with those ahead of it in the list.
7. What does the following code print?

   public class A {
   
     private String s = "A1";
   
     public A(){
       dump();
       s = "A2";
       dump();
     }
   
     public void dump(){
       System.out.println(s);
     }
   
     public static void main(String[] args) {
       A a = new B();
     }
   }
   
   class B extends A {
   
     private String s = "B1";
   
     public B(){
       dump();
       s = "B2";
       dump();
     }
   
     public void dump(){
       System.out.println(s);
     }
   }
   

   Answer:

   null
   null
   B1
   B2

8. How would you increment a counter in a threadsafe way?
9. How does AtomicInteger work? Does it use any internal synchronisation?
10. What does the following code print?

    int i = -100;
    int a = ~i + 1;
    a >>= 2;
    System.out.println(a);
    

    Answer: 25
11. Write a unix command to find all files containing the string "ErrorMessage".

    Answer: find . -type f -exec grep -l "ErrorMessage" {} \;

More Interview Posts

Java Interview Questions I

Here are some java questions I have been asked in interviews recently:

1. Explain what the following JVM args are used for:
   • -Xss
   • -Xmx
   • -Xms
   • -XX:PermSize
   • -XX:NewSize
   • -server vs -client
2. What is the difference between the heap and the stack? Explain what is present on the heap and stack when the following method is called:

   public void f(int i){
     Integer a = i ;
     double d = i ;
   }
   

   Answer: The primitive int 'i' is boxed into an Integer object and placed on the heap. So you have a "new Integer(i)" object present on the heap, and variables a, d and i on the stack (as well as the method f). [Further Reading]
3. What are the main collections found in the Collections API?
4. What is the difference between a List and a Set?
5. How does a HashMap work?
6. Given the following classes: Collection, Set, Map, List, ArrayList, Vector, LinkedList, Stack, HashMap, TreeMap, HashSet, TreeSet state which ones are interfaces, concrete classes and those that can be cast to Collection.
7. What happens when the following code is executed?

   List<String> list = new ArrayList<String>() ;
   list.add("foo");
   list.add("bar");
   list.add("baz");
   
   for(String s : list){
       list.remove(s);
   }
   

   Answer: A ConcurrentModificationException is thrown.
8. Given the following class:

   public class Person {
   
     private String name;
   
     public Person(String name){
       this.name = name;
     }
   
     public boolean equals(Object o){
       return name.equalsIgnoreCase(((Person)o).name);
     }
   
     public int hashCode(){
       return 0;
     }
   
     public static void main(String[] args) {
       Set<Person> set = new HashSet<Person>();
       set.add(new Person("David"));
       set.add(new Person("John"));
       set.add(new Person("DAVID"));
       set.add(new Person("Fred"));
   
       Map<Person, String> map = new HashMap<Person, String>();
       map.put(new Person("David"),"David");
       map.put(new Person("John"),"John");
       map.put(new Person("DAVID"),"DAVID");
       map.put(new Person("Fred"),"Fred");
     }
   }
   

   i) What is the size of the set and map? What is the result of map.get(new Person("David"))?
   ii) Delete the equals method and repeat i)
   iii) Delete the hashCode method and repeat i)
   iv) Delete both the equals and hashCode methods and repeat i)
   

   Answers:
   i) 3, 3, DAVID
   ii) 4, 4, null
   iii) 4, 4, null
   iv) 4, 4, null

9. Describe the different kinds of exceptions?
10. What happens when a RuntimeException is thrown but not caught by anything?
11. How are JNI Exceptions handled?
12. What does the following code print?

    public static void main(String[] args) {
     try {
      try {
       throw new Exception();
      }
      catch (Exception e) {
       System.out.println("FooI");
       throw e;
      }
      finally {
       System.out.println("FinallyI");
      }
     }
     catch (Exception e) {
      System.out.println("FooIII");
     }
     finally {
      System.out.println("FinallyII");
     }
    }
    

    Answer: FooI FinallyI FooIII FinallyII

More Interview Posts

Designing a Lottery System

I was asked this question in an interview: You need to design a database to hold customers and their lottery tickets. A lottery ticket has a sequence of 6 numbers e.g. 04 12 18 28 35 41. Once you have designed your tables, write a query which will print out a report of all customers whose tickets match three or more numbers of the winning number. Assume every customer has only one lottery ticket.

The simplest way is to have two tables:

• Customer: with an id, name etc
• Ticket: with an id, customer id and number (which will hold one of the numbers only, so you will get six records per ticket)

Given a winning number, the query to find all customers and how many numbers they matched would be:

SELECT c.name, COUNT(t.num) AS matches
FROM customer c, ticket t
WHERE c.id = t.customer_id
AND t.num IN
(
'05', /*winning number*/
'12',
'19',
'28',
'35',
'42'
)
GROUP BY customer
HAVING COUNT(t.num) >= 3
ORDER BY matches DESC

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

Fun with Pre/Post Operators

Think you know how pre and post operators work? Test yourself by working out what the following programs print. Answers at the end of the post:

1.

void function(int val){
  if(val > 0){
    function(val-1);
  }
  print(val);
}

function(5);

2.

void function(int val){
  if(val > 0){
    function(--val);
  }
  print(val);
}

function(5);

3.

void function(int val){
  if(val > 0){
    function(val--);
  }
  print(val);
}

function(5);

4.

int a = 1;
b = a++ + ++a;
print(b);

Answers:
The first program is simple enough and prints out the numbers 5, 4, 3, 2, 1, 0.

The second program prints out the numbers 4, 3, 2, 1, 0, 0. --val decrements the value of the variable before assigning it. For example, if a=5, and b=--a, then b=4 and a=4.

The third program throws a StackOverflowError. val-- assigns the value of the variable first, before decrementing it. For example, if a=5, and b=a--, then b=5 and a=4.

The fourth program prints 4, because b = 1 + 3.

Interview Questions

Here are a few questions you may be asked if interviewing for a technology / developer role in an investment bank:

Java:

• What is object orientation?
• State three fundamental concepts in object-oriented programming (e.g encapsulation, abstraction, inheritance)?
• What is the super class of all classes?
• State three methods of the Object class.
• What is the difference between checked and unchecked exceptions?
• Name the subclasses of Throwable.
• What is the Error class?
• Why are hashcode() and equals() important?
• What is hashcode() used for in a Hashmap?
• Write an equals method for a Person class which contains a String attribute called name.
• List XML parsers and how would you decide if you should use SAX or DOM?
• Discuss testing with JUnit.

Oracle:

• Given an Employee (name, dept_id) table and a Department (id, name) table, write a query to display which department each employee belongs to and another query to list all departments which have exactly 10 employees.
• What steps would you take to identify why a query is slow and how would you optimise it?
• What kinds of Hints are there?
• What is the difference between a normal index and a clustered index?

Problem Solving:

• You have 8 coins which look identical. However, one of them is heavier than the rest. You have a weighing scale. Find the heaviest coin using the scale the fewest times as possible.
  Answer: Weigh coins 1,2,3 vs 4,5,6. If they weigh the same, weigh 7 vs 8 to get the heaviest. If they are not the same, pick the heaviest batch (e.g. 1,2,3) and weigh 1 vs 2,3 and so on.
• In the diagram below, you have two lists. Change the ordering of the elements in the first list, so that they appear in the same order as the second list. You have a container which can hold only one element to help you.

A          B
B          C
C   +--+   D
D   |  |   E
E   +--+   F
F          G
G          A

Answer: Put A into the container. Shift all elements up by one. Move A into the vacant slot in the bottom of the list.

Risk and PnL:

• What is Real PnL?
• What is attribution i.e. what attributes make this PnL?
• What is explained and unexplained pnl?
• What is Delta Risk and why is it important?
• What market data do you need to calculate Delta Risk and how is it calculated?
• What is a yield curve?
• What is a volatility surface?

• Real PnL: Profit and Loss compared to yesterday REAL_P+L = PVToday - PVYest
• Attribution: What made this PnL such as The Greeks: Delta PnL, Gamma PnL, Theta PnL, Vega PnL, New deals, Dropped deals, Amended deals, Cash flows
• PnL Explained: The addition of all these attributions that explains the Real PnL.
• PnL Unexplained: The difference between the Real PnL and the Explained PnL.
• The target is to get Unexplained as close to 0 as possible.

Related Posts:

• Interview Tips

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

Interview Tips

I've had a few people - interns and grads - applying to investment banks asking me about interviews. I've been through the whole interview process at various places when I first left university and am now involved in interviewing candidates for positions in investment banking technology.

There are a few routine questions which everyone asks, so you should prepare them beforehand. There are also lots of interview question and answer banks online where you can find really good sample answers to common questions. Just Google around. I will try to think of the questions that I have been asked over the years and will categorise them so that they are easier for you to prepare. I will try to give you as many tips as possible. But remember that what works for me may not work for you!


Opening

Greet the interviewer with a firm handshake and a smile. You will probably be nervous but try to stay relaxed, always be polite (e.g. accept a glass of water if offered), smile, make eye contact and pay attention to the questions. Sometimes I forget what the question was, halfway through the answer! Always give clear and concise answers. I also like to take a notebook and a pencil with me to the office. It looks professional, you can make notes while the interviewer explains the company and you can also jot down some questions to ask later. At first, the interviewer will ask you some harmless questions, but answer these nicely because these create the first impression:

• Hello! How are you?
• How was the journey? Did you find us easily?
• Where do you come from?
• One of my favourite things is to comment on the building (e.g. Nice building / office!) when the interviewer is walking me to the room. It is a nice ice breaker and opens the interviewer up.

Know the company

Interviewers always ask about the company. Research:

• Core values / principles / morals
• Company structure i.e. business divisions, hierarchy etc
• News articles e.g press releases from the companies website or search for the company in Google News. This is important so that you can comment on something read in the company’s annual report, web page or latest news report.
• You may also want to read about other companies in the same field and update yourself on what is happening currently in this field even though it may not be related to the company you are applying to.
• Why did you choose this company?
• Have you heard about us in the news recently?

Know the industry

• Learn banking jargon e.g. what is an investment bank, stock, bond, share, risk etc. (I was once asked to define an investment bank)
• What are the main problems facing banks today?
• Future of banking? (globalisation maybe? More mergers)

Know yourself

Be confident in your abilities and sell yourself! Keep in mind that there are hundreds of candidates applying and you need to make yourself stand out and be remembered.

• Tell me about yourself (very open ended question: you have to give a brief history of your life including university, work, extracurriculars)
• Why do you want to work in IT? (be passionate e.g. I like the rapid pace of change of this field, you can’t predict where it will go in the future; I love learning new cutting edge technologies)
• Why should we hire you? (Sell yourself with lots of keywords: ambitious, energetic, adaptive, versatile, juggle multiple priorities, enthusiastic, an agent of change, I like to be stretched and challenged, I’m the best!)
• What motivates you? (self motivated, recognition, good work atmosphere, work colleagues etc but NOT money)
• Why did you choose to do a Masters in this degree?
• Why did you choose a bank and not an IT company? (I’m interested in the financial world too)
• What are your short / long term goals in life?
• What are your strengths / weaknesses? (Strengths: flexibility, teamwork Weaknesses: Everyone has weaknesses, don't say you don't have any! Say how you combat your weakness. e.g. I get nervous during presentations but I always prepare well beforehand)
• How do you measure your success?
• How important is money to you? (not very)
• What are your extra curricular activities?
• What are you passionate about?
• Work experience

Team Work

Companies are looking for team players, so expect lots of questions on team work.

• Describe a project
• What was your role in the team?
• How do you handle conflicts?
• What makes a good team? (a good balance of characters)
• Desribe a situation in which others in the team did not agree with you. How did you persuade them to see things from your perspective?
• Describe something that went wrong or a wrong decision you made and what you learned from your mistakes? (Everyone makes mistakes but you have to say what you learnt from them and how they made you stronger)
• Are you a team player or do you enjoy individual research?
• How do you handle multiple jobs with conflicting deadlines?
  

Know the Technology

You have to be well-versed in various technologies especially for a technical interview. Common questions are asked on:

• Java (especially Threading and Collections)
  
• XML / XSLT
  
• Web Services and Technologies (e.g. .NET, SOAP)
  
• UNIX vs Windows
• Databases - SQL and Oracle
  
• Security issues (e.g. in Wireless Networks)
• E-Commerce and e-banking
• .NET vs J2EE
• What factors would you consider in choosing a programming language (e.g. Java or C++)?
• Recent Viruses (e.g. Slammer had a big effect)
• Outsourcing (most banks do it)
• UML
• Open Source
  
• Up and coming technologies that will have a big impact in the future e.g. AJAX, Ruby, Linux
  
• Read recent tech news items - check out my del.ici.ous page for technology links

Brain Busters

These questions are asked in order to find out whether you are able to think quickly and under pressure. I hate them! The trick is to keep talking about what you are thinking / reasoning. Do not sit quietly while you try to solve the question in your head. The ones I got were:

• If you were an animal what animal would you be and why?
• What is the cube root of 81?
• How many tennis balls were used in the Wimbledon Men’s Singles tournament?
• How many pennies can you fill in this room?
• Why are man-hole covers round? (so that they don't fall in)

Closing

I know that you will be relieved when the interview is over, but do NOT run away quickly. Stay relaxed and thank the interviewer for his/her time. Say that you enjoyed talking to him/her and have learnt a great deal about the company and that you would love to work there. Its always good to have some questions to ask. I have found that interviewers like to be asked questions about themselves! Be nosy about their life:

• How did you end up working here?
• What do you like most about working here?

If you have their email address send them a thank-you email as soon as you get home.

Good luck with the interview and if you have any further questions, don't hesitate to ask me!