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 Onsite rounds at Amazon.

What role is this question designed for?

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

Replace Delimited Tokens in a String | Amazon Coding Question

Replace Delimited Tokens in a String

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an input string `s` and a dictionary `replacements` mapping keys to replacement strings, replace every placeholder in `s` with its corresponding value. A placeholder is defined as a substring that: - starts with a semicolon `;`, - is followed by a non-empty key consisting of lowercase English letters, digits, or underscores, - ends with a colon `:`. For example, if `replacements = {"name": "Alice", "city": "Seattle"}`, then: ```text s = "Hello ;name:, welcome to ;city:." ``` should become: ```text "Hello Alice, welcome to Seattle." ``` Requirements: - Replace every placeholder whose key exists in `replacements`. - If a placeholder is malformed or its key does not exist in `replacements`, leave the original text unchanged. - Return the transformed string. - Aim for an efficient solution in both time and space. Discuss the time and space complexity of your approach.

Quick Answer: This question evaluates string parsing, token recognition, and dictionary lookup competencies for robust text replacement, including handling malformed placeholders and missing keys.

Given a string s and a dictionary replacements, return a new string where each valid placeholder is replaced by its mapped value. A valid placeholder has the form ;key:, where key is non-empty and every character in key is a lowercase English letter, a digit, or an underscore. Rules: - If key exists in replacements, replace the whole placeholder with replacements[key]. - If the placeholder is well-formed but key does not exist in replacements, leave it unchanged. - If a sequence starting with ';' is malformed (for example, empty key, missing ending ':', or an invalid character inside the key), leave the original text unchanged. - Replacement text is inserted as-is and is not parsed again. Return the transformed string.

Constraints

0 <= len(s) <= 200000
Keys in valid placeholders contain only lowercase English letters, digits, and underscores
replacements maps string keys to string values

Examples

Input: ("Hello ;name:, welcome to ;city:.", {"name": "Alice", "city": "Seattle"})

Expected Output: "Hello Alice, welcome to Seattle."

Explanation: Both ;name: and ;city: are valid placeholders, and both keys exist in replacements.

Input: ("User ;user:, role ;role:.", {"user": "Bob"})

Expected Output: "User Bob, role ;role:."

Explanation: ;user: is replaced with Bob, but ;role: is left unchanged because role is not in the dictionary.

Input: ("Bad ;token and empty ;: plus good ;ok:.", {"token": "X", "ok": "yes"})

Expected Output: "Bad ;token and empty ;: plus good yes."

Explanation: ;token is malformed because it has no closing colon, ;: is malformed because the key is empty, and ;ok: is valid and replaced.

Input: (";a1:;b_2:!", {"a1": "X", "b_2": "Y"})

Expected Output: "XY!"

Explanation: Adjacent placeholders are both valid and should both be replaced.

Input: ("Mix ;bad-key: and ;good_key1:.", {"good_key1": "OK", "bad": "NO"})

Expected Output: "Mix ;bad-key: and OK."

Explanation: ;bad-key: is malformed because '-' is not allowed in a key, so it stays unchanged. ;good_key1: is valid and replaced.

Input: ("", {"name": "Alice"})

Expected Output: ""

Explanation: An empty input string remains empty.

Hints

Scan the string from left to right. When you see ';', try extending a second pointer over a valid key and check whether the next character is ':'.
Build the answer using a list of string pieces and join at the end to avoid expensive repeated string concatenation.

Quick Overview

This question evaluates string parsing, token recognition, and dictionary lookup competencies for robust text replacement, including handling malformed placeholders and missing keys.