## Interviews

Despite my background and resume, I am actually really bad at interviews, except for technical interviews, in which case, I am actually really good. However, if the interviewer pops up a nontechnical question and I get the least bit nervous, I often become inarticulate, incoherent, and can kiss the interview goodbye--not always, depending on the phase of the moon, since I can be sometimes be very eloquent. I haven't really isolated the reason for my inconsistency in communication skills--why sometimes I am really elegant, and, at other times, I seem retarded; I know it has something to do with my comfort level in situations.

I guess I am the sort of person who doesn't get out much, like the scientist (played by Star Trek's data) in *Independence Day*. I can program all day and night and not have any contact with anyone.

In technical interviews, I often amaze the interviewers and teach them a trick or two. In some technical interviews, I would argue with the interview about the correctness of my approach and then present a mathematical proof of my approach.

In my Excel interview, the interviewer was somewhat concerned about my combative attitude, but was very admiring of my technique. He hired me. Little did he know that poor social skills and teamwork skills came along with technical skills. I had a yearly review, in which my manager said that my review is unlike anyone else's, because my reviews always dealt with my communication issues rather than meeting goals or merit.

Fortunately, I am not looking for a job, but trying to create my own.

When I interviewed for Microsoft Excel in 1994, I was asked the following few questions. I don't think these questions are asked anymore.

int BinarySearch(int array[], int v, int length) { int min = 0; int max = length-1; while (min<=max) { int mid = (max+min)/2; int cmp = v - array[mid]; if (cmp<0) max = mid-1; else if (cmp>0) min = mid+1; else return mid; } return -1; }

Now, this is the most concise way of writing BinarySearch, and I couldn't imagine writing it any other way. I wrote this really quickly, in about 2 minutes, and the interviewer was amazed at the speed. He gave me a few curve balls, asking me what if there are duplicates how do I get the index of the first value. Well, I added an extra condition at the end:

else if (mid>min and array[mid-1]) max = mid-1;

It was less than five minutes into the interview. The interviewer expected this question to take entire hour of the interview, so I got a free ride. This seemed like such a easy problem, that I found it difficult to believe others would have trouble. Years later, I saw other people's implementations, all of which were convoluted and incorrect, so it can't be that easy.

I had another interview asking me to delete a node from a linked list. Now, I also wrote this very quickly in about 5 minutes, but I used a rarely used technique with double pointers, which blew the interviewer away. I remember him saying, "Who would ever think to use double pointers?"

void Delete(LinkedList **list, int v) { while ( (*list) != null) { if ( (*list)->v == v ) { LinkedList *del = *list; *list = (*list)->next; free(del); return; } list = &(*list)->next; } }

To delete the node, you must call the Delete( &listHead, v). This is more compact and faster than other approaches that I have seen. As you can see, I am very minimalistic.

The interviewer wanted me to write a FAST bit counter, in which I wrote this routine. This just takes advantage of a little known trick combining arithmetic and logical operators. There are other more readable ways, but this is proportional to the number of bits, so it is faster than bit shifting, but not as fast as table lookup. I just knew that the interviewer wanted me to try the bit shift approach first, and see if I could come up fancy approach later.

On the other hand, there is another technique that I discover in the web that can compute the bitcount in an ingenious way with at most 5 adds and 5 shifts operations.

int BitCount(int v) { int count = 0; while ( v != 0 ) { v &= v-1; count++; } return count; }

I had another question on permutating a list with equal probability for all possibilies, in which the interviewer questioned my approached and I ended up correcting him with a mathematical proof. I also had a few riddles, each of which I answered trivially. It helped that I used to love solving puzzles and riddles and competed in competitions in my early years. I'll share those on a later post.