Amazon·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

Amazon Research Scientist coding screen, one algorithm question and then some discussion about how you'd extend it. Pretty straightforward but the follow-up conversation about streaming variants was where things got interesting.

Questions Asked (1)

Given a string, find the index of the first character that does not repeat anywhere else in the string. Return -1 if no such character exists.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Two-pass approach, count all characters first then scan again for the first one with a count of exactly one.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose a two-pass solution using a hash map to count character frequencies. In the first pass, build the frequency map; in the second pass, iterate through the string and return the index of the first character with a count of 1. If no such character exists, return -1.

Pro tip: Mention that you can optimize space by using an array of size 256 if the character set is ASCII, and discuss the trade-off between time and space. Also, explicitly state the time and space complexity of your solution to demonstrate thoroughness.

1. Clarify requirements and edge cases

Ask about the character set (e.g., ASCII or Unicode), string length limits, and whether the string can be empty. Confirm that 'first' means the smallest index.

2. Choose data structures

Select a hash map (or an array if the character set is small) to store character frequencies. Explain why this allows O(1) average-time lookups.

3. First pass: count frequencies

Iterate through the string once, updating the frequency count for each character in the map.

4. Second pass: find first unique

Iterate through the string again, and return the index of the first character whose frequency is 1. If none, return -1.

5. Analyze complexity and test

State that time complexity is O(n) and space complexity is O(k) where k is the number of distinct characters. Walk through a few test cases, including empty string and all repeating characters.

Key Points to Mention

Time complexity: O(n) with two passes, which is optimal.
Space complexity: O(k) where k is the number of distinct characters; can be O(1) if using a fixed-size array for ASCII.
Handling edge cases: empty string, string with all repeating characters, and strings with special characters.
Choice of data structure: hash map vs. array, and when to use each.
The importance of the second pass to preserve the original order and find the first unique character.
Potential follow-up: what if the string is very large and cannot fit in memory? Discuss streaming approach.

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