# Posts tagged as “javascript”

Suppose an array of length `n` sorted in ascending order is rotated between `1` and `n` times. For example, the array `nums = [0,1,4,4,5,6,7]` might become:

• `[4,5,6,7,0,1,4]` if it was rotated `4` times.
• `[0,1,4,4,5,6,7]` if it was rotated `7` times.

Notice that rotating an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

Given the sorted rotated array `nums` that may contain duplicates, return the minimum element of this array.

Example 1:

```Input: nums = [1,3,5]
Output: 1
```

Example 2:

```Input: nums = [2,2,2,0,1]
Output: 0
```

Constraints:

• `n == nums.length`
• `1 <= n <= 5000`
• `-5000 <= nums[i] <= 5000`
• `nums` is sorted and rotated between `1` and `n` times.

Idea:

Divide and Conquer

Solution:

``````/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
// exit recursion:
// only one or two elements in the array
if (l + 1 >= r)
return Math.min(nums[l], nums[r]);
// this array is sorted
if (nums[l] < nums[r])
return nums[l];

let mid = l + Math.floor((r - l) / 2);
return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}``````

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

```Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
```

Example 2:

```Input: root = []
Output: []
```

Example 3:

```Input: root = [1]
Output: [1]
```

Example 4:

```Input: root = [1,2]
Output: [1,2]
```

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `-1000 <= Node.val <= 1000`

Idea: (Recursion)

```We can encodes the tree to a single string.
// # indicates reach to the leave
Convert above tree to 12##34##56## ```

Time Complexity O(n)

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/

/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
let res = [];
serializer(root, res);
return res.join(",");
};

var serializer = function(root, output) {
if (root === null) {
output.push("#");
return;
}
output.push(root.val);
serializer(root.left, output);
serializer(root.right, output);
}

// Decodes your encoded data to tree.
var deserialize = function(data) {
data = data.split(",");
let index = 0;

function deserializer(data) {
if(index > data.length || data[index] === "#") {
return null;
}
let root = new TreeNode(parseInt(data[index]));
index++;
root.left = deserializer(data);
index++;
root.right = deserializer(data);
return root;
}
return deserializer(data);
};``````

Given an integer `n`, return the least number of perfect square numbers that sum to `n`.

perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1``4``9`, and `16` are perfect squares while `3` and `11` are not.

Example 1:

```Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
```

Example 2:

```Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
```

Constraints:

• `1 <= n <= 104`

Idea: (Dynamic Programing)

• Time complexity: O(n * sqrt(n))
• Space complexity: O(n)
```dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 =
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 =
dp[0] + 5 = 5
};
so dp[5] = 2```

Solution:

``````/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
// Important: n + 1 length because we use dp[0]
let dp = new Array(n + 1).fill(Number.MAX_VALUE);
dp[0] = 0;
for (let i = 1; i <= n; i++)
for(let j = 1; j * j <= i; j++)
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

return dp[n];
};``````

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

```Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
```

Example 2:

```Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in non-decreasing order.

Solution 1: (Quick Sort)

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
nums = nums.map(num => num * num);
quickSort(nums, 0, nums.length - 1);
return nums;
};

function quickSort(nums, left, right) {
let index;
if (nums.length > 1) {
// index returned from partition
index = partition(nums, left, right);
// more elements on the left side of the pivot
if (left < index - 1)
quickSort(nums, left, index - 1);
// more elements on the right side of the pivot
if (index < right)
quickSort(nums, index, right);
}
// you can return or not return,
// since we change nums, no need to return
// return nums;
}

