Great explanation! I like the simple example and using arrows to point at which index is being changed. The repetition helps a ton as well. Hope you keep doing more of these!
3 ปีที่แล้ว +6
Just to a note, for swapping variables in Python you should be able to use a tuple arr[i], arr[pick] = arr[pick], arr[i]
I suspect that by scaling random index to remaining array you will break uniformity - you actually don't need to scale - just take each index and pick random index for swap from whole array
this solution lacks the very important PROOF that the probability for any number to land at any index is the same, so here it is: calculation for the probability for some index i to land in index 0: 1/n, as it is the 1st iteration. calculation for the probability for some index i to land in index 1: (n-1)/n * (1/(n-1)). the left hand side is the probability for index j!=i to be selected, because i is already selected, and can't be selected again. the selection from (n-1) index has probability of (1/(n-1)). Now apply same logic for array of size k=n-1, for any k. stopping condition: n=1 (or 0), for probability 1 to land in index 0. Python code: def swap(arr, i, j): assert i < len(arr) assert j < len(arr) temp = arr[i] arr[i] = arr[j] arr[j] = temp def reorder_in_place(arr): length = len(arr) for i in range(length): dice = random.randrange(i, length) swap(arr, i, dice) return arr
Pretty sure Knuth shuffle is O(n) and it also does it in place. Just study Knuth shuffle, it's a super easy algorithm. It's useful in making card games too, so now you can use it for more than just coding interviews
You should not shrink the size of the pool of positions that you randomize your index on. You should always use "floor(rand() * size_of_array)" for a truly random result. Here's one way to think about it. If it was truly random it should be possible to get the same array as an output as the one you get as an input. With the solution I gave you you can get there. Great video!
This is the straight-forward approach, unfortunately it doesn't give you a random permutation. As a short mathematical pseudo-proof for an intuition: Assume that you have an array of size n. At each step your algorithm has n possible choices. Then after n iterations you have n^n total possible outcomes of the algorithm. However the total number of permutations of n element array is n!. Unfortunately n^n = n * n * ... * n cannot possibly be evenly divided by n! = n * (n-1) * ... * 2 * 1. Therefore there must be some permutations that are more likely then others. For a better explanation (also with simulations using the different algorithms) there's this wonderful blog post: blog.codinghorror.com/the-danger-of-naivete/
His approach does let you get the same array as output because the algorithm let's an index swap with itself. Look at 3:16 in the video. He does screw that fact up in the rest of the evaluation. He should have multiplied by 5 for the first iteration instead of 4, and that would have made it completely random.
NOOO!!! Delete this comment, you are misleading people and it has too many upvotes. You will "over shuffle" if you do that. This is somewhat hand wavey, but consider this: You will have n^n shuffles in your naive method. There are n! possible arrangements of cards. Clearly n^n > n!, meaning you are generating more outcomes that possible arrangements, meaning multiple outcomes are getting mapped to the same arrangement. Rigorous proof: stats.stackexchange.com/a/3087
You can get a randomize discrete number for each index by floor(rand()*100) then you O(n) sorting algorithms like bucket sort since the numbers are refined from 0 to 99.
for i = 0 to n -1: temp1 = floor(rand()*n) temp2 = floor(rand()*n) swap(arr[temp1],arr[temp2]) What is wrong with this? It is O(n) (Swapping can be done using another temp variable)
The possible new orders aren't evenly distributed. One might occur more often than the others. But when you write "for i in range(r):", the distribution becomes more even when r becomes bigger and it becomes less even when the array size increases. We'd have 0(r) for time and 0(1) for space.
@@timonpasslick I was referring to your suggestion that "One might occur more often than the others" - it's not true. The algorithm itself is not good, of course, - since both indexes are randomly selected known number of times we can calculate how many indexes with which probability will remain on their places.
My solution is to call random and floor function to get the random number. You start at index 0 and go to index n-1. You get your random value (which is between 0 and n-1), and make it the new index for your current index, so you swap the values (need a temporary variable). Repeat this till you reached the end of the array and you are done.
If you swap the last index (in this case 4) with position 0 through 3.. that means there is a 0% chance the number will stay in its current position. This would not be a truly random number and predicting the outcome of the "shuffle" becomes easier
When going through it the first time (around 2:20) he specifically says he's picking a value out of ALL the values in the array. Later, in the pseudocode (7:05) it specifically shows pick = floor( (i+1) * rand() ) That i+i _includes_ the index being selected for. So you're never swapping the last index (in this case 4) with just positions 0 through 3. pick = floor( (4+1) * rand() ) = floor( 5 * rand() ) = {0, 1, 2, 3, 4} (each with a 20% chance of being picked)
from random import randint import math def rand(): alea = randint(0,1000) return alea/1000 def floor(num): return math.floor(num) def switch(lst, i, j): temp = lst[j] lst[j] = lst[i] lst[i] = temp def random_reor(lst): for i in range(len(lst)): switch(lst, i, floor(rand()*len(lst))) that's my sol
I have a problem with that method in that it isn't random. If it were truly random, the last number would have just as high of a chance of _remaining_ as the last number as any other number would have a chance of replacing it. The solution I had was similar, but you could switch with either the left or the right side of the current number. You could pick a random number from the left side and from the right side and pick one of those two to switch, weighing the odds by how many numbers were on each side. If you wanted, you could repeat the whole thing a few times to make it more random, and it would remain O(n). *Edit* Actually, it may be easier to simply do this method from right to left and then repeat it from left to right while still being random **enough**
The last number *DOES* have just as high of a chance of remaining as the last number as any other number has of replacing it. It's included in the indexes being selected from. It's stated in words when he starts his demonstration ("We choose from ALL the numbers in the array"), it happens during his demonstration, and it's coded in the pseudocode. Why are there so many comments with this mistake in them?
ik this is 7months old, but if you allow it to choose one of the ones that havent been shuffled yet, than 9 could be chosen as well which would be random as well. Random shuffling doesnt require new positions for each value. Theoretically you dont even need to abandon the already shuffled ones so you could switch the current value with any value in the array, but it raises the chance of doing the same steps reversed, so this is very likely the best solution for O(n).
There is a lot of confusion here. I believe what you were going for is the modern Fisher-Yates shuffle algorithm. Anybody interested can look it up on Wikipedia. The modern FY states that when you first start from right to left at n-1, 0
@@wulymammoth The example at 4:58 is the SECOND loop of the algorithm, where the 5th element of the array (highlighted in blue) has already been done. So picking a number between 0 and 3 inclusive is correct.
It kinda follows from the algorithm. First you have n possible positions, then n-1 down to 1. Exactly n! possible configurations. And that is the formula for calculating the number of permutations of an array of size n.
Why couldn’t you just visit each position of the array and, for each such position, randomly generate a different position to which the current element should be transposed. Of course, this means swapping the current position with the random position. Some elements will definitely get swapped more than once. It is even possible that some elements don’t get swapped at all. But that’s all determined by the rand() function, which is completely ok.
@@thest.kitts-nevislabourpar3281 Had the exact same approach. Even if some numbers don't change their position after execution, it is due to the rand() function and can't be predicted.
to settle this, we can use a computer! write test - rearange array (2 or more elements, with unique values) billion times and calculate average value for each position.
In Python : # Rearranging elements of an array in O (n) import random x = [7, 5, 2, 11, 4, 9] s = set() i = 0 while len(s) is not len(x): curr_index = random.randint(0, len(x)-1) if curr_index not in s: x[curr_index], x[i] = x[i], x[curr_index] s.add(curr_index) i+=1 print(x)
Well you did not define random in any particular way so, since every permutation of the array of n integers is equally "random" by using rand() we just set the initial index say, as 0. Then get a random number using rand() say 5 and then lets suppose the value of element at index 5 is 3. We swap the values of elements at initial index and at index 5. Then we set the new initial index to 3. This way we can go through n! iterations but not generate all n! permutations.
Just some improvements in respect to floor and rand. Completely confused on whether you must use these two functions or not because the way you used floor is similar to the way you would use mod. The way you explained the question didn't clarify if I could use other operations like multiply or mod. You could easily not need floor to solve this problem and used a different set of operations. Also, didn't clarify whether rand returned a float or an integer. Complete throw off.
Mathematically, yes, but modulus is the most expensive arithmetic operation there is: embeddedgurus.com/stack-overflow/2011/02/efficient-c-tip-13-use-the-modulus-operator-with-caution/ Does not affect complexity of course, but especially on architectures with less sophisticated ALUs it's an order of magnitude in performance.
If you really want to do that, don't just pretend size < 100. Do (size * rand()) % current_index. However, the solution in the video is more efficient and more straight forward.
That solution is incorrect. It isn't completely random. Take for example an array of 49 elements. The numbers that map to index 0 with your function are 0, 49, and 98 giving it a 3% chance of being picked. Similarly index 1 will also have a 3% chance of being selected. Every other index will have a 2% chance of being selected. The effect of this is that numbers in smaller indices will have a higher probability of being mapped to larger indices in the new mapping. This is a problem for every number of indices that does not evenly divide 100, so even iteration down to 25 would be affected too. Which means it is not truly random because the mapping is not independent of current position in the array. The lack of randomness would have a pretty noticeable effect in practice.
For the O(n) solution, isn't the fact that any given index is guaranteed to not stay the same (since only the other indices are valid choices to swap with) , mean that it is not randomly reordered because [0,1,2,3,4] -> [1,0,2,3,4] is a reordered array by only changing two indices and leaving the rest as is?
Peterolen But in the O(n) solution, he excludes picking index 'i' as an option to switch with. So wouldn't that make the array staying exactly the same impossible? To be clear, when I say 'the' O(n) solution, I am referring to the O(n) solution presented in this video.
Your solution is not correct. Because the order is not random. For example 1 will always end up in first or second items of the array and no where else.
What if you picked a number bigger than the size of the array. in your example lets say you picked 9 then you had to put the element on the 9th index and it doesn't exist. Also what about characters? You said there could be anything. I had a solution in just 2 min when you said to pause. Complexity O(n/2). Just loop to the half of array and generate 2 random numbers and swap arr[rand1] with arr[rand2]. It should be pure random because rand1 or rand2 could be same in another ittration.
It's impossible to pick a number bigger than the size of the array, according to the definitions of the functions given. If you believe otherwise, then you have misunderstood the definitions. Characters, Strings, anything would also work. We're selecting from the _indexes_, and the contents don't matter, because they never enter into the equation. O(n/2) *is* O(n). If you believe otherwise, then you have misunderstood the meaning of Big O. Your solution is not uniformly random. It's mentioned many times in the comments, with many explanations as to why it isn't.
You might want to learn about the slice operator in python wich can do exactly what you want. www.pythoncentral.io/how-to-slice-listsarrays-and-tuples-in-python/
Can we generate a random number on every iteration and swap the current index element with a the random no. Is this a good solution. Code for this is below: #include #include #include using namespace std; int main(int argc, char const *argv[]) { int a[] = {3,4,2,1,7,6}; srand(unsigned (time(NULL))); int r; for (int i = 0; i < 6; ++i) { r = rand() % 6; int temp = a[i]; a[i] = a[r]; a[r] = temp; } for (int i = 0; i < 6; ++i) { cout
You could try and put two things at the same random index. Then you would have to linear search for an empty slot. This is basically getting hashing collisions. It's inefficient.
Wouldn't the first solution's time complexity be O(n+nlogn)? There's an n term for assigning each element a key, and then nlogn to quicksort the array.
TWICE in the video it's specified that a number has a chance to stay where it is. Where are you getting this 0% probability from? Did you not understand the explanation or the pseudocode?
It wouldn't be O(n) with any link list because accessing an item on a list itself is O(n). It is assumed that the data would have a constant look up time.
No? If 1 or 9 are randomly selected to be swapped to the end at ANY point, then obviously no? Remember that it was originally 1, 0 at the beginning and 0 got swapped out? It's only 9,1 or 1,9 _at the end_ when it's down to just two unplaced numbers.
Most interviewers will ask many questions. Including easy to difficult problems. Often it's the way that one solves the problem that matters. Also, there are many different fields of software development, with many different requirements.
Great explanation! I like the simple example and using arrows to point at which index is being changed. The repetition helps a ton as well. Hope you keep doing more of these!
Just to a note, for swapping variables in Python you should be able to use a tuple
arr[i], arr[pick] = arr[pick], arr[i]
easy:
array a with size n
for i
I suspect that by scaling random index to remaining array you will break uniformity - you actually don't need to scale - just take each index and pick random index for swap from whole array
this solution lacks the very important PROOF that the probability for any number to land at any index is the same, so here it is:
calculation for the probability for some index i to land in index 0:
1/n, as it is the 1st iteration.
calculation for the probability for some index i to land in index 1:
(n-1)/n * (1/(n-1)). the left hand side is the probability for index j!=i to be selected, because i is already selected, and can't be selected again.
the selection from (n-1) index has probability of (1/(n-1)).
Now apply same logic for array of size k=n-1, for any k.
stopping condition: n=1 (or 0), for probability 1 to land in index 0.
Python code:
def swap(arr, i, j):
assert i < len(arr)
assert j < len(arr)
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
def reorder_in_place(arr):
length = len(arr)
for i in range(length):
dice = random.randrange(i, length)
swap(arr, i, dice)
return arr
Pretty sure Knuth shuffle is O(n) and it also does it in place. Just study Knuth shuffle, it's a super easy algorithm. It's useful in making card games too, so now you can use it for more than just coding interviews
You should not shrink the size of the pool of positions that you randomize your index on. You should always use "floor(rand() * size_of_array)" for a truly random result.
Here's one way to think about it. If it was truly random it should be possible to get the same array as an output as the one you get as an input. With the solution I gave you you can get there.
Great video!
Could you articulate why?
This is the straight-forward approach, unfortunately it doesn't give you a random permutation. As a short mathematical pseudo-proof for an intuition: Assume that you have an array of size n. At each step your algorithm has n possible choices. Then after n iterations you have n^n total possible outcomes of the algorithm. However the total number of permutations of n element array is n!. Unfortunately n^n = n * n * ... * n cannot possibly be evenly divided by n! = n * (n-1) * ... * 2 * 1. Therefore there must be some permutations that are more likely then others. For a better explanation (also with simulations using the different algorithms) there's this wonderful blog post: blog.codinghorror.com/the-danger-of-naivete/
His approach does let you get the same array as output because the algorithm let's an index swap with itself. Look at 3:16 in the video. He does screw that fact up in the rest of the evaluation. He should have multiplied by 5 for the first iteration instead of 4, and that would have made it completely random.
Nope, look up Knuth Shuffle, it's the 100% proper way to randomize an array in place and it's dead simple too
NOOO!!! Delete this comment, you are misleading people and it has too many upvotes. You will "over shuffle" if you do that. This is somewhat hand wavey, but consider this:
You will have n^n shuffles in your naive method. There are n! possible arrangements of cards. Clearly n^n > n!, meaning you are generating more outcomes that possible arrangements, meaning multiple outcomes are getting mapped to the same arrangement.
Rigorous proof:
stats.stackexchange.com/a/3087
I was just asked this question at an interview with Amazon yesterday. I wish I had seen this video a few days ago!
Was this interview an onsite interview? I ask because I have one coming up, and so how did it go for you?
F
You can get a randomize discrete number for each index by floor(rand()*100) then you O(n) sorting algorithms like bucket sort since the numbers are refined from 0 to 99.
for i = 0 to n -1:
temp1 = floor(rand()*n)
temp2 = floor(rand()*n)
swap(arr[temp1],arr[temp2])
What is wrong with this?
It is O(n) (Swapping can be done using another temp variable)
Mohit Jarvis Sharma that's the first solution to come to my mind too, except I ran the loop n/2 times.
The possible new orders aren't evenly distributed. One might occur more often than the others.
But when you write "for i in range(r):", the distribution becomes more even when r becomes bigger and it becomes less even when the array size increases.
We'd have 0(r) for time and 0(1) for space.
@@timonpasslick it's not true if rand returns perfectly continuous distribution [0,1) - you always can map continuous distribution to any discrete
@@z08840 Then it would be true if this was the Fisher Yates shuffle but with this algorithm it's not.
@@timonpasslick I was referring to your suggestion that "One might occur more often than the others" - it's not true.
The algorithm itself is not good, of course, - since both indexes are randomly selected known number of times we can calculate how many indexes with which probability will remain on their places.
My solution is to call random and floor function to get the random number. You start at index 0 and go to index n-1. You get your random value (which is between 0 and n-1), and make it the new index for your current index, so you swap the values (need a temporary variable). Repeat this till you reached the end of the array and you are done.
Random value should be between index and n-1 because list before index is already shuffled
Great videos! What is the software you use for the drawings?
a very systematic approach. Love it!
If you swap the last index (in this case 4) with position 0 through 3.. that means there is a 0% chance the number will stay in its current position. This would not be a truly random number and predicting the outcome of the "shuffle" becomes easier
Ben Wright You also count that number in the random
When going through it the first time (around 2:20) he specifically says he's picking a value out of ALL the values in the array.
Later, in the pseudocode (7:05) it specifically shows pick = floor( (i+1) * rand() )
That i+i _includes_ the index being selected for.
So you're never swapping the last index (in this case 4) with just positions 0 through 3. pick = floor( (4+1) * rand() ) = floor( 5 * rand() ) = {0, 1, 2, 3, 4} (each with a 20% chance of being picked)
from random import randint
import math
def rand():
alea = randint(0,1000)
return alea/1000
def floor(num):
return math.floor(num)
def switch(lst, i, j):
temp = lst[j]
lst[j] = lst[i]
lst[i] = temp
def random_reor(lst):
for i in range(len(lst)):
switch(lst, i, floor(rand()*len(lst)))
that's my sol
I would use
floor((rand() * 10) / 2) = i
for n in array:
Swap value i and n
Not sure if thats O(N) but it seems efficient to me
I have a problem with that method in that it isn't random.
If it were truly random, the last number would have just as high of a chance of _remaining_ as the last number as any other number would have a chance of replacing it.
The solution I had was similar, but you could switch with either the left or the right side of the current number. You could pick a random number from the left side and from the right side and pick one of those two to switch, weighing the odds by how many numbers were on each side. If you wanted, you could repeat the whole thing a few times to make it more random, and it would remain O(n).
*Edit*
Actually, it may be easier to simply do this method from right to left and then repeat it from left to right while still being random **enough**
The last number *DOES* have just as high of a chance of remaining as the last number as any other number has of replacing it. It's included in the indexes being selected from. It's stated in words when he starts his demonstration ("We choose from ALL the numbers in the array"), it happens during his demonstration, and it's coded in the pseudocode.
Why are there so many comments with this mistake in them?
floor(4*rand()) could be equal to 4 if rand()==1.
This is unlikely to happen, but if it does, you'll try to access an invalid memory position
Look at the explaination of the rand() function, he clearly says 0
It's not only unlikely to happen, it's literally impossible. rand() will NEVER equal 1. It can't. Look at the definition.
from random import shuffle
def reorder(arr1):
shuffle(arr1)
print(arr1)
arr1=[1,0,3,9,2]
reorder(arr1)
how did u learn this..
I am a bit confused..
can I learn by any source..
have any link?????😢☺
2:53 at this point you can choose 9 again.. then it will not be suffled?
ik this is 7months old, but if you allow it to choose one of the ones that havent been shuffled yet, than 9 could be chosen as well which would be random as well. Random shuffling doesnt require new positions for each value. Theoretically you dont even need to abandon the already shuffled ones so you could switch the current value with any value in the array, but it raises the chance of doing the same steps reversed, so this is very likely the best solution for O(n).
There is a lot of confusion here. I believe what you were going for is the modern Fisher-Yates shuffle algorithm. Anybody interested can look it up on Wikipedia.
The modern FY states that when you first start from right to left at n-1, 0
What error?? That's exactly what the code in the video does.
The code in the video is:
pick = floor((i + 1) * rand()),
after which 0
@@ZantierTasa if you look at 4:58, you'll see that the range is 0
@@wulymammoth The example at 4:58 is the SECOND loop of the algorithm, where the 5th element of the array (highlighted in blue) has already been done. So picking a number between 0 and 3 inclusive is correct.
You didn't actually prove that every permutation is equally likely...
It kinda follows from the algorithm. First you have n possible positions, then n-1 down to 1. Exactly n! possible configurations. And that is the formula for calculating the number of permutations of an array of size n.
Why couldn’t you just visit each position of the array and, for each such position, randomly generate a different position to which the current element should be transposed. Of course, this means swapping the current position with the random position. Some elements will definitely get swapped more than once. It is even possible that some elements don’t get swapped at all. But that’s all determined by the rand() function, which is completely ok.
@@thest.kitts-nevislabourpar3281 Had the exact same approach. Even if some numbers don't change their position after execution, it is due to the rand() function and can't be predicted.
to settle this, we can use a computer! write test - rearange array (2 or more elements, with unique values) billion times and calculate average value for each position.
function randomize(arr){
for(var i = 0; i
In Python :
# Rearranging elements of an array in O (n)
import random
x = [7, 5, 2, 11, 4, 9]
s = set()
i = 0
while len(s) is not len(x):
curr_index = random.randint(0, len(x)-1)
if curr_index not in s:
x[curr_index], x[i] = x[i], x[curr_index]
s.add(curr_index)
i+=1
print(x)
Well you did not define random in any particular way so, since every permutation of the array of n integers is equally "random" by using rand() we just set the initial index say, as 0. Then get a random number using rand() say 5 and then lets suppose the value of element at index 5 is 3. We swap the values of elements at initial index and at index 5. Then we set the new initial index to 3. This way we can go through n! iterations but not generate all n! permutations.
Do we loop backwards just for the sake of handy floor( (i+1) * rand() ) ?
i could only think of o(n), log n approach doesn't seem to be a natural thought for anyone
You should've chosen ceil or floor equally likely.
Just some improvements in respect to floor and rand. Completely confused on whether you must use these two functions or not because the way you used floor is similar to the way you would use mod. The way you explained the question didn't clarify if I could use other operations like multiply or mod. You could easily not need floor to solve this problem and used a different set of operations. Also, didn't clarify whether rand returned a float or an integer. Complete throw off.
Peterolen one thing I learn during interviews is you cant assume anything. Everything must be explicit.
At 00:29, the video shows "0
We could use
(100 * rand()) % current_index
Mathematically, yes, but modulus is the most expensive arithmetic operation there is:
embeddedgurus.com/stack-overflow/2011/02/efficient-c-tip-13-use-the-modulus-operator-with-caution/
Does not affect complexity of course, but especially on architectures with less sophisticated ALUs it's an order of magnitude in performance.
If you really want to do that, don't just pretend size < 100. Do (size * rand()) % current_index.
However, the solution in the video is more efficient and more straight forward.
That solution is incorrect. It isn't completely random. Take for example an array of 49 elements. The numbers that map to index 0 with your function are 0, 49, and 98 giving it a 3% chance of being picked. Similarly index 1 will also have a 3% chance of being selected. Every other index will have a 2% chance of being selected. The effect of this is that numbers in smaller indices will have a higher probability of being mapped to larger indices in the new mapping. This is a problem for every number of indices that does not evenly divide 100, so even iteration down to 25 would be affected too. Which means it is not truly random because the mapping is not independent of current position in the array. The lack of randomness would have a pretty noticeable effect in practice.
why it is necesarry to do n to 1, and not 1 to n?
My solution in JS before watching the video:
function interval_int_rand(low, high) {
return Math.floor(Math.random() * (high - low) + low)
}
function rearrange(array) {
const result = [...array];
for (let i = 0; i < result.length; i++) {
const index = interval_int_rand(i, result.length);
const temp = result[i];
result[i] = result[index];
result[index] = temp;
}
return result;
}
😱😱😱 so random 😂
Or you could convince management that requirements are wrong and changing array order randomly is no good for business.
This is kinda like selection sort
complicated but helpful
This should solve the problem:
const shuffleOrder = (arr) =>{
for(let i = 0; i
Big O for quicksort is n^2
en.wikipedia.org/wiki/Quicksort
For the O(n) solution, isn't the fact that any given index is guaranteed to not stay the same (since only the other indices are valid choices to swap with) , mean that it is not randomly reordered because [0,1,2,3,4] -> [1,0,2,3,4] is a reordered array by only changing two indices and leaving the rest as is?
Peterolen That's a yes, right?
Peterolen But in the O(n) solution, he excludes picking index 'i' as an option to switch with. So wouldn't that make the array staying exactly the same impossible?
To be clear, when I say 'the' O(n) solution, I am referring to the O(n) solution presented in this video.
thanks dude
good
Your solution is not correct. Because the order is not random. For example 1 will always end up in first or second items of the array and no where else.
Not true. You are missing the probability that any other item gets swapped with 1.
What if you picked a number bigger than the size of the array. in your example lets say you picked 9 then you had to put the element on the 9th index and it doesn't exist. Also what about characters? You said there could be anything.
I had a solution in just 2 min when you said to pause. Complexity O(n/2).
Just loop to the half of array and generate 2 random numbers and swap arr[rand1] with arr[rand2]. It should be pure random because rand1 or rand2 could be same in another ittration.
Looping half of the array. How is it equal to looping complete array?
We are considering n as the size of the array. right?
It's impossible to pick a number bigger than the size of the array, according to the definitions of the functions given. If you believe otherwise, then you have misunderstood the definitions.
Characters, Strings, anything would also work. We're selecting from the _indexes_, and the contents don't matter, because they never enter into the equation.
O(n/2) *is* O(n). If you believe otherwise, then you have misunderstood the meaning of Big O.
Your solution is not uniformly random. It's mentioned many times in the comments, with many explanations as to why it isn't.
Amazing. This feels like the bottom up approach. Correct me if I'm wrong!
if this question was asked in a coding interview question should we use library function ?
You can always ask during the interview. Most likely they won't mind.
hey YK. how do we do "for i from n-1 down to 1" (6:32), in python. Its like a reverse loop which iterates from the opposite end index.
plz help
You might want to learn about the slice operator in python wich can do exactly what you want.
www.pythoncentral.io/how-to-slice-listsarrays-and-tuples-in-python/
Can we generate a random number on every iteration and swap the current index element with a the random no. Is this a good solution. Code for this is below:
#include
#include
#include
using namespace std;
int main(int argc, char const *argv[])
{
int a[] = {3,4,2,1,7,6};
srand(unsigned (time(NULL)));
int r;
for (int i = 0; i < 6; ++i)
{
r = rand() % 6;
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
for (int i = 0; i < 6; ++i)
{
cout
eZpZ lemon squeezy
The question's instructions are very unclear...
Whats stopping you from setting a random index for each object in the array for example...
You could try and put two things at the same random index. Then you would have to linear search for an empty slot. This is basically getting hashing collisions. It's inefficient.
Just do this , swap(arr[i],arr[rand()%(i+1)]); from i to n;
Wouldn't the first solution's time complexity be O(n+nlogn)? There's an n term for assigning each element a key, and then nlogn to quicksort the array.
Alec Strickland O(n+nlogn) = O(nlogn). U can prove this using limit theorem. I.e lim(n + nlogn) / nlogn = 0
I did this
lista.sort(key=lambda x : random.random())
simple and I using less registers then You
Sorting is at best O(n log n) time complexity.
The algorithm exposed in the video is O(n)
@@coolfunmario you are right thanks :)
Do we really learn all this in college.
yes
This one was kinda obvious.
Bogo sort ftw
C++ rand() function really sucks so it might not work well for c++ haha
Works fine :)
Slightly modified
#include
#include
int Rand(int min, int max)
{
if (max - min == 0) return 0;
return rand() % (max - min) + min;
}
template
void RandomReorder(T arr[], int size)
{
srand(time(0)):
for (int i = 0; i < size; ++i)
{
int swapIndex = Rand(0, size - 1);
T temp = arr[i];
arr[i] = arr[swapIndex];
arr[swapIndex] = temp;
}
}
Your solution is wrong. Any number never stays in their same place(0 probabily), so it's not random.
Mmm, no, a number could stay or be put back later at it's initial place. Why do you think there is a restriction on that? The code allows it
TWICE in the video it's specified that a number has a chance to stay where it is. Where are you getting this 0% probability from? Did you not understand the explanation or the pseudocode?
I have an awesome solution
Here's javascript solution (ps I didn't see the solution so it might be bad):
function random(arr)
{
var rands = {};
for(var i=0; i
Frankly, this wouldn’t be O(n) if it is a large linked list
It wouldn't be O(n) with any link list because accessing an item on a list itself is O(n). It is assumed that the data would have a constant look up time.
I was thinking to solve it by randomly swapping the contents of the array n times... 😆
This solution is far from random. The array will ALWAYS begin with 9,1 or 1,9 ...
wrong.
No? If 1 or 9 are randomly selected to be swapped to the end at ANY point, then obviously no? Remember that it was originally 1, 0 at the beginning and 0 got swapped out?
It's only 9,1 or 1,9 _at the end_ when it's down to just two unplaced numbers.
wtf this is so easy who would actually ask this .... for internships i guess?
Most interviewers will ask many questions. Including easy to difficult problems. Often it's the way that one solves the problem that matters.
Also, there are many different fields of software development, with many different requirements.
You can also do it without extra space