DEV Community: Nayeem Reza

Best Time to Buy and Sell Stock

Nayeem Reza — Mon, 11 May 2020 12:20:02 +0000

🔗 Problem Description:

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. 
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution Approach

We can solve that by iterating over the given array of prices once! We have to keep track of the minimum-price we have seen so far and in each day we'll check if we can maximize our profit by calculating the difference between minimum price we have seen so far and the price of the current day. Let's see an example -

A = [7, 1, 5, 3, 6]
maxProfit = 0, minPrice = MAX

In each iteration we'll do these
    minPrice = min(A[i], minPrice)
    maxProfit = max(maxProfit, A[i] - minPrice)

i = 0
minPrice = min(7, MAX) ::= 7
maxProfit = max(0, 7 - 7) ::= 0

i = 1
minPrice = min(1, 7) ::= 1
maxProfit = max(0, 1 - 1) ::= 0

i = 2
minPrice = min(5, 1) ::= 1
maxProfit = max(0, 5 - 1) ::= 4

i = 3
minPrice = min(3, 1) ::= 1
maxProfit = max(4, 3 - 1) ::= 4

i = 4
minPrice = min(6, 1) ::= 1
maxProfit = max(4, 6 - 1) ::= 5

return maxProfit ::= 5

Here's the code -

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        int minPrice = INT_MAX;

        int size = prices.size();
        for(int i=0; i<size; i++) {
            int diff = prices[i] - minPrice;
            minPrice = min(minPrice, prices[i]);
            maxProfit = max(maxProfit, diff);
        }

        return maxProfit;
    }
};

Complexity Analysis

Time Complexity `O(n)`

Linear time solution; only traversing the array

Space Complexity `O(1)`

Constant space

Blind75: Array

Nayeem Reza — Mon, 11 May 2020 12:12:49 +0000

#	Array Problems
1	Two Sum
2	Best Time to Buy and Sell Stock
3	Contains Duplicate
4	Product of Array Except Self
5	Maximum Subarray
6	Maximum Product Subarray
7	Find Minimum in Rotated Sorted Array
8	Search in Rotated Sorted Array
9	3Sum
10	Container with most Water

Two Sum

Nayeem Reza — Mon, 11 May 2020 11:51:07 +0000

🔗 Problem Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution Approach

Given an array of integers and a target value. We need to find out two numbers from the array which will sum the target value. To do this in the brute-force approach we can easily check all possible cases to find two numbers which will get us the target sum. But this approach will cost O(n^2) time. We can minimize this time complexity by using a hash-table. We'll iterate through the array and for each number we'll store the subtracted value from the target and the index to the hash-table. And in each iteration we'll check if the current number exists in the hash-table. If we get the value in hash-table that means we've found the two values that will give us the target sum!

Suppose, given -

nums = [2, 3, 5, 7]
target = 9

Let's have our HashMap M and visualize what we're doing in each iteration -

i = 0:
check nums[i] = 2 exists in M
[NO] Insert 9 - 2 = (7 -> 0) in M
     M = { 7: 0 }

i = 1
check nums[i] = 3 exists in M
[NO] Insert 9 - 3 = (6 -> 1) in M
     M = { 7: 0, 6: 1 }

i = 2
check nums[i] = 5 exists in M
[NO] Insert 9 - 5 = (4 -> 2) in M
     M = { 7: 0, 6: 1, 4: 2 }

i = 3
check nums[i] = 7 exists in M
[YES] return { i, M[7] } = { 3, 0 }

That's basically the illustration of our thought process, let's now try to code -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        unordered_map<int, int> M;

        for(int i=0; i<size; i++) {
            int diff = target - nums[i];
            if(M.find(nums[i]) != M.end()) {
                return { M[nums[i]], i };
            }

            M[diff] = i;
        }

        return {};
    }
};

