I recently appeared for MS interview and one of the question was very interesting.
So you are getting stream of sorted data in form of arrays, and you have to return a sorted array of all the merged data. The catch was the interviewer was not allowing me to use the middle array space in case of merge in merge sort.
I did give a Treemap solution which I think he was unsatisfied with cause I eventually got rejected.
But anyone here can let me know how can I do this without using any extra space?

Bonus Questions asked in Micorosoft interviews:

1. Word Search - https://leetcode.com/problems/word-search/description/
2. 0/1 Knapsack Question