Deshaw Inc Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

If the range is a to b, then generate a random no as
r=rand(b)%a+rand(b-a)
maintain a hash table to check that the no of times the value has been returned is less than n. Maintain the no as key and count as value.
So, if(count(r)<=arr[r]){
count(r)++;
return r;
}

- alex October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@alex , u misunderstand the Q ... like me, i will tell u complete Q

write a function to generate random value for array index with satisfying given conditions.

condition:
1)Every index should be select "C" times
"C" is the value that is filled in array in all indexes.
Given
1) array with size "n" , having filled with constant value "c" in each index.
2) randomGenFromMToN() will give random number from m to n;

- nagyuga October 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

modified it. Hope it is fine now.

- alex October 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do you require uniform distribution at the start?
After every deletion ?

Also,

rand(b)%a+rand(b-a) <=== off by one error?

Also, the above might not be very uniform (it is close to uniform if and only if the length of the sequence given by rand() is "long" relative to the b-a ... assuming the C type rand() ).

The question as stated is not clear. After all numbers are are deleted , then what do your function return?

- S O U N D W A V E October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int generateRand()
{
     int mat[5][5] = { 1,2,3,4,5,
                                6,7,1,2,3,
                                4,5,6,7,1,
                                2,3,4,5,6,
                                7,0,0,0,0};   
         int x;
         do{
         int i = rand(5);         // assuming rand(5)  generates number from 0 to 4
         int j = rand(5);
         x = mat[i][j];
         }
         while(x==0);
         
         return x;
}

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

If I understand the problem, the array exists for tracking the resource count. When a slot in the array drops to zero, that index can't be used again.

So performance becomes the issue as more as more slots drop to zero. Finding an entry in the array that contains a count > 0 gets hard and harder.

So searching for that last entry in the array with the value 1 could turn into a linear search...unless you come up with a better solution.

- Dave September 02, 2014 | Flag Reply


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