← AT&T Interview Insights

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

Intermediate
Jun 2026

Summary

Coding screen for a software engineer role, just one problem but it had enough moving parts to trip you up if you weren't careful. The inverted index angle wasn't immediately obvious to me and I spent a minute or two going down a brute-force path before catching myself.

Questions Asked (1)

Q1

Given a mapping of sentence indices to sentence strings, a list of query words, and an integer N, score each sentence by the total number of times any query word appears in it, then return the indices of the top N sentences in descending score order, breaking ties by ascending index.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

My first instinct was to just loop over every sentence for every query word, which works but feels gross once you think about doing it repeatedly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose an efficient algorithm using a hash map to count word frequencies per sentence. After scoring, sort the sentences by score descending and index ascending, and return the top N indices.

Pro tip: Mention that you would preprocess the query words into a set for O(1) lookups, and tokenize sentences once to avoid repeated work. Also, discuss how to handle ties and the importance of stable sorting.

1. Clarify requirements and edge cases

Ask about input size, whether sentences can contain punctuation, case sensitivity, and if N can exceed the number of sentences. Confirm the tie-breaking rule.

2. Design the algorithm

Propose using a hash map to count occurrences of each query word per sentence. For each sentence, tokenize it and increment a score counter for each token that is in the query set.

3. Compute scores efficiently

Iterate through each sentence, tokenize, and for each token check membership in the query set. Accumulate the score for that sentence. Store scores in a list of (score, index) pairs.

4. Sort and select top N

Sort the list of (score, index) pairs by score descending and index ascending. Return the indices of the first N elements.

5. Analyze complexity and trade-offs

Discuss time complexity: O(S * L + S log S) where S is number of sentences and L is average sentence length. Mention space complexity and potential optimizations like using a min-heap for top N if N is small.

Key Points to Mention

  • Tokenization and case normalization (e.g., lowercasing) to ensure accurate word matching.
  • Using a hash set for query words to achieve O(1) lookup per token.
  • Handling ties by sorting with a custom comparator (score descending, index ascending).
  • Edge cases: empty sentences, no query words, N larger than number of sentences.
  • Time and space complexity analysis, and possible optimizations for large datasets.
  • Alternative approaches like using a priority queue (min-heap) for top N when N is much smaller than total sentences.

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