If you're interested in functional programming, you might also want to checkout my second blog which i'm actively working on!!
Wednesday, January 29, 2014
Code puzzler: Tape Equilibrium
Suppose you get an array of ints of arbitrary length. Now we need to find out what is the mimimal absolute difference of the 2 sums of numbers if you split the array at any position in a left and right array. And preferably in a efficient way.
It has reminded me of the in-place version of quicksort algorithm: http://en.wikipedia.org/wiki/Quicksort#In-place_version
BTW, a couple of improvements to your implementation: 1. You should avoid using Arrays.copyOfRange. It's so inefficient. 2. You can immediately break the loop as soon as the following becomes true: (difference > minDifference).
Yeah.... arrays are a pain to work with... I probably should convert the int array to a List first but even that takes a few lines of code extra... java does not autobox them unfortunately. But with a list I can easily take subLists.
It has reminded me of the in-place version of quicksort algorithm: http://en.wikipedia.org/wiki/Quicksort#In-place_version
ReplyDeleteBTW, a couple of improvements to your implementation:
1. You should avoid using Arrays.copyOfRange. It's so inefficient.
2. You can immediately break the loop as soon as the following becomes true: (difference > minDifference).
Well, my second point is incorrect if there may be negative ints.
ReplyDeleteYeah.... arrays are a pain to work with... I probably should convert the int array to a List first but even that takes a few lines of code extra... java does not autobox them unfortunately. But with a list I can easily take subLists.
ReplyDeleteHi, Thanks for this great image that explores and helps me to understand what the Tape-Equilibrium is!.
ReplyDelete