Pular para o conteúdo principal

The Interview Game - Part II

I am trying to digest my last interview. What I did right and wrong.
As the previous event, I had 4 technical interviews but different from previous event, interviewers asked more times about my experience. What am I doing? What was my last big decision? What is interesting in my current job? And so on. This is something that I didn’t like because I have been working here for only 3 months in my new job so it was not easy to talk about things that I am still learning.
  • My first interviewer gave me 2 questions…I spend a good time with a bad solution in my second problem and that was an easy question. In the end I gave a good answer but I had already involved.
    Question 1: how to convert a file path (file path will always have root dir) to an canonical path. Ex: "/a/b/../c" $\Rightarrow$ "/a/c".
    Question 2: how to implement a data structure for control use of limited resources of 3 kinds. (Ex: Lock SA is a company that provide lockers to users in airport. When a new customer arrive, he can ask to keep his/her baggage there or to get back his/her baggage. Describe a data structure to handle that problem).
  • Second interviewer also gave me 2 questions…In the middle of first question, the interviewer ask me about how many byte a certain object will use: geez! I said that it was 3 *32 bytes when I would/should like to answer 3*32 bits or 3*4 bytes. Second, I gave a bad code answer but I fix it as soon as it was pointed as wrong. The 2th question I failed to provide a right answer. The interviewer gave me some tips and I fixed the code again but I couldn’t finish the question at time.
    Question 1: Let T a tree that holds arithmetic "operations" (ex: $+ \rightarrow
    5, + \rightarrow *, * \rightarrow 5, * \rightarrow 6$
    ). Let class Node with method eval(). (calling eval of previous root Node object should return 35). "Implement" this Arithmetic tree.
    Question 2: Implement an algorithm that returns a subset of a collection that provide the maximum product of n elements.
  • The third interviewer asked me many questions about my current job, my function, etc. After that, he ask me to “describe” a solution for Stamp E-Bay version. It was so abstract that I didn’t get if my propose was good enough or not.
    Question: Sketch a EBay Web site to sell/Buy Stamps.
  • The fourth interviewer was toughest but he was not the more challenging interviewer.
    • He asked about how long I had of experience and I said that was more than 8 years. He was not convinced because I have just finished graduation in 6 years. But this is a Brazilian reality.
    • He ask me about my Master’s Degree. I have closed my course although I was hoping finished that as soon as possible. Because I was Using Linkedin format, I provided a expecting conclusion year and the interviewer was no very happy with this expecting conclusion year since I had gave up of my Master’s.
    • Third, he asked me to implement an algorithm to verify if a digraph was an acyclic digraph…
    My solution simply tested all possible paths from sources vertices to end vertices individually. I know that solution was terrible, but I was scratching the first solution that came in my mind. The new question was... how is the complexity for this algorithm?
    In this point something sad happened. My answer was almost right. I said that should be something exponential like $O(\gamma^E)$ where $\gamma$ is average of outcome arcs, and E is number of arcs. But I was not convincing…
    I was trying to prove it reflecting about worst case scenario. Now improving that...
    $\gamma$ = Average outcome arcs = arcs / vertices
    Let G a graph with vertices $(a_1, a_2, \ldots a_n, b_1, b_2, \ldots b_n)$ and the follow configuration...
    $(a_1 \rightarrow a_2, a_1 \rightarrow b_2, \ldots a_{n-1} \rightarrow a_n, a_{n-1} \rightarrow b_n)$
    $(b_1 \rightarrow a_2, b_1 \rightarrow b_2, \ldots b_{n-1} \rightarrow a_n, a_{n-1} \rightarrow b_n)$
    The 2 ending vertices have no arcs. All others have 2 edges. So, all possible paths  = 2V − 2.In this case... edges, E = 2 * (V − 2). So, for this scenario the complexity will be O(2E).
    What was I doing wrong? I am not getting how to calculate gamma. What should the worst gamma be for complexity considerations for this algorithm?
    The right answer could consider how many arcs is possible from a digraph. And it should be V(V − 1) where V is number of vertices. But I knew that the algorithm find cycles. So, I was thinking that it should limit to a constant. But how many arcs could have the most complete acyclic digraph? At least (Sum of 1 .. n)/n. So gamma actually is proportional to number of vertices. The right answer is O(VE). I was wrong once again but in this time, the interviewer didn’t provide any tip.
    The second point is ... oh, it is so obvious that I can find cycles removing layers of the graph from border (fringe) to the inner part. It should be O(V + A). =(
    Question: Implement an algorithm to verify if a digraph is an acyclic digraph


Postagens mais visitadas deste blog

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

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

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