Puzzle Interview Questions

  1. With a pencil and paper:
    1. Draw a large square
    2. Insrcribe a circle inside the large square
    3. Inscribe a small square inside the circle
    4. What is the ratio of the area of the large square to the area of the small square?

      Assume the width of the large square is d. The diameter of the circle inside the square is d and its radius is r = d/2.
      The small circle’s diagonal measures 2r. Therefore its area is 2r2. The large square’s area is d2 or 4r2.
      Therefore the ratio of the areas is 2:1.

  2. You wake up one morning to find an intact Boeing 747 in your front yard. You need to rent a crane to remove it. You need to determine the weight of the airplane in order to rent the correct crane. How do you figure out the weight of the airplane?

    I’d look it up on Google.
    But assuming I don’t have Google I’d guess like this:
    Plane can carry 500 passengers. Each passenger weighs 200 lbs plus about 100 lbs for a chair and 100 lbs for luggage and food. Let’s round up to 1000 lbs. That comes out to 500,000 lbs.
    Let’s assume the plane should be about 10 times heavier to carry such a load which is about the ratio between a car and a full passenger load.
    Therefore I will guess a Boeing 747 weighs between 5 and 10 million lbs.

  3. On a traditional analog clock, how many degrees separate the hour and minute hands at 3:15?

    Minute hand is at 90 degrees, where 3 is located.
    The hour hand is at the 3 plus 25% of the way to 4. There is 360/12 degrees between each numeral.
    Therefore the difference between the hour and minute 360/12/4 which is 7.5 degrees.

