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.
Given an integer n, return the least number of perfect square numbers that sum ton.
A 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.
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].
/**
* @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 trueifwordexists 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 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
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);
}
A transaction in a database system must maintain Atomicity, Consistency, Isolation, 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
SQL
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?
Validate User Inputs and Sanitize Data
Use Prepared Statements And Parameterization
HTML
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:
Start downloading external files (JavaScript, CSS, images) as they’re encountered in the HTML
Parse external files once they are downloaded (or if they are inline and don’t require downloading)
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
if the loading fails, then proceed without this file
End HTML Parsing
Create the DOM – including all the styles we have so far
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);
Start painting the document to the display window (with any styles that have already loaded)
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);
Re-paint the document, including any new images and styles
CSS
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
Javascript
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.
PHP
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
Concept
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.
Docker
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
API
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:
HEAD /users/{id|slug}
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.
Other less-than-ideal answers include:
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
Node.js
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.
SEO
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)
Add XML sitemap
Add robots.txt file
Integrate Google analytics
Avoid broken links
Avoid Javascript errors
Avoid W3C markup validation errors
Minify your assets
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
Reduce cookie size
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
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);
}
