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

Enjoy free content straight from your inbox 💌

00:00

In our last lesson, we looked at the concept of loop in variance and how they can help you solve programming challenges. In this lesson, we will build upon that by solving a problem that is perhaps not as simple as finding the minimum in N array and solve it with the same concept so you get a better understanding. And this programming challenge actually comes from a Google interview. Celeste, jump in and have a look. Here's the programming challenge statement. Given a string return, the maximum consecutive repeating character in the string. Whenever you are given a programming challenge,

00:33

it's always a good idea to start off by writing a few examples. So in this first example, the longest repeating character is character capital C in the middle of the string. In the second example, there are two repeating characters, which are O and a, but the first longest one that we experienced is O. And we are going to assume that that is what we want to return. And just for amusement, here's an example with emoji characters. Now the next step of course, to solve any programming challenge is to write a skeleton function. Our skeleton function is going to take an input string and is going to return a string of length,

01:07

one containing the longest, consecutive repeating character. Now, before we start looping through the characters in the input string, we maintain a few in variants. The first one is a variable called longest, which stores the longest character that we have experienced so far, as well as how many times this character repeated consecutively. And of course, at the time when we haven't experienced any of the characters from the input, or by chance the input string is an empty one. Returning an empty string is also an excellent choice. Now as we progress through the various characters in the input string, the current consecutive character will change over time.

01:40

For the first example, initially it'll be A, then it'll be B, then it'll be C, and then it'll be a, again. The solution to the problem is essentially maintaining this current consecutive and then constantly comparing it to the longest that we have experienced previously. And if at any point the current consecutive exceeds the longest that we experienced previously, we update the longest to the new value. So in code, we start off by looping through the input characters with a simple four off loop. The next step is to maintain the current consecutive. And we can do that by checking if the character is the same as the current car.

02:14

And if it is, we've experienced one more of the current character and we simply increment it count. Otherwise, our current consecutive has changed and we need to start off with the new character at count one. Now, in addition to maintaining the invariant about the current consecutive character that we are experiencing, we also maintain the invariant that at any point within the loop longest points to the longest current consecutive we have ever experienced. And that is easily done by simply checking the current count against the longest count. And if that is the case, we store the current into the longest by creating a shallow copy using the

02:48

JavaScript spread operator. And that's the entire solution to the problem. By the time this fall loop terminates because of maintaining the invariant about the longest and the current, we can be guaranteed that the longest is the maximum that we have ever experienced. Now, as a bonus, it's always good to talk about space and time complexity. So in terms of space complexity, we are only maintaining two simple variables. So it is constant OF one. And in terms of space complexity, since we are looping through all of the input characters, it is directly dependent upon that and therefore OFN or linear time.

03:19

And of course, as bonus points, if ever given time, you should always add tests to verify that your code functions as expected. And as you can see for this particular case, the tests are quite easy. The key intuition for this particular lesson is that we actually needed to maintain two kinds of variables. One global maximum that we have experienced so far, and one local chain that we are experiencing right now, so that if it ever exceeds the global maximum, 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