Pseudo code is fine for the coding part.

Question 4 (40 points) You are given a file with keys and values. The keys are in increasing order from 1 to 1,000,000, but some keys in this file may be missing. For convenience, we assume that key "1" will always exist. The goal is to reconstruct missing keys with the value from the previous key For example, if the file contains The cleaned output would be: [30 points] Assume that only one key may be missing in each gap. That is, if key k is missing, key k-1 always exists. Produce a MapReduce program that will clean the above dataset. Write the Map and Reduce functions of each program separately. Use Emit(k, v) to produce key k and value v to the output Map (Key K, Value V)