Arrays and Hashing
6 / 170Arrays and HashingLesson 1 of 10About 27 min
The first and most useful trade in the course: spend memory to stop rescanning.
A large family of problems reduces to one question asked repeatedly: have I already seen this value? The slow answer is to look back through everything processed so far. The fast answer is to have kept a record as you went.
Take a concrete task: report the first character in a string that has appeared before. Here is the slow version, written out so the waste is visible. For each character it scans everything before it.
def first_repeated_char_slow(text): for i in range(len(text)): for j in range(i): if text[i] == text[j]: return text[i] return None print(first_repeated_char_slow("abcdeb"))The fast version keeps a set of everything seen so far. Notice the shape: check, then record.
def first_repeated_char(text): seen = set() for ch in text: if ch in seen: return ch seen.add(ch) return None print(first_repeated_char("abcdeb"))The problem below asks a simpler question than the example above: not which value repeats, just whether any value does. Decide what you want to happen at the moment you find a member of the set, and write it.
This version adds before it checks. Type exactly what it prints.
def buggy(words): seen = set() for word in words: seen.add(word) if word in seen: return word return None print(buggy(["red", "green", "blue"]))Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.