Tag Archives: interview

Print matrix elements in spiral order

This is one of the common interview questions used to test how cleanly you can code without ending up in knots handling the indexes.

Problem statement:

Given an N x M matrix, print the elements in spiral order.
Example for matrix:
[
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14]
]

Output would be 1 2 3 4 5 10 14 13 12 11 6 7 8 9

Solution:
There could be various ways of solving this. I am sharing the approach I used to solve it.
The idea is to keep 4 indexes to track the matrix boundaries, start with a direction value pointing to right initially and then once it hits the right most boundary, change direction and update the relevant boundary value.
For example, when we are going in right direction, and we hit the boundary, we need to go clockwise and change to go down next and we also need to increment the xMin value as we have covered the row corresponding to that xMin value.

public static void printSpiral(int[][] matrix, int n, int m) {
    int xMin = 0, yMin = 0, xMax = n - 1, yMax = m -1;
    // Current co-ordinates
    int x = 0, y = 0;
    char direction = 'r';
    while (xMin <= xMax && yMin <= yMax) {
        // Get the next direction
        switch(direction) {
        case 'd': if (x == xMax) {direction = 'l'; yMax--;} break;
        case 'r': if (y == yMax) {direction = 'd'; xMin++;} break;
        case 'u': if (x == xMin) {direction = 'r'; yMin++;} break;
        case 'l': if (y == yMin) {direction = 'u'; xMax--;} break;
        }
        // Print the current co-ordinates
        System.out.print(matrix[x][y] + " ");
        // Update the current co-ordinates
        switch(direction) {
        case 'd': x++; break;
        case 'r': y++; break;
        case 'u': x--; break;
        case 'l': y--; break;
        }
    }
}

Facebook Interviews-3

I used the time between the last round and this round to brush up my coding skills and review a few standard algorithms. I knew that my coding skills were not up to the mark as the interviewer would expect. I was just hoping that I get lucky this time as well and get through to the next round and in the time I get before next interview, I shall work on improving it. Fortunately, I didn't have to make that effort. So, here goes the description of what transpired in that interview.

I got the call from interviewer at the scheduled time. He introduced himself as Jeffrey and talked about the team he worked in (I remembered the interviewer's name this time but not the team or what he did). Like the last interview, this time also I was asked to create a document on collabedit.com and share it's key. After this, he asked me about my work experience and asked me about a situation in work life which I found challenging and how did I go on to face this challenge. He probed me further with similar HR type questions like describe a situation which you showcased your team-player skills. I wasn't expecting such questions in this interview as I was expecting it to be similar to last round. I tried to answer them as well as I could. He asked me what are the facebook products you like. After I named Facebook news feed, he asked me what feature you would like to add or improve to better the product. This was the last such type of question, before he got down to asking a technical question.

The question was:

In PHP, there is concept of single class inheritance i.e. a new class can extend an existing class. You are given a php source file which contains a few classes defined in it. You have to print the class hierarchy in the given desired format.
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:

A
        B
               C
        D
E

I said we could use a Tree data structure and do a BFS (Breadth First Search) to print it this way. Then I soon realized that I should use DFS (Depth First Search) instead and told him so. He asked me to go ahead and write down the code on how to parse the php file to get the desired output. I said we can use a left child-right sibling representation for the nodes of tree. I wrote down some code to show how parsing can be done. I could see myself that my code was half-baked. However, he let me off the hook on that code and asked me how to write down the printing function supposing I have constructed the tree and I have the root node. The task was simple for me at that point, write down the depth first search function for a node. But somehow, at that moment I wasn't thinking in terms of writing a simple recursive solution which could have done it easily. Then, I was thinking in terms of stack-based implementation of DFS. I didn't realize it at that time that I had to write the DFS not for a general graph, but for a simple tree structure. Hence, there were no complications of maintaining which nodes had already been visited. But I was thinking about how to handle the nodes already been visited while attempting to write the code and hence, the cluttered thought process which resulted in incomplete code in the stipulated time.

The interviewer interrupted me while I was struggling to write clean code, he said since he is running out of time, he asked me to stop writing the code and tried to reassure me by saying that I was on the right track. I too knew, I was on the right track but it was just that I was not using the right mode of transportation. I was trying to sail a ship on the road. He then asked me if I had a question to ask him, I asked him absent-mindedly similar questions that I asked from the HR contact. I don't remember what he said as I was having a conflicting thought running in my mind. I was thinking whether I should admit or not that I am a bit out of touch with coding. In the end, the confession mindedness prevailed over the practical mindedness.

I said to him that I had a confession to make that I am a bit rusty with coding and that's why I was struggling to write the code cleanly. I said that I was making efforts at that time to improve upon my coding speed and efficiency. I don't know what the interviewer would have felt but he agreed that I needed some work to do on my coding speed. Well, I don't know if my confession played a role in my rejection or was it the inability to give a proper solution to the question that led to my rejection. I believe that it was the latter.

A few days later, I got the email which tried to describe my rejection in the gentlest of words as possible.

Hi Anurag,

Thanks for taking the time to talk on the phone with us. Your background is impressive, and we enjoyed speaking with you.

Unfortunately, we will not be moving forward with you in the interview process at this time. The volume of interviews we’ve been conducting combined with the quality of candidates that we’ve been talking to often forces us to make difficult decisions.
....

Rejections are always hard to handle especially when expectations from self are high based on your own past record. It took me a few days of pep-talk to self to take in the feeling of rejection and be ready to go on about work and self in a normal way. After rejections, one usually has the options of either hitting the bar to drown himself or to raise the bar to perform better. I decided to choose the latter option and I did clear the raised bar (will write about what I meant and how I did it in one of the posts soon).

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).