Arrays, Strings, Hash Maps, And Frequency Counting
Asked of: Software Engineer
Last updated

What's being tested
Array/string counting questions test whether you can turn brute-force comparisons into linear or near-linear passes using prefix/suffix state, two pointers, hash maps, and frequency vectors. Interviewers are probing correctness under duplicates, zeros, negative values, collisions, and boundary cases—not just happy-path O(n) code.
Patterns & templates
-
Prefix/suffix accumulation — compute left-to-right and right-to-left products/counts in
O(n)time; avoid division and handle zeros explicitly. -
Two-pointer scan on sorted arrays — move
l/rbased on sum comparison; skip duplicate values when returning unique pairs. -
Frequency map counting — use
dict,HashMap, orCounterfor character/item counts; compare vectors inO(k)wherekis alphabet size. -
Fixed alphabet arrays — prefer
int[26]orint[128]for lowercase/ASCII strings; faster and simpler than hash maps when domain is bounded. -
Partition state tracking — maintain left/right distinct-character counts as a split moves; update counts carefully when a frequency reaches zero.
-
Modulo reasoning — maximize distinct remainders by tracking used residues in a set; remember residues range from
0tok - 1. -
Hash map internals — know hashing, buckets, collisions, load factor, resizing, and worst-case
O(n)lookup; mention concurrency concerns when relevant.
Common pitfalls
Pitfall: Using division in product-except-self fails when zeros appear and may violate the stated constraint.
Pitfall: Returning duplicate pairs from a sorted array because you advance pointers but do not skip repeated values.
Pitfall: Treating hash map operations as always
O(1)without acknowledging collisions, resizing cost, and adversarial keys.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Explain hash map internals and edge casesAmazon · Software Engineer · Take-home Project · medium
- Optimize with a cache/hash mapAmazon · Software Engineer · Technical Screen · Medium
- Find returning users from access logsAmazon · Software Engineer · Onsite · Medium
- Find all pairs summing to target in sorted arrayAmazon · Software Engineer · Technical Screen · Medium
- Determine max remainders and anagram after deletionsAmazon · Software Engineer · Take-home Project · Medium
- Compute product excluding index without divisionAmazon · Software Engineer · Onsite · Medium
- Optimize with caching or hash mapsAmazon · Software Engineer · Technical Screen · Medium
- Validate 9x9 grid in one passAmazon · Software Engineer · Onsite · Medium
- Count partitions and equal-cost packagesAmazon · Software Engineer · Take-home Project · Medium
- Solve string partition and equal-sum package problemsAmazon · Software Engineer · Take-home Project · Medium
- Minimize cost & recommend moviesAmazon · Software Engineer · Technical Screen · Medium
- Find most frequent log userAmazon · Software Engineer · Onsite · Medium
Related concepts
- Arrays, Strings, and HashingCoding & Algorithms
- Arrays, Strings, Hash Maps, And Sliding WindowsCoding & Algorithms
- Core Data Structures, Algorithms, And ComplexityCoding & Algorithms
- Core Data Structures, Sorting, And ComplexityCoding & Algorithms
- Arrays, Sliding Windows, DP And Stack PatternsCoding & Algorithms
- Arrays, Strings, And Matrix FundamentalsCoding & Algorithms