Exoplanets » 
Looking for a new gig again, so back into the swing of interviewing, and going through the crap of being asked questions that I only get asked in interviews. I don't know why people feel the need to ask these questions. Get people to write code. I've had only one great interview where they sent over a small subsection of the application, with the unit tests, and asked to code up the guts (it was a simple app & good test). And still the classic great Sapient test, here's an hour, write up some pseudo code for the problem on the whiteboard. Then we'll pull it to shreds in the next hour. Best way to interview a coder.
Can you explain Java class loaders? Well yes I can, but in the past decade, I haven't had to really care about it. Once I did have a problem with the order a scheduler was loader and 5 minutes on google found and fixed the problem.
That said, it's part of the game, so I can't complain. (Well yes I can bitch here)
But anyway, in between refreshing my memory on how to setup hibernate (the number 1 question asked in interviews), I felt the need to actually code, so signed up to topcoder.
This isn't proper, proper code, you have 75 minutes to solve 3 problems. And in order to spit out the code that quickly, it isn't the most pretty, or most refined. It does the job. I competed this weekend, managed to solve the level 1 problem fairly quickly (7 odd minutes). Struggled with level 2. My edge case was slightly off. Took me an hour and a half of debugging to work it out. Just need a bit more practice and I'll be back in the swing of things....only to probably not get a chance to use it again at work for a while. But stuff like this reminds me why I chose to be a programmer, I fucking love this shit.
Anyway, here's the questions & code I had and a few comments on my part.
Problem Statement
Fox Ciel is playing a game called Addition Game. Three numbers A, B and C are written on a blackboard, and Ciel initially has 0 points. She repeats the following operation exactly N times: She chooses one of the three numbers on the blackboard. Let X be the chosen number. She gains X points, and if X >= 1, the number X on the blackboard becomes X1. Otherwise, the number does not change. Return the maximum number of points she can gain if she plays optimally.
Definition
Class:
AdditionGame
Method:
getMaximumPoints
Parameters:
int, int, int, int
Returns:
int
Method signature:
int getMaximumPoints(int A, int B, int C, int N)
(be sure your method is public)
Constraints

A, B and C will each be between 1 and 50, inclusive.

