If you already have a subscription, you can sign in.

1.Loop Invariants

free

⏱️ 2:45

2.Longest Consecutive Character

free

⏱️ 3:47

3.FizzBuzz ... Moore

free

⏱️ 4:24

4.Bracket Matching

free

⏱️ 2:55

5.Swap Two Variables In-Place

free

⏱️ 2:09

6.Array Sorting in JavaScript

⏱️ 3:45

7.Create a Linked List

free

⏱️ 4:40

8.Classic Linked List

⏱️ 2:05

9.Doubly Linked List

⏱️ 4:54

10.Revese a Linked List In-Place

⏱️ 3:45

11.Random Integers

⏱️ 3:30

12.Perfect Shuffle an Array

⏱️ 4:58

13.Derangement

⏱️ 3:48

14.Tree Data Structure Math Simplified

⏱️ 8:01

15.Queue Data Structure

⏱️ 7:23

16.Find the Repeated Item

⏱️ 3:32

17.Remove all Duplicates

⏱️ 3:25

18.Two Sum

⏱️ 3:37

19.Two Sum Sorted

⏱️ 3:36

20.Three Sum

⏱️ 7:23

00:00 Now there are a lot of algorithmic questions

00:02 that are related to randomization,

00:05 but the most popular one that I can think of is the problem

00:07 of shuffling, for example, shuffling a deck of cards.

00:10 And that is the problem that we will look at in this lesson.

00:14 So let's go. Now

00:16 before we look at anything else, the first thing

00:18 that we need to clarify is the concept

00:20 of the perfect shuffle.

00:22 What a perfect shuffle essentially means is

00:24 that any item can appear in any position

00:27 with equal probability.

00:29 So if we have N items in end positions,

00:31 then any item can appear in any position

00:34 with the probability one over end.

00:36 Now, that might sound like a hard ask,

00:38 but it's actually quite easy to achieve.

00:41 Fundamentally, we pick an item one by one

00:43 and put it in the output.

00:45 So assuming we have an array, A, B, C, D, F, whatever,

00:49 we pick an item at random.

00:50 Let's say we pick C and we put it in position zero

00:53 and we pick a next random item.

00:55 Let's say we pick D, put it in position one,

00:58 and then pick the next random item and so on.

01:01 And we can actually prove the mathematical correctness

01:03 of this algorithm quite easily.

01:05 So let's do that next.

01:07 Now, since we're going to pick the first item at random,

01:09 the odds of it getting picked are going to be quite fair.

01:12 It's going to be simply one over N.

01:13 As we have N items,

01:15 things get a bit more interesting when we pick up the next

01:18 item at index one.

01:19 The odds of it getting picked are essentially the odds

01:22 of it not getting selected in the first attempt

01:24 and getting selected in the second attempt.

01:27 Now, the odd of it not getting selected in the first attempt

01:29 are actually quite high as we have N minus one items

01:32 that will not get picked among the N items.

01:35 The odds of it getting picked in the second attempt is

01:38 simply going to be one over the N minus one.

01:40 Items that we will be picking amongst

01:42 the N minus ones will cancel out with each other, leaving us

01:46 with the standardized one over N.

01:48 And this process will continue

01:50 for all other attempts as well.

01:51 Only the chain of the item not getting in into nth

01:54 attempts will get longer.

01:55 However, we will always be left

01:57 with one on top and N at the bottom.

02:00 So with the mathematical analysis

02:02 of picking an item randomly one by one out of the way,

02:05 let's look at our example once more.

02:07 Our objective is to randomly select the items one by one.

02:10 However, there is one more complication that we need

02:13 to think of at each step.

02:15 We have to remember which items we have already picked

02:18 and which items are still available to be randomly chosen.

02:21 Now, we could do this in separate data structures,

02:24 however, it's actually quite easy to do in a single array.

02:27 So let's look at an example.

02:29 We will essentially have the array as a shuffle

02:31 and an un shuffle portion.

02:33 We start off with a completely empty shuffled portion.

02:37 So in our first attempt, let's say we pick C,

02:40 move it into index zero,

02:42 and we take whatever was there, for example,

02:44 in this case it is A,

02:45 and move it into where C originally was.

02:48 Now we have this shuffle portion containing C

02:50 and this uns shuffle portion

02:52 containing all the other members.

02:54 And the next item we pick,

02:55 we will pick randomly starting at index one all the way

02:58 Till N.

03:00 Let's say we pick T, we swap what was already there,

03:03 which is the character B, and move it into where D was.

03:06 So in each step, the shuffle portion gets bigger

03:08 and bigger till we eventually run out

03:10 of all the uns shuffled members.

03:12 And then we have a completely shuffled array.

03:15 Now understanding how the algorithm works might have been a

03:18 bit involved, but quoting it up is

03:20 actually going to be quite easy.

03:21 We start off by bringing in our random integer function,

03:24 which we coded up in our previous lesson.

03:26 And then we have this template function,

03:29 which will take an array of type T

03:30 and return an array of type T.

03:32 And the first thing that we will do is

03:34 that we will create a copy of the input array

03:36 as I don't like mutating our input arrays.

03:39 However, if you'd lead this call

03:40 to slice this algorithm will still work perfectly fine.

03:43 It's just that the input array is

03:44 what we will be shuffling in place.

03:47 Now for the main core of the algorithm, we simply have

03:49 to loop through end times for an items.

03:52 And in each iteration, the first thing

03:54 that we do is we get a random index starting at I all the

03:58 way till the end of the array,

03:59 and then we swap the item at the random index

04:01 with the item at the I index.

04:04 This means that the array has been shuffled up till I,

04:07 and then the loop continues with i plus plus.

04:10 This one line swapping of I item

04:13 with the random index item is a JavaScript trick

04:15 that I have a lesson dedicated to

04:17 as well, if you are interested.

04:19 Now, once this loop terminates,

04:20 we've essentially placed N items into N positions,

04:23 which is exactly what we want our shuffle algorithm to do.

04:26 Now because we are only looping

04:28 to the input array once the time complexity

04:30 of this algorithm is OFN.

04:33 And because we are creating a new array with array

04:35 to slice the space, complexity is OFN.

04:39 However, if you remove this call to slice,

04:41 we can essentially shuffle the input array in place,

04:43 therefore giving us a space complexity

04:45 of OF one, which is constant.

04:49 Now shuffling is a very well understood problem,

04:51 and the algorithm that we implemented in this lesson is

04:54 known as the modernized version of the Fisher Yates Shuffle.

1.Loop Invariants

free

⏱️ 2:45

2.Longest Consecutive Character

free

⏱️ 3:47

3.FizzBuzz ... Moore

free

⏱️ 4:24

4.Bracket Matching

free

⏱️ 2:55

5.Swap Two Variables In-Place

free

⏱️ 2:09

6.Array Sorting in JavaScript

⏱️ 3:45

7.Create a Linked List

free

⏱️ 4:40

8.Classic Linked List

⏱️ 2:05

9.Doubly Linked List

⏱️ 4:54

10.Revese a Linked List In-Place

⏱️ 3:45

11.Random Integers

⏱️ 3:30

12.Perfect Shuffle an Array

⏱️ 4:58

13.Derangement

⏱️ 3:48

14.Tree Data Structure Math Simplified

⏱️ 8:01

15.Queue Data Structure

⏱️ 7:23

16.Find the Repeated Item

⏱️ 3:32

17.Remove all Duplicates

⏱️ 3:25

18.Two Sum

⏱️ 3:37

19.Two Sum Sorted

⏱️ 3:36

20.Three Sum

⏱️ 7:23