This solution has linear time-complexity and linear space-complexity i.e. O(n). Can we achieve this in constant space by not using any additional data-structure? We can do that if the given array is sorted, then we can use an invariant to solve that in constant space! Having two pointers e.g. i and j, pointing to the 0th index and the n-1th index of the array! In each iteration we'll check if we can get A[i] + A[j] == target, because that's the result we want! But, what will happen when there will be inequality, or what will be the policy to move the indexes? Here, we'll be using the invariants. If we get A[i] + A[j] < target, we know that we cannot get the target by moving i forward, because it'll give us another larger value then the current A[i] as the array is sorted; so, we'll move j by decrementing the value, by this way we'll have a chance of minimizing the A[i] + A[j] and take closer to the target value. Otherwise, when A[i] + A[j] > target, if we understand the previous invariant then we can easily go with this, which is moving i forward because our sum i.e. A[i] + A[j] is lower than the target, if we move the ithe index forward we'll get a higher value. Let's go through an illustration of our solution approach -

A = [2, 5, 7, 9, 13]
target = 14

i = 0, j = 4
A[i] + A[j] ::= 2 + 13 ::= 15 > target ::= 15 > 14
Decrement j ::= 3

i = 0, j = 3
A[i] + A[j] ::= 2 + 9 ::= 11 < target ::= 11 < 14
Increment i ::= 1

i = 1, j = 3
A[i] + A[j] ::= 5 + 9 ::= 14 = target ::= 14 = 14
Done, return { i, j } ::= { 1, 3 }

Here's the code of this solution -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0, j = nums.size() - 1; i < j; ) {
            if(nums[i] + nums[j] == target) {
                return { i, j };
            } else if(nums[i] + nums[j] > target) {
                j--;
            } else {
                i++;
            }
        }

        return {};
    }
};

Complexity Analysis

Time Complexity `O(n)`

Linear time; as we need to iterate the whole array in the worst case

Space Complexity `O(1)`

Constant space; no additional data-structure applied

Blind75: Introduction

Nayeem Reza — Mon, 11 May 2020 11:50:31 +0000

In Dec 2018, TeamBlind released this article saying -

New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the best LeetCode questions that teach you to core concepts and techniques for each category/type of problems! Many other LeetCode questions are a mash of the techniques from these individual questions. I used this list in my last job hunt to only do the important questions.

In this series, I'll be solving each of the problems from Blind75 and post the solution approach and the thought process behind each coding problem that I'll attempt to do. Also, I'll add complexity(time, space) analysis of the solutions. I'll use c++ as my programming language to solve these but the main idea is to gather the solution thought process and by that, you can solve the problems in any language you want!

How to identify and resolve wasted renders in React

Nayeem Reza — Mon, 11 May 2020 07:34:58 +0000

Originally published in medium

How to identify and resolve wasted renders in React | by Nayeem Reza | We’ve moved to freeCodeCamp.org/news | Medium

Nayeem Reza ・ Jul 9, 2020 ・
Medium

So, recently I was thinking about performance profiling of a react app that I was working on, and suddenly thought to set a few performance metrics. And I did come across that the first thing I need to tackle is wasted renders I’m doing in each of the webpages. You might be thinking about what are wasted renders by the way? Let’s dive down in.

From the beginning, React has changed the whole philosophy of building web apps and subsequently the way front-end developers think. With its introduction of Virtual DOM, React makes UI updates as efficient as they can ever be. This makes the web app experience neat. Have you ever wondered how to make your React applications faster? Why do moderately sized React web apps still tend to perform poorly? The problems lie in how we are actually using React!

How React works

A modern front-end library like React doesn’t make our app faster wondrously. First, we developers should understand how React works. How do the components live through the component lifecycles in the applications lifetime? So, before we dive into any optimization technique, we need to have a better understanding of how React actually works under the hood.

At the core of React, we have the JSX syntax and React’s powerful ability to build and compare virtual DOMs. Since its release, React has influenced many other front-end libraries. For example, Vue.js also relies on the idea of virtual DOMs.

Each React application begins with a root component. We can think of the whole application as a tree formation where every node is a component. Components in React are ‘functions’ that render the UI based on the data. That means props and state it receives; say that is CF

