Upstart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Coding round at Upstart for a software engineer role. The problem looked like a cipher/crypto puzzle at first glance but was really just a composition of two substitution maps, which made it more approachable once I saw what was actually being asked.

Questions Asked (1)

You have two substitution cipher mappings: one used between sender A and B, and another between B and C. Given the final ciphertext that D receives after both substitutions have been applied, recover the original plaintext A wrote.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to try reversing each map separately in sequence, which would've worked but felt clunky.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the two substitution ciphers are applied sequentially (A→B then B→C), so the final ciphertext is the result of composing the two mappings. Then invert the composition: first invert the B→C mapping to recover the intermediate ciphertext, then invert the A→B mapping to recover the original plaintext. Discuss how to represent and invert the mappings efficiently, and handle edge cases like missing mappings or non-bijective substitutions.

Pro tip: Mention that if the substitutions are not bijective (e.g., many-to-one), the original plaintext may not be uniquely recoverable, so you should ask clarifying questions about the cipher properties before assuming invertibility. This shows you think about ambiguity and real-world constraints.

1. Clarify the cipher composition

Confirm that the two substitution ciphers are applied in sequence: first A→B, then B→C, so the final ciphertext is C(B(A(plaintext))). Ask whether the mappings are one-to-one (bijective) and whether they are given as full tables or partial mappings.

2. Model the mappings

Represent each substitution as a dictionary or array mapping input characters to output characters. For inversion, build reverse mappings (cipher→plain) for each substitution, noting any collisions or missing entries.

3. Invert in reverse order

Starting from the final ciphertext, apply the inverse of the B→C mapping to get the intermediate ciphertext, then apply the inverse of the A→B mapping to get the original plaintext. This is equivalent to computing the inverse of the composed function.

4. Handle edge cases and complexity

Discuss what happens if a character is not in the reverse mapping (e.g., return error or placeholder), or if the mapping is not bijective (multiple plaintexts possible). Analyze time complexity: O(n) for n characters, assuming O(1) dictionary lookups.

5. Optimize and generalize

Optionally, precompute the composed inverse mapping (C→A) to decode in a single pass. Mention that this approach generalizes to any number of sequential substitutions by composing inverses in reverse order.

Key Points to Mention

Composition of functions: final ciphertext = C(B(A(plaintext))), so plaintext = A^{-1}(B^{-1}(C^{-1}(ciphertext)))
Representation of substitution ciphers as dictionaries or arrays for O(1) lookup
Inversion requires bijective mappings; if not, plaintext may be ambiguous
Time and space complexity: O(n) time, O(1) extra space if mappings are fixed size (e.g., 26 letters)
Edge cases: characters missing from reverse mapping, non-bijective substitutions, empty input
Optimization: precompute composed inverse mapping for single-pass decoding

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.