Deduplicate a Member's Skills

Updated · By

Normalize each entry to a lookup key (lowercase, single spaces), map it through the alias taxonomy to its canonical name, and keep a set of names already emitted so each skill appears once, in first-seen order. Unknown skills are kept as typed. It is a single pass: O(n) time and O(n) extra space for n entries.

mediumPattern: Arrays and hashingFrom Devana's LinkedIn question set

Problem

Members type their skills freely, so one profile can list JS, Javascript, JavaScript and java script as four separate skills. Search, recommendations and endorsements all work better with one canonical entry per skill.

You are given a taxonomy that maps known aliases, already lowercased, to a canonical skill name. Write canonicalize_skills(raw_skills, taxonomy), which returns the member's skills with every alias replaced by its canonical name and every duplicate removed, without merging skills that are genuinely different.

def canonicalize_skills(raw_skills: list[str], taxonomy: dict[str, str]) -> list[str]:

This is one of Devana's own questions, written in the style of LinkedIn's interviews. It is not a question leaked from LinkedIn, and Devana is not affiliated with LinkedIn.

Constraints

  • Lookup ignores case and extra spaces: Java Script and java script are the same key.
  • A skill missing from the taxonomy is kept, spelled as the member first typed it, with surrounding spaces trimmed.
  • Each skill appears once, in the order it first appeared; spellings of an unknown skill that differ only in case count as one.
  • Matching is by whole alias, never by substring or similarity, so Java and JavaScript stay separate.
  • Blank entries are dropped.

Examples

Example 1

Input:  raw_skills = ["JS", "JavaScript", "ES6"]
        taxonomy = {"js": "JavaScript", "javascript": "JavaScript", "es6": "JavaScript"}
Output: ["JavaScript"]

Three spellings of one skill collapse to its canonical name, once.

Example 2

Input:  raw_skills = ["Java", "JavaScript", "Kubernetes"]
        taxonomy = {"java": "Java", "javascript": "JavaScript"}
Output: ["Java", "JavaScript", "Kubernetes"]

Java and JavaScript share a prefix but are different skills. Kubernetes is not in the taxonomy, so it is kept as typed rather than dropped.

Hints

Open one at a time, and try the problem again after each.

Hint 1

Two entries that differ only in case or spacing should produce the same lookup key. Decide that key first.

Hint 2

The taxonomy is already a hash map from alias to canonical name, so each raw skill needs exactly one lookup.

Hint 3

To keep first-seen order and drop repeats, walk the list once with a set of names you have already output.

Hint 4

Two unknown spellings such as Terraform and terraform should collapse too. Store names in the seen set lowercased.

Approach: from brute force to optimal

Brute force: compare with everything kept so far

For each raw skill, look it up in the taxonomy, then scan the output list to see whether that name is already there.

Complexity: O(n²) time for n entries, O(n) space

One pass with a seen set

Normalize to a key, look the key up, and test membership in a set of lowercased names already emitted. Each step is constant time on average, and appending to a list keeps the member's order.

The part worth saying out loud is what the code refuses to do: no substring matching and no edit distance. Those catch more spellings and also merge Java into JavaScript, which is a worse error than a duplicate.

Complexity: O(n × L) for names of length L, effectively O(n); O(n) extra space

How to say it in the interview

Start with what must not happen: Java and JavaScript must never merge. That shows you know why the tempting fixes are wrong before you write anything. Then describe the normalized key, the single taxonomy lookup and the seen set that preserves order, and state O(n).

Solution

Python

def canonicalize_skills(raw_skills, taxonomy):
    result, seen = [], set()
    for raw in raw_skills:
        key = " ".join(raw.lower().split())        # case and spacing never matter
        if not key:
            continue
        name = taxonomy.get(key, " ".join(raw.split()))
        if name.lower() not in seen:
            seen.add(name.lower())
            result.append(name)
    return result

JavaScript

function canonicalizeSkills(rawSkills, taxonomy) {
  const result = [];
  const seen = new Set();
  for (const raw of rawSkills) {
    const words = raw.split(/\s+/).filter(Boolean);
    const key = words.join(" ").toLowerCase(); // case and spacing never matter
    if (!key) continue;
    const name = Object.hasOwn(taxonomy, key) ? taxonomy[key] : words.join(" ");
    if (!seen.has(name.toLowerCase())) {
      seen.add(name.toLowerCase());
      result.push(name);
    }
  }
  return result;
}

Both versions are tested against the same cases, including every example on this page.

  • Unknown skills keep the member's spelling. Dropping them would delete real skills the taxonomy has not caught up with yet.
  • The seen set holds lowercased canonical names, so two unknown spellings that differ only in case still collapse.
  • Object.hasOwn keeps a skill typed as constructor from matching a built-in property of the taxonomy object.

Follow-up questions

Why is edit distance dangerous here?

Short names that look alike are often different technologies: Java and JavaScript, C and C#, React and Preact. A threshold loose enough to catch typos merges them, and a wrong merge is worse than a duplicate.

How can co-occurrence with other skills help?

Skills listed together hint at meaning. An unknown alias that keeps appearing next to React and TypeScript is more likely JavaScript tooling than Java. Use that to suggest taxonomy entries for review, not to merge automatically.

How does a genuinely new skill enter the taxonomy?

Count unknown keys across all members. Ones that pass a threshold go to a review queue, where a person adds them as an alias of an existing skill or as a new canonical one.

How would you audit the taxonomy for wrong merges?

Look for canonical skills whose aliases rarely appear alongside each other's usual neighbors, and sample the members whose lists changed most after canonicalization.

Common mistakes

  • Matching by substring or prefix, which merges Java into JavaScript.
  • Dropping skills that are not in the taxonomy.
  • Deduplicating before mapping aliases, so JS and JavaScript both survive.
  • Returning a set, which loses the order the member chose.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Practice this problem out loud

Josh, Devana's AI interviewer, runs this exact problem as a voice mock interview, asks follow-ups like the ones above, and scores you out of 100. The Free plan has 3 interviews a month, no card needed.

Practice this problem in a mock interview