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.

Decrypt a twice-encrypted message using known pairs

Quick Overview

This question evaluates the ability to reconstruct and compose bijective character-substitution mappings, testing competency in string manipulation, mapping inference, and basic cipher reasoning.

Loading coding console...

Part 2: Decrypt a Twice-Encrypted Message Using Known Pairs

You are given two known plaintext/ciphertext pairs. Each pair was produced using a Caesar cipher with one fixed shift over lowercase English letters. The first pair reveals the A->B shift, and the second pair reveals the B->C shift. A message from C to A was encrypted twice: first with the A->B shift, then with the B->C shift. Decrypt the final ciphertext by reversing those two shifts.

Constraints

1 <= len(clearMsgAb) == len(cipheredMsgAb) <= 10^5
1 <= len(clearMsgBc) == len(cipheredMsgBc) <= 10^5
0 <= len(cipheredMsgCba) <= 10^5
Each known pair uses one consistent Caesar shift for every character
All strings contain only lowercase letters a-z

Examples

Input: ('abc', 'bcd', 'xyz', 'zab', 'zruog')

Expected Output: 'world'

Explanation: A->B shift is 1, B->C shift is 2. Decrypt by -2, then -1.

Input: ('abc', 'abc', 'bcd', 'cde', '')

Expected Output: ''

Explanation: Edge case: empty final ciphertext decrypts to an empty string.

Input: ('az', 'cb', 'lmn', 'opq', 'cde')

Expected Output: 'xyz'

Explanation: Shifts are 2 and 3, so the total encryption shift was 5.

Input: ('hello', 'hello', 'world', 'world', 'same')

Expected Output: 'same'

Explanation: Both shifts are 0, so the message is unchanged.

Hints

Recover each shift by comparing any plaintext character with its ciphertext counterpart.
To undo double encryption, decrypt in the reverse order of encryption.

Part 3: Calculate Buffet Revenue with Capacity Limits and Repeat Visits

A buffet has limited seating capacity. payments[i] is how much customer i is willing to pay. events is a sequence of customer IDs. For each customer, the 1st, 3rd, 5th, ... appearance means that customer arrives; the 2nd, 4th, 6th, ... appearance means that customer leaves. If a customer arrives when the buffet is full, they join a FIFO waiting queue. Whenever a seat opens, the earliest waiting customer is seated immediately before the next event. A customer pays only once in total: the first time they actually get seated, even if they visit multiple times later. If a waiting customer leaves before getting seated, they pay nothing for that visit. Return the total revenue.

Constraints

0 <= capacity <= 10^5
0 <= len(payments) <= 10^5
0 <= len(events) <= 2 * 10^5
0 <= events[i] < len(payments) when events is non-empty
The event stream is valid: each customer's occurrences alternate arrival, departure, arrival, departure, ...

Examples

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

Expected Output: 60

Explanation: All three customers eventually get seated once, so revenue is 10 + 20 + 30.

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

Expected Output: 11

Explanation: Customer 1 waits, then gets seated immediately when customer 0 leaves.

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

Expected Output: 12

Explanation: Customer 1 is seated once from the waiting line and visits again later, but pays only on the first successful seating.

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

Expected Output: 0

Explanation: Edge case: capacity is zero, so nobody can ever be seated.

Input: (5, [], [])

Expected Output: 0

Explanation: Edge case: no customers and no events.

Hints

Track which customers are currently seated and which are waiting.
You need FIFO order for the waiting line, but a waiting customer may also leave before being seated.

Part 4: Decode an Anagram-Based Scrambled String Using a Vocabulary List

You are given a vocabulary list and a scrambled sentence. Every scrambled word is an anagram of exactly one vocabulary word, and it also has the same first and last character as the correct vocabulary word. Decode the full sentence. The uniqueness guarantee matters because some vocabulary words may share the same letters, such as 'pears' and 'spear'.

Constraints

1 <= len(vocabulary) <= 10^5
The total length of all vocabulary words is at most 2 * 10^5
The total length of the scrambled sentence is at most 2 * 10^5
All words contain only lowercase English letters
The scrambled sentence may be empty
Each scrambled word matches exactly one vocabulary word

Examples

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

Expected Output: 'spear something'

Explanation: Both 'pears' and 'spear' have the same letters, but 'seapr' starts with 's' and ends with 'r', so it maps to 'spear'.

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

Expected Output: 'a'

Explanation: Edge case: single-letter word.

Input: (['listen', 'silent', 'evil', 'vile'], 'litsen vlie')

Expected Output: 'listen vile'

Explanation: The anagram key plus matching first/last letters gives a unique answer for each word.

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

Expected Output: ''

Explanation: Edge case: empty sentence.

Input: (['dusty', 'study'], 'sutdy dtsuy')

Expected Output: 'study dusty'

Explanation: These two vocabulary words are anagrams, so the first and last characters are needed to distinguish them.

Hints

A plain character-count signature is not enough if two vocabulary words are anagrams of each other.
Include the first and last character in the key you build for each word.

Quick Overview