Java Arrays and strings
The largest share of screening problems, and three techniques cover most of them.
3 concepts · 9 interview questions
What this topic covers
Every concept in arrays and strings, and the questions each one gets asked as. Where a question links, it has a full write-up.
Two pointers
Walking a sorted array from both ends, or with a fast and a slow index, turns many nested-loop problems into a single pass.
- Find two numbers in a sorted array that sum to a target.
- Remove duplicates from a sorted array in place.
- Detect a cycle in a linked list, and find where it starts.
Sliding window
For problems about a contiguous run, expanding and contracting a window is linear where re-examining every substring is quadratic or worse.
- Longest substring without repeating characters.
- Maximum sum subarray of size k.
- When does a sliding window not apply?
String manipulation
Java strings are immutable, so the naive solution allocates on every step. Most string questions are secretly about that.
- Reverse the words in a sentence, in place where possible.
- Check whether two strings are anagrams.
- Why is building a string in a loop with plus a problem?