Pular para o conteúdo principal

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.

Comentários

Postagens mais visitadas deste blog

Pequeno manual do ócio em terras alemãs

  Pequeno manual do ócio em terras alemãs Como Lei alemã favorece aproveitadoras (e alguns aproveitadores que nunca tive o desprazer de conhecer)   Há algumas vias pelas quais pessoas de países em desenvolvimento migram para países como a Alemanha.   Por exemplo, é sabido que países desenvolvidos sofrem de escassez de mão-de-obra qualificada. Por esse motivo, países como a Alemanha dispõe vistos "especiais" para profissionais em demanda. Esse é o conceito do Blaukart (Blue Card) que na Alemanha se destina a profissionais salário anual seja superior a 55 mil euros ou 43 mil no caso de profissionais de áreas em alta demanda. Não há como recrutar essa mão-de-obra sem que a família desses profissionais também possa ser relocada. Então esses profissionais e seus familiares são relocados.   Além de se qualificar para essas vagas em demanda, ou ser parte direta da família qualificada, outra via possível para a imigração para o território alemão é através do matrimôni

The escape of blue eyed vampires (answer)

The island of blue eyed vampires (answer) An initial idea Each one needs to figure out if him/herself is blue eyed. They assume having blue eyes and see how the others react. A technical details There are some variations to formalize this problem using different type of logic: modal logic, temporal logic, Public Announcement Logic and so on. I believe that those kind of prove are tedious to write and read. For now, I will write a sketch to a prove but I belive the best way to prove is using an algorimthm what basically, it would be an adaptation of DPLL algorithm (Davis–Putnam–Logemann–Loveland) that uses dedutive reasoning and prove by contraction. Legend \[\begin{matrix} BlueEyed(X) :X \text{ is blue eyed.} \\ Leave(X) :X \text{ leaves.} \\ O(y) :y \text{ holds at the next (temporal) state.} \end{matrix}\] In this temporal simplified logic, we have a set of state that holds the in- formation of days, \(W = \{d_0, d_1, d_2, d3 \ldots , d_n\}\) and transition \(S : W \rightarrow

Answering: top reasons I hate living in Brazil

Yes, some guys shared a teasing topic about “Top reasons why I hate living in Brazil”: http://www.gringoes.com/forum/forum_posts.asp?TID=17615&PN=1&title=top-reasons-i-hate-living-in-brazil What is the point here? The whole text is loaded of cliclés, people that you will hardly find, etc most of time just pissing people off.   I don’t think Brazil is the best country in the world. Also, I don’t think Brazilians don’t make mistakes. Actually we do all the time but most of us really care about our mistakes specially those were pointed out. Some feel like an expatriate, alien in own country. Others reflect about how we could improve. Others  simply don’t accept teases from John Does. So, I’m actually truly bothered with people believing in a bunch of false statements (specially Brazilians) or supporting some cynical arguments disguised “sincere” criticisms . Yes, I make mistakes all the time, and as most of Brazilians, I don’t speak English. However, I will