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

Mounting a Windows Hard Drive on Linux

Today, I had problems with my Windows hard drive. The operating system (XP) refused to start up and was complaining about corrupt system files. I wanted to back up my files in case things got worse. Luckily, I have a USB external hard drive enclosure and an Ubuntu Linux netbook so this is what I did:

• I took out the hard drive from my Windows laptop.
• I inserted it into my Akasa Integral External Enclosure and plugged it via USB into my Ubuntu netbook.
• Ubuntu wasn't about to mount it automatically and gave me an error saying that the hard drive had problems and that I should "force" it to mount using a command.
• I opened a terminal and typed the following commands to mount the disk manually:

$ sudo mkdir /media/disk
$ sudo mount -t ntfs /dev/sdb1 /media/disk -o force
$ cd /media/disk

• I was then able to browse the contents of the Windows drive and back up important files.
• Finally, I unmounted the drive as follows:

$ sudo umount /dev/sdb1