# 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;
}
}
}


# Returning a random line from a file given as input

Problem Statement:

Given a file as input, you have to return back a string representing the contents of one of the lines present in the file. The algorithm should be designed in a way such that probability of each line getting returned is same i.e. if the file has $n$ lines, probability of each line getting returned as output would be $\frac{1}{n}$.

Constraints:

• The file should be scanned only once.
• There should be only constant extra space used.

Solution:

String getRandomLine(File file){
String output = null;
int linecount = 0;
Random r = new Random();
linecount++;
int rand = r.nextInt(linecount);
if(rand+1 == linecount){
}
}
}
return output;

Are you surprised that this simple method works? 😀

Explanation

The proof of correctness can be seen through mathematical induction on the loop invariant.

Statement is that after seeing n lines, the probability of each line as output is $\frac{1}{n}$

Base case: linecount=1, then first line is stored as output as rand is 1 in first iteration. So, 1/1 = 1

Hypothesis: Assume, that it works correctly, for linecount=k, such that probability of k lines seen so far is $\frac{1}{k}$.

Induction step: we read k+1 th line and we get a random number between 0 to k. Probability of each random number being generated is $\frac{1}{k+1}$. So, the probability of current line (if random number generated is k) being stored as output becomes $\frac{1}{k+1}$. Let's see what happens to probability of each of the previous k lines. The probability of getting a number in the range 0 to k-1 while generating a random number in this iteration is  $\frac{k}{k+1}$, and the probability of each of the previous k lines was $\frac{1}{k}$ at end of last iteration, so now multiplying these two probabilities, the probability of each of those k previous lines becomes $\frac{1}{k+1}$.

An exercise

In this solution, we are generating random numbers in the range 0 to k each time. Suppose, we wanted to cut down the time taken to generate random number in each iteration. So, we generated a random decimal number outside this loop in the range [0,1) and inside the loop, we multiplied that by linecount to get an integer in the range [0, linecount). Will this still give each line in file an equal chance of being the output string?

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.

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


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