Volition Programmer Test 2003.txt

Volition, Inc. Programmer's Test
Created: October 12, 1999
Last Revision: Tuesday, January 7, 2003 (MWA)

Please attempt all questions on this test.  Type your answers immediately
after the questions.  If you are unable to solve a problem, typing your
thoughts as you attempt the problem is useful.

There are eleven questions on this test.  If you get stuck on one, move to the
next one.  Please be sure that you completely understand the problem
before attempting a solution.

Point totals for each question (or sub-question) are given in square
brackets.  There are 100 total points.

You will have two-and-a-half hours to complete this test.

Name: F Alan Hickman
Date: 12/03/2003

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(1) Consider the following important infinite sequence of numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

where the zeroth element is 1, the first element is 1, the second element is 2, etc.

(1a) [3] Write an iterative (non-recursive) function to return the Nth
element in this sequence using this function prototype:

int sequence(int index);

(For example, sequence(3) would return 3, as 3 is the third element in the
list, counting from 0.)


int sequence(int index)
{
    int first, second, sum, i;

    //range check
    if (index < 0)
        return 0;

    //handle the first two cases
    if (index == 0 || index == 1)
        return 1;

    //calculate the other cases
    first = second = 1;
    for (i = 2; i < index; i++)
    {
        sum = first + second;
        first = second;
        second = sum;
    }

    return sum;
}

(1b) [3] Write a recursive function to return the Nth element in this 
sequence using the same prototype.

int sequence(int index)
{
    int first, second, sum, i;

    //range check
    if (index < 0)
        return 0;

    //handle the first two cases
    if (index == 0 || index == 1)
        return 1;

    //recursively handle other cases
    return (sequence(index - 2) + sequence(index - 1));    
}

(1c) [4] Which implementation is faster?  Why?  What are the key
differences?  Quantify the difference in speed.

The iterative version is faster since it avoids the extra overhead
due to function calls. Specifically, the recursive version requires
2*index extra function calls, for index >= 2. 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(2) [10] Write a function to remove all nodes containing even values from
a linked list of integers.  Upon exit, a new list will be returned that
contains all the even values.  The original list will contain only odd
values.   You should do this by modifying the original list.  YOU SHOULD
NOT CREATE ANY NEW NODES.

