Searching, Hashing & DP
Hash-map and set lookups, an LRU cache, dynamic programming, and brute-force search in Go — with complexity trade-offs.
8 questions
MiddleCodeVery commonSolve Two Sum in O(n) returning the two indices
Solve Two Sum in O(n) returning the two indices
Keep a map[int]int from value → index. Iterate with for i, n := range nums; for each n, look up target-n via comma-ok — if found at index j, return []int{j, i}; else store seen[n] = i. This is O(n), versus the brute-force O(n²) nested scan.
Common mistakes
- ✗Sorting first and losing the original indices the problem asks for
- ✗Doing two passes when one pass with comma-ok suffices
- ✗Believing the brute-force nested loop is O(n) on average
Follow-up questions
- →Why does storing value→index let you find the complement in one pass?
- →How do you handle duplicate values that form the pair, like
[3,3]target 6?
JuniorCodeCommonCount how many times each value appears in an int slice
Count how many times each value appears in an int slice
Make the result with make(map[int]int), then range over the slice doing m[v]++ for each value. A read of a missing key returns the zero value 0, so m[v]++ works on the first sighting without an explicit check. Each map access is O(1), so the whole count is one O(n) pass, and the map's keys double as the set of distinct values.
Common mistakes
- ✗Guarding with
okbecause you think a missing key panics - ✗Believing a map cannot be incremented in place
- ✗Forgetting that a missing int key reads as 0
Follow-up questions
- →How do you find the most frequent value once you have the counts?
- →How would you list only the distinct values from this map?
JuniorCodeCommonCompute the n-th Fibonacci number in O(n) time, O(1) space
Compute the n-th Fibonacci number in O(n) time, O(1) space
Return n for n < 2, then keep two rolling values a, b := 0, 1 and update a, b = b, a+b in a loop from 2 to n, returning b. This is O(n) time, O(1) space — far better than naive recursion, which is exponential. A memoized recursion caches in a map[int]int.
Common mistakes
- ✗Using naive double recursion, which is exponential time
- ✗Storing the whole sequence when two rolling variables suffice
- ✗Splitting
a, b = b, a+binto two statements, corrupting the update
Follow-up questions
- →Why does naive
fib(n-1) + fib(n-2)recursion run in exponential time? - →How does the parallel assignment
a, b = b, a+bavoid needing a temp variable?
MiddleCodeCommonFind the users with the most total steps who missed no day
Find the users with the most total steps who missed no day
Seed a map userID → {daysIn, stepsSum} from day 0 only — anyone not present on day 0 can never appear on every day. For each later day, increment daysIn and stepsSum only for users already in the map. Then over the map, keep users whose daysIn == len(statistics), find the max stepsSum among them, and collect every user matching that max. Empty input returns an empty Result.
Common mistakes
- ✗Adding new users from later days, who cannot have been present on every day
- ✗Using a nested membership scan instead of a single accumulation pass
- ✗Returning one winner instead of collecting all tied maxima
Follow-up questions
- →Why is seeding from day 0 the key to avoiding a membership scan?
- →What is the time complexity in terms of the total number of entries?
MiddleTheoryCommonHow does an LRU cache get O(1) get, put, and eviction?
How does an LRU cache get O(1) get, put, and eviction?
An LRU cache pairs a hash map with a doubly linked list. The map sends a key straight to its list node in O(1). The list holds nodes in recency order — least-recently-used at one end, most-recent at the other. On every get or put the node moves to the most-recent end by relinking neighbours in O(1), and eviction pops the least-recent end, also O(1).
Common mistakes
- ✗Using a singly linked list, which makes node removal O(n)
- ✗Dropping the map and scanning the list to find a key
- ✗Scanning all entries to find the eviction victim instead of popping an end
Follow-up questions
- →Why must the list be doubly linked rather than singly linked?
- →How does an LRU policy differ from a TTL-based expiry policy?
MiddleCodeOccasionalExclude all innocents from suspects (set difference)
Exclude all innocents from suspects (set difference)
Build a map[int]struct{} set from innocents (the zero-size value means membership only, no payload). Range suspects, appending each value whose comma-ok lookup is absent from the set — O(n+m) time, O(m) space. Because both inputs are sorted, a two-pointer merge is an O(1)-space alternative.
Common mistakes
- ✗Scanning
innocentsper suspect and calling it O(n) instead of O(n·m) - ✗Mutating
suspectsin place withappend, corrupting the caller's slice - ✗Building the set from
suspects, which loses the original order and any duplicates
Follow-up questions
- →Both inputs are sorted — how would a two-pointer merge cut the extra space to O(1)?
- →Why prefer
map[int]struct{}overmap[int]boolfor a membership set?
MiddleCodeOccasionalGenerate a slice of n unique random integers
Generate a slice of n unique random integers
Keep a map[int]struct{} as a set and a result slice. Loop until len(res) == n: draw rand.Int(), and if it is already in the set, skip it with continue; otherwise append it and record it in the set. The struct{} value uses no memory, and the set gives O(1) duplicate checks, so the expected cost is near O(n) when the range is large.
Common mistakes
- ✗Skipping the dedup check and assuming
rand.Int()never collides - ✗Sorting-then-dedup, which can yield fewer than
nvalues - ✗Using a linear slice scan instead of a map for O(1) lookup
Follow-up questions
- →Why can this loop spin a long time if the random range is small and
nis near its size? - →How would a shuffle of
0..mgeneratenunique values without rejection?
MiddleCodeRareBrute-force a password from its md5 hash over a known alphabet
Brute-force a password from its md5 hash over a known alphabet
Enumerate candidate strings in order — treat the step counter as a number in base len(alphabet), decoding each step into the corresponding string over the alphabet. For each candidate compute hashPassword(guess) and compare it to h with bytes.Equal; return on the first match. The search is O(a^n) for an n-length password over an a-symbol alphabet — exponential, so it only works for short passwords.
Common mistakes
- ✗Thinking
md5can be reversed or undone by hashing again - ✗Comparing hashes with
==on slices instead ofbytes.Equal - ✗Underestimating the O(a^n) blow-up for longer passwords
Follow-up questions
- →How would a precomputed rainbow table change the time cost of this attack?
- →How do a salt and a slow hash like bcrypt make this brute force impractical?
