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 Upstart.

What role is this question designed for?

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

Decode an anagram sentence using vocabulary constraints

Quick Overview

This question evaluates string manipulation, anagram detection, and constrained dictionary mapping skills, testing attention to character-level constraints and correct disambiguation among similar vocabulary entries.

Loading coding console...

Part 2: Decode a Doubly Encrypted Message Using Inferred Cipher Keys

A message from C back to A was encrypted twice. First, the sender applied the same character-substitution rule used for messages from A to B. Then, they applied the same character-substitution rule used for messages from B to C. You are given one known plaintext/ciphertext pair for A to B and one known plaintext/ciphertext pair for B to C. Infer both substitution rules, then decode the final message by reversing the B to C cipher first and the A to B cipher second. Each hop uses a one-to-one per-character substitution. If any sample pair is inconsistent, or if the final message contains a character that cannot be decrypted, return an empty string.

Constraints

0 <= len(clear_msg_ab), len(ciphered_msg_ab), len(clear_msg_bc), len(ciphered_msg_bc), len(ciphered_msg_cba) <= 100000
All strings contain lowercase English letters only
Within each sample pair, the same plaintext character must always map to the same ciphertext character, and vice versa

Examples

Input: ('abcd', 'mnop', 'mnop', 'xyzw', 'yxwz')

Expected Output: 'badc'

Explanation: Decrypt yxwz with the inverse of B to C to get nmpo, then decrypt nmpo with the inverse of A to B to get badc.

Input: ('aaaa', 'bbbb', 'bbbb', 'cccc', 'cccc')

Expected Output: 'aaaa'

Explanation: Repeated characters are allowed as long as the mapping stays consistent.

Input: ('', '', '', '', '')

Expected Output: ''

Explanation: An empty message decodes to an empty message.

Input: ('ab', 'cd', 'cd', 'ef', 'eg')

Expected Output: ''

Explanation: The final message contains g, but the B to C sample does not provide a way to decrypt it.

Input: ('aa', 'ab', 'bc', 'de', 'de')

Expected Output: ''

Explanation: The A to B sample is inconsistent because a maps to both a and b.

Hints

Build the inverse substitution map for each known cipher pair, because decoding goes from cipher character back to clear character.
Validate consistency while building the map: one plaintext character cannot map to two ciphertext characters, and one ciphertext character cannot map to two plaintext characters.

Part 3: Compute Buffet Revenue with Capacity Limits and Repeated Visits

A buffet restaurant has a maximum seating capacity. You are given an array payments where payments[i] is how much customer i is willing to pay, and an event list events where each value is a customer ID. For each customer, the first appearance means they arrive, the second means they leave, the third means they arrive again, and so on. If a customer arrives when the restaurant is full, they wait outside until their matching leave event; they never take a seat during that visit. A customer pays only the first time they successfully get a seat, even if they visit again later. Return the total revenue earned.

Constraints

0 <= capacity <= 100000
0 <= len(payments) <= 100000
0 <= len(events) <= 200000
0 <= payments[i] <= 10^9
Every customer ID in events is a valid index into payments
For each customer, appearances alternate arrival and departure, starting with arrival

Examples

Input: (2, [10, 20, 30], [0, 1, 2, 0, 2])

Expected Output: 30

Explanation: Customers 0 and 1 get seats and pay. Customer 2 arrives when full, waits outside, and leaves without paying.

Input: (1, [5, 7], [0, 0, 0, 0, 1, 1])

Expected Output: 12

Explanation: Customer 0 visits twice but pays only once. Customer 1 pays on their first successful entry.

Input: (1, [4, 6], [0, 1, 0, 1, 1, 1])

Expected Output: 10

Explanation: Customer 1 first waits outside and pays nothing, then later returns when a seat is available and pays 6.

Input: (0, [8, 9], [0, 0, 1, 1])

Expected Output: 0

Explanation: With zero capacity, nobody can ever enter.

Input: (3, [2, 4], [])

Expected Output: 0

Explanation: No events means no customers and no revenue.

Hints

Track each customer in one of three states: absent, inside, or waiting.
Use a set to remember which customers have already paid so you never charge them twice.

Part 4: Decode an Anagram Sentence Using Vocabulary Constraints

You are given a vocabulary list and a sentence whose words have been scrambled. Each scrambled word is an anagram of exactly one vocabulary word, and it must have the same first and last character as the original word. Decode the sentence by replacing every scrambled word with its matching vocabulary word. If any scrambled word cannot be matched uniquely, return an empty string.

Constraints

0 <= len(vocabulary) <= 100000
0 <= total number of characters across all vocabulary words and the sentence <= 200000
All words contain lowercase English letters only
Vocabulary words are non-empty

Examples

Input: (['pears', 'spear', 'something'], 'seapr sothinmeg')

Expected Output: 'spear something'

Explanation: seapr matches spear because they are anagrams and both start with s and end with r.

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

Expected Output: ''

Explanation: An empty sentence decodes to an empty sentence.

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

Expected Output: 'a b'

Explanation: Single-letter words are their own anagrams and have the same first and last character.

Input: (['listen', 'silent'], 'tinsel')

Expected Output: ''

Explanation: Although tinsel is an anagram, it does not share the first and last characters with either vocabulary word.

Input: (['reaps', 'rapes', 'pear'], 'rpeas')

Expected Output: ''

Explanation: rpeas could match both reaps and rapes under the given key, so decoding is ambiguous.

Hints

A useful key is based on length, first character, last character, and the multiset of letters.
Be careful: two different vocabulary words can have the same sorted letters, so you must include the first and last characters too.

Last updated: Apr 19, 2026

Quick Overview