Unique Identifier Generator — Problem Statement & Solution Guide

HashingMediumMixed

TimeO(n * L)

SpaceO(n)

Problem Description

You are given an array of book objects. Each book has three string fields: title, author, and a four‑digit string year. Your task is to produce a list of unique identifiers, one for each book, following these rules:

1. Construct a base identifier by concatenating the title, author, and year with hyphens, replacing any spaces in the title or author with underscores. For example, a book with title "The Great Gatsby", author "F. Scott Fitzgerald", and year "1925" yields the base id "The_Great_Gatsby-F._Scott_Fitzgerald-1925".

2. If the base identifier has not appeared before, use it as the final identifier.

3. If the base identifier has already been used, append a hyphen followed by the smallest positive integer that makes the identifier unique. For instance, if "The_Great_Gatsby-F._Scott_Fitzgerald-1925" already exists, the next duplicate becomes "The_Great_Gatsby-F._Scott_Fitzgerald-1925-1", the following one "The_Great_Gatsby-F._Scott_Fitzgerald-1925-2", and so on.

Return the list of identifiers in the same order as the input books.

Input format:

- An array of objects, each with keys "title", "author", and "year".

Output format:

- An array of strings, each string being the unique identifier for the corresponding book.

The function should run efficiently even when the input array contains up to 10^5 books.

DSA Pattern Breakdown

"Unique Identifier Generator"

medium

WHY DOES IT MATTER?

Hash‑based deduplication ensures that each identifier is unique in constant time, which is essential for systems that rely on unique keys for indexing, caching, or routing. Without it, duplicate identifiers could cause data corruption, race conditions, or incorrect query results.

OPTIMIZATION CHALLENGE

The key insight is to use the base identifier itself as the hash key, allowing O(1) detection of duplicates. This eliminates the need for nested loops or repeated scans of the output list, reducing the time complexity from quadratic to linear.

REAL-WORLD CONNECTION

In distributed databases like Cassandra or DynamoDB, partition keys must be unique to avoid data loss. Similarly, URL shorteners generate unique tokens for each long URL; they use hash maps or databases to detect collisions and append suffixes or random strings to maintain uniqueness.

When implementing the algorithm, preallocate a StringBuilder (or equivalent) for each identifier to avoid repeated string concatenations, which can be expensive in languages with immutable strings. Also, consider using a case‑insensitive hash map if the business logic treats "Title" and "title" as the same.

COMPLEXITY AT A GLANCE

⏱ Time:O(n * L)

💾 Space:O(n)

Core Theory — Why This Approach?

The Unique Identifier Generator problem is fundamentally a string manipulation and deduplication task. A naive approach would simply concatenate the title, author, and year with hyphens, replacing spaces with underscores, for each book. While this works for small datasets, it fails to guarantee uniqueness when two books share the same title, author, and year, leading to collisions that can break downstream systems such as databases or APIs. The optimal paradigm introduces a hash map (or dictionary) to track how many times a particular base identifier has already appeared. When a duplicate is encountered, the algorithm appends a numeric suffix (e.g., "-1", "-2") to the base identifier, ensuring each output string is unique. This approach guarantees O(1) average‑time lookups for duplicate detection, keeping the overall time complexity linear in the number of books and the average length of the string fields. It also uses O(n) additional space to store the counts, which is acceptable for typical input sizes.

The core algorithmic pattern here is *hash‑based deduplication*, a common technique in distributed systems for generating unique keys, sharding data, or de‑duplicating logs. By leveraging a hash map, we avoid the quadratic cost of repeatedly scanning the output list for duplicates, which would be prohibitive for large inputs. The key insight is that the identifier construction is deterministic and can be used as a hash key, allowing constant‑time checks and updates.

In practice, this pattern is essential when you need to generate stable, collision‑free identifiers for entities that may have identical attributes, such as user accounts, product SKUs, or log entries. The same technique underlies URL shorteners, cache keys, and distributed transaction IDs, where uniqueness and performance are critical.

Interview Questions on This Problem

Q1How would you modify the algorithm if the year field could be missing or malformed?

I would first validate the year string to ensure it is a four‑digit numeric value. If it is missing or malformed, I would replace it with a placeholder like "0000" or "unknown" before constructing the base identifier. This guarantees that the identifier remains deterministic and that the hash map can still detect duplicates based on the corrected year.

Q2What is the time complexity of generating identifiers for n books, each with average string length L?

The time complexity is O(n * L). For each book, we perform a constant amount of string operations proportional to the combined length of title, author, and year, and we perform O(1) hash map operations to check and update counts.

Q3Explain how you would handle case sensitivity to avoid accidental duplicates in titles or authors.

I would normalize the title and author strings by converting them to a consistent case (e.g., all lowercase) before constructing the base identifier. This ensures that "Harry Potter" and "harry potter" are treated as the same key, preventing duplicate identifiers that differ only by case.

Examples

Example 1

Input

[{"title":"1984","author":"George Orwell","year":"1949"},{"title":"To Kill a Mockingbird","author":"Harper Lee","year":"1960"},{"title":"The Hobbit","author":"J.R.R. Tolkien","year":"1937"}]

Output

["1984-George_Orwell-1949","To_Kill_a_Mockingbird-Harper_Lee-1960","The_Hobbit-J.R.R._Tolkien-1937"]

Explanation: All three books produce distinct base identifiers, so no counters are added.

Example 2

Input

[{"title":"Dune","author":"Frank Herbert","year":"1965"},{"title":"Dune","author":"Frank Herbert","year":"1965"},{"title":"Dune","author":"Frank Herbert","year":"1965"}]

Output

["Dune-Frank_Herbert-1965","Dune-Frank_Herbert-1965-1","Dune-Frank_Herbert-1965-2"]

Explanation: The first book uses the base id. The second duplicate receives '-1', and the third receives '-2'.

Example 3

Input

[{"title":"The Catcher in the Rye","author":"J.D. Salinger","year":"1951"},{"title":"The Catcher in the Rye","author":"J.D. Salinger","year":"1951"},{"title":"The Catcher in the Rye","author":"J.D. Salinger","year":"1951"},{"title":"The Catcher in the Rye","author":"J.D. Salinger","year":"1951"}]

Output

["The_Catcher_in_the_Rye-J.D._Salinger-1951","The_Catcher_in_the_Rye-J.D._Salinger-1951-1","The_Catcher_in_the_Rye-J.D._Salinger-1951-2","The_Catcher_in_the_Rye-J.D._Salinger-1951-3"]

Explanation: Each subsequent duplicate appends an incrementing counter to maintain uniqueness.

Constraints

1 <= books.length <= 100000
1 <= title.length <= 100
1 <= author.length <= 100
year is a string of exactly 4 digits between "1000" and "9999
All input strings contain only printable ASCII characters

Optimal Approach & Strategy

Use a hash map to store counts of each base identifier. For each book, generate the base identifier, look up its count, and if >0, append the count as a suffix. Increment the count in the map. This runs in O(n) time with O(n) space.

Brute Force Approach

Create the base identifier for each book by concatenating fields. Then, for each new identifier, scan the list of already generated identifiers to check for duplicates and, if found, append a suffix. This requires nested loops and is O(n^2) in the worst case.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n * L)

function generateUniqueIdentifiers(books) {
    const identifiers = {};
    const result = [];
    for (const book of books) {
        let identifier = `${book.title}_${book.author}_${book.year}`;
        if (identifiers[identifier]) {
            identifiers[identifier]++;
            identifier += `_${identifiers[identifier]}`;
        } else {
            identifiers[identifier] = 0;
        }
        result.push(identifier);
    }
    return result;
}

class Solution {
public:
    std::vector<std::string> generateUniqueIdentifiers(std::vector<Book> books) {
        std::unordered_map<std::string, int> identifiers;
        std::vector<std::string> result;
        for (const auto& book : books) {
            std::string identifier = book.title + "_" + book.author + "_" + std::to_string(book.year);
            if (identifiers.find(identifier) != identifiers.end()) {
                identifiers[identifier]++;
                identifier += "_" + std::to_string(identifiers[identifier]);
            } else {
                identifiers[identifier] = 0;
            }
            result.push_back(identifier);
        }
        return result;
    }
};

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public String[] generateUniqueIdentifiers(Book[] books) {
        Map<String, Integer> identifiers = new HashMap<>();
        String[] result = new String[books.length];
        for (int i = 0; i < books.length; i++) {
            String identifier = books[i].getTitle() + "_" + books[i].getAuthor() + "_" + books[i].getYear();
            if (identifiers.containsKey(identifier)) {
                identifiers.put(identifier, identifiers.get(identifier) + 1);
                identifier += "_" + identifiers.get(identifier);
            } else {
                identifiers.put(identifier, 0);
            }
            result[i] = identifier;
        }
        return result;
    }
}

def generate_unique_identifiers(books):
    identifiers = {}
    result = []
    for book in books:
        identifier = f"{book['title']}_{book['author']}_{book['year']}"
        if identifier in identifiers:
            identifiers[identifier] += 1
            identifier += f"_{identifiers[identifier]}"
        else:
            identifiers[identifier] = 0
        result.append(identifier)
    return result

function generateUniqueIdentifiers(books) {
    const identifiers = {};
    const result = [];
    for (const book of books) {
        let identifier = `${book.title}_${book.author}_${book.year}`;
        if (identifiers[identifier]) {
            identifiers[identifier]++;
            identifier += `_${identifiers[identifier]}`;
        } else {
            identifiers[identifier] = 0;
        }
        result.push(identifier);
    }
    return result;
}

Asked in Top Tech Interviews

uncategorizedmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Unique Identifier Generator Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Unique Identifier Generator — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor