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  = 2^V − 2.In this case... edges, E = 2 * (V − 2). So, for this scenario the complexity will be O(2^E).
  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(V^E). 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