Microsoft Deputy CEO Puzzle

Yesterday I got a mail from one of my friend whose title read as: FW: Microsoft Puzzle. I just click opened the mail to have a look at the puzzle. Though I am not too sure if this puzzle was really asked my the Microsoft HR team for recruiting their Deputy CEO. Anyways by any chance, if it was really asked by the Microsoft HR Team, I thought it worth sharing with you all.

Click for the puzzle here

Try out the puzzle. The deputy CEO was given 15 minutes so you deserve atleast that [:P]. Anyways, if after 15 minutes or half an hour you are still scratching your head, feel free to see the answer below the puzzle.

Enjoy and have fun solving the puzzle.
Abhinav

My Interview with Yahoo-Inc! (Part 1)

Hello Friends,

Last month I was interviewed by Yahoo-Inc! for a job as software engineer. Here I would like to point out the discussions and various question/answer sessions I went through before I got my confirmation letter 🙂 Probably someone looking to join yahoo can take some tips from here.

In total I went through 7 rounds of interview (1 telephonic, 1 HR, 1 with Manager, 3 technical, 1 general aptitude). I will try my best to recall and summarize all of them for you all. But before I go ahead, I would like to thank my good friend Rajib Das for forwarding my resume in Yahoo and providing me with an opportunity to have a crack at it. Here I go:

  • Telephonic Interview: As it happens with all multinational firms, you go through a telephonic screening before you are actually called for a face-to-face interview. One good thing which happened for me even before the interview started was that, the interviewer already went through my CV thoroughly before interviewing me & he also checked my website Altertunes before interviewing me. You can be unlucky at times, if the interviewer comes with an open mind and try to test you in areas where you lack deep knowledge.

    My telephonic interview started early in the morning around 10 o’clock. It started with general about me questions. With my experiences I have learnt that these about me  sessions decide to a certain extent where your interview will head to. Hence, I always try to attract interviewer’s attention on my strong areas i.e. Audio Processing and web development.

    Next luckily for me he started discussing about Altertunes and various technologies used in developing the same. He specifically asked me questions like:

    1. How have you build the spell checker algorithm for Altertunes ?
    2. From where are you playing all the mp3 files ? Are they on your server ?
    3. If you have to, how will you implement the Orkut’s people connection algorithm ? i.e. If User A visits User C’s profile where User C is not a direct connection of User A, then Orkut shows a possible shortest connection. Something like this User A -> User B -> User C.
    4. What considerations have you taken while building the auto-suggest feature for Altertunes ?

    Though in my opinion a concrete answer do not exist for any of the above questions. There can be many possible solutions for every question he asked me. Here are my answers to his questions.

    1. I have used the spell checking algorithm as described by Peter Norvig, the director of research at Google in his post here. Many say, the 20 lines of code written by him in python is pure genius, and truly without any doubt it is one of the shortest and most efficient code that one can ever see. However for Altertunes, I have used a tweaked version of the same coded in PHP. For me the 20 lines code in python took 74 lines in PHP, however the results are just excellent for Altertunes. My spell checker for Altertunes gives over 90% accuracy for single word artists and over 80% accuracy for multiple word artists.
      Another simple but less accurate approach which I tried earlier was by using PHP’s inbuild function SOUNDEX, which is a phonetic algorithm for indexing names as sound, as pronounced in english. Read more about SOUNDEX here. However, the spell checker using SOUNDEX is not as accurate as the algorithm described by Peter Norvig.

    2. The answer to this question lies in one work Crawlers. I wrote crawlers in PERL which crawls the web for mp3 files and index them in the Altertunes database. However this answer didn’t satisfied the interviewer and he asked me Can you explain the architecture which you follow for developing crawlers? Probably he wanted to hear the word resolver from me, because as soon as I started telling him about resolvers he stopped me in between and proceeded to the next question. For more hint on how have I used PHP to develop web crawlers for Altertunes read here.
    3. Answer to the third question was probably hidden in the question itself. Shortest Path, is what we want hence we will obviously use one of the shortest path algorithm. As I didn’t had much knowledge on shortest path algorithms then, I suggested Dijkstra algorithm as the most appropriate for this task. However when I later discussed this problem with one of my friend, he told me probably Breath First Search (BFS) will be best suited for this problem.
    4. Here actually he asked me How have you developed the auto-suggest feature for Altertunes? For which I replied in one work AJAX. However, probably he wanted some more technical stuff on this topic and hence the next question he fired was What considerations have you taken while building the auto-suggest feature for Altertunes ? I still don’t really know what exactly was he looking for. My reply to him was, ‘I am sending each and every word typed in the input box to the server and getting response to all requests. However before sending the next request I wait for the previous response to come as I wanted my users to experience an incremental search.’

    I thought this was all that he will ask me for the telephonic interview, but ailaaa ! He started firing some questions from general algorithm and aptitude. A few questions which he further asked me were:

    • Given a tree, how will you create a mirror image of the tree? What algorithm will you use? What traversal will you prefer? 🙂
    • There is a link list, which contains a closed loop in it. How will you determine that closed loop in the link list? 🙂
    • Given a few numbers, how will you push them into a stack such that whenever I pop the top most element from that stack, I get the minimum number from the bunch. Also he wanted me to tell the pop push algorithm such that the order of insertion and popping should be O(1). 🙁
    • Given two log of wood which burns completely in 1 hour each. How will you determine 45 minutes.

    Hopefully this was all which I was asked in my telephonic interview. Within 10 minutes of the interview I received a call from the HR, asking me to come for a face-to-face interview which I scheduled for a week later. As I already got a feel of what all will be coming in the face-to-face interview, I didn’t wanted to go under prepared.

  • Face-to-Face Round 1: Before going for the in person interview, I tried my best to make myself familiar with the mother of all algorithm books by Cormen. You can download an e-copy of the same from here, size is about 10 Mb. Alternately you can search for -inurl:htm -inurl:html intitle:”index of” +(“/ebooks”|”/book”) +(chm|pdf|zip) +”cormenin google and get loads of sources for the same. You may change the search string to find other books from different formats. Anyways coming back to the interview.

    Just like my telephonic interview, the 1st round started at sharp 10 o’clock. The interviewer seemed liked a mixed bag to me. He tried to ask me questions ranging from C++, PERL, PHP, Java, Client-Server Model, Probability and even general aptitude. Here are a few questions which I can recall that were asked from me:

    1. Given a HTML page, how will you represent the same in XML format ?
    2. What are the advantages of Hidden Markov Model over other pattern recognition algorithms ?
    3. Yahoo is organizing an online programming competition and I am the head. There will be over a few million programmers participating in this contest. I have a set of 10 programming questions with me, which I give to each programmer one by one. As the programmer submits the solutions I check it, and if found perfect I give him the next question. Who-so-ever completes the 10 programming questions first is the winner. You have to award top 10 programmers. How will you go about developing such a system ? What all precautions will you take while developing such a system ? How many CPU will be required for such a system ? How will you protect the system from going down, in cases when a programmer tries to submit a virus as a solution ? etc etc
    4. Whats the probability that, my and your birthday lies on the same date and same day of the year ? (There were about 3-4 probability questions that he asked me)
    5. Draw and explain the whole client-server model ?
    6. Explain in detail, what all happens from the moment one submit a URL in the browser till the user sees the requested page on the browser?
    7. Write algorithms for Breath First Search (BFS) and Depth First Search (DFS) ? Which one is preferred over the other and why ?

    Then like the telephonic interview he fired almost the same set of questions over Altertunes. Probably there were a few more which I can’t recall at this point. Possibly the ones which I wasn’t able to reply. 😉 And that was it.

  • Face-to-Face Round 2: This was a complete session on aptitude level questions, which just kept coming one after the another. Some questions over which you can probably spend the whole day and say ‘This can be done the other way round too‘. Here are a few that I remember as of now:
    1. You have to weight all the weights between 1 and 100. Tell minimum number of weights required to do the same? (Probably the answer I gave was, weights which are a power of 2 i.e. 1,2,4,8,16,32 and 64)
    2. You have to weight all the weights between 1 and 100. Tell minimum number of weights required to do the same, however in this case you can use both pans to measure a particular weight ? For eg. If we need to weight 2 Kgs we can have 3 Kg weigh on one side and a 1 Kg + 2 Kg weight on the other side. (Probably the answer I gave was, weights which are a power of 3 i.e. 1,3,9,27…)
    3. You have a few eggs and there is a 100 level building. Determine the minimum number of attempts required to detect the floor from which, if we drop the egg it will break ? (Always consider the worst case that the egg will break at the top floor and for minimum attempts proceed from lower floor to top floor in non-uniform steps. Probably I was able to do this in 14 tries. Check if you can do the same :P)
    4. There is a huge string containing letters. Now in the string there are a lots and lots of palindromes. You need to find out the palindrome of the longest length. How will you do the same ? (Note: When I was reached the solution using stacks and queues, to complicate things he told me that a palindrome can further have a palindrome within it for eg. PALINDROMEDALADXYXDALADEMORDNILAP , hence we see the string has DALAD as a palindrome which is hidden in the full string which is a palindrome of bigger size.)
    5. There is a link list which have a lot of circular loops into it. How will you find the longest loop in the link list ?
    6. You have a very very large text file containing words. Consider that you can’t read it fully in the memory at once. How will you go about finding a word in the text file ?
    7. You have a very very large text file containing numbers. Consider that you can’t read it fully in the memory at once. How will you go about arranging the numbers in ascending or descending order ?
    8. A few questions on probability were discussed.

    There were a lot more which he asked from me. I guess there are easily 7-8 questions more that he asked from me. However this was the most interesting round that I had over the whole interview.

Probably thats enough for the first post. I will continue to write about my other rounds in upcoming posts. Till then if you have any questions or comments feel free to post them here.