In Cracking the Coding Interview by Gayle Laakmann McDowell, there's a question that asks you to write code for the following:
Given two sorted arrays, A and B. Write a method merging the elements of B into A in sorted order. Assume A has a large enough buffer at the end to hold all of B's elements.
Though the problem isn't very hard, I've been striving to increase the readability of my code in general. As such, I wrote two versions of my solution, and am looking for input on which version is most readable.
Version 1:
// Given two sorted arrays, adds the elements of the second array into
// the first, while maintaining ordering property.
// XXX: Assumes first array has enough buffer space to hold all elements
public static <Type extends Comparable<Type>> Type[]
mergeIntoFirstArray(Type[] first_array, Type[] second_array) {
int first_idx = numElementsInArray(first_array) - 1;
int second_idx = second_array.length - 1;
int merge_idx = numElementsInArray(first_array) + second_array.length - 1; //
// merge largest values first, until either array is exhausted
while (first_idx >= 0 && second_idx >= 0) {
Type first_value = first_array[first_idx];
Type second_value = second_array[second_idx];
// add the largest value
if (first_value.compareTo(second_value) > 0){
first_array[merge_idx] = first_value ;
first_idx--;
} else {
first_array[merge_idx] = second_value ;
second_idx--;
}
merge_idx-- ;
}
// if second_array still has values, merge them in
while (second_idx >=0) {
first_array[merge_idx] = second_array[second_idx] ;
merge_idx-- ;
second_idx--;
}
return first_array ;
}
Version 2:
public static <Type extends Comparable<Type>> Type[]
mergeIntoFirstArrayV2(Type[] first_array, Type[] second_array) {
int f = numElementsInArray(first_array)-1;
int s = second_array.length - 1;
// merge in largest values first
for (int merge_idx = f + s + 1 ; merge_idx >= 0 ; merge_idx--) {
Type fvalue = f >= 0 ? first_array[f] : null;
Type svalue = s >= 0 ? second_array[s] : null;
// first value exists, and is greater than second value
if (fvalue != null &&
(svalue == null || fvalue.compareTo(svalue) > 0)) {
first_array[merge_idx] = svalue ;
s_idx--;
}
else {
first_array[merge_idx] = svalue ;
s_idx--;
}
}
return first_array ;
}
Any meaningful input on improving the readability of either method would also be appreciated. For one, I think my variable names might be unclear or too long in some cases. For version 2, I suspect that though the code is more concise, it is harder to understand at a glance.
yield
as well as a look-ahead iterator (something that allows to peek cheaply), then this problem would have a beautiful solution. Otherwise, it feels kind of ugly at the end. \$\endgroup\$ – Leonid Nov 23 '12 at 13:45