Real world Java coding challenge

[Dru Lee Parsec]

Hey there folks. How ya doing?

I ran into a kind of cool little problem at work and I thought I'd toss it out as a coding challenge since it's kind of an interesting problem but it's not too difficult to solve.

Imagine you are recording millions of banking transactions. Each one of these transactions has a unique identifier which is the date-time down to the millisecond that we processed that transaction (we will never process more than one transaction per millisecond).

Now assume that we're communicating this data to somebody else's server via XML and the tag they gave us to uniquely identify a transaction is only 10 characters long.

Problem: This format: YYYYMMDDHHMMSSXXX (Year, month, day, hour, minute, second, millisecond) takes up 17 characters and we only have 10 characters allowed in our XML.

Solution: Use the numbers 0 to 9, the letters A to Z and a to z to give us a base 62 number. It's just like hexadecimal encoding but in base 62 instead of base 16. In 10 characters we can contain a number as large as 839,299,365,868,340,224 which is 18 characters long.


Goal: Write two methods.

The first method takes a String in base 62 form (i.e. 9IjeF362m) as a parameter and returns a 17 character string in the date time format I described above.

The 2nd method does the opposite. It takes a 17 character date-time and spits out the base 62 version of it.

Month, day, hours, minutes, seconds, and milliseconds are always padded with leading zeros. In other words January 7th 2002 will always show as

20020107

and not

200217

Have fun.

P.S. Y100K issue: We should note that we'll run out of digits on December 31st 99,999. But I won't be around in 97,997 years to worry about it. We'll let the robot programmers worry about it when that happens.

[bwkaz]

Originally posted by Dru Lee Parsec
P.S. Y100K issue: We should note that we'll run out of digits on December 31st 99,999. But I won't be around in 97,997 years to worry about it. We'll let the robot programmers worry about it when that happens. LOL!!

Do you care if we only do the functions, or do you want them in a class, with a main(), actually able to be compiled and run, and all that?

Obviously just doing the functions would be easier...

[Dru Lee Parsec]

I think it would be nice to have a class with a main method. Then you could pass a date to the "date to base62" converter method. Take that result and pass it back to the "Base62 to date" method to see if it parses back to the same date you started with.

[bwkaz]

This would be quite a bit easier if the constant Character.MAX_RADIX was higher than 36 -- say, like at least 62. Because that way, of course, we could use the BigInteger class' radix-conversion functions, along with toString, to do all of this with relatively little work. ;)

I've got something that in theory works, except I'm still getting ArrayIndexOutOfBoundException's on it. That, plus the fact that I can't run it on my own machine (Sun is being retarded, they won't release a version of the JDK that works when only gcc 3.2 is installed, at least until JDK version 1.4.2), is making it take a whole lot longer than I thought it would... Plus, I should really do my real homework. :sick:

[darelf]

from http://hints.linuxfromscratch.org/hints/javafromscratch.txt

Also since the JDK binary from Sun is linked against gcc2, download the lib from
it from <http://www.linuxfromscratch.org/~timothy/misc/> and move it where the
jdk can find it.
mv libstdc++-* $JAVA_HOME/jre/lib/i386/


That way you can run it without installing GCC2...

Does this help?

[Dru Lee Parsec]

This would be quite a bit easier if the constant Character.MAX_RADIX was higher than 36 -- say, like at least 62.

That is a cool idea. Too bad it's limited to 36 (0 to 9 and A to Z).

Hmm, I didn't even think of solving it that way. So even if it doesn't work, it's still a darn good idea.

[bwkaz]

darelf -- yeah, I had seen that before, but a couple of people have said that, IIRC, keeping the older libstdc++ around might cause problems. The javafromscratch hint only uses that file to compile a new JDK, not while Java is being used. Are you using your own JDK, or the downloadable one from Sun? If you haven't seen it cause problems, I'll give it a try.

Although, interestingly, JDK 1.4.1_01 (the version I just got about 2 hours ago or so) no longer gives errors about .so files not found. The error is now this:

There was an error trying to initialize the HPI library.
Please check your installation, HotSpot does not work correctly
when installed in the JDK 1.2 Linux Production Release, or
with any JDK 1.1.x release.
Could not create the Java virtual machine.

Now it's possible that this HPI library isn't loading because of libstdc++ (actually, I'm pretty sure that's the problem, no "possible" about it), but a better error message would sure help...

DLP -- I was thinking more about this, and if only 62 was a perfect square, it would still work. You'd use the square root of 62 as your radix, and then take each pair of characters in the BigInteger's string, and convert that pair to one base-62 digit.

Like if you wanted base 64 instead, we could pull the base-10 number into a BigInteger, and then push it out to a String, in octal. Then for every pair of digits, there would be 64 combinations -- just enough for one base-64 digit.

That works in general for base-n**k numbers (k any integer; it's the number of digits you take together) if you have a base-n number. So if only BigInteger would convert to non-integer bases! :P

But oh well, I think going back and doing it the long (a.k.a. manual) way will work, eventually. I've just got to get enough time to really trace through it and find the problem.

[Dru Lee Parsec]

Well, I have a quick and dirty proof of concept program done. Now I have to put it into it's own class, clean up all the debug lines, and get rid of all the static definitions (Since everything is being called form the main method all the methods need to be static since main is static).

The code is attached

[darelf]

bkwaz... I'm using it with the downloaded binary of 1.4.0, it seems to work well for me.
I just put in the the $wherever_java_is/jre/lib/i386/

That way, only java uses it. It doesn't corrupt anything else. I too will be glad when they release a version for GCC 3.

[bwkaz]

Originally posted by darelf
bkwaz... I'm using it with the downloaded binary of 1.4.0, it seems to work well for me.
I just put in the the $wherever_java_is/jre/lib/i386/

That way, only java uses it. It doesn't corrupt anything else. I too will be glad when they release a version for GCC 3.

OK, will try. Thanks! Yeah, it would be nice if they'd compile with gcc 3... it would also be nice if they'd compile with gcc 3 and -O3 -march=athlon-xp -mmmx -msse -m3dnow -mfpmath=sse (actually, one or more of those might be the default with -O3 and -march=athlon-xp, but I don't know which one(s)). But I think we all know they won't -- because then it wouldn't be as cross-platform.

I would really like to see multiple JVM's, one for each -march=xxxx possibility, and each one optimized as much as compilers will let you. But somehow, I don't think that'll happen, unfortunately. Maybe I should just build it myself... but if I do that, I can't redistribute the .class files (right? those are the license terms?). Which isn't a huge deal, just a minor annoyance more than anything.

In any case, thank you!