Retrieval: telling these apart

Two problems from this unit, cold, plus the discriminations that decide whether the pattern actually transfers.

You solved these problems days or hours ago with the pattern freshly explained above them. That is the easy condition. The interview condition is meeting a problem with no label attached and having to work out which idea applies.

So this lesson does two things. It asks you to rebuild two problems from scratch without looking at your earlier submissions, and it drills the specific confusions that show up when these patterns arrive with no label on them.

Quick check· 5 min

Which structure does the job?

You need to return every pair of indices (i, j) with i less than j whose values are equal. Which structure fits best?

A set of values seen so farA dict from value to the single most recent indexA dict from value to a list of every index where it appearedA Counter of value frequencies

Select all that apply· 5 min

Where does a prefix array help?

Select every problem below that a precomputed prefix array makes meaningfully faster.

Answer many queries for the sum of a range, on an array that never changesFor each position, the product of all other elementsDecide whether an array contains any duplicate valueFor each position, the count of even numbers at or before itDecide whether an array is already sorted

Problem· 10 min

Two Sum, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

Problem· 15 min

Top K Frequent Elements, from scratch

Arrays and Hashing

15 / 170

Arrays and HashingLesson 10 of 10About 39 min

Retrieval: telling these apart

Two problems from this unit, cold, plus the discriminations that decide whether the pattern actually transfers.

Quick check· 5 min

Which structure does the job?

You need to return every pair of indices (i, j) with i less than j whose values are equal. Which structure fits best?

A set of values seen so farA dict from value to the single most recent indexA dict from value to a list of every index where it appearedA Counter of value frequencies

Select all that apply· 5 min

Where does a prefix array help?

Select every problem below that a precomputed prefix array makes meaningfully faster.

Problem· 10 min

Two Sum, from scratch

Problem· 15 min