/**
* @param {number[]} prices
* @return {number}
*/
const maxProfit = function(prices) {
let min = prices[0];
let max = 0;
for (const price of prices) {
min = Math.min(min, price);
max = Math.max(max, price - min);
}
return max;
};
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5
n = size of input array
Time complexity: O(n)
Space complexity: O(1)
/**
* @param {number[]} height
* @return {number}
*/
const maxArea = (height) => {
let low = 0;
let high = height.length - 1;
let max = 0;
while (low < high) {
max = Math.max(max, (high - low) * Math.min(height[low], height[high]));
if (height[low] <= height[high]) {
low++
} else {
high--;
}
}
return max;
};
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
Group Permutations of the same strings in a given list in Javascript:
/**
* @param {string[]} strs
* @return {string[][]}
*/
const groupAnagrams = function(strs) {
const obj = {};
for (const str of strs) {
const key = str.split('').sort().join('');
(obj[key] || (obj[key] = [])).push(str);
}
return Object.values(obj);
};
console.log(groupAnagrams(['abc', 'bbc', 'cab', 'ccc']));
// [["abc", "cab"], ["bbc"], ["ccc"]]
Javascript (ES6) code to rotate a Image or a 2D square matrix in place:
const rotate = (matrix) => {
const n = matrix.length;
for (let layer = 0; layer < Math.floor(n / 2); layer++) {
for (let i = layer; i < n - layer - 1; i++) {
const temp = matrix[layer][i];
matrix[layer][i] = matrix[n - i - 1][layer];
matrix[n - i - 1][layer] = matrix[n - layer - 1][n - i - 1];
matrix[n - layer - 1][n - i - 1] = matrix[i][n - layer - 1];
matrix[i][n - layer - 1] = temp;
}
}
};
Demo
Output
rotate([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
]);
/*
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3],
]
*/Event emitter pattern implemented using a Javascript ES6 class.
class EventEmitter {
constructor() {
this.events = {};
}
subscribe = (event, cb) => {
(this.events[event] || (this.events[event] = [])).push(cb);
return {
unsubscribe: () => {
(this.events[event] && this.events[event]).splice(this.events[event].indexOf(cb) >>> 0, 1);
}
};
};
emit = (event, ...rest) => {
(this.events[event] || []).forEach(val => {
val(...rest);
});
};
}
const eventEmitter = new EventEmitter();
const ret1 = eventEmitter.subscribe('test', () => {
console.log('test1');
});
const ret2 = eventEmitter.subscribe('test', () => {
console.log('test2');
});
const ret3 = eventEmitter.subscribe('test3', () => {
console.log('test3');
});
t.emit('test'); // test1, test2
ret1.unsubscribe();
ret1.unsubscribe(); // Should still function as expected.
t.emit('test'); // test2
We are working on a security system for a badged-access room in our company’s building.
We want to find employees who badged into our secured room unusually often. We have an unordered list of names and entry times over a single day. Access times are given as numbers up to four digits in length using 24-hour time, such as “800” or “2250”.
Write a function that finds anyone who badged into the room three or more times in a one-hour period. Your function should return each of the employees who fit that criteria, plus the times that they badged in during the one-hour period. If there are multiple one-hour periods where this was true for an employee, just return the earliest one for that employee.
badge_times = [
[‘Paul’, ‘1355’],
[‘Jennifer’, ‘1910’],
[‘Jose’, ‘835’],
[‘Jose’, ‘830’],
[‘Paul’, ‘1315’],
[‘Chloe’, ‘0’],
[‘Chloe’, ‘1910’],
[‘Jose’, ‘1615’],
[‘Jose’, ‘1640’],
[‘Paul’, ‘1405’],
[‘Jose’, ‘855’],
[‘Jose’, ‘930’],
[‘Jose’, ‘915’],
[‘Jose’, ‘730’],
[‘Jose’, ‘940’],
[‘Jennifer’, ‘1335’],
[‘Jennifer’, ‘730’],
[‘Jose’, ‘1630’],
[‘Jennifer’, ‘5’],
[‘Chloe’, ‘1909’],
[‘Zhang’, ‘1’],
[‘Zhang’, ’10’],
[‘Zhang’, ‘109’],
[‘Zhang’, ‘110’],
[‘Amos’, ‘1’],
[‘Amos’, ‘2’],
[‘Amos’, ‘400’],
[‘Amos’, ‘500’],
[‘Amos’, ‘503’],
[‘Amos’, ‘504’],
[‘Amos’, ‘601’],
[‘Amos’, ‘602’],
[‘Paul’, ‘1416’],
];
Expected output (in any order)
{
Paul: [‘1315’, ‘1355’, ‘1405’],
Jose: [‘830’, ‘835’, ‘855’, ‘915’, ‘930’],
Zhang: [’10’, ‘109’, ‘110’],
Amos: [‘500’, ‘503’, ‘504’],
}
n: length of the badge records array.
const badge_records = [
['Paul', '1355'],
['Jennifer', '1910'],
['Jose', '835'],
['Jose', '830'],
['Paul', '1315'],
['Chloe', '0'],
['Chloe', '1910'],
['Jose', '1615'],
['Jose', '1640'],
['Paul', '1405'],
['Jose', '855'],
['Jose', '930'],
['Jose', '915'],
['Jose', '730'],
['Jose', '940'],
['Jennifer', '1335'],
['Jennifer', '730'],
['Jose', '1630'],
['Jennifer', '5'],
['Chloe', '1909'],
['Zhang', '1'],
['Zhang', '10'],
['Zhang', '109'],
['Zhang', '110'],
['Amos', '1'],
['Amos', '2'],
['Amos', '400'],
['Amos', '500'],
['Amos', '503'],
['Amos', '504'],
['Amos', '601'],
['Amos', '602'],
['Paul', '1416']
];
const getOftenUsersOfBadge = (records) => {
records.sort((a, b) => a[1] - b[1]);
const obj = {};
for (const [name, time] of records) {
(obj[name] || (obj[name] = [])).push(time);
}
const result = {};
for (const [key, val] of Object.entries(obj)) {
const len = val.length;
if (len >= 3) {
for (let i = 2; i < len; i++) {
if (val[i] - val[i - 2] <= 100) {
const start = i - 2;
const max = parseInt(val[start]) + 100;
while (parseInt(val[++i]) <= max) {}
result[key] = val.slice(start, i);
break;
}
}
}
}
return result;
};
console.log(getOftenUsersOfBadge(badge_records));
/* Explanation:
1) Sort the input records based on times in increasing order.
2) Build a map { name : [time1, time2, ... timen], }
3) Computing times
1 --> 00:01
101 --> 01:01
diff is 100 for 1 hour.
No need to check (i < len) in the while loop as we break the loop on first failure of condition.
*/
const twoDarray = Array(3).fill(0).map(x => Array(3).fill(0));
console.log(twoDarray);
// [[0, 0, 0], [0, 0, 0], [0, 0, 0]]Given an ordered list of employees who used their badge to enter or exit the room, write a function that returns two collections:
1. All employees who didn’t use their badge while exiting the room – they recorded an enter without a matching exit. (All employees are required to leave the room before the log ends.)
2. All employees who didn’t use their badge while entering the room – they recorded an exit without a matching enter. (The room is empty when the log begins.)
Each collection should contain no duplicates, regardless of how many times a given employee matches the criteria for belonging to it.
records1 = [
["Martha", "exit"],
["Paul", "enter"],
["Martha", "enter"],
["Steve", "enter"],
["Martha", "exit"],
["Jennifer", "enter"],
["Paul", "enter"],
["Curtis", "exit"],
["Curtis", "enter"],
["Paul", "exit"],
["Martha", "enter"],
["Martha", "exit"],
["Jennifer", "exit"],
["Paul", "enter"],
["Paul", "enter"],
["Martha", "exit"],
["Paul", "enter"],
["Paul", "enter"],
["Paul", "exit"],
["Paul", "exit"]
]
Expected output: ["Paul", "Curtis", "Steve"], ["Martha", "Curtis", "Paul"]
Other test cases:
records2 = [
["Paul", "enter"],
["Paul", "exit"],
]
Expected output: [], []
records3 = [
["Paul", "enter"],
["Paul", "enter"],
["Paul", "exit"],
["Paul", "exit"],
]
Expected output: ["Paul"], ["Paul"]
records4 = [
["Paul", "enter"],
["Paul", "exit"],
["Paul", "exit"],
["Paul", "enter"],
]
Expected output: ["Paul"], ["Paul"]const mismatches = (records) => {
const obj = {};
const notExited = [];
const notEntered = [];
for (const [name, state] of records) {
if (!(name in obj)) {
obj[name] = 0;
}
if (state === 'enter') {
obj[name]++;
} else {
obj[name]--;
}
if (obj[name] > 1) {
if (!notExited.includes(name)) {
notExited.push(name);
}
obj[name] = 0;
}
if (obj[name] < 0) {
if (!notEntered.includes(name)) {
notEntered.push(name);
}
obj[name] = 0;
}
}
for (const [key, val] of Object.entries(obj)) {
if (val === 1) {
if (!notExited.includes(key)) {
notExited.push(key);
}
}
}
return [notExited, notEntered];
};
console.log(mismatches([
["Martha", "exit"],
["Paul", "enter"],
["Martha", "enter"],
["Steve", "enter"],
["Martha", "exit"],
["Jennifer", "enter"],
["Paul", "enter"],
["Curtis", "exit"],
["Curtis", "enter"],
["Paul", "exit"],
["Martha", "enter"],
["Martha", "exit"],
["Jennifer", "exit"],
["Paul", "enter"],
["Paul", "enter"],
["Martha", "exit"],
["Paul", "enter"],
["Paul", "enter"],
["Paul", "exit"],
["Paul", "exit"]
]),
mismatches([
["Paul", "enter"],
["Paul", "exit"]
]),
mismatches([
["Paul", "enter"],
["Paul", "enter"],
["Paul", "exit"],
["Paul", "exit"],
]),
mismatches([
["Paul", "enter"],
["Paul", "exit"],
["Paul", "exit"],
["Paul", "enter"],
]));
Implement a method to search for an element in DOM by it’s Id. We use Breadth First Search (BFS) algorithm to traverse the DOM and store the elements in a queue in the following example.
Example: document.getElementById(‘demo’)
<div id="demo">
<div>1</div>
<div>2</div>
<div>
<div id="hello">Hello world!</div>
</div>
<div>3</div>
</div>
<script>
const getElementById = (element, id) => {
const queue = [element];
while (queue.length) {
const curr = queue.shift();
if (curr.id === id) {
return curr;
}
if (curr.children.length) {
queue.push(...curr.children);
}
}
};
console.log(getElementById(document.documentElement, 'hello').innerHTML); // Hello world!
</script>
/**
* @param {string} str
* @return {boolean}
*/
const isValid = function(str) {
/*
if (typeof str !== 'string') {
return false;
}
*/
const stack = [];
const map = {
')': '(',
'}': '{',
']': '['
};
for (const char of str) {
if (Object.values(map).includes(char)) {
stack.push(char);
} else if (Object.keys(map).includes(char)) {
if (map[char] !== stack[stack.length - 1]) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
};
console.log(
isValid('{{[test]})'), // false
isValid('({[test]})'), // true
isValid('({['), // false
isValid(''), // true
);
/* You can verify the following cases as well, by uncommenting the if statement at the start of the method.
console.log(
isValid(), // false
isValid(null), // false
isValid(0), // false
isValid(1), // false
isValid(1.12) // false
);
*/