function partition(nums, start, end) {
let l = start, r = end;
let mid = Math.floor((start + end) / 2);
let pivot = nums[mid];
// Important: l <= r not l < r
while (l <= r) {
while(nums[l] < pivot)
l++;
while(nums[r] > pivot)
r--;
if (l <= r) {
// swap
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
return l;
}``````

Solution 2: (Merge Sort)

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
nums = nums.map(num => num * num);
let temp = [];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
};

function mergeSort(nums, start, end, temp) {
if (start >= end) return;
let mid =  Math.floor((start + end) / 2);
mergeSort(nums, start, mid, temp);
mergeSort(nums, mid + 1, end, temp);
merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
let mid =  Math.floor((start + end) / 2);
let l_index = start;
let r_index = mid + 1;
let index = start;
while (l_index <= mid && r_index <= end) {
if (nums[l_index] < nums[r_index]) {
temp[index++] = nums[l_index++];
} else {
temp[index++] = nums[r_index++];
}
}
while (l_index <= mid) {
temp[index++] = nums[l_index++];
}
while (r_index <= end) {
temp[index++] = nums[r_index++];
}
for (let i = 0; i <= end; i++)
nums[i] = temp[i];
}``````

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```

Example 2:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```

Example 3:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

Constraints:

• `m == board.length`
• `n = board[i].length`
• `1 <= m, n <= 6`
• `1 <= word.length <= 15`
• `board` and `word` consists of only lowercase and uppercase English letters.

Idea:

DFS

Solution:

``````/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
for (let x = 0; x < board[0].length; x++)
for (let y = 0; y < board.length; y++)
if (dfs(board, word, 0, x, y)) return true;
return false;
};

function dfs(board, word, i, x, y) {
// exit recursion:
if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
return false;
// found the last letter
if (i === word.length - 1)
return true;

let cur = board[y][x];
// mark it 0 means already visit
board[y][x] = 0;
let found = dfs(board, word, i + 1, x + 1, y) ||
dfs(board, word, i + 1, x - 1, y) ||
dfs(board, word, i + 1, x, y + 1) ||
dfs(board, word, i + 1, x, y - 1);
// recover
board[y][x] = cur;
return found;
}``````

There are `N` rooms and you start in room `0`.  Each room has a distinct number in `0, 1, 2, ..., N-1`, and each room may have some keys to access the next room.

Formally, each room `i` has a list of keys `rooms[i]`, and each key `rooms[i][j]` is an integer in `[0, 1, ..., N-1]` where `N = rooms.length`.  A key `rooms[i][j] = v` opens the room with number `v`.

Initially, all the rooms start locked (except for room `0`).

You can walk back and forth between rooms freely.

Return `true` if and only if you can enter every room.

Example 1:

```Input: [[1],[2],[3],[]]
Output: true
Explanation:
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.
```

Example 2:

```Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.
```

Note:

1. `1 <= rooms.length <= 1000`
2. `0 <= rooms[i].length <= 1000`
3. The number of keys in all rooms combined is at most `3000`.

Idea:

DFS

Solution:

``````/**
* @param {number[][]} rooms
* @return {boolean}
*/
var canVisitAllRooms = function(rooms) {
let visited = [];
dfs(rooms, visited, 0);
return visited.length === rooms.length;
};

function dfs(rooms, visited, roomNum){
// exit recursion:
if (visited.includes(roomNum)) return;

visited.push(roomNum);
// possible solution
for (let key of rooms[roomNum])
dfs(rooms, visited, key);
}``````

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

```Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

```

Example 2:

```Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in a strictly increasing order.

Idea:

Recursion + Divide and Conquer

Time complexity: O(n)
Space complexity: O(logn)

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
return createBST(nums, 0, nums.length - 1);
};

function createBST(nums, l, r) {
// exit recursion condition
if (l > r) return null;

let mid = l + Math.floor((r - l) / 2);
let root = new TreeNode(nums[mid]);
root.left = createBST(nums, l, mid - 1);
root.right = createBST(nums, mid + 1, r);
return root;
}``````

## What are the ACID properties in DBMS?

A transaction in a database system must maintain AtomicityConsistencyIsolation, and Durability − commonly known as ACID properties − in order to ensure accuracy, completeness, and data integrity.

• Atomicity means that either rollback or commit the complete transaction.
• Consistency is handled by MySQL’s logging mechanisms, which record all changes happening to your database and help us to ensure that no in-consistency will occur.
• Isolation provides several low level locking which avoids (if properly handled) any other process to acquire lock on resource which is already in use by other process.
• MySQL implements durability by maintaining a binary transaction log file that tracks changes to the system during the course of a transaction. In the event of a hardware failure or abrupt system shutdown, recovering lost data is a relatively straightforward task by using the last backup in combination with the log when the system restarts. By default, InnoDB tables are 100 percent durable (in other words, all transactions committed to the system before the crash are liable to be rolled back during the recovery process), while MyISAM tables offer partial durability.

## What is transaction?

A transaction is a logical unit of work that contains one or more SQL statements. Transactions are atomic units of work that can be committed or rolled back. When a transaction makes multiple changes to the database, either all the changes succeed when the transaction is committed, or all the changes are undone when the transaction is rolled back.

## When should you use transactions in my queries?

• Use a transaction when you have a series of writes that need to be performed atomically; that is, they should all succeed or none should.
• Needs the ability to rollback every change, if an error occurs or some other reason.

## Transaction best practices

Using the SQL Server transaction helps maintaining the database integrity and consistency. On the other hand, a badly written transaction may affect the overall performance of your system by locking the database resources for long time. To overcome this issue, it is better to consider the following points when writing a transaction:

• Narrow the scope of the transaction
• Retrieve the data from the tables before opening the transaction if possible
• Access the least amount of data inside the transaction body
• Do not ask for user input inside the body of the transaction
• Use a suitable mode of transactions
• Use as suitable Isolation Level for the transaction

## Difference between DELETE and TRUNCATE

DELETE is a DML(Data Manipulation Language) command and is used when we specify the row(tuple) that we want to remove or delete from the table or relation. The DELETE command can contain a WHERE clause. If WHERE clause is used with DELETE command then it remove or delete only those rows(tuple) that satisfy the condition otherwise by default it removes all the tuples(rows) from the table.

TRUNCATE is a DDL(Data Definition Language) command and is used to delete all the rows or tuples from a table. Unlike the DELETE command, TRUNCATE command does not contain a WHERE clause. In the TRUNCATE command, the transaction log for each deleted data page is recorded. Unlike the DELETE command, the TRUNCATE command is fast. Like DELETE, we can rollback the data even after using the TRUNCATE command.

## What is Pattern Matching in SQL?

• Using the % wildcard to perform a simple search
The % wildcard matches zero or more characters of any type and can be used to define wildcards both before and after the pattern. Search a student in your database with first name beginning with the letter K:
• SELECT * FROM students WHERE first_name LIKE ‘K%’
• Omitting the patterns using the NOT keyword
Use the NOT keyword to select records that don’t match the pattern. This query returns all students whose first name does not begin with K.
• SELECT * FROM students WHERE first_name NOT LIKE ‘K%’
• Matching a pattern anywhere using the % wildcard twice
Search for a student in the database where he/she has a K in his/her first name.
• SELECT * FROM students WHERE first_name LIKE ‘%Q%’
• Using the _ wildcard to match pattern at a specific position
The _ wildcard matches exactly one character of any type. It can be used in conjunction with % wildcard. This query fetches all students with letter K at the third position in their first name.
• SELECT * FROM students WHERE first_name LIKE ‘__K%’
• Matching patterns for specific length
The _ wildcard plays an important role as a limitation when it matches exactly one character. It limits the length and position of the matched results. For example –
• SELECT * /* Matches first names with three or more letters */ FROM students WHERE first_name LIKE ‘___%’ SELECT * /* Matches first names with exactly four characters */ FROM students WHERE first_name LIKE ‘____’

## How to create empty tables with the same structure as another table?

`SELECT * INTO Students_copy FROM Students WHERE 1 = 2;`

## What is Normalization?

Normalization represents the way of organizing structured data in the database efficiently. It includes creation of tables, establishing relationships between them, and defining rules for those relationships. Inconsistency and redundancy can be kept in check based on these rules, hence, adding flexibility to the database.

## What is Denormalization?

Denormalization is the inverse process of normalization, where the normalized schema is converted into a schema which has redundant information. The performance is improved by using redundancy and keeping the redundant data consistent. The reason for performing denormalization is the overheads produced in query processor by an over-normalized structure.

## SQL Injection

SQL injection is a code injection technique that might destroy your database.

SQL Injection Based on 1=1 is Always True and Based on “”=”” is Always True

## How to prevent SQL injection?

1. Validate User Inputs and Sanitize Data
2. Use Prepared Statements And Parameterization

## Do your best to describe the process from the time you type in a website’s URL to it finishing loading on your screen? How is an HTML page rendered? What elements are created in what order?

Step 1 >> Get the ip address of the URL.
System checks the browser cache. Browser caches the DNS data for some time.
=> OS cache=>  DNS cache maintained by the router => next level where DNS cache of your ISP => DNS query to search for the required DNS data.

Step 2>> Once the browser gets the IP address it opens TCP connection and sends HTTP request to the web server.

Step 3>> The web server will handle the request [it happens in multiple steps] and send the HTTP response to the client/browser.

Step 4>> The browser parse the HTML document and render it.

Rendering steps:

• if the files are scripts, then run them in the order they appear in the HTML
• if they try to access the DOM right now, they will throw an error
• while they run, they will prevent any other rendering, which is why some scripts are put at the bottom of the body
• for CSS files, save the style rules in order they appear in the HTML
• if they’re images then display them
1. End HTML Parsing
2. Create the DOM – including all the styles we have so far
3. Execute the DOMContentLoaded event when the DOM is fully constructed and scripts are loaded and run happens even if all other external files (images, css) are not done downloading (from step 4) in the Chrome F12 developer tools this is represented by a blue line on the Network view will start running anything you’ve added to this event, e.g. window.addEventListener(“DOMContentLoaded”, doStuff, true);
4. Start painting the document to the display window (with any styles that have already loaded)
5. Execute the window.onload event when all external files have loaded in the Chrome F12 developer tools this is represented by a red line on the Network view this will start running the jQuery ready function \$(document).ready(function(){ … }); will start running any code you’ve added to this event, e.g. window.addEventListener(“load”, doStuff, true);
6. Re-paint the document, including any new images and styles

## Can you describe specificity in CSS?

• Inline styles – An inline style is attached directly to the element to be styled. Example: <h1 style=”color: #ffffff;”>.
• IDs – An ID is a unique identifier for the page elements, such as #navbar.
• Classes, attributes and pseudo-classes – This category includes .classes, [attributes] and pseudo-classes such as :hover, :focus etc.
• Elements and pseudo-elements  – This category includes element names and pseudo-elements, such as h1, div, :before and :after.

## What are the values that you can position an element?

static, relative, absolute, fixed, sticky

## Can you explain closure in JS?

Closure means that an inner function always has access to the vars and parameters of its outer function, even after the outer function has returned. Closures keep access to the variables they can be used to save state. And things that save state look a whole lot like objects

## Difference between const, let, and var

var declarations are globally scoped or function scoped while let and const are block scoped. var variables can be updated and re-declared within its scope; let variables can be updated but not re-declared; const variables can neither be updated nor re-declared. They are all hoisted to the top of their scope

## What are the areas of scope in JS?

• Global scope
• Local scope / function scope
• Block scope – introduced in ES6 that limits a variables scope to a given parenthesis block

## What’s the difference between bind, apply and call?

The call, bind and apply methods can be used to set the this keyword independent of how a function is called. The bind method creates a copy of the function and sets the this keyword, while the call and apply methods sets the this keyword and calls the function immediately.

`call` requires the arguments to be passed in one-by-one, and `apply` takes the arguments as an array.

## What is the difference between single-quoted and double-quoted strings in PHP?

• Single quoted strings will display things almost completely “as is.” Variables and most escape sequences will not be interpreted. The exception is that to display a literal single quote, you can escape it with a back slash `\'`, and to display a back slash, you can escape it with another backslash `\\` (So yes, even single quoted strings are parsed).
• Double quote strings will display a host of escaped characters (including some regexes), and variables in the strings will be evaluated. An important point here is that you can use curly braces to isolate the name of the variable you want evaluated. For example let’s say you have the variable `\$type` and you want to `echo "The \$types are"`. That will look for the variable `\$types`. To get around this use `echo "The {\$type}s are"` You can put the left brace before or after the dollar sign. Take a look at string parsing to see how to use array variables and such.

