Interview Question


Country: United States




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

Assume generate m random intgers from n intgers, it can shuffle the first m elements.

int Random(int start, int end)
{
   // return a random intger btw start and end;
}

void gr(int m, int n)
{
    int *a = new int[n];
    for(int i = 0, i < n; i++)
      a[i] = i;

    for(int i = 0; i < m; i++)
    {
      int r = Random(i, n-1);
      swap(a[i], a[r]);
    }

    // Output the first m elements of a
}

- Leo March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a classic phone screen question. Leo's solution is the classic answer. If the first element isn't drawn on the first iteration, you want to keep it as a candidate, hence the swap. (And the swap also effectively removes the just-chosen number as a candidate, and adds it to the result set, effectively killing three birds with one stone.)

If you can process each number on the fly (by outputting them, using them directly, yielding them from a coroutine, appending to a passed in collection, or calling back a callback function), then replace the swap with a simple assignment of a[r] = a[i], since you won't need to revisit the value of a[i] after emitting it.

- showell30@yahoo.com March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Guys, you did not read.
=======
write a program to Generating Random Integer numbers without repetition
======
You need a GUID generator, not any random no generator. Any computerised random generator are bound to repeat, not because they are not random, but because they have a finite integer range.

- NoOne October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One simplest solution is :

Generate sudo random number, using any methods(such as linear congruential generators, Fibonacci generators), or can use inbuilt method. call it x
  hash it, if already present then try again, otherwise store it in array, and set hash function true.

Obviously here we require O(n) space, and they will not be following uniform distribution.

- sonesh March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

$ sudo random number
Access Denied.

LOL! :-)

- Anonymous March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about a sudoku random number? After all, repeats are disallowed in any square, any row, and any column. Problem solved!

- showell30@yahoo.com March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@showell : If the numbers have any kind of relation between them, then they are not random, the term random is define in this way that we can't predict them, they can't follow any pattern even when some one draw infinitely many,
Now there is no way to generate perfect random number, all random number generator(I mentions above), generates only sudo random numbers, but as our computer are not powerful enough to find any patterns in these sudo random numbers, so we generally accept them.

- sonesh March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sonesh, I'm joking. I'm playing off the pseudo-misspelled-as-sudo pun. Don't blame me, Anonymous started it. :)

- showell30@yahoo.com March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

congruential
a= (a*b +1) mod m
a= ((a div m) mod r) mod m

- abhi March 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how would you find a number to be even or odd without using / and %

- Poorni March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

main()
{
int x;
read x;
if(x&1)
printf("odd");
else
printf("evven");
}

- mallesh July 21, 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