Google Interview Question Software Engineer / Developers
0of 0 votesCode merge sort
How will you test this function
Country: United States
Did he ask for in-place merging or was making copies of the merging arrays allowed?
In place merging is complicated ...
/ *** In Place Merge Sort ***/
public class MergeSort {
public void mergeSort(int[] arr, int low, int high){
if(high > low){
int mid = (low + high) / 2;
mergeSort(arr,low,mid);
mergeSort(arr,mid+1,high);
mergeInPlace(arr,low,mid,high);
}
}
private void mergeInPlace(int[] arr, int low, int mid, int high) {
int i = low, j = mid + 1, tempVar = 0;
while(i <= mid && j <= high){
if(arr[i] > arr[j]){
tempVar = arr[i];
arr[i] = arr[j];
int newIndex = j;
while(newIndex <= high && arr[newIndex+1] < tempVar){
arr[newIndex] = arr[newIndex+1];
newIndex++;
}
arr[newIndex] = tempVar;
j++;
}else{
i++;
}
}
for(int l=low; l<=high; l++){
System.out.print(arr[l] + " ");
}
System.out.println();
}
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
int[] arr = {1, 5, 3, 4, 6};
mergeSort.mergeSort(arr, 0, arr.length-1);
System.out.println(" ------------------- ");
int[] arr_2 = {2, 9, 3, 3, 4, 8};
mergeSort.mergeSort(arr_2, 0, arr_2.length-1);
}
}
public int[] MergeSort(int[] arr, int[] arr2)
{
int[] result = new int[arr.Length + arr2.Length];
int index = 0;
int index2 = 0;
for (int i = 0; i < result.Length; i++)
{
if (index == arr.Length)
{
for (int j = index2; j < arr2.Length; j++)
{
result[i++] = arr2[j];
}
break;
}
if (index2 == arr2.Length)
{
for (int j = index; j < arr.Length; j++)
{
result[i++] = arr[j];
}
break;
}
if (arr[index] > arr2[index2])
{
result[i] = arr2[index2];
index2++;
}
else
{
result[i] = arr[index];
index++;
}
}
return result;
}
void mergeSort (vector<int> & Arrary)
{
int len = Arrary.length();
vector<int> workArrary;
for( int blockSize = 1; blockSize < len; blockSize *= 2)
{
for (int blockHead = 0; blockHead<len; blockHead += blockSize)
{
merge(Arrary, blockHead, blockSize, workArrary);
}
}
Arrary = workArrary;
}
merge( vector<int> & Arrary, int blockHead, int blockSize, vector<int> & workArrary)
{
int leftIndex = 0;
int rightIndex = 0;
for (int i = 0; i< 2 * blockSize; i++)
{
if ( leftIndex == blockSize)
{
workArrary[i] = Arrary[blockSize + (rightIndex++)];
continue;
}
if (rightIndex == blockSize)
{
workArray[i] = Arrary[leftIndex++];
continue;
}
workArrary = Arrary[leftIndex]<Arrary[rightIndex]? Arrary[leftIndex++]: Arrary[rightIndex++];
}
}
/* test cases
* 0, 1, 0000000, 10101010,010101, 123456, 654321, -1 -2 -3 -4 -5,
*/
Merge Sort can be tested for the possible cases:
- Anonymous December 20, 20111. Giving odd and even number of terms
2. Already sorted in increasing and decreasing order
3. Repeating the middle element
4. Same term repeated for all the ith terms
5. Same number of terms and the same terms in the output so as to check the merging os proper