This problem is written to give a new problem solver a sense of how problem solving feels like in its core essence. You face something which at first glance seems impossible but as you stay with it for sometime you end up solving it.

This problem also can be used to teach a maxim of George Polya - solve an easier problem. If you want to be a world class problem solver you must read his book - How to Solve It.

The prerequisite for this problem is knowing the data structure set. Ask someone if you don't know it.

Let's assume you and I are having a conversation.

I'd ask you: What's making the problem difficult?
You'd say: We could have used a set but we can't store all the data there. Not being able to store the data is making the problem difficult.
I'd ask you: Okay, how about we remove the difficulty for a few minutes? Can we solve a simpler problem where you can store the data?
You'd say: What would be a simpler problem?
I'd say: Like instead of a million large words, how about I give you a million numbers? Can you solve it?
You'd say: Of course. I will just put that in a set.
I'd say: Okay, what did we do to make the problem simpler?
You'd say: We just turned our words into numbers.
I'd say: Is there a name for that technique of converting words to numbers?
You'd say: Oh yah, I think it's called hashing.
I'd say: Is that something we can use to solve this problem?
You'd say: Ah, I see. I can hash each word into a number and keep a set of numbers. If a hash matches an existing one that means that word is present. I think I solved it!
I'd say: Yap, that is a solution. However, is it possible to map two words into the same number?
You'd say: You mean hash collision?
I'd say: Yes.
You'd say: Okay, my solution won't work then. So we have to lower the probability of hash collision.

Then you'll think really hard for a while.
Then you'll say: How about instead of one hash function we use multiple hash functions and store that tuple in a set?

Turns out two good hash functions can be enough for this problem.

And that's how you solve this problem. Or any problem.



82% Solution Ratio
BSMRSTU_CSEEarliest, May '18
hmdkamrulFastest, 0.0s
hmdkamrulLightest, 7.6 kB
Nusab19Shortest, 108B
Toph uses cookies. By continuing you agree to our Cookie Policy.