Skip to content

Topic 2 of 20

Arrays, Strings & Hashing

Hash maps, frequency counting and prefix sums: the tools behind a third of all interview questions.

35 problems13 Easy17 Medium5 Hard

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

  1. 1

    The most-asked interview problem ever; teaches the 'store the complement' idea behind countless solutions.

    Hash Map LookupReported at: AmazonGoogleApple+20
  2. 2

    Shows the time-vs-space trade-off between sorting and hashing in its simplest form.

    Hash SetReported at: AmazonGoogleApple+5
  3. 3

    Counting characters with a fixed-size array is the base of every anagram and permutation problem.

    Frequency CountReported at: AmazonMetaMicrosoft+5
  4. 4

    Building a hash map yourself (buckets, collisions) makes the O(1) promise concrete.

    Hashing InternalsReported at: AmazonMicrosoftApple+5
  5. 5

    A quick drill on comparing two frequency tables.

    Frequency CountReported at: GoogleAppleSpotify+1
  6. 6

    Two maps enforce a one-to-one mapping, a subtle bug trap interviewers use.

    Bijective MappingReported at: AmazonGoogleLinkedIn
  7. 7

    Same bijection idea applied across words instead of characters.

    Bijective MappingReported at: AmazonAdobeUber
  8. 8

    Left-to-right parsing with a look-ahead rule; a common phone-screen question.

    String ParsingReported at: AmazonAppleGoogle+5
  9. 9

    Vertical scanning across strings; also the motivating example for tries.

    String ScanningReported at: MetaAppleGoogle+5
  10. 10

    Carry handling on a digit array, the same idea as adding big numbers.

    Carry PropagationReported at: MetaGoogleAmazon+3
  11. 11

    Introduces an O(1)-space voting trick that surprises most candidates.

    Boyer-Moore VotingReported at: AmazonMicrosoftApple+5
  12. 12

    Left sum vs right sum is the gentlest introduction to prefix sums.

    Prefix SumReported at: MetaAmazonApple+5
  13. 13

    Precompute once, answer every range query in O(1): the core prefix-sum payoff.

    Prefix SumReported at: Meta
  14. 14

    Choosing a good hash key (sorted string or count tuple) is the whole problem.

    Hash Map GroupingReported at: AmazonMicrosoftMeta+15
  15. 15

    Beats the O(n log n) sort with bucket sort; a favourite follow-up.

    Bucket SortReported at: MetaAmazonMicrosoft+7
  16. 16

    Prefix/suffix passes without division; a very frequent Amazon and Meta question.

    Prefix & Suffix ProductsReported at: AmazonMetaMicrosoft+5
  17. 17

    Encoding row, column and box membership in sets; clean hashing of 2D data.

    Hash Set per GroupReported at: AmazonMicrosoftMeta+3
  18. 18

    Starting only from sequence beginnings gives O(n); a classic 'think before you sort' problem.

    Hash SetReported at: AmazonMicrosoftGoogle+5
  19. 19

    Frequency counting followed by bucket ordering.

    Frequency CountReported at: MicrosoftMetaAmazon+2
  20. 20

    Extends voting to two candidates; tests whether you truly understood the trick.

    Boyer-Moore VotingReported at: AmazonMicrosoftAdobe
  21. 21

    Three reversals rotate in O(1) space, a reusable in-place trick.

    Reversal TrickReported at: AmazonMicrosoftGoogle+3
  22. 22

    Find-swap-reverse in place; asked often and easy to get subtly wrong.

  23. 23

    Careful edge-case handling (signs, whitespace, overflow), exactly what interviewers watch for.

    String ParsingReported at: MetaMicrosoftAmazon+5
  24. 24

    The canonical 'count prefixes equal to sum − k' problem; appears everywhere.

    Prefix Sum + Hash MapReported at: MetaAmazonGoogle+10
  25. 25

    Prefix sums modulo k: the same pattern with a number-theory twist.

    Prefix Sum + Hash MapReported at: MetaAmazonGoogle+3
  26. 26

    Mapping 0 to −1 turns a balance question into a prefix-sum question.

    Prefix Sum + Hash MapReported at: AmazonMetaApple+1
  27. 27

    Extends prefix sums to grids with inclusion-exclusion.

    2D Prefix SumReported at: MetaAmazonGoogle+1
  28. 28

    Combining two structures to get O(1) for everything; a top design question.

    Hash Map + ArrayReported at: MetaAmazonMicrosoft+5
  29. 29

    Uses the array itself as a hash set for O(1) extra space.

    In-place Index MarkingReported at: AmazonMicrosoftGoogle+2
  30. 30

    Complement lookup with duplicate handling, a step up from Two Sum.

    Hash Map LookupReported at: AmazonAppleBloomberg+5
  31. 31

    The hardest classic in-place trick (cyclic placement); asked at Google and Amazon.

    In-place Index MarkingReported at: AmazonMicrosoftGoogle+3
  32. 32

    Adds duplicates to the O(1) design, forcing careful index bookkeeping.

    Hash Map + ArrayReported at: MetaLinkedIn
  33. 33

    Collapses a 2D problem into many 1D 'subarray sum equals k' problems.

  34. 34

    Pure implementation under pressure; a known Google and LinkedIn question.

    String SimulationReported at: GoogleMetaApple+2
  35. 35

    Introduces the prefix function (KMP) for linear-time string matching.

    KMP / Prefix FunctionReported at: MicrosoftAppleBloomberg