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

Expressões, preconceito e racismo

Expressões preconceituosas e racistas Antes de alguma outra frase, primeiro peço licença para falar de mais um assunto do qual não domino. Falo por acreditar que um leigo presta serviço maior ao debater assunto com base em fontes (ainda que seja uma Wikipedia) e no pensamento lógico do que simplesmente se manter mudo a questões do cotidiano. Em voga agora está em falar quais são ou eram as expressões preconceituosas e racistas que até a pouco eram toleradas em muitos meios.
Como é covarde dizer que em boca fechada não entra racismo. O racismo não é perpetrado apenas por quem profere mas por quem se cala à agressão perpetrada a outrem. Mas veremos que a questão é muito mais complexa que os cães raivosos do politicamente correto querem dizer.
Tomo aqui a palavra racista, como sendo algo usado para impor a dominação de uma “raça” sobre outra. Portanto, a acusação de racismo vai muito além da mera acusação de preconceito. Não tenho o menor apreso por vitimismo barato, onde expressões que…

Um texto pós-moderno - better man

Espere olhando para as horas... são 4 horas. Tem que parar. Nesse tom melancólico, começa a modesta música "better man", uma balada pop composta por Eddie Vedder ainda na adolescência. A música é a ilustração perfeita da ironia. O próprio título é irônico, uma vez que em momento algum na música aparece um better man.

She lies and says she's in love with him, can't find a better man...

Irônico, não!? Para começar, com a personagem central da história, a mulher que aguarda tarde da noite seu esposo... Ela chega a treinar com o espelho o fim do relacionamento. E o que faz? Diz a negação do que queria dizer.

Vedder escreve músicas sobre sentimentos fortes. Sua relação com a mãe foi bastante complicada pelo o que descreve em suas canções. Na trilogia Mommy, Vedder descreve um homem perturbado com o relacionamento materno; a mãe mente para o filho sobre a identidade do pai, revela a verdade para o garoto na puberdade dizendo a ele como se parece com o verdadeiro pai e o leva …

Curry with JS

Partial application and currying with Javascript In the strict way, currying is the technique of transforming a function that takes multiple arguments (a tuple of arguments) to one function that receive only one. In such way, currying techniques allow transform one multi-parameter function in a chain of functions, each one with a single argument. Looks complicated? Blah.. it is not true.
In this little article, we are actually more interesting in partial applications. Let’s take the Mozilla Example for replace function in String. As we know, we can use a “replacer” function as paramenter for replace method in String object.
Let’s say that we want to split a String defined by a non-numerical part, a numerical part and finally a non-alphanumeric part. Here is how:
function replacer(match, p1, p2, p3, offset, string){ // p1 is nondigits, p2 digits, and p3 non-alphanumerics return [p1, p2, p3].join(' - '); }; We can try it as usual…
var newString = "abc12345#$*%".r…