Pages: 1 2 3 4 5 6 7 8 9 10 11 ... 55 >>

27/02/11

Permalink 08:04:00 pm, by Brad Email , 1590 words   English (UK)
Categories: General

Algorithms and Code

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 X-1. 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: 446

4)


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 < N-1 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[N-1] 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 top-left 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[i-1] != 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[i-1] != 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, NSize-1, 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 15-20 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.

02/02/11

Permalink 08:13:42 pm, by Brad Email , 132 words   English (UK)
Categories: General

Exoplanets

Here's my latest paper on exoplanets. My subject this semester was Radio Astronomy and Search for Intelligent Life. This subject I really didn't enjoy, the course was a little disjointed, and my brain hurt from trying to understand some of it.

Thankfully I finished and submitted before Kepler just discovered 1200 more. http://news.discovery.com/space/kepler-exoplanet-count-increase-110202.html

24/30

http://www.theedgeofmadness.com/astronomy/P029-HET608-BradJayakody.pdf

My ALMA understanding is a little off. And I needed to go into a little more depth into solar system formation and what the planets suggest with those theories. I also relied on 2 books a little too much.

So I got another distinction, meaning amazingly I'm on a distinction average so far (3 subjects). This semester I'm doing HET624, Galaxies and their places in the universe.

28/10/10

Permalink 01:31:42 pm, by Brad Email , 23 words   English (UK)
Categories: General

Scott's Surveyors

http://scotts-surveyors.co.uk

In my opinion these guys are the worst landlords I've ever dealt with. Deal with at your own risk.

16/07/10

Permalink 08:15:18 pm, by Brad Email , 120 words   English (UK)
Categories: General

Virgin Media Installation Headaches

So took 2 weeks to book in my virgin media broadband installation timeslot. 1-6pm on friday. Waiting, waiting, waiting. 6pm rolls around, still no engineer.

Get a call at 6:30, sorry guy can't come out today, we can do saturday, will call up to confirm in half an hour. 1.5 hours later, still no call. So I call them.

On the expensive 0845 number. 15 minutes on hold, passed around to 3 departments. Finally get told, we don't know why it was cancelled, you will have to wait another 2 weeks for the next free slot. WTF? You don't show up, you show up the next day. You don't make me wait another 2 weeks, with again no guarantee of anyone showing up. So screw Virgin Media.

09/07/10

Permalink 02:32:08 am, by Brad Email , 241 words   English (UK)
Categories: General

Astronomy

I'm doing my Masters of Astronomy at Swinburne University. Remotely. Rather enjoyable so far.

Managed to get 78% in both subjects so far, just managing a distinction in both. Considering that was the best mark I ever managed at uni when I did my IT degree, I'm rather happy. Much more work than I thought, if I wasn't working during the last two weeks of the semester, I don't know how I would have managed. Next semester I plan on only doing one subject. One will be fine as a hobby, otherwise all I was doing was work and uni.

Anyway, here's my first two projects. I really need to work on my academic writing within them. I can write bullshit, but I really need to formalise my writing style.


The Fermi Paradox


Life in the Solar System

21/30 for Fermi.

My time dilating explanation is a little confusing. And my supervisor had a great point of humanity does do generational work - Gaudi's Sagrada Família for example. I should have remembered that, I've been there.

25/30 for Life in the Solar System.

I'm missing some explanations on what is life - specifically in regards to viruses, why fire is not life, prions. And my explanation of the MHZ could be extended.

On how life started on Earth, I'm missing talking about stromatolites and fossils.

Anyway, enjoy, and swear at my writing style. Lana did, and I was too stubborn to change it all.

1 2 3 4 5 6 7 8 9 10 11 ... 55 >>

April 2014
Mon Tue Wed Thu Fri Sat Sun
 << <   > >>
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30        
A brief blog describing what is going on in the life of Brad Jayakody

Search

XML Feeds

free blog software