Topic 2 of 20
Arrays, Strings & Hashing
Hash maps, frequency counting and prefix sums: the tools behind a third of all interview questions.
The concept
Arrays and strings are the raw material of most interview questions, and hashing is the single most useful tool for working with them. A hash map gives you average O(1) insert and lookup, which lets you trade a little memory for a huge drop in time: the O(n²) "check every pair" solution becomes a single O(n) pass that asks "have I seen what I need?".
The second big idea is the prefix sum. Precompute running totals once, and the sum of any subarray becomes one subtraction. Combine a prefix sum with a hash map ("how many earlier prefixes equal current − k?") and you can count subarrays with a target sum in linear time. This pattern reappears in 2D grids, in modular arithmetic and in balance problems.
Finally, practise in-place tricks: using the array's own indices as a hash, swapping elements into position, and reversing sections. They give O(1) extra space solutions that interviewers often ask for as a follow-up.
Patterns you will learn
Problems, in order
- 1Two SumEasy
The most-asked interview problem ever; teaches the 'store the complement' idea behind countless solutions.
Hash Map LookupReported at: AmazonGoogleApple+20 - 2
Shows the time-vs-space trade-off between sorting and hashing in its simplest form.
Hash SetReported at: AmazonGoogleApple+5 - 3Valid AnagramEasy
Counting characters with a fixed-size array is the base of every anagram and permutation problem.
Frequency CountReported at: AmazonMetaMicrosoft+5 - 4Design HashMapEasy
Building a hash map yourself (buckets, collisions) makes the O(1) promise concrete.
Hashing InternalsReported at: AmazonMicrosoftApple+5 - 5Ransom NoteEasy
A quick drill on comparing two frequency tables.
Frequency CountReported at: GoogleAppleSpotify+1 - 6
Two maps enforce a one-to-one mapping, a subtle bug trap interviewers use.
Bijective MappingReported at: AmazonGoogleLinkedIn - 7Word PatternEasy
Same bijection idea applied across words instead of characters.
Bijective MappingReported at: AmazonAdobeUber - 8Roman to IntegerEasy
Left-to-right parsing with a look-ahead rule; a common phone-screen question.
String ParsingReported at: AmazonAppleGoogle+5 - 9
Vertical scanning across strings; also the motivating example for tries.
String ScanningReported at: MetaAppleGoogle+5 - 10Plus OneEasy
Carry handling on a digit array, the same idea as adding big numbers.
Carry PropagationReported at: MetaGoogleAmazon+3 - 11Majority ElementEasy
Introduces an O(1)-space voting trick that surprises most candidates.
Boyer-Moore VotingReported at: AmazonMicrosoftApple+5 - 12Find Pivot IndexEasy
Left sum vs right sum is the gentlest introduction to prefix sums.
Prefix SumReported at: MetaAmazonApple+5 - 13
Precompute once, answer every range query in O(1): the core prefix-sum payoff.
Prefix SumReported at: Meta - 14Group AnagramsMedium
Choosing a good hash key (sorted string or count tuple) is the whole problem.
Hash Map GroupingReported at: AmazonMicrosoftMeta+15 - 15Top K Frequent ElementsMedium
Beats the O(n log n) sort with bucket sort; a favourite follow-up.
Bucket SortReported at: MetaAmazonMicrosoft+7 - 16
Prefix/suffix passes without division; a very frequent Amazon and Meta question.
Prefix & Suffix ProductsReported at: AmazonMetaMicrosoft+5 - 17Valid SudokuMedium
Encoding row, column and box membership in sets; clean hashing of 2D data.
Hash Set per GroupReported at: AmazonMicrosoftMeta+3 - 18
Starting only from sequence beginnings gives O(n); a classic 'think before you sort' problem.
Hash SetReported at: AmazonMicrosoftGoogle+5 - 19
Frequency counting followed by bucket ordering.
Frequency CountReported at: MicrosoftMetaAmazon+2 - 20Majority Element IIMedium
Extends voting to two candidates; tests whether you truly understood the trick.
Boyer-Moore VotingReported at: AmazonMicrosoftAdobe - 21Rotate ArrayMedium
Three reversals rotate in O(1) space, a reusable in-place trick.
Reversal TrickReported at: AmazonMicrosoftGoogle+3 - 22Next PermutationMedium
Find-swap-reverse in place; asked often and easy to get subtly wrong.
- 23String to Integer (atoi)Medium
Careful edge-case handling (signs, whitespace, overflow), exactly what interviewers watch for.
String ParsingReported at: MetaMicrosoftAmazon+5 - 24Subarray Sum Equals KMedium
The canonical 'count prefixes equal to sum − k' problem; appears everywhere.
Prefix Sum + Hash MapReported at: MetaAmazonGoogle+10 - 25Continuous Subarray SumMedium
Prefix sums modulo k: the same pattern with a number-theory twist.
Prefix Sum + Hash MapReported at: MetaAmazonGoogle+3 - 26Contiguous ArrayMedium
Mapping 0 to −1 turns a balance question into a prefix-sum question.
Prefix Sum + Hash MapReported at: AmazonMetaApple+1 - 27
Extends prefix sums to grids with inclusion-exclusion.
2D Prefix SumReported at: MetaAmazonGoogle+1 - 28
Combining two structures to get O(1) for everything; a top design question.
Hash Map + ArrayReported at: MetaAmazonMicrosoft+5 - 29
Uses the array itself as a hash set for O(1) extra space.
In-place Index MarkingReported at: AmazonMicrosoftGoogle+2 - 30K-diff Pairs in an ArrayMedium
Complement lookup with duplicate handling, a step up from Two Sum.
Hash Map LookupReported at: AmazonAppleBloomberg+5 - 31
The hardest classic in-place trick (cyclic placement); asked at Google and Amazon.
In-place Index MarkingReported at: AmazonMicrosoftGoogle+3 - 32
Adds duplicates to the O(1) design, forcing careful index bookkeeping.
Hash Map + ArrayReported at: MetaLinkedIn - 33
Collapses a 2D problem into many 1D 'subarray sum equals k' problems.
- 34
Pure implementation under pressure; a known Google and LinkedIn question.
String SimulationReported at: GoogleMetaApple+2 - 35
Introduces the prefix function (KMP) for linear-time string matching.
KMP / Prefix FunctionReported at: MicrosoftAppleBloomberg