UI = CF(data)

Users interact with the UI and cause the change in data. The interactions are anything a user can do in our application. For example, clicking a button, sliding images, dragging list items around, and AJAX requests invoking APIs. All those interactions only change the data. They never cause any change in the UI.

Here, data is everything that defines the state of an application. Not just what we have stored in our database. Even different front-end states like which tab is currently selected or whether a checkbox is currently checked or not are part of this data. Whenever there is a change in data, React uses the component functions to re-render the UI, but only virtually:

UI1 = CF(data1)
UI2 = CF(data2)

React computes the differences between the current UI and the new UI by applying a comparison algorithm on the two versions of its virtual DOM.

Changes = Difference(UI1, UI2)

React then proceeds to apply only the UI changes to the real UI on the browser. When the data associated with a component changes, React determines if an actual DOM update is required. This allows React to avoid potentially expensive DOM manipulation operations in the browser. Examples such as creating DOM nodes and accessing existing ones beyond necessity.

This repeated differentiating and rendering of components can be one of the primary sources of React performance issues in any React app. Building a React app where the differentiating algorithm fails to reconcile effectively, causing the entire app to be rendered repeatedly which is actually causing wasted renders and that can result in a frustratingly slow experience.

During the initial render process, React builds a DOM tree like this —

Suppose that a part of the data changes. What we want React to do is re-render only the components that are directly affected by that specific change. Possibly skip even the differentiating process for the rest of the components. Let’s say some data changes in Component 2 in the above picture, and that data has been passed from R to B and then 2. If R re-renders then it’ll re-render each of its children that means A, B, C, D and by this process what actually React does is this:

In the image above, all the yellow nodes are rendered and differentiated. This results in wasted time/computation resources. This is where we will primarily put our optimization efforts. Configuring each component to only render and differentiate when it is necessary. This will allow us to reclaim those wasted CPU cycles. First, we’ll take a look into the way that we can identify wasted renders of our application.

Identify wasted renders

There are a few different ways to do this. The simplest method is to toggle on the highlight updates option in the React dev tools preference.

While interacting with the app, updates are highlighted on the screen with colored borders. By this process, you should see components that have re-rendered. This lets us spot re-renders that were not necessary.

Let’s follow this example.

Note that when we’re entering a second todo, the first ‘todo’ also flashes on the screen on every keystroke. This means it is being re-rendered by React together with the input. This is what we are calling a “wasted” render. We know it is unnecessary because the first todo content has not changed, but React doesn’t know this.

Even though React only updates the changed DOM nodes, re-rendering still takes some time. In many cases, it’s not a problem, but if the slowdown is noticeable, we should consider a few things to stop those redundant renders.

Using shouldComponentUpdate method

By default, React will render the virtual DOM and compare the difference for every component in the tree for any change in its props or state. But that is obviously not reasonable. As our app grows, attempting to re-render and compare the entire virtual DOM at every action will eventually slow the whole thing down.

React provides a simple lifecycle method to indicate if a component needs re-rendering and that is, shouldComponentUpdate which is triggered before the re-rendering process starts. The default implementation of this function returns true

function shouldComponentUpdate(nextProps, nextSate) {
    return true;
}

When this function returns true for any component, it allows the render differentiating process to be triggered. This gives us the power of controlling the render differentiating process. Suppose we need to prevent a component from being re-rendered, we need simply to return false from that function. As we can see from the implementation of the method, we can compare the current and next props and state to determine whether a re-render is necessary:

function shouldComponentUpdate(nextProps, nextSate) {
    return nextProps.id !== this.props.id;
}

Using pure-components

As you work on React, you definitely know about React.Component but what’s the deal with React.PureComponent? We’ve already discussed shouldComponentUpdate lifecycle method, in pure components, there is already a default implementation of, shouldComponentUpdate() with a shallow prop and state comparison. So, a pure component is a component that only re-renders if props/state is different from the previous props and state.

