June 11, 2003

JavaOne - More programming puzzles

Java
Neal Gafter (left) and Joshua Bloch during their "Programming Puzzles" session.

This session promises to be a lot of fun. In the past years, I missed similar presentations considering them entry level, only to hear from colleagues that attended that the sessions were really good. The session is presented by Joshua Bloch and Neal Gafter of Sun Microsystems. After this session I need to get some food, I'm really hungry.

12:15pm It started. The first problem is "Random Behavior".

public class RandomSet {
  public static  void main(String[] args) {
    Set s = new HashSet();
    for (int i = 0; i < 100; i++)
      s.add(randomInteger());
    System.out.println(s.size());
  }

  private static Integer randomInteger() {
    return new Integer(new Random().nextInt());
  }
}

What is the size of the set printed at the end: 1, 50 or 100? Because the Random is initialized each time in randomInteger(), and that is always initialized with the current time of day in miliseconds, on fast machines the seed is pretty much the same. By sharing the Random object, you can actually get real random numbers.

Second problem is "Making a Hash of It".

public class Name {
  private String first, last;

  public Name(String first, String last) {
    if (first == null || last == null)
      throw new NullPointerException();
    this.first == first; this.last = last;
  }
  public boolean equals(Name o) {
    return first.equals(o.first) && last.equals(o.last);
  }

  public int hashCode() {
    return 31 * first.hashCode() + last.hashCode();
  {

  public static void main(String[] args)
    Set S = new HashSet();
    s.add(new Name("Mickey", "Mouse"));
    System.ouyt.println(s.contains(new Name("Mickey", "Mouse"));
  }
}

What does this program output, true or false? Because equals() takes as argument a Name and not an Object, the method is not actually overriding equals(Object), but overloads equals(). Thus the method is never called, so the program always returns false. The solution is to change the signature of equals() to take an Object as argument.

Next problem is "Ping Pong":

class PingPong {
  public static synchronized void main(String[] a) {
    Thread t = new Thread() {
      public void run() {
        pong();
      }
    };

    t.run();
    System.out.println("Ping");
  }

  static synchronized void pong() {
    System.out.println("Pong");
  }
}

What is the output of this program? PingPong, PongPing or it varies?

The answer is PongPing, because by the time pong() executes the class already holds the lock. Well, if the programmer actually wanted to start the thread, he should have written t.start() instead of t.run(). In that case the output would be PingPong. The issue is that Thread implements Runnable, which it shouldn't because it's difficult to catch these problems.

Next problem is "Reflection Infection":

public class Reflector {
  public static void main(String[] args) throws Exception {
    Set s = new HashSet();
    s.add("foo");
    Iterator i = s.iterator();
    Method m = i.getClass().getMethod("hasNext", new Class[0]);
    System.out.println(m.invoke(i, new Object[0]));
  }
}

Won't compile? true? Throws exception? None of the above?

Most people think it will throw an exception, which is correct: attempt to invoke a method on a private class. The problem is that i.getClass() is not an Iterator, which is an interface, but a private class of the JVM. The correct way to do it is rewrite it to Iterator.class.getMethod() instead.

Next problem is "String Cheese":

public class StringCheese {
  public static void main(String[] args) throws Exception {
    byte b[] = new byte[256];
    for (int i = 0; i < 256; i++)
      b[i] = (byte)i;
    String str = new String(b);
    for (int i = 0; i < str.length(); i++)
      System.out.print((int)str,charAt(i) + " ");
  }
}

The numbers from 0 to 255? The number from 0 to 127 then -128 to -1? It varies? None of the above?

The answer is it varies because the sequence depends on the default charset, which depends on OS and locale. The problem is String(byte[] bytes) which constructs a String according to the default charset and locale. To fix it you have to explicitly specify the charset new String(b, "ISO-8553-1")

Next problem is "All Strung Out":

public class Puzzle {
  public static void main(String[] args) {
    String s = new String("bla");
    System.out.println(s);
  }
}

class String {
  java.lang.String s;

  public String(java.lang.String s) {
    this.s = s;
  }

  public java.lang.String toString() {
    return s;
  }
}

Won't compile? blah? Throws an exception? Other?

It throws an exception at runtime. NoSuchMethodError is throwsn because Puzzling is missing a main method. The String argument of main() is the String class defined by us. To fix the problem you have to declare java.lang.String or rename the our String class to MyString. Moral: don't reuse names by hiding, shadowing or overloading.

Next problem is "Elvis Lives":

public class Elvis {
  public static final Elvis INSTANCE = new Elvis();
  private final int beltSize;

  private static final int CURRENT_YEAR = Calendar.getInstance().get(Calendar.YEAR);

  private Elvis() { beltSize = CURRENT_YEAR - 1930; }
  public static void main(String[] args) {
    System.out.println("Elvis wears size " + INSTANCE.beltSize() + " belt.");
  }
}

Elvis wears size 0 belt? Elvis wears size 73 belt? Elvis wears size -1930 belt? None of the above?

The answer is -1930 because of a recursive initialization in the initialization of INSTANCE. In the constructor, the value of CURRENT_YEAR is actually 0, because it was not yet initialized. To fix it, you need to move the initialization of INSTANCE after the initialization of CURRENT_YEAR. Moral: watch out for circular initialization.

Next problem is "What's the point":

class Point {
  protected final int x, y;
  private final String name; // Cached at construction time
  protected String makeName() { return "[" + x + ", " + y + "]"; }
  public final String toString() { return name; }
  Point(int x, int y) {
    this.x = x; this.y = y;
    this.name = makeName();
  }
}

public class ColorPoint extends Point {
  private final String color ;
  protected String makeName() { return super.makeName() + ":" + color; }
  ColorPoint(int x, int y, String color) {
    super(x, y);
    this.color = color;
  }

  main() {
    System.out.println(new ColorPoint(4, 2, "purple"));
  }
}

The output is [4, 2]: null because the subclass method executes before subclass constructor body. To fix it use a lazy initialization, by removing the this.name assignment in Point and introducing a synchronized String toString() in Point, that check the value of name ivar and assigns to it the first time. Moral: never call overridable methods from constructors.

Next is "Shifty":

public class Shifty {
  public static void main(String[] args) {
    int distance = 0;
    while ((-1 << distance) != 0)
      distance++;
    System.out.println(distance);
  }
}

31? 32? 33? None of the above?

None of the above: infinite loop because (-1 << 32) == -1. Moral shift distances are computed mod 32 or 64. It's impossible to shift out an entire int using any shift operator.

Next is "Line Printer":

public class LinePrinter {
  public static void main(String[] args) {
    char c = 0x000A; // \u000A is Unicode for newline
    System.out.println(c);
  }
}

Two blank lines? 10? Won't compile? It varies?

The character \u000A will be broken by the compiler in two, essentially making the comment line break at the Unicode word. Moral: Unicode escapes are dangerous, always use escape sequences.

Posted by ovidiu at June 11, 2003 01:49 PM |
 
Copyright © 2002-2011 Ovidiu Predescu.