← AT&T Interview Insights

AT&T·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Technical phone screen for a software engineer role, just one coding question but it had a complexity discussion attached which I was not fully expecting. Pretty standard stuff but the inverted index angle made it feel slightly more interesting than a typical string problem.

Questions Asked (1)

Q1

Given a mapping from sentence index to sentence text, return a mapping from each word to the sorted list of sentence indices where that word appears. Matching should be case-insensitive, treat whitespace-separated tokens as words, and strip punctuation. Also discuss the time complexity of your solution.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Basically an inverted index builder.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and edge cases, then outline a solution using a hash map to store word-to-sentence-index lists. Emphasize normalization (lowercasing, punctuation stripping) and discuss time complexity in terms of total words processed.

Pro tip: Mention that you would use a defaultdict(list) to avoid key errors and that sorting can be done once at the end or maintained during insertion if indices are processed in order. Also, discuss trade-offs between preprocessing all sentences versus lazy processing.

1. Clarify Requirements and Edge Cases

Ask about punctuation handling (e.g., hyphens, apostrophes), case sensitivity, and whether sentence indices are 0-based or 1-based. Confirm that words are whitespace-separated tokens after stripping punctuation.

2. Design the Data Structure

Use a hash map (dictionary) where keys are normalized words and values are lists of sentence indices. Consider using a defaultdict(list) for efficient insertion.

3. Process Each Sentence

Iterate through the mapping, for each sentence, normalize the text (lowercase, remove punctuation), split into words, and for each word, append the sentence index to the list in the hash map.

4. Sort and Return

After processing all sentences, sort each list of indices (if not already sorted) and return the mapping. If sentences are processed in increasing index order, lists will be naturally sorted, avoiding extra sorting.

5. Analyze Time Complexity

State that the time complexity is O(N + M log M) where N is total number of words across all sentences and M is the average number of occurrences per word (for sorting). If indices are processed in order, sorting is not needed, making it O(N).

Key Points to Mention

  • Normalization: lowercasing and punctuation stripping using regex or string translation.
  • Use of defaultdict(list) to simplify code and avoid key checks.
  • Sorting: either sort each list at the end or rely on processing sentences in index order.
  • Time complexity: O(N) if indices are processed in order, otherwise O(N + K log K) where K is total occurrences.
  • Space complexity: O(N) for storing the mapping.
  • Edge cases: empty sentences, words with apostrophes (e.g., 'don't'), and non-alphanumeric characters.

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