function shouldComponentUpdate(nextProps, nextSate) {
    return shallowCompare(this.props, nextProps) 
             && shallowCompare(this.state, nextState);
}

In shallow comparison, primitive data-types like string, boolean, number are being compared by value and complex data-types like array, object, function are compared by reference

But, what if we have a functional stateless component in which we need to implement that comparison method before each re-rendering happens? React has a Higher Order Component React.memo. It is like React.PureComponent but for functional components instead of classes.

const functionalComponent = (props) => {
    /* render using props */
}

export default React.memo(functionalComponent);

By default, it does the same as shouldComponentUpdate() which only shallowly compares the props object. But, if we want to have control over that comparison? We can also provide a custom comparison function as the second argument.

const functionalComponent = (props) => {
    /* render using props */
}

const areEqual = (prevProps, nextProps) => {
    /*
    return true if passing nextProps to render would return 
    the same result as passing prevProps to render, 
    otherwise return false 
    */
}

export default React.memo(functionalComponent);

Making Data Immutable

What if we could use a React.PureComponent but still have an efficient way of telling when any complex props or states like an array, object, etc. have changed automatically? This is where the immutable data structure makes life easier.

The idea behind using immutable data structures is simple. As we’ve discussed earlier, for complex data-types the comparison performs over their reference. Whenever an object containing complex data changes, instead of making the changes in that object, we can create a copy of that object with the changes which will create a new reference.

ES6 has object spreading operator to make this happen.

const profile = { name: 'Uranium Reza', age: 27 };

const updateProfile = (profile) => {
    return { ...profile, gender: 'M' };
}

We can do the same for arrays too:

this.state = {
    languages: ['French', 'English'],
}

this.setState(state => ({
    words: [...state.languages, 'Bangla']
}));

Avoid passing a new reference for the same old data

We know that whenever the props for a component changes, a re-render happens. But sometimes the props didn’t change. We write code in a way that React thinks it did change, and that’ll also cause a re-render but this time it’s a wasted render. So, basically, we need to make sure that we’re passing a different reference as props for different data. Also, we need to avoid passing a new reference for the same data. Now, we’ll look into some cases where we’re creating this problem. Let’s look at this code.

class BookInfo extends React.Component {
    render() {
        const book = {
            name: "1984",
            author: "George Orwell",
            publishedAt: "June 8, 1949"
        };

        return (
            <div>
                <BookDescription book={book} />
                <BookReview reviews={this.props.reviews} />
            </div>
        );
    }
}

Here’s the content for the BookInfo component where we’re rendering two components, BookDescription and BookReview. This is the correct code, and it works fine but there is a problem. BookDescription will re-render whenever we get new reviews data as props. Why? As soon as the BookInfo component receives new props, the render function is called to create its element tree. The render function creates a new book constant that means a new reference is created. So, BookDescription will get this book as a news reference, that’ll cause the re-render of BookDescription. So, we can refactor this piece of code to this:

class BookInfo extends React.Component {
    book = {
        name: "1984",
        author: "George Orwell",
        publishedAt: "June 8, 1949"
    };

    render() {
        return (
            <div>
                <BookDescription book={this.book} />
                <BookReview reviews={this.props.reviews} />
            </div>
        );
    }
}

Now, the reference is always the same, this.book and a new object isn’t created at render time. This re-rendering philosophy applies to every prop including event handlers, like:

class Foo extends React.Component {
    handleClickOne() {
        console.log("Click happened in One!");
    }

    handleClickTwo() {
        console.log("Click happened in Two!");
    }

    render() {
        return (
            <React.Fragment>
                <button onClick={this.handleClickOne.bind(this)}>
                    Click me One!
                </button>
                <button onClick={this.handleClickTwo.bind(this)}>
                    Click me Two!
                </button>
            </React.Fragment>
        );
    }
}

Here, we’ve used two different ways (binding methods and using arrow function in render) to invoke the event-handler methods but both will create a new function every time the component re-renders. So, to fix these issues, we can bind the method in the constructor and using class properties which is still in experimental and not standardized yet but so many devs are already using this method of passing functions to other components in production-ready applications:

class Foo extends React.Component {
    constructor() {
        this.handleClickOne = this.handleClickOne.bind(this);
        this.handleClickTwo = this.handleClickTwobind(this);
    }
    handleClickOne() {
        console.log("Click happened in One!");
    }

    handleClickTwo() {
        console.log("Click happened in Two!");
    }

    render() {
        return (
            <React.Fragment>
                <button onClick={this.handleClickOne}>Click me One!</button>
                <button onClick={this.handleClickTwo}>Click me Two!</button>
            </React.Fragment>
        );
    }
}

Wrapping up

Internally, React uses several clever techniques to minimize the number of costly DOM operations required to update the UI. For many applications, using React will lead to a fast user interface without doing much work to optimize for performance specifically. Nevertheless, if we can follow the techniques I’ve mentioned above to resolve wasted renders then for large applications we’ll also get a very smooth experience in terms of performance.

Follow me on twitter and RT if you loved it!

Debug using git bisect

Nayeem Reza — Mon, 11 May 2020 06:57:48 +0000

What's git bisect?

I just learned about git bisect from this

Kate Efimova 💫

@kefimochi

"Git bisect" is pretty cool 🔥

Here's a quick summary, from my understanding:

Git bisect is useful when you can't easily trace a bug to a specific piece of code. It runs a binary search on all the commits between good state(no bugs) & bad state(that bug you were looking for🐞)

01:28 AM - 11 May 2020

8 74

and from the very first look of it, I was like - whooosh! It should be awesome. From the man page, it says this -

TLDR; git-bisect - Use binary search to find the commit that introduced a bug

So, that's kind of our day-to-day software engineering need, amirite? In the middle of our development of a particular feature, somehow we stumbled upon a situation where an existing code fragment is broken, but it shouldn't because we didn't touch (or actually couldn't remember) any related codes! What do we do then? I personally checkout to particular commits that I feel suspicious or check the file changes, but that's a hell lot of work to actually narrow down the bug. To automate this process, we can use git bisect.

This command uses a binary search algorithm to find which commit in our project’s history introduced a bug. First, we have to tell which one is the "bad" commit that is known to contain the bug, most of the cases that's where the HEAD is, but we can specify a commit hash also! Then, we have to mark a "good" commit where we specifically know everything was working fine. So, if you can remember the binary-search technique, we are marking the low and high indexes here! Then git bisect picks a commit between those two endpoints and asks us whether the selected commit is "good" or "bad". It continues narrowing down the range until it finds the exact commit that introduced the problem.

In fact, git bisect can be used to find the commit that changed any property of our project; e.g., the commit that fixed a bug, or the commit that caused a benchmark’s performance to improve. To support this more general usage, the terms "old" and "new" can be used in place of "good" and "bad", or we can choose our own terms.

How to use git bisect?

First, we have to start a bisect session and mark the good and bad commit hashes i.e. defining the boundary in which we'll search for the bug -

# startup git bisect
$ git bisect start

# give git a commit where there is not a bug
$ git bisect good <commit-hash>

# give git a commit where there is a bug
$ git bisect bad <commit-hash>

Bisecting: X revisions left to test after this (roughly Y steps)
[commit-hash] <commit-message>

Now, the process has been started automatically and git will start splitting the revisions in half and loading them up for us. It will checkout each revision and then ask us if the commit is good or bad. Then, we have to compile and test the code for that specific version to give a verdict to it i.e. good/bad! Our answer will be like this -

# If that version works correctly, type
$ git bisect good

# If that version is broken, type
$ git bisect bad

# Then git bisect will respond with something like
Bisecting: 12 revisions left to test after this (roughly 4 steps)

And after each prompt, it will use a binary search to very quickly narrow down the offending commit. The number of revisions we have between our “good” and “bad” commits will determine how long this process takes but it will still be quicker than individually checking out each commit. Roughly it takes log2(revisionCount) i.e. Y = log2(X)

