Tuesday, February 20, 2007

PDFTron Interview

I had an interview for a summer internship position with a local software company called PDFTron this morning. I think the interview went pretty well. There were some typical questions asking about my experience and job expectations, as well as some more technical questions involving programming concepts. They also gave me four programming tasks which I had to implement using C++ (writing out code on a piece of paper):

1) Write a function which converts a string to a positive integer. Ignore the '+' and '-' characters, return 0 if the string is empty, and return any interpreted digits if a non-numerical character is encountered. Here was my solution:

int atoi (char * string)
{
if (*string=='\0') return 0;
int value = 0;
while (*string!='\0')
{
if (*string=='0') value+=0;
else if (*string=='1') value++;
else if (*string=='2') value+=2;
else if (*string=='3') value+=3;
else if (*string=='4') value+=4;
else if (*string=='5') value+=5;
else if (*string=='6') value+=6;
else if (*string=='7') value+=7;
else if (*string=='8') value+=8;
else if (*string=='9') value+=9;
else if (*string=='+') value/=10;
else if (*string=='-') value/=10;
else return value/10;
value*=10;
string++;
}
return value/=10;
}

2) Swap positions of the nibbles in a byte:

char nibbleSwap (char byte)
{
char nibble1 = byte&0xF0;
char nibble2 = byte&0x0F;
return ((nibble1/16)|(nibble2*16));
}

3) Write a function which computes x to the power of n using O(log n) multiplications.

int power (int base, int n)
{
if (n == 0) return 1;
if (n == 1) return base;
int half = n/2;
int value = power(base, half);
if (n%2==0) return (value*value);
else return (value*value*base);
}

This has a recurrence relation of T(n) = T(⌊n/2⌋) + Θ(1) for n>=2 and T(n) = Θ(1) for n<2. T(n) is ∈ Θ(log n).

4) Implement a function which draws a line, given coordinates for a start point, coordinates for an end point, and a two dimensional array representing grayscale pixels (8 bits per pixel). I didn't get around to attempting this question since I ran out of time.
Post a Comment