Synopsys R&D Interview Question
Senior Software Development EngineersCountry: India
But , if stream is infinite, then hashset will run out of memory soon. So i think clearing it ll be equally important.
@Sushant
On what criteria would you clear the hashset?
Actually, the solution to a problem depends on the context. If the problem is such that all we see are 32 bit numbers and we have 4GB of RAM, then one can use a bit vector to mark the presence of elements as they are seen. We can then check the bit-vector to see whether or not an element exists.
We could use a Rabin-Karp Algorithm(Check on Wiki) to search the number that you are looking for :
You could follow the steps mentioned below :
1] Generate the hash of the number that you are looking for
2] Keep generating the rolling hash of the input stream as it keeps coming in.
Rolling hash : s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
3]Whenever the hash of the number you are looking for matches the hash of the numbers from the stream you have found the number.
I am assuming that given infinite array are in sorted form.
Then use expontial searching in expontial factor = 10 or use any smaller number.
Each time compare with high bound and if element is smaller then high bound then take high bound and previous bound and now you can apply binary searching.
Please make comment if solution is not feasible.
This question is not clear. There are so many factors that may change the solution.
- oOZz June 22, 2013It's not even interesting to search a number in streaming case. For instance, if you can read as fast as the streaming numbers, then you don't even need a data structure to search the number, you can just compare as the numbers coming in.