## How to check whether a variable is null in PHP?

Answer: Use the PHP is_null() function or === NULL

## What is ORM?

ORM stands for Object-Relational Mapping (ORM) is a programming technique for converting data between relational databases and object oriented programming languages such as PHP, Java, C#, etc.

An ORM system has the following advantages:

• Let’s business code access objects rather than DB tables.
• Hides details of SQL queries from OO logic.
• No need to deal with the database implementation.
• Entities based on business concepts rather than database structure.
• Transaction management and automatic key generation.
• Fast development of application.

## What is Dependency Injection?

Dependency Injection (DI) is a design pattern used to implement IoC. It allows the creation of dependent objects outside of a class and provides those objects to a class through different ways. Using DI, we move the creation and binding of the dependent objects outside of the class that depends on them.

## What is Inversion of Control?

Inversion of control is a broad term but for a software developer it’s most commonly described as a pattern used for decoupling components and layers in the system. For example, creates a dependency between the TextEditor and the SpellChecker.

``````public class TextEditor {
private SpellChecker checker;
public TextEditor(SpellChecker checker) {
this.checker = checker;
}
}``````

## What is Bridge pattern?

Bridge pattern is used when we need to decouple an abstraction from its implementation so that the two can vary independently. This type of design pattern comes under structural pattern as this pattern decouples implementation class and abstract class by providing a bridge structure between them.

