Arrays, Strings, and Hashing
Asked of: Software Engineer
Last updated
What's being tested
These problems test string scanning, array filtering, and hash-based frequency reasoning under tight correctness constraints. Interviewers are looking for clean handling of substrings, prefixes, character/digit multisets, and movement invariants with predictable O(n) or O(n * k) complexity.
Patterns & templates
-
Frequency maps for anagrams — compare
`Counter`/fixed-size arrays; useO(1)alphabet-sized comparisons when characters are bounded. -
Substring enumeration — nested loops generate
s[i:j]; expectO(n^2)substrings, so pair withsetlookup or pruning. -
Prefix filtering — use
word.startswith(prefix)for simple scans inO(total_chars); use a Trie only when many repeated prefix queries exist. -
Sliding window for fixed-length chunks — maintain character counts incrementally instead of rebuilding each substring in
O(k)time. -
Invariant checking for token transforms — ignore empty spaces, preserve token order, and validate directional movement constraints in one pass.
-
Digit feature extraction — convert each number to unique digits, update frequency buckets
0..9, and return the largest bucket count.
Common pitfalls
Pitfall: Treating anagrams as sorted strings everywhere can add avoidable
O(k log k)cost per substring.
Pitfall: Forgetting duplicate handling; clarify whether duplicate dictionary words should be returned once or preserved.
Pitfall: For transform problems, matching token counts is not enough; direction and wall constraints must also remain valid.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
- Check if all substrings are anagrams of wordsGoogle · Software Engineer · Technical Screen · medium
- Check if all substrings are dictionary wordsGoogle · Software Engineer · Technical Screen · medium
- Return dictionary words matching a prefixGoogle · Software Engineer · Technical Screen · medium
- Find longest duplicated substringGoogle · Software Engineer · Technical Screen · hard
- Add two big integers from digit listsGoogle · Software Engineer · Technical Screen · medium
- Find largest subset sharing a common digitGoogle · Software Engineer · Take-home Project · easy
- Find minimum covering substringGoogle · Software Engineer · Onsite · Medium
- Determine validity after digit-constrained deletionsGoogle · Software Engineer · Onsite · Medium
- Parse strings and find meeting slotsGoogle · Software Engineer · Onsite · Medium
- Decide string transform with directional tokens and wallsGoogle · Software Engineer · Technical Screen · Medium
Related concepts
- Arrays, Strings, Hash Maps, And Frequency CountingCoding & Algorithms
- Arrays, Strings, Hash Maps, And Sliding WindowsCoding & Algorithms
- Core Data Structures, Algorithms, And ComplexityCoding & Algorithms
- Core Data Structures, Sorting, And ComplexityCoding & Algorithms
- Array And String AlgorithmsCoding & Algorithms
- Arrays, Strings, And Matrix FundamentalsCoding & Algorithms