CareerCup

A and B are unsorted.
Example: A={1, 2, 0, 4, 3, 2, 1, 5, 7} B={2, 8, 0, 7, 6, 5, 3, 4, 5, 6, 5} then o/p array Z={2, 2, 2, 4, 3, 3, 5, 6, 7}

To solve this problem, we can follow the following steps:

Create a hashmap of the values in array A, where the keys are the values and the values are the indices.
Sort array B in ascending order.
Iterate through each value b in B.
If b is greater than the maximum value in A, we can skip it since it won't have any effect.
If b is less than or equal to the minimum value in A, we can also skip it since it won't have any effect.
Find the index i of the smallest value in A that is greater than or equal to b using binary search.
Increment the value of A[i-1] by 1.
If A[i-1] equals A[i], remove A[i-1] from the hashmap.
Append the updated A to the output array Z.
Return Z.
The worst-case time complexity of this algorithm is O(M + N + H), where H is the maximum value in array B. This is because we need to iterate through all the values in A and B and perform binary search for each value in B. The worst-case space complexity is O(M), as we only need to store the hashmap of values in A.

Here is the Python code for this algorithm:
def generate_output_array(A, B):
value_index_map = {value: index for index, value in enumerate(A)}
B.sort()
output = []
for b in B:
if b > A[-1] or b <= A[0]:
continue
i = bisect_left(A, b)
A[i-1] += 1
if A[i-1] == A[i]:
del value_index_map[A[i-1]]
output = A[:]
return output