The Character Map

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

Domain
Python
Difficulty
easy
Seniority
L6
Asked in
Quantiphi

Problem

Each record in records is a parsed log line: a single-character channel tag paired with the number of bytes that line carried. Return a dict mapping each channel tag to the total bytes across all lines that carried it.

Every character leaves a trace. Add them up.

Example 1

Input:

records = [["w",30],["e",5],["w",12]]

Output:

{"w":42,"e":5}

Example 2

Input:

records = [["i",8]]

Output:

{"i":8}

Worked solution and explanation

What this problem really is

This is a grouped sum wearing a logging costume. The real question the interviewer is asking: can you keep a running total per key while scanning a list exactly once? A set will happily tell you which tags showed up, but it throws the byte amounts on the floor. And .count() counts records, not bytes, so it answers a different question. The only thing that actually works is a dict whose values you add into as you walk the records. Miss that and a tag that appears twice either clobbers its first amount or comes back as a record count instead of a byte total.

Why a set or a count() will not save you

Rescan per tag (O(n^2))
For every distinct tag, filter the whole list and sum the matches. It is correct, but you walk the records once per tag, so 10,000 records spread across many tags balloons into millions of comparisons.
One pass (O(n))
Add each record's bytes onto its tag as you encounter it. Every record is touched exactly once, and the totals are finished the moment the scan ends.

Build it step by step

Step 1: Start with an empty totals dict

Keys will be the channel tags, values the running byte totals. A set cannot do this job: it remembers which tags appeared but has nowhere to store a per-tag sum.

Step 2: Scan the records once

Unpack each pair into its tag and byte count, then add the bytes onto that tag's running total with totals.get(tag, 0) + amount. The get default of 0 seeds a tag the first time you meet it, so the first record adds onto 0 and every later record adds onto what is already there.

Step 3: Return the totals

An empty input returns an empty dict for free, because the loop body never runs. No special case needed.

The solution

Single-pass grouped accumulation
def the_character_map(records):
    totals = {}
    for tag, amount in records:
        totals[tag] = totals.get(tag, 0) + amount
    return totals

Common follow-up questions