For example, if the original list contained the elements {1, 2, 3, 4, 5},
upon exit it would contain {1, 3, 5} (or {5, 3, 1} -- order doesn't matter)
and the function would return a pointer to the list {2, 4} (or {4, 2}).

Be sure to deal with all degenerate cases.

typedef struct node {
	int	value;
	node	*next;
} node;

node *split_list(node **inlist)
{
    node *curNode, *nextNode, *lastEvenNode, *oddList = NULL;

    if (!inlist || !*inlist)
         return NULL;

    curNode = *inlist;
    lastEvenNode = NULL;
    while (curNode)
    {
        nextNode = curNode->next;

        //If odd number, move to oddlist, and adjust the
        //next pointer of the last even node past this node.
	if (curNode->value % 2 != 0)
        {
            curNode->next = oddList;
            oddList = curNode;
            if (lastEvenNode)
                lastEvenNode->next = nextNode;
        }
        else
            lastEvenNode = curNode;

        curNode = nextNode;
    }

    return oddList;
}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(3) Given the following function header:

// Determine the second largest element in an array of ints
// If the two largest values in the array are identical, return that
// value.
// Formal parameters:
//   count - number of elements in array
//   plist - pointer to first element in array
// Return value:
//   value of second largest element in array
//   ERROR if data input is invalid

int find_second_largest(int *plist, int count);

(3a) [10] Write the function described by the preceeding comment header.

int find_second_largest(int *plist, int count)
{
    int largest, nextLargest, i;

    if (!plist)
        return ERROR;    //Assuming ERROR is defined somewhere

    if (count < 1)
        return ERROR;

    largest = nextLargest = INT_MIN;    //defined in limits.h
    for (i = 0; i < count; i++)
    {
        if (plist[i] > largest)
            largest = plist[i];
        else if (plist[i] == largest || plist[i] > nextLargest)
            nextLargest = plist[i];
    }

    return nextLargest;
}

(3b) [5] List 5 useful test cases that can be used to test the function
that you just wrote for accuracy.  Please explain why the test cases that
you have listed are useful in testing your function.

1: An empty set (first paramater of NULL), to check for invalid input
2: An invalid count (second paramater < 1), to check for invalid input
3: A set containing just one number, to ensure that both largest and
	nextLargest will be set to that value
4: A set with the two largest values identical, to ensure that the
	criterion of that number being returned is satisfied.
5: A set containing INT_MIN, to ensure that use of that value as an
	initial value for comparision does not affect the result.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(4) [10] Write a function to determine the most frequently used
letter in a null terminated string.  Ignore case.  For example, 
in the string "ZzZ A man, a plan, a canal, Panama! ZzZzzZZz" the 
answer would be "z".  Assume the string is at least one thousand
and no more than one billion characters long.  

Very important: SPEED IS THE MOST CRITICAL FACTOR.  Your program 
may use no more than one megabyte of RAM.  Make sure your code won't 
crash.

Use the following function prototype:

char most_frequent_char(char *buf);

char most_frequent_char(char *buf)
{
    unsigned int characterCounts[26] = {0};
    int charIndex, mostFrequent = 0;

    while (*buf)
    {
        if (isalpha(*buf))
        {
            //hopefully not compiling for an EBCDIC system...
            charIndex = tolower(*buf) - 'a';
            characterCounts[charIndex]++;

            //this works for the initial character since, so long as the
            //initial value of mostFrequent is in bounds, it will be 0.
            if (characterCounts[mostFrequent] < characterCounts[charIndex])
                mostFrequent = charIndex;
        }
        buf++;
    }

    return (char) ('a' + mostFrequent);
}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(5) [10] A 32 bit-per-pixel (bpp) representation of a pixel on
the screen stores color data as follows:

-------------------------
|  8  |  8  |  8  |  8  |    # bits
-------------------------
|  A  |  R  |  G  |  B  |
-------------------------

8 bits of alpha, 8 bits of red, 8 bits of green, and 8 bits of blue.

One 16 bpp representation of a pixel looks like the following:
-------------------------
|  1  |  5  |  5  |  5  |    # bits
-------------------------
|  A  |  R  |  G  |  B  |
-------------------------

Where there is 1 bit of alpha and 5 bits each of red, green, and blue
colors.  Note that the above charts do not necessarily define byte
boundaries.  They only show the number of bits that are representing
the color and alpha values.

Write a function to swizzle bitmap data that is in 32bpp format into the
given 16bpp format.  Use the following function definitions:

typedef unsigned short ushort;

// function to swizzle pixel data from a 32bpp format to a 16bpp format
//
// src:		pointer source data in 32bpp
// dest:	pointer to dest data to be stored in 16bpp
// src_w:	width of source bitmap
// src_h:	height of source bitmap
//
void swizzle_8888_to_1555(ubyte *src, ubyte *dest, int src_w, int src_h);

Assume that *dest has enough memory to hold the new 16bpp bitmap that you
are creating.  Please be specific about any assumptions that you make about
the incoming data.  Speed is not critically important.

void swizzle_8888_to_1555(ubyte *src, ubyte *dest, int src_w, int src_h)
{
    int i, j;
    ubyte inR, inG, inB, inA, outR, outG, outB, outA;
    ubyte swizPixHigh;

    //assumes all R,G,B, and A values are unsigned
    for (i = 0; i < src_W; i++)
    {
        for (j = 0; j < src_h; j++)
        {
            //swizzle alpha
            if (*src > 127)
                outA = 1;
            else
                outA = 0;
            src++;
            
            //For the other colors, shave off the three least signifigant
            //bits.
            outR = *src >> 3;
 	    src++;
            
            outG = *src >> 3;
 	    src++;
 
            outB = *src >> 3;
 	    src++;
 
            //Combine the pixels into a 32-bit packed value
            swizPixHigh = (outA << 7) | (outR << 2) | (outG >> 3);
            swizPixLow = (outG << 6) | outB;

            *dst++ = swizPixHigh;
            *dst++ = swizPIxLow;
        }
    }
}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(6) [10] Take a square that is one unit long in both axes and draw a
circle inside of the square so that the radius of the circle is 0.5 units.
By picking uniformly random points distributed inside of the square,
we can estimate the value of PI.  Use the fact that the area of a circle
is equal to:

pi * (R^2).

You have the following functions available to you

float fl_rand();  // returns random number between 0.0 and 1.0f

Write a function to estimate the value of pi.  Use the following function
definition

// this function estimates the value of pi
//
// num_iterations: number of points to distrubute inside of a unit square.
// The larger the number of iterations, the closer approximation to pi
//
// returns:  estimation of pi
//
float estimate_pi(int num_iterations);

float estimate_pi(int num_iterations)
{
    int i, pointsInCircle = 0;
    float x, y, distance;
    
    if (!num_iterations)
        return 0;

    for (i = 0; i < num_iterations; i++)
    {
        x = fl_rand();    
        y = fl_rand();

        //is this point in the circle?
        distance = sqrt(x * x + y * y);
        if (distance < 0.5f)
            pointsInCircle++;
    }

    return (pointsInCircle / (float) num_iterations) / 0.25f;
}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(7) As part of a frequently executed AI routine, you need to build 
a data structure containing the IDs of all the monsters that are within 20
meters of the player. There are up to 100 monsters per level, so
there may be 0 to 100 monsters that meet this criterion. The order of
elements in this data structure is unimportant.

(7a) [5] What are the advantages and disadvantages of collecting this data
in (A) an array, and (B) a linked list with dynamically allocated
nodes.

An array would require more memory than a linked list, unless there
are exactly 100 monsters within range of the player. However, it would
be cheaper to fill an array than a linked list since no nodes need be
created or destroyed.

(7b) [5] Which would you choose?

I would choose the array, as the number of possible monsters in range
is small, so the extra memory wasted is not much of an issue.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(8) [5] Consider the following function:

int f(int x)
{
   int   r=0;
   int   i,j,k;

   for ( i = 0; i < x; i++ ) {
      for ( j = 0; j < i; j++ ) {
         for ( k = 3; k < i+j; k++ ) {
            if ( ((x+k) % 4) == 1 ) {
               break;
				}
            r++;
         }
      }
   }

   return r;
}

If this function takes 100 milliseconds to run when x has a 
value of 1000, about how long will it take to run when x 
has a value of 2000?  Explain your answer.

200 milliseconds. The time required by the two inner loops
is constant with respect to x, therefore the running time
of the function is linear in x.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(9) [10] You are writing some code for a 3D shooter.  You need 
to determine if someone should fire on its target.  You are told 
that the attacker should fire on its target if:

1. The attacker is within FIRE_RANGE units of the target
2. The target is in front of the attacker 

Assume you have the following functions and typedefs available
to you:

typedef struct vector {
float x, y, z;
} vector;

typedef struct matrix {
   vector rvec;	// right unit vector
   vector uvec;	// up unit vector
   vector fvec;	// foward unit vector
} matrix;

// return dot product of vector v1 and v2
float vec_dotproduct(vector *v1, vector *v2);

// return magnitude of vector
float vec_magnitude(vector *v);

// normalize the vector v
void vec_normalize(vector *v);

// subtract v2 from v1, putting the result in out
void vec_subtract(vector *out, vector *v1, vector *v2);


Complete this function, returning 1 if the attacker should 
fire on its target, otherwise return 0.  All positions are 
in global coordinates.

bool attacker_should_fire(matrix *attacker_orient, vector 
*attacker_pos,vector *target_pos)
{
    vector distanceVec;
    float distance;

    //calculate the distance to the target
    vec_subtract(&distanceVec, attacker_pos, target_pos);
    distance = vec_magnitude(&distanceVec);
    if (distance > FIRE_RANGE)
        return 0;

    if (vecDotProduct(&attacker_orient->fvec, &distanceVec) /
        distance < 0)
        return 0;

    return 1;
}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(10) [5] Consider the following code:

#define MAX_ITEMS 10													

typedef struct list_item {													
	float val;															
	float ival;															
	char greatest_token;												
} list_item;															

list_item *List[MAX_ITEMS];												

void perform_some_useful_function(char *str, int index, float val)		
{																		
	list_item *l_item;													
	char *c;
	int greatest_c;

	// get a handle to the list item
	l_item = List[index];

	// update with new data
	l_item->val = val;
	l_item->ival = index / val;

	// scan through the string looking for highest ASCII value
	c = str;
	while ( *c ) {
		// is this higher than the last?
		if( *c > greatest_c ) {
			greatest_c = *c;
		}

		// next character
		c++;
	}

	// store the greatest val
	l_item->greatest_token = greatest_c;
}

List 5 things that might cause this code to crash or are
otherwise risky.

1: The List array is not bounds checked: overflow or underflow
	may occur.
2: A possible divide by zero exists when index is divided by val.
3: During this division, the integer index must be converted to
	a float, which may result in a loss of data.
4: greatest_c is used before it is initialized in the while
	loop comparison.
5: l_item->greatest_token is of type char, and is assigned
	an integer value, loss of data may occur.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(11) [5] Assume the following is a function from a working C++ program.
How many top level function calls could be generated directly from the
'simple' function?  Please list them.

int simple(int a)
{
	thing x;
	x.set(a);
	x += 2;
	return x.get();
}

If I understand the question correctly,
1: The default thing constructor
2: thing::set(int);
3: thing::operator+=(int)
4: thing::get();

This document is intended for the use of the individual(s)
or entity to which it is addressed and may contain information
that is privileged, confidential and exempt from disclosure
under applicable law. If the reader of this message is not the
intended recipient, or the employee or agent responsible for
delivering the message to the intended recipient, you are hereby
notified that any dissemination, distribution or copying of this
communication is strictly prohibited. If you have received this
communication in error, please notify us immediately and delete
this message. Thank you.