Synopsys R&D Interview Question for Senior Software Development Engineers


Country: India




Comment hidden because of low score. Click to expand.
2
of 4 vote

This question is not clear. There are so many factors that may change the solution.
It'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.

- oOZz June 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the there will be multiple queries for searching a number at various times. It's possible that the number that you want to search now had been read t minutes ago.

- Epic_coder June 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

But , if stream is infinite, then hashset will run out of memory soon. So i think clearing it ll be equally important.

- Sushant June 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Murali Mohan June 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it also depends on whether duplicate numbers are streamin

- anonymous June 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- shyamal.pandya June 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Sharma June 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what's wring with following

boolean search(int x) {
while(true) {
  int input=readinput();
  if(!(x^input)) {
    return true;  
 }
}
}

- Manish June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is wrong with

boolean search(int x) {
while(true) {
  int input=readinput();
  if(x == input) {
    return true;  
 }
}
}

- Manish June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Keep adding the elements to a hashset and query it for the given element.

- Murali Mohan June 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Just XOR the number (to be searched) with incoming numbers

boolean search(int x) {
while(true) {
  int input=readinput();
  if(!(x^input)) {
    return true;  
 }
}
}

- kp June 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

stupendous answer.

- kb June 24, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More