Not-Really-Interview Questions

After being informed by a third party that RIM probably prefers to keep interview questions private, (okay, so it was actually much less polite than that, but I won’t hold that against anyone), I’ve decided to post about two questions other than those in my interview, but with slightly similar components to how I answered the otherwise-unrelated questions in my RIM interviews. I haven’t checked whether these answers would compile, since I wouldn’t be able to in an interview.

Question: Write a C function to select k random elements in a random order from a set of n pointers in O(k) time. The original set can be reordered.

void** selectRandom(void** pSet,DWORD n,DWORD k) {
    // Create the array to be returned, null-terminated
    void** pSelected = (void**)malloc((k+1)*sizeof(void*));
    pSelected[k] = NULL;
    DWORD selectedIndex = 0;
    // Select elements until no more needed
    while (k--) {
        DWORD index = (DWORD)((rand()*((QWORD)n))>>32);	// This is more uniform and faster than using modulus
        void*const element = pSet[index];		// Select the edge from the list
        pSet[index] = pSet[--n];			// Remove it by replacing with the last element
        pSelected[selectedIndex++] = element;
    }
    return pSelected;
}

Question: Write a C function to sort an array of floats (i.e. 4-byte floating-point numbers in the appropriate IEEE format) in O(n) time, where n is the number of floats in the array.

The answer needs a bit of explanation first. Positive floating-point numbers when interpreted as integers are in the same numerical order in both cases. e.g. 2.0 > 1.0 and the integer interpretation of 2.0 is greater than the integer interpretation of 1.0. Negative floating-point numbers when interpreted as integers are in the opposite numerical order. e.g. -2.0 < -1.0, but the integer interpretation of -2.0 is less than the integer interpretation of -1.0. Mixed sets of negative and positive numbers results in other special cases. What would be ideal is a constant-time bijective mapping from a floating-point number to an unsigned integer that will maintain perfect ordering through positive and negative numbers. It can be shown that there is exactly one such mapping, and it is simple enough to be constant time.

The mapping is: take the bitwise not of negative numbers, and flip the sign bit of positive numbers. After applying this to all numbers in the array, one can use 4-pass, base-256 radix sort on the numbers as unsigned 32-bit integers, then use the reverse mapping back to floating-point numbers. This works with 6 passes through the array. There is a way to do the full thing with 4 passes through the array, but it’s unsure which would be faster.

Advertisements

~ by Neil Dickson on October 19, 2007.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: