reactjs

Promise Async Await

react state

javascript

Avatar

CSS Flexbox

promise

HTML background

merge-rebase

web security

algorithm

security

Javascript

ReactJS

html

Van Truong

When talking about React performance, there are two major stages that we need to care about:

- __initial render__ - happens when a component first appears on the screen
- __re-render__ - second and any consecutive render of a component that is already on the screen

> __*Every re-render in React starts with a state change.*__ __It's the only “trigger” in React for a component to re-render.__

Now, that probably doesn't sound right... after all, don't components re-render when their props change? What about context??

Here's the thing: *when a component re-renders, it also re-renders all of its descendants*.

- __*Big Misconception #1*__: The entire app re-renders whenever a state variable changes.

In fact, re-renders only affect the component that `owns the state + its descendants` (if any). React's `main job` is to keep the application UI in sync with the React state. The point of a re-render is to figure out __what needs to change__.

- __*Big Misconception #2*__: A component will re-render because its props change.

When a component re-renders, it tries to re-render all descendants, *regardless of whether they're being passed a particular state variable through props or not.*. __It's not about the props__

A sneakier version of this problem has to do with refs. If we pass a ref as a prop, `React` won't be able to tell whether or not we've mutated it since the last render. And so it chooses to re-render, to be on the safe side.

You might be familiar with `React.memo`, or the `React.PureComponent` class component. These two tools allow us to __ignore certain re-render requests.__

```js
function Decoration() {
  return <div className="decoration">⛵️</div>;
}
export default React.memo(Decoration);
```

By wrapping our Decoration component with `React.memo`, we're telling React *Hey, I know that this component is pure. You don't need to re-render it __unless its props change.__* Only when memoization techniques are used (`React.memo`, `useMemo`), then props change becomes important.

## When React component re-renders itself?

There are four reasons why a component would re-render itself: __*state changes*__, __*context changes*__, __*hooks changes*__ and *__parent re-renders__*. There is also a big myth: that re-renders happen when the component’s props change. By itself, it’s not true.

### 🧐 Re-renders reason: context changes

When the value in Context Provider changes, __*all components that use this Context will re-render*__, even if they don’t use the changed portion of the data directly. Those re-renders __can not be__ prevented with memoization directly, but there are a few workarounds that can simulate it.
![context changes](https://www.developerway.com/assets/react-re-renders-guide/part2-context-example.png)

### 🧐 Re-renders reason: hooks changes

Everything that is happening inside a hook “belongs” to the component that uses it. The same rules regarding Context and State changes apply here:

- state change inside the hook will trigger an __unpreventable__ re-rerender of the “host” component
- if the hook uses Context and Context’s value changes, it will trigger an __unpreventable__ re-rerender of the “host” component

### 🧐 Re-renders reason: parent re-renders

A component will re-render itself if its parent re-renders. Or, if we look at this from the opposite direction: *when a component re-renders, it also re-renders all its children*.

![dd](https://www.developerway.com/assets/react-re-renders-guide/part2-parent-example.png)

## Preventing re-renders with composition

### ⛔️ Antipattern: Creating components in render function

more info [here](https://www.developerway.com/posts/react-re-renders-guide#part3.1)

### ✅ Preventing re-renders with composition: moving state down

![Move state down](https://www.developerway.com/assets/react-re-renders-guide/part3-moving-state-down.png)

### ✅ Preventing re-renders with React.memo
Wrapping a component in React.memo will stop the downstream chain of re-renders that is triggered somewhere up the render tree, unless this component’s props have changed.

This can be useful when rendering a heavy component that is not dependent on the source of re-renders (i.e. state, changed data).
![React memo](https://www.developerway.com/assets/react-re-renders-guide/part4-memo-normal-example.png)

__All props__ that are not primitive values have to be memoized for React.memo to work

![memo non primitive props value](https://www.developerway.com/assets/react-re-renders-guide/part4-memo-with-props.png)

### ✅ Necessary useMemo/useCallback

- If a child component is wrapped in `React.memo`, all props that are not primitive values have to be memoized
- If a component uses non-primitive value as a dependency in hooks like `useEffect`, `useMemo`, `useCallback`, it should be memoized.

![necessary useMemo deps](https://www.developerway.com/assets/react-re-renders-guide/part5-necessary-usememo-dep.png)

### ✅ useMemo for expensive calculations

> One of the use cases for useMemo is to avoid expensive calculations on every re-render.

useMemo has its cost (consumes a bit of memory and makes initial render slightly slower), so it should not be used for every calculation. In React, mounting and updating components will be the most expensive calculation in most cases (unless you’re actually calculating prime numbers, which you shouldn’t do on the frontend anyway).

As a result, the typical use case for useMemo would be to memoize React elements. Usually parts of an existing render tree or results of generated render tree, like a map function that returns new elements.

### ✅ Improving re-render performance of lists

In addition to the regular re-renders rules and patterns, the key attribute can affect the performance of lists in React.

Value in key should be a string, that is consistent between re-renders for every element in the list. Typically, item’s id or array’s index is used for that.

It is okay to use array’s index as key, if the list is static, i.e. elements are not added/removed/inserted/re-ordered.

Using array’s index on dynamic lists can lead to:

- bugs if items have state or any uncontrolled elements (like form inputs)
- degraded performance if items are wrapped in React.memo

### ✅ Preventing Context re-renders: memoizing Provider value

If Context Provider is placed not at the very root of the app, and there is a possibility it can re-render itself because of changes in its ancestors, its value should be memoized.
![](https://www.developerway.com/assets/react-re-renders-guide/part7-context-provider-memo.png)

### ✅ Preventing Context re-renders: splitting data and API

If in Context there is a combination of data and API (getters and setters) they can be split into different Providers under the same component. That way, components that use API only won’t re-render when the data changes.

![split data & api context](https://www.developerway.com/assets/react-re-renders-guide/part7-context-split-api.png)

### ✅ Preventing Context re-renders: splitting data into chunks

If Context manages a few independent data chunks, they can be split into smaller providers under the same provider. That way, only consumers of changed chunk will re-render.

![split data into chunks](https://www.developerway.com/assets/react-re-renders-guide/part7-context-split-data.png)

### References
- [Why React Re-Renders](https://www.joshwcomeau.com/react/why-react-re-renders/)
- [React re-renders guide: everything, all at once](https://www.developerway.com/posts/react-re-renders-guide)


Understand how React work under the hood and its fundamental knowledges.

All about React Re-render

## TL;DR
- They both use to merge contents of one branch to another, the different mainly come from Git History of each approach
- If you have any doubt, just use `git merge`

## Details

We will go through this example to explain the different between `merge` and `rebase`

![start](https://raw.githubusercontent.com/xuanthulabnet/learn-git/master/docs/git010.png)

### Git merge

When we want to merge commits inside `beta` into `master`, we will run these commands:

```
git checkout master
git merge beta
```

Here is the result of git history:
- The commits will be merge in chronological order and `an extra merge commit` will be added

![merge](https://raw.githubusercontent.com/xuanthulabnet/learn-git/master/docs/git011.png)

### Git rebase

`Git rebase` also merge commits from other branch into the current branch, but it will find the last common commit between 2 branches, then change base branch and gradually create new commits to adapt with new base.

In case, we run the command `git rebase beta` from master branch
- Git will change the base to `beta` branch, then move new commits on master (D1, D2) to new base. This process may have code conflict, therefore the commit will not exactly same with D1, D2 anymore, that's why it is `D1'`, and `D2'`
- No new commit added (unlike `git merge`)

![rebase](https://raw.githubusercontent.com/xuanthulabnet/learn-git/master/docs/git012.png)

Tips to reduce merge conflicts when using `rebase`:
- `Rebase` often, recommend doing it at least once a day.
- Try to squash changes on the same line into one commit as much as possible.

## Conclusion

In general, The only differences between a `rebase` and a `merge` are:

- The resulting tree structure of the history
- Merge will generally create an extra commit
- Merge and rebase will handle conflicts differently. `Rebase will present conflicts one commit at a time` where `merge will present them all at once`.

So the short answer is to pick rebase or merge based on what you want your history to look like.

## Reference

- [xuanthulab.net](https://xuanthulab.net/lenh-git-merge-va-rebase-gop-va-viet-lai-lich-su-commit.html)

Git merge vs Git rebase

This post mainly wrap up the information about CSS Flex, more detail tutorial you can find here:
- [W3School](https://www.w3schools.com/css/css3_flexbox.asp)
- [CSS-trick](https://css-tricks.com/snippets/css/a-guide-to-flexbox/)

![Flexbox Cheat Sheet](https://res.cloudinary.com/practicaldev/image/fetch/s--wZRwgDoY--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://github.com/simonpaix/images/blob/main/blog/Flexbox_CheatSheet_LearnPine.png%3Fraw%3Dtrue)

First thing to remember:

- main-axis: the flex direction (default: row)
- cross-axis: opposite of main-axis (default: column)

**Parent properties:**
- `display`: flex
- `flex-direction` : set the main axis
- `flex-wrap` allows the items to wrap as needed
- `justify-content`: defines alignment along the main axis
    - Possible values: `flex-start`, `flex-end`, `center`, `space-between`, `space-around`, `space-evenly`
- `align-items`: defines alignment along the cross axis
    - Possible values: `flex-start`, `flex-end`, `center`, `stretch`, `baseline`
- `align-content` aligns when having multiple lines, like `justify-content` does with individual items. When there is only one line, `align-content` has no effect. **Use with `flex-wrap: wrap`**

**Children properties:**
- `align-self` override default alignment (or the one specified by align-items) for a specific item
    - possible values: `flex-start`, `flex-end`, `center`, `flex-end`, `baseline`, `stretch`
- `order` changes the order of flex items (default: 0)
- `flex-growth` allows item to grow using remaining space (default: 0)
    - If all items have flex-grow: 1, the remaining space is distributed equally
- `flex-shrink`  defines the ability for a flex item to shrink (default: 1)
    - The higher value, the more it shrink compared to siblings
- `flex-basis` sets the default size of a flex item, it accepts:
    - specific values: pixels, rm, %, auto
    - content: automatic sizing, based on its content
    - global values: inherit, initial, unset
- `flex`: define the size of of children
    - `flex-growth` default: 0
    - `flex-shrink`: default: 1
    - `flex-basis`: default: auto
    - `flex: 1` -> all equal, or `width: 100%` or `flex-basis: 100%`

# Practices

**Flexbox design patterns:**

- Columns with same width for all:

```css
.parent {
  display: flex;

  .children {
    flex-basis: 100%;
    /* flex: 1 */
  }
}
```

- **Grid-ish**: use all available spaces, if not wrap and move on

```css
.parent {
  display: flex;
  flex-wrap: wrap;

  .children {
    flex: 1 1 30%;
  }
}
```

- **Content and sidebar**

```css
.parent {
  display: flex;
  flex-wrap: wrap;

  .children1 {
    flex: 1 1 70%;
    min-width: sth;
  }

  .children2 {
    flex: 1 1 30%;
    min-width: sth;
  }
}
```

- **Another example**

![CSS flex design example](//images.ctfassets.net/tk7dn5bsmtgs/2e4sdCM3NzSShM1JOa090C/af387d91ea75f1c00696eef6191d942c/Untitled.png)

    - The container is set using Flexbox
    - We want the value of dropdown take up all remaining space ⇒ `flex-grow: 1`
    - We want the vertical divider to take up full height ⇒ `align-self: stretch`


Summarize the most important attributes of CSS Flexbox and common practices

About CSS Flexbox

Probably you've worked with React state for countless time, but do you know how everything work under the hood ? This post with help you understand it better and I'm confident that this topic is really useful.

So, what and why state in React ?

## State: A Component's Memory

Here is the the problems with normal local variables in React app:

- **Local variables don’t persist between renders.** When React renders this component a second time, it renders it from scratch—it doesn’t consider any changes to the local variables.
- **Changes to local variables won’t trigger renders.** React doesn’t realize it needs to render the component again with the new data.

Components often need to change what’s on the screen as a result of an interaction. Typing into the form should update the input field, clicking `next` on an image carousel should change which image is displayed, clicking “buy” should put a product in the shopping cart. Components need to `remember` things: the current input value, the current image, the shopping cart. In React, this kind of component-specific memory is called state.

To update a component with new data, two things need to happen:

- __Retain the data between renders.__
- __Trigger React to render the component with new data (`re-rendering`).__

The `useState` Hook provides those two things:

- A state variable to retain the data between renders.
- A state setter function to update the variable and *trigger React to render the component again.*

### How does React know which state to return? 

You might have noticed that the `useState` call does not receive any information about which state variable it refers to. There is no "identifier" that is passed to useState, so how does it know which of the state variables to return? Does it rely on some magic like parsing your functions? The answer is no.

Instead, to enable their concise syntax, Hooks rely on a __*stable call order*__ on every render of the same component. This works well in practice because if you follow the rule `only call Hooks at the top level`, Hooks will always be called in the __same order__.

Here is the simple version of how react state is implemented, the general idea is that all states are saved inside `compoentHooks`, and we use `currentHookIndex` to track which value should be created or returned
- If `currentHookIndex` have value ⇒ return it, increase `currentHookIndex`.
- If not, create that `[value, setValue]` pair and save to array, increase `currentHookIndex`.

```js
let componentHooks = [];
let currentHookIndex = 0;

// How useState works inside React (simplified).
function useState(initialState) {
  let pair = componentHooks[currentHookIndex];
  if (pair) {
    // This is not the first render,
    // so the state pair already exists.
    // Return it and prepare for next Hook call.
    currentHookIndex++;
    return pair;
  }

  // This is the first time we're rendering,
  // so create a state pair and store it.
  pair = [initialState, setState];

  function setState(nextState) {
    // When the user requests a state change,
    // put the new value into the pair.
    pair[0] = nextState;
    updateDOM(); // Trigger UI update
  }

  // Store the pair for future renders
  // and prepare for the next Hook call.
  componentHooks[currentHookIndex] = pair;
  currentHookIndex++;
  return pair;
}
```

__*What can be deducted from the above implementation is:*__

- __States__ is the data stored here lives one level outside of the component being rendered. This state __is not shared with other components__ but it is `maintained in a scope that is accessible to subsequent rendering of the specific component`.

## State as a Snapshot

__Setting state only changes it for the next render__. During the first render, number was 0. This is why, in that render’s onClick handler, the value of number is still 0 even after `setNumber(number + 1)` was called:

```js
<button onClick={() => {
  setNumber(number + 1);
  setNumber(number + 1);
  setNumber(number + 1);
}}>+3</button>
```

After set state value for three time, in the next render the value of score still just `1` since the value of score is not update immediately.

Here is what this button’s click handler tells React to do:

- `setNumber(number + 1)`: number is `0` so `setNumber(0 + 1)`.
  - React prepares to change number to 1 on the next render.
- `setNumber(number + 1)`: number is `0` so `setNumber(0 + 1)`.
  - React prepares to change number to 1 on the next render.
- `setNumber(number + 1)`: number is `0` so `setNumber(0 + 1)`.
  - React prepares to change number to 1 on the next render.

Even though you called `setNumber(number + 1)` three times, in this render’s event handler number is always `0`, so you set the state to 1 three times. This is why, after your event handler finishes, React re-renders the component with number equal to 1 rather than 3.

__React keeps the state values `fixed` within one render’s event handlers__. You don’t need to worry whether the state has changed while the code is running.

But what if you wanted to read the latest state before a re-render? You’ll want to use a [state updater function](https://beta.reactjs.org/learn/queueing-a-series-of-state-updates)

You can fix this to actually increase score by 3 by passing an __updater function__  when setting state. Notice how replacing `setScore(score + 1)` with `setScore(s => s + 1)` fixes the “+3” button.

> `setState` do not effect immediately, the updated value only available in the next render
If we use state value, it is still snapshot value because **React keeps the state values “fixed” within one render’s event handlers**

## Queueing a Series of State Updates

Setting a state variable will queue another render. But sometimes you might want to perform multiple operations on the value before queueing the next render

**React waits until *all* code in the event handlers has run before processing your state updates.**
 This is why the re-render only happens *after* all these `setNumber()` calls.

In case, we pass an updater function, it will be added to the queue, 

```js
setNumber(n ⇒ n + 1);
setNumber(n ⇒ n + 1);
setNumber(n ⇒ n + 1);
```

Here, `n ⇒ n + 1` is called an **updater function.** When you pass it to a state setter:

1. React queues this function to be processed after all the other code in the event handler has run.
2. During the next render, React goes through the queue and gives you the final updated state.

Here’s how React works through these lines of code while executing the event handler:

1. `setNumber(n ⇒ n + 1)`: `n ⇒ n + 1` is a function. React adds it to a queue.
2. `setNumber(n ⇒ n + 1)`: `n ⇒ n + 1` is a function. React adds it to a queue.
3. `setNumber(n ⇒ n + 1)`: `n ⇒ n + 1` is a function. React adds it to a queue.

When you call `useState` during the next render, React goes through the queue. The previous `number` state was `0`, so that’s what React passes to the first updater function as the `n` argument. Then React takes the return value of your previous updater function and passes it to the next updater as `n`, and so on:

| queued update | n | returns |
| --- | --- | --- |
| n => n + 1 | 0 | 0 + 1 = 1 |
| n => n + 1 | 1 | 1 + 1 = 2 |
| n => n + 1 | 2 | 2 + 1 = 3 |

React stores `3` as the final result and returns it from `useState`.

### What happens if you update state after replacing it ?

what is the value of Number, if its initial value is 0 ⇒ answer is 6

```js
<button onClick={() => {
  setNumber(number + 5);
  setNumber(n ⇒ n + 1);
}}>
```

Here’s what this event handler tells React to do:

1. `setNumber(number + 5)`: `number` is `0`, so `setNumber(0 + 5)`. React adds *“replace with `5`”* to its queue.
2. `setNumber(n => n + 1)`: `n => n + 1` is an updater function. React adds *that function* to its queue.

During the next render, React goes through the state queue:

| queued update | n | returns |
| --- | --- | --- |
| “replace with 5” | 0 (unused) | 5 |
| n => n + 1 | 5 | 5 + 1 = 6 |

React stores `6` as the final result and returns it from `useState`.

### What happens if you replace state after updating it

```js
<button onClick={() => {
  setNumber(number + 5);
  setNumber(n ⇒ n + 1);
  setNumber(42);
}}>
```

Here’s how React works through these lines of code while executing this event handler:

1. `setNumber(number + 5)`: `number` is `0`, so `setNumber(0 + 5)`. React adds *“replace with `5`”* to its queue.
2. `setNumber(n ⇒ n + 1)`: `n ⇒ n + 1` is an updater function. React adds *that function* to its queue.
3. `setNumber(42)`: React adds *“replace with `42`”* to its queue.

During the next render, React goes through the state queue:

| queued update | n | returns |
| --- | --- | --- |
| “replace with 5” | 0 (unused) | 5 |
| n ⇒ n + 1 | 5 | 5 + 1 = 6 |
| “replace with 42” | 6 (unused) | 42 |

Then React stores `42` as the final result and returns it from `useState`.

To summarize, here’s how you can think of what you’re passing to the `setNumber` state setter:

- **An updater function** (e.g. `n ⇒ n + 1`) gets added to the queue.
- **Any other value** (e.g. number `5`) adds “replace with `5`” to the queue, **ignoring what’s already queued.**
- ⇒ way to remember: `function` added to queue, `value` added only the ***last*** value

```jsx
setNumber(number + 3);
setNumber(number + 2);
setNumber(number + 444); // save number + 444 only, with old data
```

Here is the simple version of how React handle the queue when re-render

```jsx
export function getFinalState(baseState, queue) {
  let finalState = baseState;
  for(const step of queue) {
    if(typeof step === 'function') {
      finalState = step(finalState);
    } else {
      finalState = step;
    }
  }
  return finalState;
}
```

After the event handler completes, React will trigger a re-render. During the re-render, React will process the queue. Updater functions run during rendering, so **updater functions must be [pure](https://beta.reactjs.org/learn/keeping-components-pure)** and only *return* the result. Don’t try to set state from inside of them or run other side effects. 

***In Strict Mode, React will run each updater function twice (but discard the second result) to help you find mistakes.***

- READ the challenges here: • **[Challenges](https://beta.reactjs.org/learn/queueing-a-series-of-state-updates#challenges)**

## Recap

- Setting state does not change the variable in the existing render, but it requests a new render.
- React processes state updates after event handlers have finished running. This is called batching.
- ***To update some state multiple times in one event***, you can use `setNumber(n => n + 1)` updater function.

## Reference
- [React official document](https://beta.reactjs.org/learn/state-a-components-memory)
- [Medium - React hooks: not magic, just arrays](https://medium.com/@ryardley/react-hooks-not-magic-just-arrays-cd4f1857236e)
- [Queueing a Series of State Updates](https://beta.reactjs.org/learn/queueing-a-series-of-state-updates)

You have worked with React state for countless time, but do you understand everything about state in React and how it was implemented under the hood ? This post will wrap up the information you should know about React state.

Deeply understand React state

## Array

### Prefix Sum

__Problem:__ Calculate value from `i`, to `j` of an array A with *many random queries* (10^6 queries)

__Solution__ main idea is we cache all prefix sums to avoid recalculation if not needed

```py
prefix[i] = A[0] + A[1] + ... + A[i]
query(i, j) = prefix[j] - prefix[i-1] 
```

### Prefix Sum on Matrix

__Problem__: Given a matrix A of size nxm. `int sumRegion(int row1, int col1, int row2, int col2)` returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). (*there are a lot of queries*)

__Solution__

```py
Sum(i,j) = sum all number in rectangle (0,0,i,j)
Query(u,v,i,j) = Sum(i,j) - Sum(u-1,j) - Sum(u, j-1) + Sum(u-1,v-1)
Sum[i][j] = Sum[i-1][j] + Sum[i][j-1] - Sum[i-1][j-1] + A[i][j]
```

### Prefix XOR

__Problem__: You are given an array A of positive integers. You are also given the array queries where queries[i] = [lefti, righti]. For each query i compute the XOR of elements from left to right (that is, `arr[left] XOR arr[left + 1] XOR ... XOR arr[right]` ).

```py
query(left, right) = prefixXOR[right] *__XOR__* prefixXOR[left-1] 
```

### Dutch flag partition

__Problem__: Given an array `A` and an index `i`, rearranges the elements of A such that all elements less than `A[i]` appear first, followed by elements equal to `A[i]`, followed by elements greater than `A[i]`.

__Example:__ 

```py
A = [5, 2, 1, 4, 4, 6, 7], i = 3 
result A = [2, 1, 4, 4, 5, 6, 7]
# A = [1, 2, 4, 4, 7, 6, 5] is also a valid result
```
__Solution__

```py
pivot = A[i];
boundary = 0;
for(int i = 0; i < n; i++) {
    if A[i] < pivot: swap(A[i], A[boundary])
    boundary += 1;
}
```

Similarly, move all larger elements to the end

```
boundary = n-1;
for(int i = n-1; i >= 0; i--) {
     if A[i] > pivot: swap(A[i], A[boundary])
     boundary--;
}
```

## Bit Manipulation

```py
# get bit at a specific position
# position is counted from right to left, start from 0.

def get_bit(x, position) = (x >> position) & 1

def set_bit(x, position):
    mask = (1 << position)
    return x | mask

def flip_bit(x, position):
    mask = (1<<position)
    return x ^ mask

# Turn off the right-most bit
x & (x-1)

# Check if power of 2:
x & (x-1) == 0
```

## Merge Sort and Quick Sort

- Merge Sort
  - Time complexity: `O(nlogn)`
  - Space complexity: `O(n) + O(logn) = O(n)`

```js
function merge(left, right) {
  const sortedArr = []
  let i = 0, j = 0;

  while(i < left.length && j < right.length) {
    if(left[i] <= right[j]) {
      sortedArr.push(left[i]);
      i++;
    } else {
      sortedArr.push(right[j])
      j++;
    }
  }

  while(i < left.length) {
    sortedArr.push(left[i]);
    i++;
  }

  while(j < right.length) {
    sortedArr.push(right[j]);
    j++;
  }

  return sortedArr;
}

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

console.log(mergeSort([5, 4, 3, 2, 1]));
```

- Quick Sort
  - Time complexity:
    - Average: `O(nlogn)`
    - Worst case: `O(n) + O(n-1) + O(n-2) + ... + 1 = O(N^2)`
  - Space complexity: `O(logn)`

```js
function quickSort(arr, left = 0, right = arr.length - 1) {
  if(left > right) return;

  const p = partition(arr, left, right);
  quickSort(arr, left, p - 1);
  quickSort(arr, p + 1, right);
}

function partition(arr, left, right) {
  let boundary = left;
  const pivot = arr[right];

  for (let i = left; i < right; i++) {
    if (arr[i] < pivot) {
      [arr[i], arr[boundary]] = [arr[boundary], arr[i]];
      boundary++;
    }
  }
  [arr[boundary], arr[right]] = [arr[right], arr[boundary]]
  return boundary;
}

const arr = [5, 4, 3, 2, 1];
quickSort(arr);
console.log(arr);
```

- __Quick Sort vs Merge Sort__
  - Merge Sort is a stable algorithm (O(nlogn) all the time)
  - Quick Sort is unstable algorithm (O(nlogn) => O(n^2) worst case)
  - Quick Sort only work well on random access collection (array). So   - when sorting linked list, doubly linked list => use Merge Sort
  - when sorting a linked list using Quick Sort: choosing random pivot is very slow as we do not have random access

## Quick Select

Find the K-th smallest in an unsorted list (k)
Find the K-th largest in an unsorted list (n-k)

We can use Quick Sort idea: First set K = K - 1. Kth smallest number will be at (K-1) index in sorted array.

Choose a pivot (randomly) and apply Dutch partition => after this, we know the index of pivot. 
  - if the index of the pivot == K, we found the K-th smallest element, just return it 
  - if the index of the pivot < K, recurs for the right part 
  - if the index of the pivot > K, recurs for the left part

```cpp
int qselect(vector a, int l, int r, int k) { 
int pivotIndex = partition(a, l, r); 
if (pivotIndex == k) return a[pivotIndex]; 
if (pivotIndex > k) { 
  return qselect(a, l, pivotIndex - 1, k); 
} 
return qselect(a, pivotIndex + 1, r, k); 
}
```

Complexity:
- Average case: `O(n)`
- Worst case: `O(n) + O(n-1) + O(n-2) + … + O(1) = O(n^2)` 
- Best case: `O(n) + O(n/2) + O(n/4) + … + O(1) = O(n * (1+½+¼+⅛+...)) ~= O(n)`

## Counting Sort

Can be applied to integer array only
- Step 1: Generate the hash map that count the frequency of each element
- Step 2:

```
for value = minValue to maxValue: 
     for i = 0 to count[value]-1: 
          result.push(value)
```

__Runtime__: O(n+ maxValue - minValue + 1) 
__Space__: O(n)
> Counting sort is a sort algorithm that does not require comparison between input element. Others: Radix Sort, Bucket Sort.

__Application:__
- when to use: range is small enough. e.g 0 <= a[i] <= 10000 => O(n+10000) << O(nlogn).
- when cannot use:
  - a[i] is too big ( -10^9 <= a[i] <= 10^9)
  - a[i] is not integer (double, object)

## Sliding window min/max problems

__Problems__: Given array A, find maximum of each sliding window with size = 3; [Leetcode link](https://leetcode.com/problems/sliding-window-maximum/)

__Idea__: Using dequeue (contain indexes)
- for left to right:
  - Remove all unqualified candidate from dequeue (< current)
  - dequeue.push(current)
  - If dequeue.front() out of range => dequeue.shift()
  - If start counting => ans.push(dequeue.front())

```js
// Solution for https://leetcode.com/problems/sliding-window-maximum/

const front = (dequeue) => dequeue[0];
const back = (dequeue) => dequeue[dequeue.length - 1];

var maxSlidingWindow = function (nums, k) {
    const ans = [], dequeue = [];
    for (let i = 0; i < nums.length; i++) {
        while (dequeue.length && nums[i] > nums[back(dequeue)]) {
            dequeue.pop();
        }
        dequeue.push(i);

        if (front(dequeue) < i - k + 1) dequeue.shift();
        if (k <= i + 1) ans.push(nums[front(dequeue)]);
    }
    return ans;
};
```

## Graph - Binary Tree

### DFS

```
function dfs(s) {
  visited[s] = true;
  for (const v of adjList[s]) {
    if (!visited[v]) {
      dfs(v)
    }
  }
}
```

### Common pattern: DFS of Binary Tree with Dynamic Programming

> The basic idea is to use result of `subproblem on child node` to calculate the result of problem on `parent node`.

Examples:
- [https://leetcode.com/problems/maximum-depth-of-binary-tree/](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
- [https://leetcode.com/problems/most-frequent-subtree-sum/](https://leetcode.com/problems/most-frequent-subtree-sum/)
- [https://leetcode.com/problems/diameter-of-binary-tree/](https://leetcode.com/problems/diameter-of-binary-tree/)

### BFS

We will need these variables: `visited` to indicate node was visited or not, `dis` (optional) distance from root node, `path` (optional) store path from root to specific node. Here is the BFS algorithm:

```js
const MAX = 100
const visited = Array(MAX).fill(false);
const dis = Array(MAX).fill(0);
const path = Array(MAX).fill(-1);

function BFS(s):
  const queue = [];
  visited[s] = true;
  queue.push(s);

  while(queue.length > 0) {
    const u = queue.shift();
    for (const v of graph[u]){
      if(!visited[v]) {
        visited[v] = true;
        dis[v] = dis[u] + 1;
        path[v] = u;
        queue.push(v);
      }
    }   
```

### BFS by level on tree

Customize original BFS a bit to print all nodes by level

```js
// General idea: push into queue level by level, each time get `currentSize` values to push into `currentLevel`

const queue = [];
queue.push(root);
const ans = [];

while(queue.length > 0) {
  const currentLevel = [];
  const currentSize = queue.length;

  for(let i = 0; i < currentSize; i++) {
    const u = queue.shift();
    currentLevel.push(u);
    for (const v of graph[u]) {
      queue.push(v);
    }
  }

  ans.push(currentLevel);
}
```

## Binary Search

```js
let left, right = 0, arr.length - 1;

while(left <= right) {
  const mid = left + Math.floor((right - left) / 2);

  if(arr[mid] == target) return mid;
  else if (arr[mid] > target) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }
}
```

Let try with this problem: [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/) 

> Find a target number in a Rotated Sorted Array

![find target in rotated sorted array](//images.ctfassets.net/tk7dn5bsmtgs/6TL3jxaDTU3a1z9kZlsFdY/f1cee3d11e0675a7d4ed3d6b7116f67d/Screen_Shot_2022-08-14_at_16.16.55.png)

```js
var search = function(nums, target) {
    let left = 0, right = nums.length - 1;

    while(right >= left) {
        const mid = left + Math.floor((right - left) / 2);
        if(nums[mid] === target) return mid;

        if(nums[mid] >= nums[left]) {
            if(target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;   
        } else {
            if(target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
};
```

__*Variants:*__

- [Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)
- [Search Insert Position](https://leetcode.com/problems/search-insert-position/)

### Minimax / Maxmini Problems

__*Pattern:*__
- When got a problem about finding the `minimum value` of a `max function` ⇒ can think about Binary search
- When got a problem about finding the `maximum value` of a `min function` ⇒ can think about Binary search

__*Variants:*__
- [Path with maximum minimum value](https://leetcode.com/problems/path-with-maximum-minimum-value/)

## Two Pointers

### Sliding window

> __Pattern:__ if `[u,v]` doesn't meet the requirements, then the parent of `[u, v]` doesn't also.

__So the general algorithm will be:__

- __Step 1__: Initially l = r = 0

- __Step 2__: Try to extend r as far as possible such that subarray `[l,r]` fulfills the requirement X.

- __Step 3__: When r reaches the point where subarray `[l,r]` doesn't meet requirement X anymore, we stop and increase `l=l+1`. 

Then we repeat __Step 2__ until r reach the end of input array. The time complexity is `O(N)` since the `r` pointer only loop through the array once.

For example, [Max Consecutive Ones III](https://leetcode.com/problems/max-consecutive-ones-iii/)

> Given a binary array `nums` and an integer `k`, return the maximum number of consecutive `1`'s in the array if you can flip at most k `0`'s.

```js
var longestOnes = function(nums, k) {
    const N = nums.length;
    let left = 0, right = 0, ans = 0;
    let zeroCount = nums[0] == 1 ? 0 : 1;

    while(right < N) {
        if(zeroCount <= k) {
            ans = Math.max(ans, right - left + 1);
            right += 1;
            if(right < N) {
                zeroCount += nums[right] === 0 ? 1 : 0;
            }
        } else {
            zeroCount -= nums[left] === 0 ? 1 : 0;
            left += 1;
        }
    }

    return ans;
};
```

__Other examples__:

- [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
- [Longest Substring with at most K distinct characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/)

## Heap (TODO)

- Build heap from Array: `O(NlogN)`
- Find min/max: `O(1)`
- Insert/Delete: `O(logN)`

## Dijkstra

Shortest path in unweighted graph ⇒ `BFS` ⇒ `O(n+m)`, n nodes, m edges

__Problem__: given a weighted graph of non-negative weight, and a source node `s`, find shortest path from `s` to all other nodes.

```js
class Node {
  constructor(id, dist) {
    self.dist = dist;
    self.id = id;
  }
}

// n: nodes
// m: edges
// Time complexity: O(mlogn)

function dijkstra(s) {
  const pq = new MinPriorityQueue({ priority: node => node.dist });
  pq.enqueue(new Node(s, 0));
  dist[s] = 0;

  while(!pq.isEmpty()) {
    const top = pq.dequeue();
    const u = top.id, w = top.dist;

    for(const neighbor of adjList[u]) {
      if(w + neighbor.dist < dist[neighbor.id]) {
        dist[neighbor.id] = w + neighbor.dist;
        pq.enqueue(new Node(neighbor.id, dist[neighbor.id]));
      }
    }
  }
}
```

__*Problems*__

- [Path with Maximum Probability](https://leetcode.com/problems/path-with-maximum-probability/)

## Union Find

A data structure supports following operations:
- __Union__(u, v): given 2 stones u and v. If u and v are not in same set, merge them into 1 set. `O(logn)`
- __Find__(x): find the set that contains stone x `O(logn)`

```js
const MAX = 20;
const parent = [];
const ranks = [];

function makeSet() {
  for (let x = 0; i < MAX + 5; i++) {
    parent.push(x);
  }
  ranks = new Array(MAX + 5).fill(0);
}

function findSet(u) {
  if (parent[u] != u) {
    parent[u] = findSet(parent[u]);
  }

  return parent[u];
}

function unionSet(u, v) {
  const up = findSet(u);
  const vp = findSet(v);

  if (up == vp) return;
  if (ranks[up] > ranks[vp]) {
    parent[vp] = up;
  } else if (ranks[up] < ranks[vp]) {
    parent[up] = vp;
  } else {
    parent[up] = vp;
    ranks[vp] += 1;
  }
}
```


Common Algorithm Interview Patterns

## Promise

A `Promise` is a proxy for a value __not necessarily known__ when the promise is created. It allows you to associate handlers with an asynchronous action's eventual success value or failure reason. This lets asynchronous methods return values like synchronous methods: `instead of immediately returning the final value, the asynchronous method returns a promise to supply the value at some point in the future`.

A Promise is in one of these states:

- `pending`: initial state, neither fulfilled nor rejected.
- `fulfilled`: meaning that the operation was completed successfully.
- `rejected`: meaning that the operation failed.

A promise is said to be __*settled*__ if it is either `fulfilled` or `rejected`, but not pending.

## Static methods

### Promise.all(iterable)

Wait for __all promises to be fulfilled__, or for __any to be rejected__.

If the returned promise fulfills, it is fulfilled with an aggregating array of the values from the fulfilled promises, in the same order as defined in the iterable of multiple promises.

If it rejects, *it is rejected with the reason from the first promise in the iterable that was rejected.*

### Promise.allSettled(iterable)

Wait until __all promises have settled__ (each may `fulfill` or `reject`).

Returns a Promise that __always fulfills__ after all of the given promises is either fulfilled or rejected, with an array of objects that each describe the outcome of each promise.

`Promise.all()` will return array of resolve values only, while `Promise.allSettled()` return array of result that have detail value result of each promise (`value`, `status`, `reason`)

For example, `Promise.allSettled([Promise.reject(1),Promise.resolve(2)]).then(console.log);` will fulfills with value

```json
[
  { "status": "rejected", "reason": 1  },
  { "status": "fulfilled", "value": 2  },
]
```

### Promise.any(iterable)

Takes an iterable of Promise objects and, __as soon as one of the promises in the iterable fulfills__, returns a single promise that fulfills with the value from that promise. If no promises in the iterable fulfill (if all of the given promises are rejected), then the returned promise is `rejected` with an `AggregateError`

### Promise.race(iterable)

__Wait until any of the promises is fulfilled or rejected.__

If the returned promise fulfills, it is fulfilled with the value of the first promise in the iterable that fulfilled.

If it rejects, it is rejected with the reason from the first promise that was rejected.

### Promise.reject(reason)
Returns a new Promise object that is rejected with the given reason.

Returns a new `Promise` object that is resolved with the given value. If the value is a thenable (i.e. has a then method), the returned promise will "follow" that thenable, adopting its eventual state; otherwise, the returned promise will be fulfilled with the value.

*Generally, if you don't know if a value is a promise or not*, `Promise.resolve(value)` it instead and work with the return value as a promise.

### Promise.resolve(value)

## Instance methods

- __*Promise.prototype.then()*__
  - The `then()` method returns a `Promise`. It takes up to two arguments: callback functions for the success and failure cases of the Promise.
  - The behavior of the handler function follows a specific set of rules. If a handler function:
    - returns a value, the promise returned by then gets resolved with the returned value as its value.
    - doesn't return anything, the promise returned by then gets resolved with an `undefined` value.
    - throws an error, the promise returned by then gets rejected with the thrown error as its value.
    - returns an already fulfilled promise, the promise returned by then gets fulfilled with that promise's value as its value.
    - returns an already rejected promise, the promise returned by then gets rejected with that promise's value as its value.
    - returns another __pending__ promise object, the resolution/rejection of the promise returned by then will be subsequent to the resolution/rejection of the promise returned by the handler. Also, *the resolved value of the promise returned by then will be the same as the resolved value of the promise returned by the handler.*

- __*Promise.prototype.catch()*__
    - The `catch()` method returns a __Promise__ and deals with rejected cases only. It behaves the same as calling `Promise.prototype.then(undefined, onRejected)` (in fact, calling `obj.catch(onRejected)` internally calls `obj.then(undefined, onRejected)`)

- __*Promise.prototype.finally()*__
  - The `finally()` method of a Promise schedules a function, the callback function, to be called when the promise is __settled__. The `finally()` method can be useful if you want to do some processing or cleanup once the promise is settled, regardless of its outcome.

## Chained Promises

The methods `Promise.prototype.then()`, `Promise.prototype.catch()`, and `Promise.prototype.finally()` are used to associate further action with a promise that becomes settled. As the `then()` and `catch()` methods return promises, they can be chained.

Let's practice with this challenge to have a better understanding about chained promises

> __Challenge__: Implement a class Chain that have 3 method: `eat`, `work`, `sleep(s)` that wait for `s` before doing next action. You can call the methods in any order

```js
// Problem: method chaining sequentially (with asynchronous function)
// Idea: 
// - Using Promise as a task queue
// - Only do next action if previous Promise finished 
// - In case of sleep, return a new Promise()

// Approach 1: Using class

class Chain {
    _chain;
    constructor() {
        this._chain = Promise.resolve(true);
    }

    eat = () => {
        this._chain = this._chain.then(() => {
            console.log('eat');
        })
        return this;
    }

    work = () => {
        this._chain = this._chain.then(() => {
            console.log('work');
        })
        return this;
    }

    sleep = (s) => {
        this._chain = this._chain.then(() => {
            console.log('start sleep');
            return new Promise((resolve, reject) => {
                setTimeout(() => {
                    console.log('wake up');
                    resolve();
                }, s * 1000);
            })
        });

        return this;
    }

}

const chain = new Chain();
chain.eat().sleep(5).work().eat().work();
```

## Reference

- [Promise - MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise)

All about Promise in Javascript


## Callback

In the beginning, there were __callbacks__. __*A callback is nothing special but a function that is executed at some later time.*__

Note the nesting of callbacks and the staircase of }) at the end. This is affectionately called as __Callback Hell__. Here is an example

![callback hell example](//images.ctfassets.net/tk7dn5bsmtgs/3dyZvbFTJKv5xKjsJziN91/b5ef6269f35f29b2ebe61d8a846c846e/callback_hell.png)

__Disadvantages:__
- The code becomes harder to read 
- Error handling is complicated

## Promise

To overcome this problem, JavaScript created `Promises`. This lets asynchronous methods return values like synchronous methods: instead of immediately returning the final value, the asynchronous method returns a promise to supply the value at some point in the future.

Now, instead of nesting callbacks inward, we can chain them. Here’s an example —

![Promise chain example](//images.ctfassets.net/tk7dn5bsmtgs/5NmaKVIBafi8LyKLjel78g/60382b1f5f5b4161e9be5e7b706b1156/promise_chain.png)

The flow has become a familiar `top-to-bottom` rather than `left-to-right` as in callbacks, which is a plus. __However, Promises still suffer from some problems:__

- We still have to give a callback to every `.then`.
- Instead of using a normal `try/catch`, we have to use `.catch` for error handling.
- Looping over multiple promises in a sequence is challenging and non-intuitive.

Read more about Promise [here](https://iamcoding.vercel.app/all-about-promise-in-javascript)

## Async Functions

Introduced in ES2017(ES8), async functions make working with promises much easier.

- It is important to note the async functions work on top of promises.
- They allow asynchronous execution while maintaining a regular, `synchronous feel`.

### Semantics and Evaluation Rules

#### An async function always returns a promise.

The body of an async function is always wrapped in a `new Promise`.

```js
async function fn() {
  return 'hello';
}
fn().then(console.log)
// hello
```

The function `fn` returns `hello`. Because we have used `async`, the return value 'hello' is wrapped in a __promise__ (via Promise constructor).

Here’s an alternate representation without using async:

```js
function fn() {
  return Promise.resolve('hello');
}
fn().then(console.log);
// hello
```

#### Async functions pause at each `await` expression.

An `await` acts on an expression. When the expression is a promise, __the evaluation of the async function halts until the promise is resolved__. When the expression is a non-promise value, it is converted to a promise using `Promise.resolve` and then resolved.

```js
// utility function to cause delay
// and get random value
const delayAndGetRandom = (ms) => {
  return new Promise(resolve => setTimeout(
    () => {
      const val = Math.trunc(Math.random() * 100);
      resolve(val);
    }, ms
  ));
};
async function fn() {
  const a = await 9;
  const b = await delayAndGetRandom(1000);
  const c = await 5;
  await delayAndGetRandom(1000);

  return a + b * c;
}
// Execute fn
fn().then(console.log);
```

Let’s examine the function fn line by line:

- When `fn` is executed, the first line to be evaluated is `const a = await 9;`. It is internally transformed into `const a = await Promise.resolve(9);`.
- Since we are using `await`, `fn` __pauses until the variable__ a gets a value. In this case, the promise resolves it to 9.
- `delayAndGetRandom(1000)` causes fn to pause until the function `delayAndGetRandom` is resolved which is after 1 second. So, `fn` effectively pauses for 1 second.
- Also, `delayAndGetRandom` resolves with a random value. Whatever is passed in the resolve function, that is assigned to the variable b.
- `c` gets the value of 5 similarly and we delay for 1 second again using `await delayAndGetRandom(1000)`. We don’t use the resolved value in this case.
- Finally, we compute the result `a + b * c` which is wrapped in a Promise using `Promise.resolve`. This wrapped promise is returned.

## The challenge

> Let’s assume that we have a for loop that prints 0 to 10 at random intervals (0 to n seconds). We need to modify it using promises to print sequentially 0 to 10. For example, if 0 takes 6 seconds to print and 1 takes two seconds to print, then 1 should wait for 0 to print and so on.

```js
// Approach 1: Using promise
const wait = (i, ms) => new Promise(
    resolve => setTimeout(() => {
        console.log(i);
        resolve(i);
    }, ms)
);

let chain = Promise.resolve();

for (let i = 0; i < 10; i++) {
    chain = chain.then(() => {
        return wait(i, Math.random() * 1000);
    });
}

// Approach 2: Using async/await
async function printNumbersUsingAsync() {
  for (let i = 0; i < 10; i++) {
    await wait(i, Math.random() * 1000);
  }
}

printNumbersUsingAsync();
```

## Common mistakes

### Not using await

```js
async function foo() {
  try {
    canRejectOrReturn();
  } catch (e) {
    return 'caught';
  }
}
```

Note that we are not using `await` or `return`. __`foo` will always resolve with `undefined`__ without waiting for 1 second. However, the promise does start its execution. If there are side-effects, they will happen

### Async functions in callbacks

We often use `async` functions in `.map` or `.filter` as callbacks.

```js
const url = 'https://api.github.com/users';

const fetchPublicReposCount = async (username) => {
  const response = await fetch(`${url}/${username}`);
  const json = await response.json();
  return json['public_repos'];
}

const users = ['ArfatSalman', 'octocat', 'norvig'];

const counts = users.map(async username => {
  const count = await fetchPublicReposCount(username);
  return count;
});

// To read resolve values of counts. we can use Promise.all()
// or this syntax

const results = async() => {
  for await(const count of counts) {
    console.log(count);
  }
}

```

We might expect that counts variable will contain the numbers of repos. __However, as we have seen earlier, all async functions return promises.__ Hence, `counts is actually an array of promises`. We might need `Promise.all` to get the resolve values.

```js
// Another approach: define new async function and execute it
const getCounts = async () => {
  for (const name of users) {
    const count = await fetchPublicReposCount(name);
    console.log(count);
  }
}

getCounts();
```

## Reference

- [Deeply Understanding JavaScript Async and Await with Examples](https://blog.bitsrc.io/understanding-javascript-async-and-await-with-examples-a010b03926ea)
- [The Async Await Episode I Promised](https://www.youtube.com/watch?v=vn3tm0quoqE)
- [Promise - MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise)

Understand how Javascript handle asynchronous code.

About Promise, Async and Await in Javascript

## Hashing vs Encoding vs Encryption

| Hashing     | Encoding     | Encryption     |
| ---------- | ---------- | ---------- |
| converting a given __key__ into another smaller and __fixed-size__ value (`SHA-X`, `Bcrypt`, `MD5`)       | data is transformed from one form to other form. (`BASE64`, `ASCII`, `MP4`, `binary`, `decimal`, ...)       | An encoding technique, in which message (text, json…) is encoded by __encryption algorithm__ that only authorized people can read the message.RSA (Private key, public key)       |
| not reversible, collision       | reversible, no collision       | reversible       |
| key => value, password storage, __data’s integrity__ validation | purpose: transform data into a form that is readable by external process       | purpose: transfer private data, authorization       |

## Password Storage

> How to store passwords in DB securely ?

`Hash` + `Salt` + `Pepper`

- A `salt` is a unique, randomly generated string that is added to each password as part of the hashing process
- `Salt` is stored in database.
- Hacker has to crack hashes one at a time instead of calculating the hash once and compare with every stored hash. => slow hacking process
- Impossible to check if 2 users have same password. 
  - `hashed_password = hash(unique_salt + password)`

- `Pepper` is a randomly generated string that is added to password as part of the hashing process.
- `Pepper` is not stored in database. (`env` variable, secure centralized store)
- `pepper` is shared between all passwords rather than being unique like a salt.
- Prevent hacker from crack any hash if they only have access to the database.
  - `hashed_password = hash(common_pepper + unique_salt + password)`

## Symmetric - Asymmetric Encryption

`Symmetric encryption`:  both side (sender and receiver) share 
the same key to encrypt/decrypt the text, it is fast.

`Asymmetric encryption`
- When a message is encrypted using a `public key`, it can only be decrypted using a `private key`.
- When a message is encrypted using a `private key`, it can be only decrypted using a `public key`.
- Slow
- Most common algorithm: `RSA`

### RSA for authentication

The purpose is to confirm that a message has been sent by the entity who claims to have sent it, and proving that a message hasn’t been altered or tampered with.

- Sender produces a __digital signature__ by applying a hash function on a message m and sign it with the SK (Scret Key or Private Key)
  - `signature = encrypt(hash(m), SK)`

- Signer sends (`signature`, `hashed_of_m`) to verifier.
- Verifier verifies by reproduce message hash using PK (Public key) and compare with actual hash value.
  - To check who send it: check `decrypt(signature, PK) == hashed_of_m`
  - To check if message changed or not:	`hash(m) == hashed_of_m`

## TLS - Transport Layer Security

> HTTPS = HTTP + TLS

![TLS handshake](https://ssl.vn/wp-content/uploads/2018/09/ssl-tls-handshake-process-1024x670.png.webp)

- Using a __asymmetric encryption__ to setup TLS handshake
- Client sends `Client Hello` message to Server which include:
  - TLS version
  - Cipher suites client supports (algorithm)
  - Client random bytes

- Server sends `Server Hello` message to Client which include:
  - Server's SSL certificate
  - Server's chosen cipher suites
  - Server random bytes

- Client confirms Server's identity (authentication) by checking the server's SSL certificate using RSA encryption:
  - __*SSL certificate*__ contains:
    - __domain name__
    - __CA's digital signature__
    - __server's public key__
    - Other informations like: person/ organization owns the certificate, which Certificate authority (CA) issued it, issue date, expiration date, ...
  - The whole identity authentication is based on the idea `You trust the CA, and they trust me, therefore you can trust me.`:
    - The browser or OS has a build-in list of all CA's public key
    - It uses CA's Public Key to decrypt the CA's digital signature
    - It confirms that the decrypted data is matched.
      - Public key of server is included in the decrypted signature => check if it matches the public key in certificate.

- Key Exchange, use RSA
  - Client generates a random `pre-master secret`, encrypts it with the Server's public key (found in Server SSL's certificate), sends the result to Server
  - Server decrypts the `pre-master secret` using its secret key.
  - At this point, both Client and Server share the same `pre-master secret`. 

- Both Client and Server generate `Session key` or `Master Key` from `pre-master secret`, `client random`, and `server random`

  - `session_key = hash(pre-master secret, ClientHello.random, ServerHello.random)`
  - use client, server random to avoid replay attack: if there is no client random and server random, hacker capture the package and resend.

- Client is ready: The client sends a `finished` message that is encrypted with a `session key`.

- Server is ready: The server sends a `finished` message encrypted with a `session key`.

- The handshake is completed, and communication continues using the __symmetric encryption__ with key = Session key, since it is much faster.

## CORS

Two URLs have the same origin if they have the same: `protocol` (http, https), `host` (vnexpress.net, google.com), `port` (80, 8080)

```text
http://example.com/index.html

// Same origin
http://example.com/profile.html
http://example.com:80/profile.html

// Different origin
https://example.com/index.html
http://example.com:81/index.html
http://blog.example.com/index.html
```

__*SOP - Same Origin Policy*__: A web application using APIs can only request HTTP resources from the same origin the application was loaded from.
- a policy that is compiled by most of the browsers (security reason)
- Not apply for debug tool like `Postman`, `curl`
- Not apply for some html tags: `<script>`, `<img>`, `<link>`, `<frame>`, `<iframe>`

***CORS*** __is a mechanism to bypass SOP__, we can define which origin can request the server's origin

## JWT - Json Web Token

JWT is an open standard that defines a way for securely transmitting data between parties (client, server). This information can be verified and trusted because it is digitally signed.

> JWT = Base64(HEADER) + Base64(PAYLOAD) + Base64(SIGNATURE)

- __Header__: metadata about hashing algorithm being used
- __Payload__: data (user, expire time, role, ...)
- __Signature__: used to validate that the token is trustworthy 
and has not been tampered with

> With JWT token we can get data easily by decode payload (base64), it main feature is to check if that token is integrity or not.

> If hacker can get your JWT, they have full access to your account. Therefore, store it somewhere safe.

__*How JWT is validated*__
- JWT token is generate in server with a `secret key`
- When server receive a token: it check if the __Signature__ part is match with `hash(encode(header) + encode(payload), secret_key)` or not ⇒ Validation

__*Advantage*__
- __stateless__: server does not need to maintain a session storage because all authentication information is stored in JWT, which is stored in client side (browser).

- because JWT is sent along with the request in the __request header__, it eliminates the possibility of __CSRF__ (Cross-site Request Forgery) attack.

__*Disadvantage*__
- No Built-In Token Revocation by the User:
  - JWT only become invalid when it expires. The user has no built-in feature to explicitly revoke the validity of a token
  - The solution would be creating a database to maintain a revocation list. This would add complexity to the system and eliminate the stateless property of JWT authentication.


Storage, SSL/TLS, JWT, CORS, SQL injection ...

Technical things about Web Security

Fundamental knowledge about HTML that usually asked in interview.

HTML for interview 

## Closure

A `closure` is the combination of a function and the lexical environment within which that function was declared. `A closure is a function having access to the parent scope (variables, ...), even after the parent function has closed.`

- Among other things, closures are commonly used to give objects data privacy.

### Excercise

- __*Problem 1*__

```js
for (var i = 0; i < 3; i++) {
  const log = () => {console.log(i)};
  setTimeout(log, 100);
}

// var i get hoisted
// log is now captured the global i variable

for (let i = 0; i < 3; i++) {
  const log = () => {console.log(i)};
  setTimeout(log, 100);
}

// let i is block scope
// i value is captured inside log value
```

- __*Problem 2*__ Implement function `add(2)(3)`. Follow up question: `Implement add(2)(3)(4)..., for endless number of parameters`

```js
// Solution for add(2)(3)
const add = (x) => (y) => x + y;
```

Solution for follow up question:

```js
// Approach 1
const add = (x) => {
    let sum = x;
    const resultFn = (y) => {
        if(y=== undefined) return sum;
        sum += y;
        return resultFn;
    }
    return resultFn;
}

console.log(add(1)(2)(3)());
```

```js
// Approach 2
function add(a) {
    let curry = (b) => {
        a += b
        return curry;
    }
    curry.valueOf = () => a;
    return curry;
}

console.log(+add(1))
console.log(+add(1)(2))
console.log(+add(1)(2)(3))
console.log(+add(1)(2)(3)(4))
```

## Currying Javascript

`Currying` is a pattern where a function with more than one parameter is broken into multiple functions that, when called in series, will accumulate all of the required parameters one at a time. This technique can be useful for making code written in a functional style easier to read and compose. It's important to note that for a function to be curried, it needs to start out as one function, then broken out into a sequence of functions that each accepts one parameter.

- __*Challenge*__

```js
// Keep in mind that the arguments length of this function call be changed
function sum(a, b, c) {
    return a + b + c;
}

let curriedSum = curry(sum);

console.log(curriedSum(1, 2, 3)); // Log 6
console.log(curriedSum(1)(2, 3)); // Log 6
console.log(curriedSum(1)(2)(3)); // Log 6
```

- __*Solution*__

```js
function curry(func) {
    return function curried(...args) {
        if (args.length >= func.length) {
            return func.apply(this, args);
        } else {
            return function (...args2) {
                return curried.apply(this, args.concat(args2));
            }
        }
    };
}
```

> `apply` accept the second element as an array of arguments list.

The above function can be simplified to this one:

```js
function fixCurry(fn) {
    totalArgs = fn.length;
    return function recursor() {
        return arguments.length < totalArgs ?
            recursor.bind(this, ...arguments) : 
            fn.call(this, ...arguments);
    }
}

var add = fixCurry((a, b, c) => a + b + c); //fn = summation function
console.log(add(1, 2, 3)) // output: 6
console.log(add(1)(2, 3)) // output: 6
console.log(add(1)(3)(2)) // output: 6
console.log(add(1, 2)(3)) // output: 6
```

## Reference

- [JS Currying in Interview](https://theanubhav.com/2019/02/03/js-currying-in-interview/)


Explain in detail about Closure and its common applications

Posts