Category Archives: interview questions

Facebook Interviews-2

I had been waiting anxiously and nervously for the first telephonic round of Facebook. Finally, my phone rang a few minutes later than the scheduled interview time and I received the call. She apologized for the slight delay in calling and asked if it was still a good time to continue the interview. After I said yes, she introduced herself and said a few lines about the team she worked in. I neither remember the name of female interviewer nor the team she mentioned, perhaps because of the anxiety. She asked me to create a document on collabedit.com and share the key for that document. Once, she confirmed that she could see the document, she went ahead to ask me a coding question.

The question was:

You have to write a function which takes as input two sorted arrays A and B each containing n elements. Array A can hold upto 2*n elements where as Array B can hold upto n elements. Merge the elements of array A and array B into array A such that it is sorted. You can't use any additional data structure, you may only use extra constant memory space.

After thinking for about it for a while, I dived straight into writing the code in the online document shared with her. She asked me to elaborate what I was thinking before getting down to complete the code. I explained to her the algorithm, she was satisfied and asked me to go on and complete the code. After seeing my code, she said that it seems right. She then asked me what are the test cases that I would use to test before pushing this piece of code to production. I suggested testing this code with a few corner cases such as when the last element of array B is smaller than first element of array A and vice-versa, and a case when array A and array B were identical. She was satisfied with my response to this question. She then asked me another question.

The next question was:

You have to write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression passed as the other parameter. Return true if it matches, else false.
Regex may contain characters 'a-z', '.' and '*' where '.' matches any character and '*' means 0 or more occurrences of the previous character preceding it.

Examples:
1) a*b matches b,ab,aab
2) a.b matches aab, abb, acb,..., azb
3) .* matches all the valid strings formed by using the lowercase letters

This question was a bit tough to solve. I observed a few sample inputs and the corresponding regex patterns and started writing the code which would have worked for them but wasn't generic enough to suit especially the case when '*' was present in the regex pattern. After hitting my head against the wall for quite some time trying to solve it, the interviewer helped me by suggesting to think if I could solve this question using recursion. I started thinking on those lines and was able to come up with a recursive formula which for a specific example would read something like this:

checkRegex("a*b","aaab") = checkRegex("b","aaab") OR checkRegex("a*b","aab")

I conveyed this idea to her and how I could incorporate this idea into code. She said that I was on the right track but as time has ran out, she would have to end up this conversation then. I asked if I need to mail the code for this question to her after a few minutes. She said that it's not needed as you were proceeding on the right track.

I was not sure if I would clear this interview round but after 2 days, I got a mail from HR that I have cleared the round and my next round is scheduled on the coming Monday. I was relieved greatly to hear that as not clearing the first round of interview for an IIT CS graduate and employee of one of the big-named IT companies in the world, would have been a bitter pill to swallow, especially for me. I know the pressure of such expectations can be hard on oneself but sometimes one can't escape being a mere human. I was in a more relaxed mood while facing the next round which as it turned out ended up as being my last round (will write about it in next post).

Facebook Interviews-1

I applied for Facebook via the Careers link available on facebook.com which lists the open positions for a software developer. I submitted my resume to see if my resume clears the resume screening process and am I lucky enough to get a call. After a few days, I got a mail from a HR representative that they have received my resume and she would like to set up a telephonic conversation to know a little bit more about me, my background and experience and also tell me a bit more about the career opportunities available at facebook. After an exchange of few emails, we set up a telephonic conversation over Skype.

Finally the day in California (and the night in India) arrived, when I had my first telephonic conversation with a facebook employee. She told me beforehand that this conversation is not going to act as an elimination round. It's just a chance to know more about me. She proceeded further to probe me with questions related to my college background, my current company and experience, reasons for looking for change of company. I tried to give genuine responses to such questions. Though later, I realized that a bit of diplomacy wouldn't have hurt especially while answering the reason of looking for the change of company.

After asking such questions, she elaborated about the interview process. She said that there shall be 3 rounds of telephonic technical interviews in which I can expect to be asked to write the code on an online whiteboard like collabedit.com. Each round shall be an elimination round i.e. further progress depends on the result of previous interview. After clearing these 3 rounds, I shall be called onsite for 4 face-to-face rounds of interview. The interview process appeared very intensive and was designed to avoid getting a bad candidate get through the process. She then elaborated on how the new hires are given a chance to find a team based on their interest. She said that the new hires were given a boot camp session of six weeks in which they shall get a chance to know about all the products of Facebook. Then, they could select any team which interests them. The process sounded pretty cool and flexible. She asked me if I had any questions for her. I took this opportunity to ask a few general stereotype questions related to career growth prospects, flexibility of changing teams and what position are they hiring for.

At the end of our discussion, she said she shall get in touch with me and schedule the further technical rounds. Two weeks later, my first telephonic round was conducted about which I shall write about in my next post.

Finding factorial of a large number

In mathematics, the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5 ! = 5  \times  4  \times  3  \times  2  \times  1 = 120  \

0! is a special case that is explicitly defined to be 1.

When asked to write a program to compute factorial of a number, say n, we implement this definition into lines of code using a counter which iterates over the values from 1 to n and keep updating the result by multiplying the previous result with current value of counter. There is nothing wrong with this logic but the program fails to give correct results for 20! or higher. This is due to the limitations of the computing resources as the result becomes so large that it is not possible to store them in a 32-bit or 64-bit word.

Hence, to compute factorial of large numbers, we need to define our own logic.

Hint: Implement paper and pen method of multiplication without using Integer type variables.

Solution