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


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…