Linked List Interview Questions

  1. Implement Insert and Delete for a Singly Linked List.
    public interface Link<E> {
    	public Link<E> getNext();
    	public void setNext(Link<E> link);
    
    	public Link<E> getPrev();
    	public void setPrev(Link<E> link);
    
    	public E getValue();
    	public void setValue(E value);
    }
    
    public class SingleLink<E> implements Link<E> {
    
    	public SingleLink(E value) { this.value = value; }
    
    	private Link<E> next;
    	private E value;
    
    	public Link<E> getNext() { return next; }
    	public void setNext(Link<E> next) { this.next = next;}
    
    	public Link<E> getPrev() { throw new UnsupportedOperationException(); }
    	public void setPrev(Link<E> prev) { throw new UnsupportedOperationException(); }
    
    	public E getValue() { return value; }
    	public void setValue(E value) { this.value = value;}
    
    	@Override
    	public boolean equals(Object obj) { return this.value.equals(obj); }
    
    	@Override
    	public String toString() { return getValue().toString(); }
    }
    
    public abstract class LinkedList<E> {
    
    	protected abstract Link<E> createHead(E value);
    	protected abstract Link<E> removeHead();
    	protected abstract Link<E> append(Link<E> tail, E value);
    	protected abstract void chain(Link<E> from, Link<E> to);
    	protected abstract void deleteAfterHead(E value);
    	protected abstract boolean isInsert(Link<E> link);
    	protected abstract boolean isEnd(Link<E> link);
    
    	public void insert(E value) {
    
    		if (head == null) {
    			createHead(value);
    			return;
    		}
    
    		Link<E> tmp = head;
    		while (!isInsert(tmp))
    			tmp = tmp.getNext();
    
    		append(tmp, value);
    	}
    
    	public void delete(E value) {
    
    		if (head == null)
    			return;
    
    		if (head.equals(value)) {
    			removeHead();
    			return;
    		}
    
    		deleteAfterHead(value);
    	}
    
    	Link<E> head;
    }
    
    public class SinglyLinkedList<E> extends LinkedList<E> {
    
    	@Override
    	protected Link<E> createHead(E value) {
    		if (value != null) {
    			head = new SingleLink<E>(value);
    		} else {
    			head = null;
    		}
    		return head;
    	}
    
    	@Override
    	protected Link<E> removeHead() {
    		if (isEnd(head.getNext())) {
    			head = null;
    			return null;
    		}
    
    		head = head.getNext();
    		return head;
    	}
    
    	@Override
    	protected Link<E> append(Link<E> tail, E value) {
    		Link<E> link = new SingleLink<E>(value);
    		tail.setNext(link);
    		return link;
    	}
    
    	@Override
    	protected void chain(Link<E> from, Link<E> to) {
    		from.setNext(to);
    	}
    
    	@Override
    	protected void deleteAfterHead(E value) {
    
    		Link<E> tmp = head.getNext();
    		Link<E> prev = head;
    		while (!isEnd(tmp)) {
    			if (tmp.equals(value)) {
    				chain(prev, tmp.getNext());
    				break;
    			}
    			prev = tmp;
    			tmp = tmp.getNext();
    		}
    	}
    
    	@Override
    	protected boolean isInsert(Link<E> link) {
    		return isEnd(link.getNext());
    	}
    
    	@Override
    	protected boolean isEnd(Link<E> link) {
    		return link == null;
    	}
    }
  2. Implement Insert and Delete for a Doubly Linked List.
    public class DoubleLink<E> extends SingleLink<E> {
    
    	public DoubleLink(E value) { super(value); }
    
    	private Link<E> prev;
    
    	@Override
    	public Link<E> getPrev() { return prev; }
    
    	@Override
    	public void setPrev(Link<E> prev) { this.prev = prev; }
    }
    
    public class DoublyLinkedList<E> extends SinglyLinkedList<E> {
    
    	@Override
    	protected Link<E> createHead(E value) {
    		if (value != null) {
    			head = new DoubleLink<E>(value);
    		} else {
    			head = null;
    		}
    		return head;
    	}
    
    	@Override
    	protected Link<E> removeHead() {
    		head = super.removeHead();
    		if (head != null) {
    			head.setPrev(null);
    		}
    
    		return head;
    	}
    
    	@Override
    	protected Link<E> append(Link<E> tail, E value) {
    		Link<E> link = new DoubleLink<E>(value);
    		tail.setNext(link);
    		link.setPrev(tail);
    		return link;
    	}
    
    	@Override
    	protected void chain(Link<E> from, Link<E> to) {
    		from.setNext(to);
    		if (to != null) {
    			to.setPrev(from);
    		}
    	}
    
    	@Override
    	protected void deleteAfterHead(E value) {
    
    		Link<E> tmp = head.getNext();
    		while (!isEnd(tmp)) {
    			if (tmp.equals(value)) {
    				chain(tmp.getPrev(), tmp.getNext());
    				break;
    			}
    			tmp = tmp.getNext();
    		}
    	}
    }
  3. Implement Insert and Delete for a Sorted Linked List.
    public class SortedLinkedList<E> extends SinglyLinkedList<E> {
    
    	@Override
    	public void insert(E value) {
    
    		if (head == null) {
    			createHead(value);
    			return;
    		}
    
    		Link<E> tmp = head;
    		Link<E> prev = null;
    		// XXX: yuck, dynamic casting to Comparable
    		while (!isEnd(tmp) &&
    	Comparable<E>) tmp.getValue()).compareTo(value) < 0) {
    			prev = tmp;
    			tmp = tmp.getNext();
    		}
    
    		Link<E> link = new SingleLink<E>(value);
    		if (prev == null) {
    			link.setNext(head);
    			head = link;
    		} else {
    			prev.setNext(link);
    			link.setNext(tmp);
    		}
    	}
    }
  4. Implement Insert and Delete for a Circular Linked List.
    public class CircularLinkedList<E> extends DoublyLinkedList<E> {
    
    	@Override
    	protected Link<E> createHead(E value) {
    		head = super.createHead(value);
    		if (head != null) {
    			head.setNext(head);
    			head.setPrev(head);
    		}
    		return head;
    	}
    	
    	@Override
    	protected Link<E> removeHead() {
    		if (head.getNext() == head) {
    			head = null;
    			return null;
    		}
    		
    		Link<E> prev = head.getPrev();
    		head = head.getNext();
    		head.setPrev(prev);
    		prev.setNext(head);
    		return head;
    	}		
    
    	@Override
    	protected Link<E> append(Link<E> tail, E value) {
    		Link<E> link = new DoubleLink<E>(value);
    		tail.setNext(link);
    		link.setPrev(tail);
    		link.setNext(head);
    		head.setPrev(link);
    		return link;
    	}
    	
    	@Override
    	protected boolean isEnd(Link link) {
    		return link == head;
    	}
    
    	@Override
    	protected boolean isInsert(Link link) {
    		return link.getNext() == head;
    	}
    }

