Recognising the Pattern

Interviewers do not have unlimited questions. Almost everything asked is a variation on a small set of patterns, and the wording gives away which one before you have written a line.

The signals

• "contiguous", "substring", "subarray" with longest or shortest - sliding window.
• "sorted" and "find a pair" - two pointers.
• "has it appeared before", "count occurrences", "duplicate" - hash map or set.
• "shortest path", "fewest steps", "nearest" in an unweighted graph - BFS.
• "all paths", "is it connected", "detect a cycle" - DFS.
• "how many ways", "maximum value", "minimum cost" with choices - dynamic programming.
• "top k", "k largest", "k closest" - heap, or sort when k is close to n.
• "matching brackets", "undo", "next greater" - stack.
• "find in a sorted array", "minimum value that works" - binary search.
• "generate all combinations or permutations" - backtracking.

Two questions that settle most cases

Is the input sorted, or would sorting help? If yes, two pointers and binary search are open to you.