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


Byron Knoll said...

Jason Harrison has pointed out that the following improvements can be made:

- the solution for atoi can be compressed by using the known ordering of digits in ASCII:

int digit;
if( *string >= '0' && *string <= '9')
digit = *string - '0'
value = value *10 + digit;
return value;

- the solution for swaping nibbles can be made faster by using left and right shift operators, event integer multiplications and divisions can be slower than shifts:

return (byte & 0xf0) >> 4 | (byte & 0xof) << 4

Thanks Jason!

Anonymous said...

nibbleswap can be faster by realising that in C++, right shift is implemented with logical right shift for unsigned types: hence, suffice to use

inline char nibbleSwap(unsigned char byte){
return byte>>4 | byte<<4;

Or in Java, we can use

return byte>>>4 | byte<<4.