The UbiSoft/Gameloft guy wanted me to take a test to assess my problem-solving skills as a programmer. This morning he finally sent it to me.
The problems on it were just like the sorts on the ACM annual programming contest (which I've done very well at in the past), with the usual "it seems simple but there's a catch" bit to it. I completed all four in an hour and a half, with code which is fairly well-tested so I'm pretty sure I got the right solutions, though there's a couple where if I'd had more time to work on it I could have done some clever stuff to make it more efficient. Each of the puzzles has a subtle "gotcha" which makes the common clever solutions not work, however.
The problems are repeated inside (verbatim, all grammar weirdness and ambiguities being on the part of the interviewer) for anyone else who wants to take a crack at it. My solutions are also included in the page source in case you want to see them.
Instructions
The exercises are attached to this mail, try to make them in C language, but
it's not important if the code is not exact as long as the idea is good.
You can add any comments to your answers if you need.
There are 4 exercises, try to do 2 of them.
Problem 1
Create a function
findZeroArraySize() that takes a 2-dimensions
int array, its width and its height as arguments. The array is filled with 0 and 1. The function returns the size (in
int) of the biggst 2-dimensions sub-array filled only with 0. This function should be as fast as possible.
Ex:
If argument is
001011110
110001100
010000011
110001100
111011100
funciton returns 9.
/* problem1.c
** findZeroArraySize
**
** Unfortunately I couldn't come up with any truly clever solutions, but
** this does at least reduce the search space significantly
**
** Assumption: The array is stored row-major
*/
#include
#include
int findZeroArraySize(int *arr[], int w, int h)
{
int i, j, maxd = 0;
for (j = 0; j < h; j++)
for (i = 0; i < w; i++)
{
if (arr[j][i] == 0 && maxd < (w - i)*(h - j))
{
// Found a candidate top-left corner; trace the
// bottom-right contour
int j2 = j, iw = -1;
while (j2 < h && arr[j2][i] == 0)
{
// The bottom-left corner still starts on 0
int dim;
int i2 = i;
// While we're still narrower than the minimum width and seeing 0s, grow the subrectangle to the right
while (i2 < w
&& (iw < 0 || i2 - i <= iw)
&& arr[j2][i2] == 0)
i2++;
dim = (j2 - j + 1)*(i2 - i);
if (maxd < dim)
maxd = dim;
if (iw < 0 || i2 - i < iw)
iw = i2 - i;
j2++;
}
}
}
return maxd;
}
int main(void)
{
// For some reason I couldn't get gcc to cooperate and just do this
// in an initializer...
int **arr;
char *data[] = {
"001011110",
"110001100",
"010000011",
"110001100",
"111011100"};
int i, j;
arr = (int **)malloc(5*sizeof(int *));
for (j = 0; j < 5; j++)
{
arr[j] = malloc(9*sizeof(int));
for (i = 0; i < 9; i++)
arr[j][i] = data[j][i] - '0';
}
printf("findZeroArraySize(arr) == %d\n", findZeroArraySize(arr, 9, 5));
return 0;
}
Problem 2
Create a function
findPalin() that takes a string of characters as an argument and returns the number of palindromes (a string in which the sequence of characters is the same forwards and backwards) in that string. There is no special character. This function should be as fast as possible.
Ex:
- "aa" returns 1
- "aabb" returns 2
- "222" returns 3
- "baaab3" returns 4
/* problem2.c
** Find the number of palindromes embedded into a string
**
** Although this code appears to be fairly naive, it finds all possible
** palindromes, whereas more "clever" methods would tend to have edge cases
** which fail to recognize all possible palindromes (e.g. "aaa" would count
** as two instead of three)
*/
#include
#include
void printspan(const char *a, const char *b)
{
// For my own debug purposes
while (a <= b)
fputc(*a++, stdout);
fputc('\n', stdout);
}
int findPalin(const char *s)
{
int count = 0;
const char *last;
// Find the last character in the string
last = s;
while (*last)
last++;
last--;
while (*s)
{
const char *left = s, *right = last;
while (left < right && *right != *left)
right--;
while (left < right)
{
int isPalin = 1;
// Check the current left..right span
const char *start = left;
const char *end = right;
while (start < end)
{
if (*start != *end)
{
isPalin = 0;
break;
}
end--;
start++;
}
if (isPalin)
{
//printspan(left, right);
count++;
}
// Find the next candidate
right--;
while (left < right && *right != *left)
right--;
}
// Go to the next left point
s++;
}
return count;
}
int main(void)
{
char *tests[] = {"aa", "aabb", "222", "baaab3", "abcbabcba", NULL};
int i;
for (i = 0; tests[i] != NULL; i++)
printf("%s: %d\n", tests[i], findPalin(tests[i]));
return 0;
}
Problem 3
Create a function
findSuccessiv() that takes an
int array as argument and return the length of the longest part of this array that contains successive numbers in increasing order.
/* problem3.c
** Find the longest successive subsequence of increasing numbers
*/
#include
int findSuccessiv(const int *arr, unsigned int n)
{
int i, longest = 0, len = 0;
for (i = 0; i < n; i++)
{
if ((i == 0) || (arr[i - 1] < arr[i]))
len++; /* Either the start of the first subsequence, or
the current subsequence is continuing */
else
len = 1; // Start of a new subsequence
if (longest < len)
longest = len;
}
return longest;
}
int main(void)
{
int a1[10] = {-20, 5, 6, 7, 8, 5, 4, 3, 2, 1};
int a2[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int a3[10] = {2, 3, 4, 3, 4, 5, 6, 10, 12, 7};
printf("findSuccessiv(a1) = %d\n", findSuccessiv(a1, 10));
printf("findSuccessiv(a2) = %d\n", findSuccessiv(a2, 10));
printf("findSuccessiv(a3) = %d\n", findSuccessiv(a3, 10));
return 0;
}
Problem 4
Create a function
foo() that takes an
unsigned int array and an
unsigned int number
N as arguments. It returns the size of the largest sub-array whose sum of its elements is a multiple of
N. The array has less than 10000 elements and
N is less than 1000. This function should be as fast as possible.
/* problem4.c
** Function foo() takes an int array and a number N, and finds the length of the
** largest sub-array whose sum is a multiple of N
*/
#include
int foo(const unsigned int *arr, unsigned int s, unsigned int n)
/* arr - the array
** s - size of the array
** n - the multiplier value n
*/
{
unsigned int sums[10001];
int i, sum = 0;
int left = 0, right = 1, maxl = 0;
/* Calculate the sums */
sums[0] = 0;
for (i = 0; i < s; i++)
{
sum += arr[i];
sums[i + 1] = sum;
//printf(" %d", sum % n);
}
//printf("\n");
/* Cut the search space as much as possible by starting with the
largest arrays and bailing out when it's no longer possible to
find another array which is bigger
*/
for (left = 0; (left < s) && (maxl < s - left); left++)
{
for (right = s; maxl < right - left; right--)
{
int val = sums[right] - sums[left];
int len = right - left;
if ((maxl < len) && (val % n == 0))
maxl = len;
}
}
return maxl;
}
int main(void)
{
unsigned int arr[100];
int i;
printf("arr =");
for (i = 0; i < 100; i++)
{
arr[i] = /* rand() & 255*/ i?1:12;
printf(" %d", arr[i]);
}
printf("\n");
for (i = 1; i < 10; i++)
printf("foo(arr, %d) = %d\n", i*7, foo(arr, 100, i*7));
}
Comments
I had to do a skills test for one of the jobs I applied for recently, although that one was mostly over x86 assembly. I wish they had told me how well I had done on it; between reading up on a bit the day before and random tidbits I remembered, I had thought I had bluffed my way through pretty well.
HEY GENIUSES! An HTML comment is terminated with
-->!Anyway. Guess I'll invert all of the tests so that Firefox can stop being gimpy.