Data Structure and Algorithm - Find the Largest Number by Replacing One Array to Another (Microsoft Interview Question)

1. Problem Description
This is a Microsoft interview question for software develop engineer from careercup. Here is the original thread,
"

Given two arrays were digits of one array represent a number,maxmise the number by replacing it with elements of second array. 

eg:
arr={3,1,4,5,6}
rep={1,9,5,2,3}

after replacement
arr={9,5,4,5,6}
one digit of rep can be used to replace only once.

- ritwik_pandey 14 days ago in United States | Report Duplicate | Flag ".

2. Analysis
The idea is quite simple that replace top digit in arr with the largest number in rep if it's less, and then replace the second top digit in arr with the largest number in the remaining of rep, and then so on so forth. If the current digit in arr is larger than all the remaining of rep, then go to next digit.

This problem can be solved by borrow the idea of the merging step in the merge sort. Not the exactly same but the similar pointer operations in two arrays. Sort rep array in the descending order. Have two pointers pointing to the beginning of two arrays, arrPtr and repPtr. If the digit arrPtr points to is less than repPtr, then replace it and both pointer move forward by 1. If not, then arrPtr moves forward by 1 and repPtr stays.

Pseudo code:
1. Sort rep in the descending order as sortedRep
2. Two pointers points to arr and sortedRep as arrPtr and repPtr
3. Compare the value arrPtr points to with the value repPtr points to
    * If less, replace the value arrPtr points to with the value repPtr points to
       And move arrPtr and repPtr forward by 1
    * If not less, move attPtr forward by 1
4. Repeat Step 3 until either pointer reaches the end

Complexity:
O(n) + O(mlogm),
where n = sizeof(arr) and m = sizeof(rep)

3. Example

Example 1