The bridge pattern is useful when both the class and what it does vary often. The class itself can be thought of as the abstraction and what the class can do as the implementation. The bridge pattern can also be thought of as two layers of abstraction.

## Explain a use case for Docker

• Docker is a low overhead way to run virtual machines on your local box or in the cloud. They’re not strictly distinct machines, they don’t need to boot an OS.
• Docker can encapsulate legacy applications, allowing you to deploy them to servers that might not be easy to setup with older packages and software version.
• Docker can be used to build test boxes, during your deploy process to facilitate continuous integration(CI) testing.
• Docker can be used to provision boxes in the cloud, and with swarm you can orchestrate clusters too

## Explain the main difference between REST and GraphQL

The main and most important difference between REST and GraphQL is that GraphQL is not dealing with dedicated resources, instead everything is regarded as a graph and therefore is connected and can be queried to app exact needs.

## If you were to implement an API endpoint for checking if a resource exists, what path and method would you use?

RESTful path should only contain nouns–the method used on the endpoint should determine the action.

• POST /users create a user model
• PUT /users/{id|slug} replace a user model
• PATCH /users/{id|slug} update part of a user model
• DELETE /users/{id|slug} delete a user model
• GET /users/{id|slug} retrieve a user model

The commonly accepted way to determine if a resource exists, using the above “user” resource as an example, then:

This request will use the least amount of bandwidth as it will return no data, simply just a 200 or 404 HTTP status.

## A common issue when integrating third-party services within your own API requests is having to wait for the response, and as such, forcing the user to have to wait for a longer time. How would you do to avoid this?

The most effective way to solve this problem is to use queues. When a request is made to our API, a separate job is then created and added to a queue. This job will then be executed independently to the requested endpoint, thus allowing the server to respond without delay.

Message queue providers: Beanstalkd, RabbitMQ

## How would you prevent a bot from scraping your publicly accessible API?

Technically, it is not possible to completely prevent data scraping. However, there is an effective solution that will deter most bots: rate limiting (throttling).

