How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Find Shortest Unique Prefixes | Meta Coding Question

Find Shortest Unique Prefixes

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a list of distinct non-empty words, return the shortest unique prefix for each word in the same order as the input. A prefix of a word is considered unique if no other word in the list starts with that prefix. If multiple prefix lengths are possible, choose the shortest one. If no shorter prefix uniquely identifies the word, the entire word is the answer. **Example** Input: ```text ["zebra", "dog", "duck", "dove"] ``` Output: ```text ["z", "dog", "du", "dov"] ``` **Constraints** - The input contains at least one word. - All words are distinct. - Words contain only lowercase English letters. - Return the prefixes in the original input order.

Quick Answer: This question evaluates string-processing skills and understanding of data structures for prefix management (e.g., tries), along with algorithmic efficiency and edge-case reasoning.

Given a list of distinct non-empty lowercase words, return the shortest identifying prefix for each word in the same order as the input. A non-empty prefix is unique if no other word in the list starts with that prefix. If multiple prefix lengths are unique, choose the shortest one. If a word is itself a prefix of another word and therefore has no unique prefix within its own length, return the entire word.

Constraints

1 <= len(words) <= 10^4
1 <= len(words[i]) <= 10^3
The total number of characters across all words is at most 2 * 10^5
All words are distinct
Words contain only lowercase English letters

Examples

Input: (['zebra', 'dog', 'duck', 'dove'],)

Expected Output: ['z', 'dog', 'du', 'dov']

Explanation: 'z' only starts zebra. For dog, 'd' and 'do' are shared with other words, so 'dog' is needed. Duck is identified by 'du', and dove by 'dov'.

Input: (['alone'],)

Expected Output: ['a']

Explanation: With only one word, the first character is already unique.

Input: (['apple', 'ape', 'april', 'bat'],)

Expected Output: ['app', 'ape', 'apr', 'b']

Explanation: The three words starting with 'ap' need one more character to become distinguishable. 'bat' is uniquely identified by 'b'.

Input: (['app', 'apple', 'apricot', 'banana'],)

Expected Output: ['app', 'appl', 'apr', 'b']

Explanation: 'app' is a prefix of 'apple', so no shorter prefix uniquely identifies it and the full word is returned. 'apple' needs 'appl', 'apricot' needs 'apr', and 'banana' needs only 'b'.

Input: (['a', 'b', 'c'],)

Expected Output: ['a', 'b', 'c']

Explanation: Each one-character word is already uniquely identified by its only character.

Input: (['interview', 'internet', 'internal', 'interval'],)

Expected Output: ['intervi', 'interne', 'interna', 'interva']

Explanation: All words share 'inter'. The next characters still create pairs, so each word needs one more distinguishing character after that shared section.

Hints

Consider building a trie where each node records how many words share the prefix represented by that node.
For each word, walk through the trie until you reach the first node whose count is 1.

Quick Overview

This question evaluates string-processing skills and understanding of data structures for prefix management (e.g., tries), along with algorithmic efficiency and edge-case reasoning.