The Map Reducer

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3
Asked in
Booking.com

Problem

Given a list of values, the name of a mapper, and the name of a reducer, apply the mapper to every element, then combine the mapped results into a single value by folding them left to right with the reducer, starting the accumulator at the first mapped result. The mapper name is one of "double" (multiply by 2), "square" (multiply the value by itself), "increment" (add 1) or "identity" (leave the value as it is). The reducer name is one of "add", "subtract" or "multiply", applied as (accumulator, next). Return the final combined value, or None when values is empty.

Map it. Reduce it. One answer.

Example

Input:

values = [1,2,3,4], mapper = "double", reducer = "add"

Output:

20

Worked solution and explanation

A left fold in disguise

Strip the mapper/reducer costume and this is a left fold whose seed is the first mapped element, not a neutral zero. Anyone can map the list; what separates candidates is the fold's starting point. Seed the accumulator with an identity like 0 or 1 and you break the two reducers that have no clean identity: 'subtract' flips your answer's magnitude and 'multiply' collapses everything to 0. The map is the easy half; the reduce is where the interview lives.

def map_reduce(values, mapper, reducer):
    if not values:
        return None
    mapped = []
    for v in values:
        if mapper == "double":
            mapped.append(v * 2)
        elif mapper == "square":
            mapped.append(v * v)
        elif mapper == "increment":
            mapped.append(v + 1)
        else:
            mapped.append(v)
    result = mapped[0]
    for value in mapped[1:]:
        if reducer == "add":
            result = result + value
        elif reducer == "subtract":
            result = result - value
        else:
            result = result * value
    return result

Guard empty first, map every element, then fold from mapped[0] left to right.

Why the fold order is load-bearing

'add' and 'multiply' are commutative, so the visible test double+add on [1,2,3,4] hides the order entirely. 'subtract' is the tell: (((a - b) - c) - d) is nothing like reordering the operands. The fold MUST run strictly left to right, accumulator on the left, next value on the right, as (accumulator, next).

Step 1: Trace square + subtract on [3, 1]

Map first: 3*3=9, 1*1=1, giving [9, 1]. Seed result = 9. Fold the rest: 9 - 1 = 8. That is the expected 8. Seed with 0 instead and you would compute 0 - 9 - 1 = -10: wrong sign, wrong magnitude.

Seed at first element (correct)
result = mapped[0] then fold mapped[1:]. For [10,3,2] with 'subtract': 10 - 3 - 2 = 5. Single element [5] returns 5 untouched.
Seed at an identity (broken)
result = 0 then fold all. 'subtract' on [10,3,2] gives -15; 'multiply' seeded at 0 zeroes every product. No single seed works for all three reducers.

Common follow-up questions