Programmer Interview Questions

This test is what Westwood Studios faxes you if you request to interview for a programmer position. It is by far the most draconian programmer test I’ve come across. Most of the questions in it I could answer per their instructions. Some of them just make me think, when am I ever going to have to do this without referrence material and tools (like a calculator)?

This test was designed to determine speed, accuracy, and general problem solving abilities. When answering these questions, try to complete each problem swiftly and accurately. You may not use any reference materials nor a calculator, so please show all of your work.

1. Write a ‘C’ function to insert a structure into a circularly linked list based on a key value (ascending order). You will be given a pointer to the current head of the list and a pointer to the new entry to insert. The structure is as follows:

   
   typedef struct tag {
   
   	int x;			// This is the key value
   
   	int y;
   
   	int color;
   
   	struct tag *prev, *next;
   
   } PointType;
   
   

   The prototype for the function is:

   PointType *InsertPoint(PointType *head, PointType *new_entry);

   The function should return a pointer to the head of the list. In this implementation, an empty list is defined as (head == NULL). Otherwise, the head node is the smallest key value, head->next is the node containing the next largest key value.

2. Calculate the following arithmetic problems. Assume all numbers are base 16 and 16 bit quantities (show your work).
   
   

   1. C0 + 4ab
   2. FE * 2A
   3. FE / D
   4. 21-14

3. Assume you want to get the modulus (remainder, or % in ‘C’), given x % y. You may also assume that y is always a power of 2. Show the fastest way to do this with a simple formula. Be specific about any arithmetic operations.

4. Assume you want to test variable x (x is non-zero) to see if it is a power of 2. Show the fastest way to do this with a simple formula. Be specific about any arithmetic operations.

5. How many iterations will the function Interesting_Test() be called given the following set of code?

   
   void How_Many_Times(void)
   
   {
   
   	int loop, value;
   
   
   
   	value = 0xABCD;
   
   
   
   	for (loop = 1; ((value >> 1) & 1) | (loop & 1); loop++)
   
   	{
   
   
   		Interesting_Test();
   
   		if (loop & 1)
   
   		{
   
   			value >>= 1 ;
   
   		}
   
   	}
   
   }
   
   

6. Write a function in assembly language (80x86, 6502, 65816, or 680x0) to compare memory against a given key value. The function will take a pointer to the beginning of a block of RAM that is WORD aligned (even), the size (8-bit quantity) of the memory block, and the key value (8-bit). The function must return TRUE (1) or FALSE (0) as to whether the block of RAM consists entirely of sequential repeating occurances of the key value. The function should be as fast as possible.

   The prototype for the function is:
   char VerifyRAMBlock(char *ram, char size, char key_value);

   You may assume register parameters or stack parameters (please specify which you choose and what registers or stack order the calling routine should use).

7. Explain in English sentences an algorithm to solve the following problem:

   Assume there is a program that generates data sequences of 16 bytes each. These data sequences are to be stored in a large array in RAM until all processing is complete, and then written to out to disk. A requirement of the program is that all sequences written to disk must be unique. You may assume you have the following RAM available (given n data sequences):

   n * 16 bytes for data

   n * 4 bytes for long pointer data

   n * 2 extra bytes

   1K of general purpose RAM for variables

   You need to create a procedure that accepts and stores a single data sequence. Remember, it must not store duplicates, it must not use more than the given amount of RAM, and it must be as fast as possible. Explain (in English) how this routine would work, what data structure would contain the unique data sequences, and how to write them to disk.

8. What is wrong with the following code? Please indicate where there are problems and what the corrections should be.

   
   
   
   /* This function takes an integer (16 bit) and a pointer to an allocated character array
   
   and converts the integer to a hex string.  The string is of the form 0x1234 where 1234
   
   are hex digits.  You may assume the character string is at least 7 bytes long.  If i is
   
   zero, the string must be "0x0".  Otherwise, leading zeros should be removed. */
   
   
   
   void itoh(int I, char *s)
   
   {
   
   
   
   	int nibble, loop;
   
   
   
   	*s++ = ‘0’;
   
   	*s++ = ‘x’;
   
   
   
   	/* Is the number 0? */
   
   	if (i ==0)
   
   	{
   
   		*s++ = 0;
   
   	}
   
   	else
   
   	{
   
   		/* Go through the number nibble by nibble, starting with the most
   
   		significant */
   
   		for (loop = 3; loop > 0; loop--)
   
   		{
   
   			/* Get the nibble by shifting the number over by 12, 8, or 4 */
   
   			nibble = (i>>(loop<<4))& 0x000F;
   
   
   
   			/* Is the number in decimal range? */
   
   			if (nibble <= 10)
   
   
   
   				/* Convert the number to the character 0 – 9 */
   
   				if (nibble || (*(s-2) != 'x'))
   
   					*s++ = '0' + nibble;
   
   				else
   
   					;
   
   			else
   
   				*s++ = 'A' + (nibble – 10);
   
   		}
   
   	}
   
   	*s = '0';	/* null terminate it */
   
   }