We have to keep repeating the process: compile, test, and depending on whether it is good or bad hit git bisect good or git bisect bad to ask for the next commit that needs testing. And, eventually, there will be no more revisions left to inspect, and the command will print out a description of the first bad commit. The reference refs/bisect/bad will be left pointing at that commit.

Suppose we are trying to find the commit that broke a feature that was known to work in between these two commits 8c054db and 5908ecf. Now, after starting the git bisect session, we'll specify the good and bad commit -

$ git bisect start
$ git bisect good 5908ecf
$ git bisect bad 8c054db

And you'll see something similar to it, printed in your console -

Bisecting: 4 revisions left to test after this (roughly 2 steps)
[88f2ada15e8b2890b618e0300134deff9e4050c6] Add typography fixes

Here, I have tested my code and it's working fine; let's mark it as good -

Bisecting: 4 revisions left to test after this (roughly 2 steps)
[88f2ada15e8b2890b618e0300134deff9e4050c6] Add typography fixes
$ git bisect good

Then, it'll give us this -

Bisecting: 2 revisions left to test after this (roughly 1 step)
[aa91d493c90a854b78a02fb10b8c097f323b9d4a] 1.1.0

After testing I've found that this is not working properly; so, let's put git bisect bad. Finally, it'll print this -

aa91d493c90a854b78a02fb10b8c097f323b9d4a is the first bad commit
commit aa91d493c90a854b78a02fb10b8c097f323b9d4a
Author: uraniumreza <reza.uranium@gmail.com>
Date:   Sun May 10 19:37:40 2020 +0600

    1.1.0

 src/helper/validation.js            |   9 +++
 src/landing/components/ContactUs.js |  52 +++++++++++++---
 src/landing/service/api.js          |  12 +++
 3 files changed, 73 insertions(+), 11 deletions(-)

After finishing a bisect session i.e. you've successfully tracked down the bug, to clean up the bisection state and return to the original HEAD, we have to run the following command:

$ git bisect reset

By default, this will return our tree to the commit that was checked out before git bisect start. With an optional argument, we can return to a different commit instead:

$ git bisect reset <commit-hash>

For example, git bisect reset bisect/bad will checkout to the first bad revision, while git bisect reset HEAD will leave us to the current bisection commit and avoid switching commits at all

Can we automate the process?

That was basically a manual approach of debugging, though it helps us automating the checkout process and narrowing down the buggy commit effectively. But we can run git bisect with a script (if we have a script that can tell if the current source code is good or bad) which will automate the whole process of compiling, testing, and marking the commit as good/bad!

# git bisect run <cmd> ...
$ git bisect run node bisect/index.js

N.B. The script should exit with code 0 if the current source code is good/old, and exit with a code between 1 and 127 (inclusive), except 125, if the current source code is bad/new.

To know more about this feature please follow the reference section

Reference

https://git-scm.com/docs/git-bisect

Follow me on twitter and RT if you loved it!

DEV Community: Nayeem Reza

Best Time to Buy and Sell Stock

🔗 Problem Description:

Solution Approach

Complexity Analysis

Time Complexity O(n)

Space Complexity O(1)

Blind75: Array

Two Sum

🔗 Problem Description

Solution Approach

Complexity Analysis

Time Complexity O(n)

Space Complexity O(1)

Blind75: Introduction

How to identify and resolve wasted renders in React

How to identify and resolve wasted renders in React | by Nayeem Reza | We’ve moved to freeCodeCamp.org/news | Medium

Nayeem Reza ・ Jul 9, 2020 ・ Medium

How React works

Identify wasted renders

Using shouldComponentUpdate method

Using pure-components

Making Data Immutable

Avoid passing a new reference for the same old data

Wrapping up

Debug using git bisect

What's git bisect?

How to use git bisect?

Can we automate the process?

Reference

Time Complexity `O(n)`

Space Complexity `O(1)`

Time Complexity `O(n)`

Space Complexity `O(1)`

Nayeem Reza ・ Jul 9, 2020 ・
Medium