Interview Question
Any balanced tree will do I suppose, not necessarily splay trees.
And it is O(n log n) not O(m log m): Do you even care about elements n+1 to m?
btw, 0...n is not right I think. You have to ignore the initial decreasing sequence..
For instance n=2 and you have
32456
You will return 32456, but 35246 is larger.
Sorry I had a brain fart. Yes, this looks right to me now.
O(m log n) is doable using a max-heap of n elements.
Basically the left most number can only come from [0,...n] and if that can be changed, it is always better to change it. Then we try to determine the second left most and so on.
One possibly problem might be with repeated numbers, but in that case I guess we can choose the max which was the left most in order to save some movement cost.
Nice solution.
<pre lang="" line="1" title="CodeMonkey851" class="run-this">class MakeItLargest {
public static void main(String[] args) {
println(makeItLargest(new int[] { 1, 2, 3, 4, 5 }, 3, 0));
println(makeItLargest(new int[] { 1, 2, 3, 4, 5 }, 4, 0));
println(makeItLargest(new int[] { 1, 2, 3, 4, 5 }, 5, 0));
println(makeItLargest(new int[] { 1, 2, 3, 4, 5 }, 6, 0));
println(makeItLargest(new int[] { 1, 2, 3, 4, 5 }, 7, 0));
}
public static int[] makeItLargest(int[] a, int n, int start) {
if (n <= 0) {
return a;
}
int max = Integer.MIN_VALUE;
int maxIndex = -1;
for (int i = start, length = start + n; i <= length && i < a.length; i++) {
if (max < a[i]) {
maxIndex = i;
}
}
for (int i = maxIndex; i > start; i--) {
int tmp = a[i];
a[i] = a[i - 1];
a[i - 1] = tmp;
}
makeItLargest(a, n - (maxIndex - start), start + 1);
return a;
}</pre><pre title="CodeMonkey851" input="yes">
</pre>
Find the largest number in positions 0..n, move it to position 0, recurse on the rest of the array with the remaining moves. When implemented with a max-decorated binary tree, this algorithm is O(m log m), where m is the size of the array.
- Anonymous September 04, 2011