ygfperson
---------
Beginner
--------
Summary: ygf used basically the same algorithm that I did, and the speed was virtually a dead match in several profiling tests. However, the use of long instead of long double resulted in incorrect output at the positive and negative extremes. The function is supposed to work correctly for INT_MAX, INT_MIN and everything in between.
Code Review: Aside from using long when I clearly gave a function prototype that had long double, this code is good.
Code:
long digRev (long input) {
long output = 0;
while (input) {
output *= 10;
output += input % 10;
input /= 10;
}
return output;
}
Scores:
Correctness: 7 (Works well except for extremes)
Speed: 10 (Nice and toasty)
Elegance: 9
Portability: 6 (2 byte ints and 4 byte longs are okay, but 4 byte ints and longs are not)
Intermediate
------------
Summary: ygf went with the simplest solution, nonrecursive with three variables holding the smallest, current, and largest values. While this isn't the most elegant of solutions, it produces the correct answer, and certainly is fast. My timer scaffolding is far less accurate than my profiler (that chose to break right as I was testing this function), but the differences weren't so close that another 0 or two added to my number of iterations wouldn't fix.
Code Review: You've probably seen this one too many times if you've taken a programming course.
Code:
int stickLen(int x) {
//longest cannot be more or equal to the two lesser ones
//no three can make a triangle
//1 + 1 = 2
//1 + 2 = 3
//2 + 3 = 5
//use largest two to determine next largest because smaller ones may fail test
int i, shortest, cur_largest, largest;
if (x < 3) return -1;
for (i=2, shortest = 1, cur_largest = 1, largest = 2; i < x; ++i) {
largest = shortest + cur_largest;
shortest = cur_largest;
cur_largest = largest;
}
return largest;
}
Scores:
Correctness: 10
Speed: 10 (Faster than mine usually gets a 10)
Elegance: 7 (Most first year CS majors know this algorithm by heart)
Portability: 10 (No complaints here)
Advanced
--------
Summary: ygf went with (in my opinion) an overly complex algorithm that uses two maps and bit flags to mark first time and repeat values. The algorithm is indeed O(n), but it suffers because of the two arrays. A successful algorithm can get away with just one.
Code Review: As with every other entry at the time of this review, ygf assumed that the largest char value is 256. He did however, take into account that no printable character is signed and used unsigned char. The use of macros as named constants is a breath of fresh air, thank you for that. Here is the code:
Code:
#define REPEAT_BIT 0x01
#define FIRST_BIT 0x02
char findFirstNonRepeat (char *s) {
unsigned char bits_int[256], map[256];
int i,value;
memset(bits_int,0,256);
for (value=0;*s != '\0';++s) {
if (!(bits_int[*s] & REPEAT_BIT))
if (bits_int[*s] & FIRST_BIT)
bits_int[*s] |= REPEAT_BIT;
else {
bits_int[*s] |= FIRST_BIT;
map[value++] = *s;
}
}
for (i=0;i < value; ++i) {
if (!(bits_int[map[i]] & REPEAT_BIT))
return map[i];
}
}
One distinct flaw is what to return if there is no nonrepeating character.
Scores:
Correctness: 9 (Works in all but one case)
Speed: 5 (Half as fast as the test function)
Elegance: 6 (Nifty algo, but too complex)
Portability: 9 (One unwarranted assumption)