Throttling will prevent a certain device from making a defined number of requests within a defined time. Upon exceeding the defined number of requests, a 429 Too Many Attempts HTTP error should be thrown.

Note: It is important to track the device with more than just an IP address as this is not unique to the device and can result in an entire network losing access to an API.

• Blocking requests based on the user agent string (easy to find a way around)
• Generating temporary “session” access tokens for visitors at the front end.(this isn’t secure: storing a secret on the front end can be reverse-engineered, thus allowing anyone to generate access tokens)

## If a user attempts to create a resource that already exists, what HTTP status code would you return?

Use a 409 conflict HTTP status code / 400 bad request

## What is Event Loop?

Node.js is a single threaded application but it support concurrency via concept of event and callbacks. As every API of Node js are asynchronous and being a single thread, it uses async function calls to maintain the concurrency. Node uses observer pattern. Node thread keeps an event loop and whenever any task get completed, it fires the corresponding event which signals the event listener function to get executed.

## List some key things to consider when coding with SEO in mind

In order to build a site optimized for organic search engine rankings, it is important to implement certain standards throughout the code. These include:

• Using the correct HTML tags for content hierachy i.e. <h1>/<h2>/<h3> and p
• Use alt tag on images
• Use vanity/friendly URLs (human readable)
• Avoid Javascript errors
• Avoid W3C markup validation errors
• Enable and force SSL
• Include a meta description on each page
• Specify relevant meta tags
• Specify a favicon
• Specify unique title for each page without exceeding 70 characters
• Ensure there is enough content with enough relevant keywords
• Leverage browser caching

## List some ways you could optimize a website to be as efficient and scalable as possible.

• Ensure no validation errors with W3C
• Minified all your assets and all code
• Place all assets on CDN
• Avoid inline Javascript and CSS
• Leverage browser caching
• Prefer async resources
• Reduce DNS lookups
• Avoid URL redirects
• Avoid CSS @import
• Serve scaled images, SVG
• Avoid unnecessary images; where possible use CSS
• Enable HTTP keep-alive
• Minimize request size, avoid bad requests and 404s
• Make fewer HTTP requests, load as few external resource as possible

To be continue….

You are given the `root` of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Follow up: A solution using `O(n)` space is pretty straight forward. Could you devise a constant space solution?

Example 1:

```Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
```

Example 2:

```Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
```

Constraints:

• The number of nodes in the tree is in the range `[2, 1000]`.
• `-231 <= Node.val <= 231 - 1`

Idea:

Because inorder traverse BST, all values are sorted. We can use inorder traversal to find two nodes that have prev.val > root. val and swap them

Time complexity: O(n)
Space complexity: O(height)

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function(root) {
// javascript can't pass value by reference
// so pass array object by reference
let first = [null];
let second = [null];
let prev = [null];
inorder(root, first, second, prev);
[first[0].val, second[0].val] = [second[0].val, first[0].val];
};

function inorder(root, first, second, prev) {
// Because inorder traverse BST, all values are sorted.
// Using inorder traversal to find two nodes that have prev.val > root.val
if (root === null) return;
inorder(root.left, first, second, prev);
if (prev[0] && prev[0].val > root.val) {
if (first[0] === null) first[0] = prev[0];
second[0] = root;
}
prev[0] = root;
inorder(root.right, first, second, prev);
}``````

Given the `head` of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?

Example 1:

```Input: head = [4,2,1,3]
Output: [1,2,3,4]
```

Example 2:

```Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
```

Example 3:

```Input: head = []
Output: []
```

Constraints:

• The number of nodes in the list is in the range `[0, 5 * 104]`.
• `-105 <= Node.val <= 105`

Idea:

Merge Sort (use slow and fast pointer to find the middle of the linked list and split them)

Time Complexity: O(nlogn)

Solution:

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
// empty or one node
let right = sortList(mid);
return merge(left, right);
};

function merge(list1, list2) {
let tail = new ListNode();
while (list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 !== null) ? list1 : list2;
};