N will be between 1 and 150, inclusive.
Examples
0)
3
4
5
3
Returns: 13
The three numbers written on the blackboard are (3, 4, 5). One possible optimal strategy is as follows:
Ciel chooses 5. She gains 5 points, and the numbers become (3, 4, 4).
Ciel chooses 4. She gains 4 points, and the numbers become (3, 3, 4).
Ciel chooses 4. She gains 4 points, and the numbers become (3, 3, 3).
She gains a total of 5+4+4=13 points.
1)
1
1
1
8
Returns: 3
One optimal strategy is to choose a 1 in each of the first three turns, for a total of 3 points. The numbers then become (0, 0, 0). After that, she won't be able to gain any more points.
2)
3
5
48
40
Returns: 1140
The only optimal strategy is to choose the following numbers: 48, 47, 46, ..., 11, 10, 9.
3)
36
36
36
13
Returns: 4464)
8
2
6
13
Returns: 57
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
public class AdditionGame{
public int getMaximumPoints(int A, int B, int C, int N){
int score = 0;
for (int i=0;i<N;i++){
if ((A == 0) && (B == 0) && (C == 0)){
break;
}
if ((A >= B) && (A >= C)){
score+=A;
A;
} else if ((B >= A) && (B >= C)){
score+=B;
B;
} else if ((C >= A) && (C >= B)){
score+=C;
C;
}
}
return score;
}
Really simple brute force here. Slightly faster at only having to check if the number is greater, if previous one isn't.
Problem Statement
Fox Ciel likes sequences. One day, she invented a new type of sequence and named it the fox sequence. A sequence seq containing N elements is called a fox sequence if and only if there exist four integers a, b, c and d such that 0 < a < b <= c < d < N1 and the following five conditions are met:
seq[0], seq[1], ... , seq[a] forms an arithmetic progression with a positive common difference. An arithmetic progression is a sequence where the difference between successive elements is equal. The difference between successive elements is called the common difference. Note that 0 is neither positive nor negative.
seq[a], seq[a+1], ... , seq[b] forms an arithmetic progression with a negative common difference.
seq[b], seq[b+1], ... , seq[c] are all equal.
seq[c], seq[c+1], ... , seq[d] forms an arithmetic progression with a positive common difference.
seq[d], seq[d+1], ... , seq[N1] forms an arithmetic progression with a negative common difference.
In the following image, the top 3 sequences are fox sequences, while the bottom 3 sequences are not: You are given a sequence seq. Return "YES" if it is a fox sequence, or "NO" if it is not (all quotes for clarity).
Definition
Class:
FoxSequence
Method:
isValid
Parameters:
int[]
Returns:
String
Method signature:
String isValid(int[] seq)
(be sure your method is public)
Constraints

seq will contain between 1 and 50 elements, inclusive.

Each element of seq will be between 1 and 2,000, inclusive.
Examples
0)
{1,3,5,7,5,3,1,1,1,3,5,7,5,3,1}
Returns: "YES"
This is the topleft sequence of the image shown in the statement. The next five examples are also from that image.
1)
{1,2,3,4,5,4,3,2,2,2,3,4,5,6,4}
Returns: "YES"2)
{3,6,9,1,9,5,1}
Returns: "YES"3)
{1,2,3,2,1,2,3,2,1,2,3,2,1}
Returns: "NO"4)
{1,3,4,3,1,1,1,1,3,4,3,1}
Returns: "NO"5)
{6,1,6}
Returns: "NO"This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Working code
public class FoxSequence{
public boolean checkNegativeDifference(int a, int b, int[] seq){
int prog;
prog = seq[a+1]  seq[a];
if (prog >= 0) { return false; }for (int i = a+1; i <= b; i++){
if (seq[i]  seq[i1] != prog) {return false;}
}
return true;
}public boolean checkPositiveDifference(int a, int b, int[] seq){
int prog;
prog = seq[a+1]  seq[a];
if (prog <= 0) {return false; }
for (int i = a+1; i <= b; i++){
if (seq[i]  seq[i1] != prog) {return false;}
}
return true;
}public boolean checkEqual(int a, int b, int[] seq){
int prog;if (a == b) {return true;}
prog = seq[a+1];
if (prog != seq[a]) {return false; }for (int i = a+1; i < b; i++){
if (seq[i] != prog) {return false; }
}
return true;
}public String isValid(int[] seq){
int NSize = seq.length;
boolean MatchFound = false;
for (int a = 1; a < NSize  3; a++){
if (MatchFound) { break; }
for (int b = a + 1; b < NSize  2; b++){
if (MatchFound) { break; }
for (int c = b; c < NSize  2; c++){
if (MatchFound) { break; }
for (int d = c + 1; d < NSize  1; d++){
if (checkNegativeDifference(d, NSize1, seq) && checkPositiveDifference(c, d, seq) && checkEqual(b, c, seq) && checkNegativeDifference(a, b, seq) && checkPositiveDifference(0, a, seq)){
MatchFound = true;
break;
}
}
}
}
}if (MatchFound) { return "YES"; } else {return "NO"; }
}
}
Part of my problem is it takes me a while to understand what the hell the question is asking, since I'm out of practice on this. Prob took me 1520 minutes to work out how to solve it by hand (i.e. what it was asking me to do). Once that was done, I went for pure brute force. Let's cycle through all possible combinations of a, b, c & d.
To speed up this algorithm, move the final check out, and for each of the checks, put in that loop. There's no point always checking a = 1 for all other combinations of b, c & d, if it can't be that. But as I said, speed isn't the issue, it's just solving it.
My stuff up was two fold. I misread rule 1 as 3 as being equal difference, not equal for a bit. Then my edge case check wasn't right. I had
for (int i = a+2; i < b; i++){
which should be
for (int i = a+1; i <= b; i++){
.
I had 99% of the code done in an hour...but took me another 1.5 hours after contest to track down my error.
But man, I miss coding like this. I can count on one hand the numbers of times I've been giving a problem like this in my job (volume control for virgin player  had to use trig to work out how fair to sping the circular dial, det  the design & coding guts of the risk management framework (lots of records to be generated dynamically), Vodafone  the partial publish system (another large stored procedure for moving a subset of records that link to each other to another DB). Think that's it from the top of my head. And outside work, coding up a solver for Eternity 2 & to solve working out the maximum route for most points in the Motorcycle National Road Rally.
Why I'm doing my Masters in Astronomy. I'm so tempted to switch into doing my PhD and just spend all my time hacking around in large datasets trying to make sense of them.
This post has 1912 feedbacks awaiting moderation...