Re: Finding a constantspace algorithm
 From: Lie Ryan <lie.1296@xxxxxxxxx>
 Date: Fri, 25 Dec 2009 09:34:29 +1100
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 "inplace 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 inplace.
[1] by making assumptions that aren't specified in the problem description
.
 FollowUps:
 Re: Finding a constantspace algorithm
 From: Patricia Shanahan
 Re: Finding a constantspace algorithm
 References:
 Finding a constantspace algorithm
 From: Lie Ryan
 Re: Finding a constantspace algorithm
 From: Richard Harter
 Finding a constantspace algorithm
 Prev by Date: Re: Finding a constantspace algorithm
 Next by Date: Re: Finding a constantspace algorithm
 Previous by thread: Re: Finding a constantspace algorithm
 Next by thread: Re: Finding a constantspace algorithm
 Index(es):
Relevant Pages
