The Interview Game - Part I

Introduction

Do you want to work at a top company of Nasdaq. Ok. Go ahead, but be aware with the interviewing process. It could be not so easy as you would like to. Companies as Amazon, Google, Microsoft have famous hard selective process. So, I will try my best to help you to improve your results.

In these posts, I will talk about questions that I have been asked and what solutions I found as more appropriated. To be simpler, I will divide questions in 2 groups: general technical knowledge and algorithm questions.

This post is about the first group…

General Technical Knowledge

1. What is TCP? What is UDP? What is fundamental difference between each one?

   TCP is a network protocol that provides reliable, ordered, error-checked delivery of a stream of octets between programs running on computers connected to a local area network, intranet or the public Internet. TCP could be seen as a facility to communication.
   
   As TCP, UDP is a network protocol however UDP provides communication without prior communications to set up special transmission channels or data paths. And, by doing this UDP is a simpler protocol and useful when time is preferred rather than reliability.

2. What happens in a mouse click?

   Yes! I have already prepared an answer for this question.
   

3. What it is Permgen? How works Java memory?

   Java Memory is basically simple: for execution propose, Java uses a stack to maintain locals variables and return point. To non-locals variables, Java uses Heap Memory. Heap memory is divided by 3 areas: Eden (young generation), Tenure and Permgen. Tenure is divided in two parts: Survivor and Survivor 2.
   
   What is the basic idea behind tenure and eden regions. Verify if an object is collectable by garbage collector is a expensive operation. So, rather than verify every single object in GC operation, JVM implementations verify often newer objects. If an object survive a gc operation, the object is promoted to an area with older objects. So GC will visit younger areas often.
   
   Perm area is different story. A Perm Area is a special area in JVM Memory to store class metadata and the String pool. Garbage collector in a permgen area is very vendor-specific and it could never happen.

4. How is implemented a HashMap in Java?

   
   It is kind of weird question. Understand how a hash works is so much more important than know particularities about Java HashMap. If you know hash concepts just take a look in Java code: Grepcode: HashMap.java and Docjar: HashMap.
   
   In general lines, Java HashMap has an vector of Entry(ies). The hash function will hash object to an specific position of Entry Vector. Entry is an inner class that implements a linked list where each node holds a pointer to next one, and the pair key-value. As you should know, hashcode could have colisions (two different objects could have the same hashcode; In Java HashMap this problem is solved putting all objects with same hashcode in a linked list).
   
   Other details are related with hash function. I strongly suggest take a look at Cormen at al. but you could read hashmap internal implementation analysis in java and  hash functions.

5. How to implement a LRU cache?

   
   Least Recently Used (LRU): discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping age bits for cache-lines and track the Least Recently Used cache-line based on age-bits.
   
   Java language already has a class to do that. A LinkedHashMap (oh! Dammit. How could I have forgotten that?). http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html But, if you want to implement it by hand that will not be so hard. You will need a HashMap and a linked list of course. But, pay attention. As HashMap implementation, your internal structure needs to hold the pair key-value. I implemented at least twice, once in Ruby, other in Java. Let’s see:
   

   import java.util.HashMap;
   import java.util.Map;
   
   
   public class LinkedHashMap<K, V> {
   
   private Map<K, Node> map = new HashMap<K, Node>();
   private Node head;
   
   private int capacity;
   
   public LinkedHashMap(int capacity) {
       this.capacity = capacity;
       head = new Node(null, null);
       head.add(head); 
   }
   
   public void put(K k, V v){
       Node node = new Node(k, v); 
       map.put(k, node);
       head.add(node);
       if (map.size() > capacity) {
           Node previous = head.previous;
           previous.remove();
           map.remove(previous.k); 
       }
   }
   
   public V get(K k){
       Node node = map.get(k);
       if (node == null){
           return null;
       }
       node.remove();
       head.add(node);
       return node.v;
   }
   
   
   public class Node {
       public Node(K k, V v) { 
           this.k = k;
           this.v = v;
       }
       private Node previous, next;
       private V v;
       private K k; 
   
       public void add(Node node){
           if (next != null) next.previous = node; 
           node.next = next;
           next = node;
           node.previous = this;           
       }
   
       public Node remove(){
           Node node = previous;
           node.next = next;
           next.previous = node;
           return this;
       }
   
   }  
   }    
   

   
   My ruby implementation:
   

   require "./linked_list"
   
   class LRU
     attr_reader :head, :capacity, :map
   
       def initialize(capacity)
         @map = {}
           @capacity = capacity
           @head = Node.new
           head << head 
       end
   
       def []=(k, v)
       return unless [k].nil?
           node = Node.new(:k => k, :v => v)
           map[k]= node
           head << node
           if (map.size > capacity) 
               previous = head.previous
               previous.remove
               map.delete(previous.v[:k])
           end
       end
   
       def [](k)
           node = map[k]
           return nil if node.nil?
           node.remove
           head << node
           node.v
       end
   
       def to_s
       head.map { |n| n.v[:v]}.to_s
     end
   end 
   

   
   In my implementation, my linked list is a double linked list. The main reason to do that is simpler to implement a circular linked list. In initialization just put point the head of linked list to itself:
   
   

   head << head 

   Once you have a circular list is very obvious how to get the first element and the last element of the list: Just go forward and backward from head element.
   
   

6. How to implement a Furniture Factory Test Simulation?

   (Writing... wait) This question… oh my. Let’s see first the problem. Image you have a furniture factory that produces many kind of furnitures: chairs, dwarf gardens, tables.(...)

7. How to implement a Singleton in Java?

   It is tricky but simple question. Take a look at the following class:
   

   class Singleton {
     private static Singleton single;
   
     public static getInstance(){
       if (single == null){
         // critical region
         single = new Singleton();
       }
       return single;
     }
   }
   

   The tricky part: in the very moment in first access of getInstance method single instance is null. Two simultaneous accesses to this method will put in a race condition. Both process could achieve the critical region and get a different instance of Singleton. To avoid that you could use mutex solution with synchronization. Here some solutions:
   

   class Singleton {
     private static Singleton single;
   
     public syncrhonized static Singleton getInstance(){
       if (single == null){
         // critical region
         single = new Singleton();
       }
       return single;
     }
   }
   

   Other one:
   

   class Singleton {
     private static Singleton single;
   
     public static Singleton getInstance(){
       if (single == null){
         single = getNewInstance();
       }
       return single;
     }
   
     // ha! synchronization  only when necessary
     public syncrhonized static  Singleton getInstance(){
       if (single == null){
         single = new Singleton();
       }
       return single;
     }
   
   }
   

   But, the first access to Class is synchronized too. Classloader load a class only once. So, you could use this:
   

   class Singleton {
     private static Singleton single = new Singleton();
   
     public static getInstance(){
       return single;
     }
   }
   

   Drawback: in this situation, class loading will be slow. Class will not be available until single instance will be constructed.