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 In our last lesson, we looked at the concept

00:02 of loop in variance

00:03 and how they can help you solve programming challenges.

00:06 In this lesson, we will build upon that by solving a problem

00:08 that is perhaps not as simple

00:10 as finding the minimum in N array

00:12 and solve it with the same concept

00:14 so you get a better understanding.

00:15 And this programming challenge actually comes

00:17 from a Google interview.

00:18 Celeste, jump in and have a look.

00:24 Here's the programming challenge statement.

00:26 Given a string return,

00:27 the maximum consecutive repeating character in the string.

00:31 Whenever you are given a programming challenge,

00:33 it's always a good idea to start off

00:34 by writing a few examples.

00:37 So in this first example,

00:38 the longest repeating character is character capital C

00:41 in the middle of the string.

00:43 In the second example, there are two repeating characters,

00:45 which are O and a,

00:47 but the first longest one that we experienced is O.

00:50 And we are going to assume that

00:51 that is what we want to return.

00:53 And just for amusement, here's an example

00:55 with emoji characters.

00:57 Now the next step of course,

00:58 to solve any programming challenge is

01:00 to write a skeleton function.

01:02 Our skeleton function is going to take an input string

01:05 and is going to return a string of length,

01:07 one containing the longest, consecutive repeating character.

01:10 Now, before we start looping

01:12 through the characters in the input string,

01:13 we maintain a few in variants.

01:15 The first one is a variable called longest,

01:17 which stores the longest character that we have experienced

01:20 so far, as well as

01:21 how many times this character repeated consecutively.

01:24 And of course, at the time when we haven't experienced any

01:27 of the characters from the input,

01:28 or by chance the input string is an empty one.

01:30 Returning an empty string is also an excellent choice.

01:34 Now as we progress through the various characters in the

01:36 input string, the current consecutive

01:38 character will change over time.

01:40 For the first example, initially it'll be A,

01:43 then it'll be B, then it'll be C,

01:45 and then it'll be a, again.

01:46 The solution to the problem is essentially maintaining this

01:49 current consecutive

01:50 and then constantly comparing it to the longest

01:52 that we have experienced previously.

01:55 And if at any point the current consecutive exceeds the

01:57 longest that we experienced previously,

01:59 we update the longest to the new value.

02:01 So in code, we start off by looping

02:03 through the input characters with a simple four off loop.

02:06 The next step is to maintain the current consecutive.

02:09 And we can do that by checking if the character is the same

02:12 as the current car.

02:14 And if it is, we've experienced one more

02:16 of the current character and we simply increment it count.

02:19 Otherwise, our current consecutive has changed

02:21 and we need to start off

02:22 with the new character at count one.

02:25 Now, in addition to maintaining the invariant about the

02:27 current consecutive character that we are experiencing,

02:30 we also maintain the invariant

02:31 that at any point within the loop longest points

02:34 to the longest current consecutive we have ever experienced.

02:38 And that is easily done

02:39 by simply checking the current count

02:41 against the longest count.

02:43 And if that is the case, we store the current into the

02:45 longest by creating a shallow copy using the

02:48 JavaScript spread operator.

02:50 And that's the entire solution to the problem.

02:52 By the time this fall loop terminates

02:54 because of maintaining the invariant about the longest

02:56 and the current, we can be guaranteed

02:58 that the longest is the maximum

02:59 that we have ever experienced.

03:01 Now, as a bonus, it's always good

03:03 to talk about space and time complexity.

03:05 So in terms of space complexity,

03:06 we are only maintaining two simple variables.

03:08 So it is constant OF one.

03:11 And in terms of space complexity, since we are looping

03:13 through all of the input characters,

03:14 it is directly dependent upon that and therefore OFN

03:18 or linear time.

03:19 And of course, as bonus points, if ever given time,

03:22 you should always add tests to verify

03:24 that your code functions as expected.

03:26 And as you can see for this particular case,

03:28 the tests are quite easy.

03:31 The key intuition for this particular lesson is

03:33 that we actually needed to maintain two kinds of variables.

03:36 One global maximum that we have experienced so far,

03:39 and one local chain that we are experiencing right now, so

03:42 that if it ever exceeds the global maximum,

03:44 we can update the global one.

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