Kth largest element in an array can be determined using the “Quickselect Algorithm”.
Average performance O(n)
Worst-case performance O(n^2)
Kth largest element in an array can be determined using the “Quickselect Algorithm”.
Average performance O(n)
Worst-case performance O(n^2)
The difference between classical inheritance and prototypal inheritance is that classical inheritance is limited to classes inheriting from other classes while prototypal inheritance supports the cloning of any object using an object linking mechanism. Read more here.
== in JavaScript is used for comparing two variables, but it ignores the datatype of variable. === is used for comparing two variables, but this operator also checks datatype and compares two values.
This property of Javascript allows for private variables in a function. For example
const increment = (() => { let counter = 0; return () => { counter += 1; console.log(counter); } })(); // Self invoking function. increment(); increment(); increment();
This is one common scenario you might run into when you use async calls inside a loop. The loop executes before the async call returns and the desired output is not logged.
function httpGet(theUrl, callback) { var xmlHttp = new XMLHttpRequest(); xmlHttp.onreadystatechange = function() { if (xmlHttp.readyState == 4 && xmlHttp.status == 200) callback(xmlHttp.responseText); } xmlHttp.open("GET", theUrl, true); xmlHttp.send(null); } for (var i = 0; i < 5; i++) { httpGet('https://httpbin.org/get', function(data) { console.log(i); }); }
Output
5 5 5 5 5
Using closure we can handle this in the following way
function httpGet(theUrl, callback) { var xmlHttp = new XMLHttpRequest(); xmlHttp.onreadystatechange = function() { if (xmlHttp.readyState == 4 && xmlHttp.status == 200) callback(xmlHttp.responseText); } xmlHttp.open("GET", theUrl, true); xmlHttp.send(null); } for (var i = 0; i < 5; i++) { ((index) => { httpGet('https://httpbin.org/get', function(data) { console.log(index); }) })(i); } /* or in ES6 you can simply use the 'let' keyword. */ for (let i = 0; i < 5; i++) { httpGet('https://httpbin.org/get', function(data) { console.log(i); }); }
Output
0 1 2 3 4
The variables in javascript can be declared even after they are used as they are moved to the top of the code during execution. Hoisting doesn’t take place for initializing though. The same goes with function hoisting.
Note: There is no variable/function hoisting in ES6.
When ‘use strict’ is used you will need to declare variables while using them. There are other rules such as not being able to delete objects etc when using this mode.
Event propogation can be of 2 types Bubbling and Capturing.
Bubbling
Event propogation occurs starting from the inner element to the outermost element.
Capturing
Event propogation starts from the outermost element to innermost element. This is also known as Trickling.
If a lot of elements are handled in a similar way, then instead of assigning a handler to each of them – we put a single handler on their common ancestor.
Events bubble by default. So the difference between the two is:
target
is the element that triggered the event (e.g., the user clicked on)currentTarget
is the element that the event listener is attached to Read more…The Promise object represents the eventual completion (or failure) of an asynchronous operation and its resulting value. Read more here.
REST stands for representational state transfer. API stands for Application programming interface. Read here.
Read more here.
Read more here.
Read more here.
Stick to compositor-only properties. Read more here.
Read more here.
The localStorage and sessionStorage objects are part of the web storage API, are two great tools for saving key/value pairs locally. Using localStorage and sessionStorage for storage is an alternative to using cookies and the data is saved locally only and can’t be read by the server, which eliminates the security issue that cookies present. It allows for much more data to be saved (10MB). Cookies are still useful, especially when it comes to authentication, but there are times when using localStorage/sessionStorage may be a better alternative.
Read more here & here.
The Beacon API is a web API that allows you to send small amounts of data from a web page to a web server, asynchronously and without delaying the loading of the next page. This API is typically used for analytics and performance monitoring purposes.
const data = {
event: 'button_click',
timestamp: Date.now(),
user_id: '12345',
};
// Send data to the server asynchronously using the Beacon API
navigator.sendBeacon('/api/log-event', JSON.stringify(data));
Server-Sent Events (SSE) is a technology that enables a server to push real-time updates to a web client over a single HTTP connection. SSE is often used for applications that require real-time updates, such as live scoreboards, news feeds, or chat applications. SSE is used for light weight one way communication from server to client. Here’s an example of how to use Server-Sent Events in a web application:
Server-Side (Node.js with Express):
const express = require('express');
const app = express();
// Serve a simple HTML page to the client
app.get('/', (req, res) => {
res.sendFile(__dirname + '/index.html');
});
// SSE route for sending updates
app.get('/sse', (req, res) => {
res.setHeader('Content-Type', 'text/event-stream');
res.setHeader('Cache-Control', 'no-cache');
res.setHeader('Connection', 'keep-alive');
// Send a message to the client every 1 second
setInterval(() => {
res.write(`data: ${JSON.stringify({ message: 'Hello, world!' })}\n\n`);
}, 1000);
});
const port = process.env.PORT || 3000;
app.listen(port, () => {
console.log(`Server is running on port ${port}`);
});
In this example, the server sends a message to the client every second using an SSE endpoint (/sse
).
2. Client-Side (HTML and JavaScript):Next, you’ll create an HTML page that listens to SSE updates and displays them. Here’s an example index.html
file:
<!DOCTYPE html>
<html>
<head>
<title>SSE Example</title>
</head>
<body>
<h1>Server-Sent Events Example</h1>
<div id="sse-data"></div>
<script>
const sseDataElement = document.getElementById('sse-data');
// Create an EventSource object to listen for SSE updates
const eventSource = new EventSource('/sse');
eventSource.onmessage = (event) => {
const data = JSON.parse(event.data);
sseDataElement.innerHTML = `Message from server: ${data.message}`;
};
</script>
</body>
</html>
When you run this code, you should see “Hello, world!” messages displayed on the HTML page, updated every second, coming directly from the server.
HTTP long polling is a technique used to achieve real-time updates or push notifications from a server to a client over the HTTP protocol, even in scenarios where full-duplex communication like WebSockets is not available. In long polling, the client sends a request to the server, and the server holds the request open until new data becomes available or a timeout occurs. When new data is ready, the server responds to the client’s request, and the client immediately sends another request to keep the connection open.
const http = require('http');
const url = require('url');
// In-memory storage for messages (replace with a database in a production scenario)
const messages = [];
const server = http.createServer((req, res) => {
const reqUrl = url.parse(req.url, true);
if (reqUrl.pathname === '/poll') {
const timeout = 30000; // You can adjust the timeout as needed (e.g., 30 seconds)
const startTime = Date.now();
const checkForMessages = () => {
if (messages.length > 0) {
res.writeHead(200, { 'Content-Type': 'application/json' });
res.end(JSON.stringify({ message: messages.shift() }));
} else if (Date.now() - startTime > timeout) {
res.writeHead(200, { 'Content-Type': 'application/json' });
res.end(JSON.stringify({ message: 'timeout' }));
} else {
setTimeout(() => {
checkForMessages();
}, 1000); // Polling interval (1 second)
}
};
checkForMessages();
} else if (reqUrl.pathname === '/push' && req.method === 'POST') {
let requestBody = '';
req.on('data', chunk => {
requestBody += chunk.toString();
});
req.on('end', () => {
const parsedBody = JSON.parse(requestBody);
const message = parsedBody.message;
if (message) {
messages.push(message);
res.writeHead(200, { 'Content-Type': 'application/json' });
res.end(JSON.stringify({ status: 'Message added to the queue' }));
} else {
res.writeHead(400, { 'Content-Type': 'application/json' });
res.end(JSON.stringify({ status: 'No message provided' }));
}
});
} else {
res.writeHead(404, { 'Content-Type': 'text/plain' });
res.end('Not Found');
}
});
const PORT = process.env.PORT || 3000;
server.listen(PORT, () => {
console.log(`Server is running on port ${PORT}`);
});
In this Node.js example:
/poll
and /push
endpoints./poll
, it waits for messages to become available and responds when a message is ready or when a timeout occurs./push
, it accepts POST requests to add messages to the queue.Client (HTML/JavaScript)
<!DOCTYPE html>
<html>
<head>
<title>HTTP Long Polling Example</title>
</head>
<body>
<div id="messages"></div>
<script>
const messagesDiv = document.getElementById('messages');
function pollServer() {
fetch('/poll')
.then(response => response.json())
.then(data => {
if (data.message) {
messagesDiv.innerHTML += '<p>' + data.message + '</p>';
}
pollServer(); // Continue polling
})
.catch(error => {
console.error('Error:', error);
pollServer(); // Continue polling even in case of errors
});
}
// Start polling when the page loads
pollServer();
</script>
</body>
</html>
Reference counting vs Mark and Sweep. Read more here.
There are a lot of things to consider other than compensation, when accepting an offer especially in the Software Industry. Some of them are
Given an array of integers, move all the zeroes to the beginning of the array, leaving the order of the other integers unaltered. This operation has to be done in place.
Time Complexity O(n)
Java
package algos; public class moveZeroesToStart { public static int[] moveToStart(int[] input) { int n = input.length - 1, count = n-1; for (int i = n - 1; i >= 0; i--) { if (input[i] != 0) { input[count--] = input[i]; } } while (count >= 0) { input[count--] = 0; } return input; } public static int[] moveToEnd(int[] input) { int n = input.length, count = 0; for (int i = 0; i < n; i++) { if (input[i] != 0) { input[count++] = input[i]; } } while (count < n) { input[count++] = 0; } return input; } public static void main(String[] args) { int[] arr = { 3, 2, 0, 1, 5, 0, 0 }; arr = moveToStart(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } System.out.println(); arr = moveToEnd(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }
Output
0 0 0 3 2 1 5 3 2 1 5 0 0 0
JavaScript
var moveToStart = function(input) { var n = input.length - 1; var count = n-1; for (var i = n - 1; i >= 0; i--) { if (input[i] !== 0) { input[count--] = input[i]; } } while (count >= 0) { input[count--] = 0; }; return input; }; var moveToEnd = function(input) { var n = input.length; var count = 0; for (var i = 0; i < n; i++) { if (input[i] !== 0) { input[count++] = input[i]; } } while (count < n) { input[count++] = 0; }; return input; }; var arr = [3, 2, 0, 1, 5, 0, 0]; arr = moveToStart(arr); for (var i = 0; i < arr.length; i++) { console.info(arr[i]); } console.log(); arr = moveToEnd(arr); for (var i = 0; i < arr.length; i++) { console.info(arr[i]); }
Follow Up
To do the opposite and move zeroes to the end of the array we need to start from the beginning with the counter at 0.
Calculate the maximum amount of water that can held within a bar graph without overflow.
The amount of water that can be held at any point is the difference of the minimum of the maximum of left bars and maximum of right bars and the height of that point.
If we don’t precompute the maximum values on left and right for every index, the time complexity becomes O(n^2). So we go with the precompute option.
Time Complexity O(n)
Space Complexity O(n)
Code
package algos; import java.lang.Math; public class maxWater { public static void main(String[] args) { int[] input = { 5, 1, 3, 4 }; int len = input.length; int[] left = new int[len]; int[] right = new int[len]; int rightMax = input[len - 1], leftMax = input[0]; for (int i = 1; i < len - 1; i++) { leftMax = Math.max(leftMax, input[i]); left[i] = leftMax; rightMax = Math.max(rightMax, input[len - 1 - i]); right[len - 1 - i] = rightMax; } int count = 0; for (int i = 1; i < len - 1; i++) { count += Math.min(left[i], right[i]) - input[i]; } System.out.println(count); } }
Output
4
The following code handles negatives as well.
Time Complexity O(n)
Space Complexity O(1)
Code
package algos; public class maxThreeProd { public static int maxThree(int[] input) { if (input.length <= 3) { int ret = 1; for (int i = 0; i < input.length; i++) { ret *= input[i]; } return ret; } int m1 = Integer.MIN_VALUE; int m2 = Integer.MIN_VALUE; int m3 = Integer.MIN_VALUE; int l1 = Integer.MAX_VALUE; int l2 = Integer.MAX_VALUE; for (int i = 0; i < input.length; i++) { if (input[i] > m1) { m3 = m2; m2 = m1; m1 = input[i]; } else if (input[i] > m2) { m3 = m2; m2 = input[i]; } else if (input[i] > m3) { m3 = input[i]; } if (input[i] < l1) { l2 = l1; l1 = input[i]; } else if (input[i] < l2) { l2 = input[i]; } } return Math.max(l1 * l2 * m3, m1 * m2 * m3); } public static void main(String[] args) { int[] input = { 1, 5, 3, 2 }; if (input.length == 0) System.out.println("null"); else System.out.println(maxThree(input)); } }
Output
30
var n = '100'; var arr = []; for (var i = 0; i < n.length; i++) { arr.push(parseInt(n.charAt(i))); } var i = 0; while (i < (n.length - 1)) { for (i = 0; i < (n.length - 1); i++) { if (arr[i] > arr[i + 1]) { arr[i] = arr[i] - 1; for (var j = i + 1; j < n.length; j++) { arr[j] = 9; } break; } } } console.log(arr);
We use dynamic programming to solve this.
Space complexity = O(2*n)
Time complexity = O(n^3).
public class maxSquareX { public static void main(String[] args) { char[][] input = { { 'X', '0', 'X', 'X', 'X' }, { 'X', 'X', 'X', 'X', 'X' }, { 'X', 'X', '0', 'X', '0' }, { 'X', 'X', 'X', 'X', 'X' }, { 'X', 'X', 'X', '0', '0' }, }; int[][] rows = new int[input.length][input[0].length]; int[][] cols = new int[input.length][input[0].length]; for (int i = 0; i < input.length; i++) { for (int j = 0; j < input[0].length; j++) { if (input[i][j] == '0') { rows[i][j] = cols[i][j] = 0; } else { rows[i][j] = (i == 0) ? 1 : rows[i - 1][j] + 1; cols[i][j] = (j == 0) ? 1 : cols[i][j - 1] + 1; } } } int max = 1; // since this is the minimum answer we can get int small; // Start from bottom right for (int i = input.length - 1; i >= 0; i--) { for (int j = input[0].length - 1; j >= 0; j--) { small = Math.min(rows[i][j], cols[i][j]); while (small > max) { // we use index [j - small + 1] because small might be // input.length + 1 and when that is subtracted from 'j' we // might get an 'ArrayIndexOutOfBoundsException'. if (small <= rows[i][j - small + 1] && small <= cols[i - small + 1][j]) { max = small; } else small--; } } } } }
Output
3
Bounded Knapsack (1/0) Solution in Java using Dynamic Programming
There are few items with weights and values, we need to find the items that contribute the maximum value that can be stored in knapsack of a particular capacity.
There are only 2 choices for each item, i.e. it can either be included or excluded from the bag.
Space complexity O(i*(capacity+1))
Time complexity O(i*(capacity+1))
package algos; import java.math.MathContext; import java.util.ArrayList; class item { public int weight; public int value; public item(int weight, int value) { this.weight = weight; this.value = value; } } public class knapsackB { public static void main(String[] args) { item[] items = { new item(1, 1), new item(3, 4), new item(4, 5), new item(5, 7) }; int bag = 7; int[][] result = new int[items.length][bag + 1]; for (int it = 0; it < items.length; it++) { for (int i = 0; i <= bag; i++) { if (items[it].weight <= i) { if (it != 0) result[it][i] = Math.max(result[it - 1][i], items[it].value + result[it - 1][i - items[it].weight]); else result[it][i] = items[it].value; } else { // use previous if (it != 0) result[it][i] = result[it - 1][i]; else result[it][i] = 0; } } } // Printing Result matrix for (int it = 0; it < items.length; it++) { for (int i = 0; i <= bag; i++) { System.out.print(result[it][i] + " "); } System.out.println(""); } int itemIndex = items.length - 1; int weightIndex = bag; // Printing the answer System.out.println(result[itemIndex][weightIndex]); ArrayList < item > finalBag = new ArrayList < item > (); while (weightIndex != 0) { if (result[itemIndex][weightIndex] != result[itemIndex - 1][weightIndex]) { // include this finalBag.add(items[itemIndex]); weightIndex = weightIndex - items[itemIndex].weight; itemIndex--; } else { itemIndex--; } } // Printing the bag for (item i: finalBag) { System.out.println(i.value); } } }
Output
0 1 1 1 1 1 1 1 0 1 1 4 5 5 5 5 0 1 1 4 5 6 6 9 0 1 1 4 5 7 8 9 9 5 4
Using Recursion
This is very inefficient.
/* A Naive recursive implementation of 0-1 Knapsack problem */ class Knapsack { // A utility function that returns maximum of two integers static int max(int a, int b) { return (a > b)? a : b; } // Returns the maximum value that can be put in a knapsack of capacity W static int knapSack(int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0) return 0; // If weight of the nth item is more than Knapsack capacity W, then // this item cannot be included in the optimal solution if (wt[n-1] > W) return knapSack(W, wt, val, n-1); // Return the maximum of two cases: // (1) nth item included // (2) not included else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1) ); } public static void main(String args[]) { int val[] = new int[]{60, 100, 120}; int wt[] = new int[]{10, 20, 30}; int W = 50; int n = val.length; System.out.println(knapSack(W, wt, val, n)); } }
Output
220
Time Complexity = O(2^n).
The recursion tree is for following sample inputs. wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30} K(3, 2) ---------> K(n, W) / \ / \ K(2,2) K(2,1) / \ / \ / \ / \ K(1,2) K(1,1) K(1,1) K(1,0) / \ / \ / \ / \ / \ / \ K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0)
Bounded Knapsack with Fractions allowed
In the above problem if we are allowed to include fractions, then we sort the items based on their value to weight ratios in descending order and include them in the knapsack, until it is full.
package algos; import java.util.ArrayList; import java.util.PriorityQueue; class item { public int weight; public int value; public item(int weight, int value) { this.weight = weight; this.value = value; } public class knapsackF { public static void main(String[] args) { PriorityQueue < item > queue = new PriorityQueue < item > (4, (a, b) - > -Double.compare(a.value / (double) a.weight, b.value / (double) b.weight)); queue.add(new item(1, 1)); queue.add(new item(3, 4)); queue.add(new item(4, 5)); queue.add(new item(5, 7)); ArrayList < item > bag = new ArrayList < item > (); int capacity = 7; double val = 0; item current; while (!queue.isEmpty() && capacity != 0) { current = queue.poll(); bag.add(current); if (current.weight <= capacity) { val += current.value; capacity -= current.weight; } else { val += ((capacity / (double) current.weight) * current.value); capacity = 0; } } System.out.println(val); for (item i: bag) { System.out.println(i.value); } } }
Output
9.666666666666666 7 4
Unbounded Knapsack solution
In this approach we use Dynamic programming to store the capacities incrementally to get the required maximum value at capacity.
Time complexity = O(i*(c+1))
Space complexity = O(c+1)
package algos; class item { public int weight; public int value; public item(int weight, int value) { this.weight = weight; this.value = value; } public class knapsackU { public static void main(String[] args) { item[] items = { new item(1, 1), new item(3, 4), new item(4, 5), new item(5, 7) }; int capacity = 7; int[] capacityList = new int[capacity + 1]; for (int cap = 0; cap <= capacity; cap++) { for (item i: items) { if (i.weight <= cap) { capacityList[cap] = Math.max(capacityList[cap], i.value + capacityList[cap - i.weight]); } } } System.out.println(capacityList[capacity]); } }
Output
9
Unbounded Knapsack with Fractions allowed
This is a straightforward implementation, as we need to find the maximum ratio among the given items (value/weight) and then multiply it with the capacity of the bag.
Time complexity = O(i)
Space complexity = O(1)
package algos; import java.math.MathContext; class item { public int weight; public int value; public item(int weight, int value) { this.weight = weight; this.value = value; } public class knapsackUF { public static void main(String[] args) { item[] items = {new item(1,1), new item(3,4), new item(4,5), new item(5,7)}; int capacity = 7; double maxRatio = 0; for(item i: items) { maxRatio = Math.max(maxRatio, i.value/(double) i.weight); } System.out.println(maxRatio*capacity); } }
Output
9.799999999999999
This is straight forward implementation of the DFS (Depth First Search) traversal algorithm using recursion.
var obj = { baz: { foo: { bar: "5" }, hell: { sin: "0" } }, a: { b: "1" } }; var hash = {}; var str = ''; var dfs = function(obj, str) { for (var key in obj) { if (obj.hasOwnProperty(key)) { if (typeof obj[key] === 'string') hash[str + key] = obj[key]; else { dfs(obj[key], str + key + '.'); } } } }; dfs(obj, str); console.log(hash);
var obj = { baz: { foo: { bar: "5" }, hell: { sin: "0" } }, a: { b: "1" } }; var tracker = []; var hashMap = {}; var hashKey = ''; function dfs(obj, tracker) { for (var key in obj) { if (obj.hasOwnProperty(key)) { if (typeof obj[key] == "string") { tracker.push(key); hashKey = appendArray(tracker); hashMap[hashKey] = obj[key]; tracker.pop(); } else { tracker.push(key); dfs(obj[key], tracker); tracker.pop(); } } } } dfs(obj, tracker); console.log(hashMap); function appendArray(arr) { var ret = ''; for (var i = 0; i < arr.length; i++) { ret = ret + '.' + arr[i]; } return ret.substring(1, ret.length); }
const test = {
baz: {
foo: {
bar: "5"
},
hell: {
sin: "0"
}
},
a: {
b: "1"
}
};
const flatten = (obj, str = '', temp = {}) => {
for (const [key, val] of Object.entries(obj)) {
if (typeof val === 'object') {
flatten(val, `${str}${key}.`, temp);
} else {
temp[`${str}${key}`] = val;
}
}
};
const output = {};
flatten(test, '', output);
console.log(output);
Output
Object {baz.foo.bar: "5", baz.another.bar: "0", a.b: "1"}