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.

Comments

[leppie]

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

count will never increase, perhaps a bit to minimal. A better a approach.

int BitCount(int v)
{
int count = 0;
while ( v = v >> 1) count++;
return count;
}

[Wesner Moise]

Your version of BitCount fails to work due to a common mistake. It is not a BitCount function that you wrote, but rather a function similar to Log to base 2.

For example, 0x80000000 should return 1, but your function returns 31.

With bit shifting, you need to write it like this:

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

[leppie]

Thanks for pointing it out. I had my mind fixated "getting" the minimum bits for the value rather :)

[Leon Bambrick]

Hi Wesner, i have nothing intelligent to say like those other people, sorry.

just wanted to be picky and point out that the scientist in independence day wasn't Data from star trek ng, but jeff goldblum, from Jurassic Park and the Fly... he is also seen in the background of Annie Hall, as a flakey LA party guest putting a call through to his guru, because he'd 'forgotten his mantra'.

off topic? ok, i admit it.

[B. Garvelink]

I'm sorry Leon, but you're confused. Brent Spiner WAS in Independence Day and his character WAS (far) more fearful of daylight than Goldblum's.

Halfway across this page are some images.

:P

[Hugh Brown]

Wesner Moise:
The trick is that this algorithm strips off the bits, starting at the right. Take 7 (111b) as an example:
v = 111
v-1= 110
-> 110

v = 110
v-1= 101
-> = 100

v = 100
v-1= 011
-> = 000

So in three iterations, we have found that 7 has three bits set.

I believe that with a class definition like this:
class LinkedList
{
public:
int v;
LinkedList *next;
};

you could abbreviate your linked list code to this:

void Delete(LinkedList **list, int v)
{
while (LinkedList *tmp = *list)
{
if (tmp->v == v)
{
*list = tmp->next;
delete tmp;
return;
}
list = &tmp->next;
}
}

However, I may be misunderstanding the part about the double list.

I didn't see Independence Day but it looks like both Brent Spiner and Jeff Goldblum were in the film [1]. Based on the cast list, I'd say that Brent Spiner was the scientist (Dr. Brackish Okun). Who knew that Brent Spiner was so old? [2]

[1] http://us.imdb.com/title/tt0116629/
[2] http://us.imdb.com/name/nm0000653/

[Hugh Brown]

I think you can change this:
while (min0) min = mid+1;
else return mid;
}
to this:
while (min<=max)
{
int mid = (max+min)/2;
int cmp = v - array[mid];
if (cmp <= 0) max = mid;
else min = mid+1;
}
if (min < length && array[min] == v) return min;
else return -1;

and you pick up lowest matching value in the range. I think that's right but I have not tested the code.

Also, for reasons I can't quite remmeber but are related to integer overflow, it is recommended you write this:
int mid = (max+min)/2;
like this:
int mid = min + (max-min)/2;

If you like this kind of thing, check out this binary search coding challenge:
http://www.cix.co.uk/~solipsys/b_search/spec.htm

[Wesner Moise]

That's a more elegant approach, i agree.