Data Structures Interview Questions

  1. Find the largest int value in an int array (try to not use native functionality like “max()”)
    	public static int max(int [] array) {
    		int max = Integer.MIN_VALUE;
    		for (int ii = 0; ii < array.length; ii++) {
    			if (array[ii] > max)
    				max = array[ii];
    			if (max == Integer.MAX_VALUE)
    				break;
    		}
    		return max;
    	}
  2. What’s the difference between a stack and a queue?
     
    Stacks are LIFO, i.e. last in, first out. You push things on top of the stack and pop them off the stack.
    Queues are FIFO, i.e. first in, first out. You push things in one side, pop them off the other.
     
  3. Write a function to reverse a string (try to not use native functionality like strrev() or text[::-1])
             char * strrev(char * str) {
               int ii = 0, jj = strlen(str) - 1;
               char tmp;
               while (ii < jj) {
                 tmp = str[ii];
                 str[ii++] = str[jj];
                 str[jj--] = tmp;
               }
               return str;
             }
  4. Write a function that determines if two strings are anagrams. From wikipedia: an anagram is “the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.” (“abc” “bac” “cba” are anagrams, “abc” and “bba” are not)
  5. /**
     * Returns 1 if it's an anagram, 0 otherwise.
     */
    int anagram(char * str1, char * str2) {
    
      // quick check
      if (strlen(str1) != strlen(str2)) {
        return 0;
      }
    
      // copy str2 to our tmp
      char * tmp = malloc(strlen(str2) + 1);
      strcpy(tmp, str2);
    
      int ii = 0;
      while (str1[ii] != 0) {
        char * ch = strchr (tmp, str1[ii]);
    
        // if not found return -1 to indicate not an anagram
        if (ch == 0)
          return 0;
    
        // remove this found letter from second string
        ch[0] = 0;
        if (ch == tmp) {
          tmp = ch + 1;
        } else if (*(ch+1) != 0) {
          tmp = strcat(tmp, ch+1);
    	}
    
        // go to next character
        ii++;
      }
    
      return 1;
    }

Computing Basics Interview Questions

  1. Use recursion to write a function that determines the length of a string
    int strlen(char * str) {
      if (str[0] == 0)
        return 0;
      return 1 + strlen(str + 1);
    }
  2. What’s the number after F in hexadecimal?0x10
  3. Bitwise: what is 7 | 1? 7 & 1? ~7?

    7 (0111). 1 (0001). -8 (1000).

  4. Write a script that prints the numbers from 1 to 100. But for multiples of four print “Four” instead of the number and for the multiples of seven print “Seven”. For numbers which are multiples of both four and seven print “FourSeven”.
    for (int ii = 1; ii <= 100; ii++) {
    	boolean isMultipleOfFour = (ii % 4 == 0);
    	boolean isMultipleOfSeven = (ii % 7 == 0);
    	if (isMultipleOfFour && isMultipleOfSeven)
    		System.out.println("FourSeven");
     	else if (isMultipleOfFour)
    		System.out.println("Four");
     	else if (isMultipleOfSeven)
     		System.out.println("Seven");
    	else
    		System.out.println(ii);
    }

ATG Consulting Interview

Today I had the most detailed but at same time most interesting ATG consulting interview yet. Here are the questions I was asked with answers when appropriate in italics.

  1. Which versions of ATG have you worked with?
  2. What parts of ATG’s stack have you worked with?
  3. How do you compare ATG with Ruby on Rails?
  4. What is Nucleus?
  5. What is the ATG Repository?
  6. When creating form handlers typically what ATG base class do you extend? GenericFormHandler.java
  7. When creating droplets what ATG base class do you extend? DynamoServlet.java
  8. What form handlers and methods do you use during checkout? ShoppingCartFormHandler, numerous handlers like handleMoveToConfirm, etc.
  9. What does a user typically see during checkout? Add to shopping cart, login, billing and shipping address, payment, confirm, confirmation, email confirmation, shipped email.
  10. How do you compare strings in Java? If String a = “hello” and String b= “hello” what is a == b? True, a and b both reference the same constant string.

In another interview I was asked these questions.

  1. What is HTTP? How does it work?
  2. If HTTP is stateless then how does a web application maintain state.