Arrays, Strings, Hash Maps, And Sliding Windows
Asked of: Software Engineer
Last updated

What's being tested
These problems test linear-time string/array processing using hash maps, two pointers, and sliding windows. Interviewers are probing whether you can turn brute-force substring/subarray enumeration into O(n) or O(n log n) solutions while handling edge cases cleanly.
Patterns & templates
-
Frequency map with
dict/HashMap— count characters, words, or digit encodings; compare counts instead of repeatedly scanning substrings. -
Sliding window over contiguous substrings — expand right, update state, contract left while valid; typical
O(n)time andO(k)space. -
Minimum window substring — maintain
need,have, andformed; update answer only when all required frequencies are satisfied. -
Two-pointer string scan — use left/right indices for sanitized palindrome checks; skip non-alphanumeric characters before comparing normalized values.
-
Kadane’s algorithm for max subarray sum — track
bestEndingHereandbestSoFar; initialize with first element to handle all-negative arrays. -
Max product subarray — track both
maxEndingHereandminEndingHerebecause multiplying by a negative flips extremes. -
Canonical encoding — map letters to phone digits or normalized signatures, then group collisions with
Map<signature, List<String>>.
Common pitfalls
Pitfall: Recomputing substring counts inside nested loops turns an intended
O(n)sliding-window solution intoO(n^2 * alphabet).
Pitfall: Treating “valid window” as set containment instead of frequency containment breaks cases with repeated characters like
AABC.
Pitfall: Forgetting empty strings, single-character strings, Unicode casing, all-negative arrays, zeros in product arrays, and duplicate grouped 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
- Count Trips From Vehicle LogsLinkedIn · Software Engineer · Technical Screen · easy
- Solve Cache, Window, and Heap ProblemsLinkedIn · Software Engineer · Onsite · medium
- Solve common string and subarray problemsLinkedIn · Software Engineer · Technical Screen · medium
- Validate parentheses with one or three bracket typesLinkedIn · Software Engineer · Technical Screen · medium
- Group words that map to same phone digitsLinkedIn · Software Engineer · Technical Screen · medium
- Determine sanitized palindrome in stringLinkedIn · Software Engineer · HR Screen · Medium
- Solve min window & animal conflictsLinkedIn · Software Engineer · Onsite · Medium
Related concepts
- Arrays, Sliding Windows, DP And Stack PatternsCoding & Algorithms
- Arrays, Strings, Hash Maps, And Frequency CountingCoding & Algorithms
- String And Sliding Window AlgorithmsCoding & Algorithms
- Array And String AlgorithmsCoding & Algorithms
- Arrays, Strings, and HashingCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms