Loading...
Trading memory for time with hash maps and sets, plus the collision and ordering caveats interviewers probe.
3 questions in Data Structures & Algorithms.
Subarray Sum Equals K is solved with prefix sums and a hash map: for each running sum, count earlier prefixes equal to sum-k. This is O(n) time and works with negative numbers, unlike a sliding window. Use this hashing answer to show the decision, trade-off, and evidence rather than a memorised definition.
Every anagram class needs one canonical key: either the word's letters sorted, or a vector of letter counts. The counting key is cheaper but only if the counts are separated when they are turned into a string, because concatenating them lets a count of eleven and a count of one swap places unnoticed.
A hash map from key to a doubly linked list node, over one recency-ordered list. The map answers find-by-key, the list answers find-the-oldest, and neither answers the other in constant time. The detail that decides the answer is that the map stores the node rather than the value, which is what makes unlinking on a hit a fixed number of pointer writes.