Continue to Site

Welcome to our site!

Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

  • Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

C interview question

Status
Not open for further replies.

EngIntoHW

Member
A function called rand receives a positive integer M and returns a positive integer between 1 to M, randomly.

Write a function that given a sorted array of all integers from 1 to N, it returns an array of length N which comprises a permutation of these 1 to N numbers, so that the probability of receiving each permutation is 1/N!.

Required time complexity is O(N).

I'm not sure how you can prove that your solution returns permutations that are received in 1/N! probability.

Any help is appreciated :)
 
It's basic permutation probability which you should have already taken by the time you reached third year (seriously what classes do they make you take to get to 3rd year? Admittingly very forgettable, but this stuff is taught on the first day, if it didn't already show up in high school)

Example:
What is the probablity of getting a permutation of A, B, C?

Chance of a particular character being in the first position:
1/3
Chance of the two remaining characters being in the 2nd position:
1/2
Chance of the one remaining character being in the third position:
1/1
Probability of all of these happening at the same time:
1/3*1/2*1/1 = 1/3!

What all this means is that 1/N! is redundant information and you'd get the same result by just doing what you'd normally do to randomize the order of that data. If you actually wanted to prove it, you'd use the proving by induction method which is basically what I just did. Except instead of me using 3 items, you prove it holds true for 1 item, and then that it holds true for n+1 items. So by extension it holds true for everything from 1 to infinite. But that's a math question, not a programming question.

Unless I missed something, that's what the essence of the question appears to be, and surely the time compelxity requirement shouldn't be a problem as long as you aren't too creative in how you go about things.
 
Last edited:
Hi,

Perhaps I didn't explain myself well.

When you solve the programming question I introduced here, how can you prove that your solution returns a permutation with 1/N! probability.

For example, consider the following solution:
Lets take for example, N=4.
The given array is 1,2,3,4.
Call rand(4), say it returns 2.
Therefore, exchange between organ #2 and organ #4.

Now, call rand(3), say it returns 1.
Therefore, exchange between organ #1 and organ #3.

Now, call rand(2)...
and so on.

How can I prove that each permutation this solution returns has 1/N! probabilty?
 
Last edited:
It's an instrinsic property of ANY permutation of a set of items. It comes from the fact that an item does not reappear later on the permutation once it has appeared which is why the factorial is there. Proving it does not involve proving anything specific about your code. It involves proving something fundamental about permutations but it's pretty straightforward if just thinking about it.

(Didnt you take probability with combinations and permutations this in school? THe first time I saw this was in highschool and later on every EE had to take it in 2nd year. It sucked and we didn't use it much but still).
 
Last edited:
Hi,
I got you :)
Thank you.

I wonder, if the array wasn't sorted from 1 to N (1, 2, ..., N),
Would the solution change?

--
Yes, I took probability in school.
However, I didn't think of it as you described it.
My bad.
 
Last edited:
Yeah it took me couple minutes of staring at your post to digest all the requirements they were asking for. Then another minute to wonder why they bothered asking it at all.

THe solution would not change if it was or wasn't sorted. It remains a set of items where the order matters. It just a "sort this" question. But everyone knows how to do that so they throw in a bunch of red herrings.
 
Last edited:
Got you,

You actually look only at the indexes of the array, and not at the entries themselves, right?
Like, you sort here indexes, not values, am I correct?
 
Huh? What are you talking about?

The desire is to randomize the order that the ENTRIES are in (the value). But you can do this directly or indirectly. You can sort the items directly by changing their address (physically moving the entries around in memory) or indirectly by making an array of pointers pointing to the entries and sorting the pointer values (and leaving the entries in the same physical location in memory). The only thing that changes is how you define "order"- it's address in memory? Or it's position in the pointer array? All that changes is how you access the list. What really matters is no matter how you decide to access it, it must spit out the items (ie. their values) in the correct order.

(Sort of like physically moving houses around the block versus changing their house numbers- in one you define where the house sits on the block as the order, in the other you define the number on the house as the order.)
 
Last edited:
Hey,

You said earlier that it doesn't matter whether the array is sorted or not, the solution is valid in both cases.
Meaning, for both of the arrays - 1,2,3,4 and 6,2,3,1 - the solution returns permutations of 1/4! probability.

Therefore, I meant that you look at the problem as seating N indexes in a row, randomly, and not seating N values in a row.
 
Hmmm, when I read the question I thought it was asking for proof of how random the returned string was. In the case of your example of rand(4), if you let it run for a string of 40 results, would you get 10 1s, 10 2s, 10 3s and 10 4s or would it show a bias since it is only a pseudo random number generator.
 
Status
Not open for further replies.

Latest threads

New Articles From Microcontroller Tips

Back
Top