Re: Finding a constant-space algorithm



On 12/25/2009 7:31 AM, Richard Harter wrote:
On Fri, 25 Dec 2009 07:02:39 +1100, Lie Ryan<lie.1296@xxxxxxxxx>
wrote:

The problem description:

"""
Return an array that contains exactly the same numbers as the given
array, but rearranged so that every 4 is immediately followed by a 5. Do
not move the 4's, but every other number may move. The array contains
the same number of 4's and 5's, and every 4 has a number after it that
is not a 4. In this version, 5's may appear anywhere in the original array.
http://www.javabat.com/prob/p125819
"""


Big Juicy Hint: Use two pointers, one for 4's and one for 5's.

Try to work it out for yourself.

Solution: (rot 13)

Fgneg ol svaqvat gur svefg 4 naq gura svaq gur svefg 5. Fjnc gur
svefg 5. Gurernsgre frnepu sbe gur arkg 4 nsgre fjnccvat n 5.
Jura lbh svaq n 4, frnepu sbe gur arkg 5 naq fjnc vg. Jura lbh
eha bhg bs 4'f lbh ner qbar.

It's a cute puzzle. There is a general programming trick of the
trade here. When scanning data it can pay to use multiple
pointers.

Sorry mate, it's not that easy (you didn't think I haven't tried that approach before, did you?). That only solves the slightly easier version fix34 but not this fix45:

public int[] fix45(int[] nums) {
int five = 0;
int four = 0;
for (; four < nums.length; four++) {
if (nums[four] == 4) {
for (; five < nums.length && nums[five] != 5; five++);
swap(nums, four + 1, five);
}
}
return nums;
}

public void swap(int[] nums, int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}

specifically the naive attempt doesn't pass these:

* unittest * * result *
fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9} {9, 4, 9, 4, 5, 5}
fix45({4, 5, 4, 1, 5}) → {4, 5, 4, 5, 1} {4, 1, 4, 5, 5}


Adding the "in-place restriction" is what makes it extremely difficult; in the website I mentioned the online unittest uncovers many subtleties that you won't think of until you tried it yourself. I already have quite a few versions that either doesn't pass all the tests or "cheats"[1] or doesn't work in-place.

[1] by making assumptions that aren't specified in the problem description
.