- Published on
BigFrontEnd Category 1 Algorithms
- Authors
- Name
- Yinhuan Yuan
Introduction
This blog post summarizes the algorithm implementation questions found on BigFrontEnd.Dev.
- 1. Binary Search Questions
- 1.implement Binary Search (unique)
- 2.search first index with Binary Search(possible duplicate array)
- 3.search last index with Binary Search(possible duplicate array)
- 4.search element right before target with Binary Search(possible duplicate array)
- 5.search element right after target with Binary Search(possible duplicate array)
- 6.first bad version
- 7.implement Math.sqrt()
- 2. Sorting Questions
- 3. Linked List Questions
- 4. Tree Questions
- 5. Calculator Questions
- 6. Backtracking Questions
- 7. Other Questions
1. Binary Search Questions
1.implement Binary Search (unique)
37.https://bigfrontend.dev/problem/implement-Binary-Search-Unique
Even in Front-End review, basic algorithm technique like Binary Search are likely to be asked.
You are given an unique & ascending array of integers, please search for its index with Binary Search.
If not found, return -1
note
Please don't use Array.prototype.indexOf()
, it is not our goal.
Solution:
We can follow the pattern from Leetcode problem 10 and divide the search range from 0 to n (the length of the array) into two parts: less than the target, or greater than or equal to the target.Then, we can use the pattern code to solve it.
/**
* @param {number[]} arr - ascending unique array
* @param {number} target
* @return {number}
*/
function binarySearch(arr, target) {
let [lo, hi] = [0, arr.length]
const condition = (mid) => arr[mid] >= target
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2)
if (condition(mid)) {
hi = mid
} else {
lo = mid + 1
}
}
return arr[lo] === target ? lo : -1
}
2.search first index with Binary Search(possible duplicate array)
48.https://bigfrontend.dev/problem/search-first-index-with-Binary-Search-duplicate-array
Your are given a sorted ascending array of number, but might have duplicates, you are asked to return the first index of a target number.
If not found return -1.
note
Please don't use Array.prototype.indexOf()
, it is not our goal.
Solution:
We can use the same approach as in problem 1, which involves implementing Binary Search for unique elements.
/**
* @param {number[]} arr - ascending array with duplicates
* @param {number} target
* @return {number}
*/
// Find the lefest insertion position to maintain the order.
function firstIndex(arr, target) {
let [lo, hi] = [0, arr.length]
const condition = (mid) => arr[mid] >= target
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2)
if (condition(mid)) {
hi = mid
} else {
lo = mid + 1
}
}
return arr[lo] === target ? lo : -1
}
3.search last index with Binary Search(possible duplicate array)
49.https://bigfrontend.dev/problem/search-last-index-with-Binary-Search-possible-duplicate-array
Your are given a sorted ascending array of number, but might have duplicates, you are asked to return the last index of a target number.
If not found return -1.
note
Please don't use Array.prototype.lastIndexOf()
, it is not our goal.
Solution:
We can follow the pattern from Leetcode problem 10 and divide the search range from 0 to n (the length of the array) into two parts: less than or equal to the target, or greater than the target.Then, we can use the pattern code to solve it.
/**
* @param {number[]} arr - ascending array with duplicates
* @param {number} target
* @return {number}
*/
function lastIndex(arr, target) {
let [lo, hi] = [0, arr.length]
const condition = (mid) => arr[mid] > target
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2)
if (condition(mid)) {
hi = mid
} else {
lo = mid + 1
}
}
if (lo === 0) return -1
return lo - 1
}
4.search element right before target with Binary Search(possible duplicate array)
Your are given a sorted ascending array of number, but might have duplicates, you are asked to return the element right before first appearance of a target number.
If not found return undefined
.
note
Please don't use Array.prototype.indexOf()
, it is not our goal.
Solution:
We can use the same approach as in problem 1, which involves implementing Binary Search for unique elements.
/**
* @param {number[]} arr - ascending array with duplicates
* @param {number} target
* @return {number}
*/
function elementBefore(arr, target) {
let [lo, hi] = [0, arr.length]
const condition = (mid) => arr[mid] >= target
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2)
if (condition(mid)) {
hi = mid
} else {
lo = mid + 1
}
}
// if (lo === 0) return undefined;
return arr[lo] === target ? arr[lo - 1] : undefined
}
5.search element right after target with Binary Search(possible duplicate array)
Your are given a sorted ascending array of number, but might have duplicates, you are asked to return the element right after last appearance of a target number.
If not found return undefined
.
note
Please don't use Array.prototype.lastIndexOf()
, it is not our goal.
Solution:
Similar to problem 3, which involves searching for the last index with Binary Search in a possible duplicate array, we divide the search range from 0 to n (the length of the array) into two parts: less than or equal to the target, and greater than the target.
/**
* @param {number[]} arr - ascending array with duplicates
* @param {number} target
* @return {number}
*/
function elementAfter(arr, target) {
let [lo, hi] = [0, arr.length]
const condition = (mid) => arr[mid] > target
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2)
if (condition(mid)) {
hi = mid
} else {
lo = mid + 1
}
}
return arr[lo - 1] === target ? arr[lo] : undefined
}
6.first bad version
10.https://bigfrontend.dev/problem/first-bad-version
Say you have multiple versions of a program, write a program that will find and return the first bad revision given a isBad(version)
function.
Versions after first bad version are supposed to be all bad versions.
notes
Inputs are all non-negative integers if none found, return -1
/**
* @param {IsBad} isBad
*/
function firstBadVersion(isBad) {
// firstBadVersion receive a check function isBad
// and should return a closure which accepts a version number(integer)
return (version) => {
// write your code to return the first bad version
// if none found, return -1
let left = 0
let right = version
while (left < right) {
const mid = left + Math.floor((right - left) / 2)
if (isBad(mid)) {
right = mid
} else {
left = mid + 1
}
}
return isBad(left) ? left : -1
}
}
7.implement Math.sqrt()
103.https://bigfrontend.dev/problem/implement-Math-sqrt
Math.sqrt()
helps us getting the square root of a number.
Can your write your own mySqrt() ? You should return the integer part only, truncating the fraction part.
mySqrt(0)
// 1
mySqrt(1)
// 1
mySqrt(2)
// 1
mySqrt(4)
// 2
mySqrt(NaN)
// NaN
Attention for the special case listed up in the spec.
Follow-up
What is time & space complexity of your solution ? Can you do better?
/**
* @param {any} x
* @return {number}
*/
function mySqrt(x) {
if (isNaN(x)) return NaN
if (x < 0) return NaN
if (!isFinite(x)) return Infinity
let lo = 0
let hi = x
while (hi - lo > 0.5) {
const mid = (hi + lo) / 2
if (mid * mid > x) {
hi = mid
} else {
lo = mid
}
}
return Math.floor(hi)
}
2. Sorting Questions
1.implement Bubble Sort
40.https://bigfrontend.dev/problem/implement-Bubble-Sort
Now you are asked to implement Bubble Sort, which sorts an integer array in ascending order.
Do it in-place, no need to return anything.
Follow-up
What is time cost for average / worst case ? Is it stable?
Solution:
function bubbleSort(arr) {
const n = arr.length
for (let i = 0; i < n; i++) {
// [0, n - 1 - i] is not sorted.
// [n - i, n - 1] is sorted.
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap
;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
2.implement Merge Sort
41.https://bigfrontend.dev/problem/implement-Merge-Sort
Now you are asked to implement Merge Sort, which sorts an integer array in ascending order.
Do it in-place, no need to return anything.
Follow-up
What is time cost for average / worst case ? Is it stable?
function mergeSort(arr) {
if (arr.length <= 1) {
return
}
const mergeInPlace = (arr, left, mid, right) => {
let start2 = mid + 1
// No need to merge
if (arr[mid] <= arr[start2]) {
return
}
while (left <= mid && start2 <= right) {
if (arr[left] <= arr[start2]) {
left++
} else {
// find arr[left] > arr[start2]
// shift all element in [left, start2 - 1] to right one step
let value = arr[start2]
let index = start2
while (index !== left) {
arr[index] = arr[index - 1]
index--
}
// Move the original value in starts to left.
arr[left] = value
left++
mid++
start2++
}
}
}
const mergeSortInPlace = (arr, start, end) => {
if (start === end) {
return
}
if (start + 1 === end) {
if (arr[start] > arr[end]) {
// swap
;[arr[start], arr[end]] = [arr[end], arr[start]]
}
return
}
const mid = Math.floor((start + end) / 2)
mergeSortInPlace(arr, start, mid)
mergeSortInPlace(arr, mid + 1, end)
mergeInPlace(arr, start, mid, end)
}
mergeSortInPlace(arr, 0, arr.length - 1)
}
3.implement Insertion Sort
42.https://bigfrontend.dev/problem/implement-Insertion-Sort
Now you are asked to implement Insertion Sort, which sorts an integer array in ascending order.
Do it in-place, no need to return anything.
Follow-up
What is time cost for average / worst case ? Is it stable?
The subarray [0, i - 1] is sorted. Then, insert arr[i]
or key
to the left subarray [0, i - 1].
/**
* @param {number[]} arr
*/
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i]
let j = i - 1
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j = j - 1
}
// break when arr[j] <= key and arr[j + 1] has been backuped.
arr[j + 1] = key
}
}
4.implement Quick Sort
43.https://bigfrontend.dev/problem/implement-Quick-Sort
Now you are asked to implement Quick Sort, which sorts an integer array in ascending order.
Do it in-place, no need to return anything.
Follow-up
What is time cost for average / worst case ? Is it stable?
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
// Partition the array and get the pivot index
let pi = partition(arr, low, high)
// Recursively sort elements before partition and after partition
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
}
}
function partition(arr, low, high) {
// Choose the rightmost element as pivot
let pivot = arr[high]
let i = low - 1
for (let j = low; j < high; j++) {
// If the current element is smaller than or equal to the pivot
if (arr[j] <= pivot) {
i++
// Swap arr[i] and arr[j]
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
// [low, i] are less or equal than pivot
// [i + 1, high] are larger than pivot.
// Swap arr[i + 1] and arr[high] (or pivot)
;[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]
return i + 1
}
// Example usage:
let array = [10, 7, 8, 9, 1, 5]
quickSort(array)
console.log('Sorted array:', array)
5.implement Selection Sort
44.https://bigfrontend.dev/problem/implement-Selection-Sort
Now you are asked to implement Selection sort, which sorts an integer array in ascending order.
Do it in-place, no need to return anything.
Follow-up
What is time cost for average / worst case ? Is it stable?
/**
* @param {number[]} arr
*/
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
// find the index of element with minimal value betwee i and n - 1
let smallestIndex = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[smallestIndex]) {
smallestIndex = j
}
}
if (i !== smallestIndex) {
// swap i and smallestIndex
;[arr[i], arr[smallestIndex]] = [arr[smallestIndex], arr[i]]
}
}
}
3. Linked List Questions
1.reverse a linked list
47.https://bigfrontend.dev/problem/Reverse-a-linked-list
Another basic algorithm even for Front End developers.
You are asked to reverse a linked list.
Suppose we have Node interface like this
class Node {
new(val: number, next: Node);
val: number
next: Node
}
We can then chain nodes together to create a linked list.
const Three = new Node(3, null)
const Two = new Node(2, Three)
const One = new Node(1, Two)
//now we have a linked list
// 1 → 2 → 3
Now how can you reverse it to 3 → 2 → 1 ? you can modify the next property of each node, but not the val.
Follow up
Could you solve it with and without recursion?
function reverseLinkedListRecursive(head) {
// Base case: If head is empty or has reached the list end
if (head === null || head.next === null) {
return head
}
// Reverse the rest of the list
const newHead = reverseLinkedListRecursive(head.next)
// Modify the pointers
head.next.next = head
head.next = null
return newHead
}
function reverseLinkedList(head) {
let prev = null
let current = head
let next = null
while (current !== null) {
next = current.next // Store the next node
current.next = prev // Reverse the current node's pointer
prev = current // Move the prev and current pointers one step forward
current = next
}
return prev // New head of the reversed list
}
2.detect circle in linked list
100.https://bigfrontend.dev/problem/detect-circle-in-linked-list
A Singly Linked List is a bunch of nodes linked in one direction.
class Node {
val: any
next: Node
constructor(val: any, next:Node) {
this.val = val
this.next = next
}
}
const node2 = new Node(2)
const node1 = new Node(1, node2) // connect 1 -> 2
A Node might link to a node before it, thus creating a circle.
Can you write a function to detect it?
Follow-up
What is the space cost for your approach? Can you solve it without extra space?
/**
* @param {string} str
* @return {string}
*/
function hasCircle(head) {
if (!head) return false
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true // There is a cycle
}
}
return false // No cycle
}
4. Tree Questions
1.invert a binary tree
91.https://bigfrontend.dev/problem/invert-a-binary-tree
Inverting a node means swapping its left child and right child. You need to apply this to all nodes. As following figure illustrates.
// This is the type for the node
// type Node = null | {
// value: number
// left: Node
// right: Node
// }
/**
* @param {Node} node
* @returns {Node}
*/
function invert(node) {
if (node === null) {
return null
}
;[node.left, node.right] = [node.right, node.left]
invert(node.left)
invert(node.right)
return node
}
5. Calculator Questions
1.create a tokenizer
119.https://bigfrontend.dev/problem/create-a-tokenizer
For tasks of string processing, in many cases we are given a string, and are asked to understand this string in specific logic and then return the result.
For example, if we are to calculate the result of following expression:
1 * (20 - 300)
before we implement the logic, first we need to get the "keywords"(tokens) and ignore the spaces, like following:
'1', '*', '(', '20', '-', '300', ')'
Then we can process above tokens and get the result easier.
You are asked to implement a tokenize() for arithmetic expression , which works as below:
const tokens = tokenize(' 1 * (20 - 300 ) ')
while (true) {
let token = tokens.next()
if (token.done) {
break
}
console.log(token.value)
}
or you can use for ... of
for (let token of tokens) {
console.log(token)
}
Because it is trivial, in a real interview you talk to interviewer and implement tokenizer later, this could save yourself some time for more important tasks.
Input
input only contains valid non-negative integers with +, -, *, /, (, ) and spaces, space should be ignored.
your method should return an Generator object.
/**
* @param {string} str
* @return {Generator}
*/
function* tokenize(expression) {
const tokenPattern = /\d+|[+*/()-]/g
const tokens = expression.match(tokenPattern)
if (tokens) {
for (const token of tokens) {
yield token
}
}
}
2.calculate arithmetic expression
124.https://bigfrontend.dev/problem/calculate-arithmetic-expression
In 119. create a tokenizer, you are able to extract the tokens from a string with invalid spaces.
Now please calculate() the result of the string. You can use the tokenizer you wrote before.
calculate('1 * (20 - 300 ) ')
// -280
calculate(' 1/0 ')
// Infinity
the input expression is syntactically valid, containing non-negative integers, +, -, *, /, (, ) and spaces Don't use eval()
function* tokenizer(str) {
const tokens = str.match(/\d+|[+*/()-]/g)
if (tokens) {
for (const token of tokens) {
yield token
}
}
}
function infixToPostfix(str) {
const precede = { '(': 1, '+': 2, '-': 2, '*': 3, '/': 3 }
const op_stack = []
const postfix = []
for (const token of tokenizer(str)) {
if (token === '(') {
op_stack.push(token)
} else if (['+', '-', '*', '/'].includes(token)) {
// pop to postfix until the top of stack is less than the current operator.
while (op_stack.length > 0 && precede[op_stack[op_stack.length - 1]] >= precede[token]) {
const op = op_stack.pop()
postfix.push(op)
}
// precede[op_stack.peek()] < precede[token]
op_stack.push(token)
} else if (token === ')') {
// pop to the postfix until the top of stack is (.
while (op_stack.length > 0 && op_stack[op_stack.length - 1] !== '(') {
const op = op_stack.pop()
postfix.push(op)
}
// op_stack.peek() is (
op_stack.pop() // Remove the ( from the stack
} else {
postfix.push(Number(token))
}
}
while (op_stack.length > 0) {
postfix.push(op_stack.pop())
}
return postfix
}
function calculatePostfix(postfix) {
const stack = []
postfix.forEach((token) => {
if (['+', '-', '*', '/'].includes(token)) {
const v2 = stack.pop()
const v1 = stack.pop()
let v
if (token === '+') {
v = v1 + v2
} else if (token === '-') {
v = v1 - v2
} else if (token === '*') {
v = v1 * v2
} else if (token === '/') {
if (v2 === 0) {
v = v1 > 0 ? Infinity : v1 === 0 ? NaN : -Infinity
} else {
v = v1 / v2
}
}
stack.push(v)
} else {
stack.push(token)
}
})
return stack.pop()
}
/**
* @param {string} str
* @returns {Number}
*/
function calculate(str) {
// your code here
const postfix = infixToPostfix(str)
return calculatePostfix(postfix)
}
6. Backtracking Questions
1.All Combinations Of Size K
/**
* This generates an array of unique sub"sets" (represented by ascendingly sorted subarrays)
* of size k out of n+1 numbers from 1 to n.
*
* By using a backtracking algorithm we can incrementally build sub"sets" while dropping candidates
* that cannot contribute anymore to a valid solution.
* Steps:
* - From the starting number (i.e. "1") generate all combinations of k numbers.
* - Once we got all combinations for the given number we can discard it (“backtracks”)
* and repeat the same process for the next number.
*/
export function generateCombinations(n: number, k: number): number[][] {
const combinationsAcc: number[][] = []
const currentCombination: number[] = []
function generateAllCombos(n: number, k: number, startCursor: number): number[][] {
if (k === 0) {
if (currentCombination.length > 0) {
combinationsAcc.push(currentCombination.slice())
}
return combinationsAcc
}
const endCursor = n - k + 2
for (let i = startCursor; i < endCursor; i++) {
currentCombination.push(i)
generateAllCombos(n, k - 1, i + 1)
currentCombination.pop()
}
return combinationsAcc
}
return generateAllCombos(n, k, 1)
}
2.Backtracking Generate Parentheses
/**
* Given a number n pairs of parentheses, generate all combinations of valid parentheses
* @param {number} n: Number of given parentheses
* @return {string[]} result: Array that contains all valid parentheses
* @see https://leetcode.com/problems/generate-parentheses/
*/
const generateParentheses = (n: number): string[] => {
const result: string[] = []
const solve = (chars: string, openParentheses: number, closedParentheses: number) => {
if (openParentheses === n && closedParentheses === n) {
result.push(chars)
return
}
if (openParentheses <= n) {
solve(chars + '(', openParentheses + 1, closedParentheses)
}
if (closedParentheses < openParentheses) {
solve(chars + ')', openParentheses, closedParentheses + 1)
}
}
solve('', 0, 0)
return result
}
export { generateParentheses }
7. Other Questions
1.Find two numbers that sum up to 0
106.https://bigfrontend.dev/problem/Find-two-numbers-that-sum-up-to-0
Given an array of integers, find two number that sums up to 0, return their indices.
There might be multiple pairs, any of them would do. If not found, return null
findTwo([1, 2, 3, -1])
findTwo([1, 2, 3, -1, -2, 0])
findTwo([1, 2, 3, 4])
// null
/**
* @param {number[]} arr
* @return {number[]}
*/
function findTwo(arr) {
const memo = new Map()
const n = arr.length
for (let i = 0; i < n; i++) {
if (memo.has(arr[i])) {
return [memo.get(arr[i]), i]
} else {
memo.set(-arr[i], i)
}
}
return null
}
2.Find the largest difference
107.https://bigfrontend.dev/problem/Find-the-largest-difference
Given an array of numbers, pick any two numbers a and b, we could get the difference by Math.abs(a - b)
.
Can you write a function to get the largest difference?
largestDiff([-1, 2, 3, 10, 9])
// 11, obviously Math.abs(-1 - 10) is the largest
largestDiff([])
// 0
largestDiff([1])
// 0
/**
* @param {number[]} arr
* @return {number}
*/
function largestDiff(arr) {
// your code here
if (arr.length === 0) return 0
const minVal = Math.min(...arr)
const maxVal = Math.max(...arr)
return maxVal - minVal
}
isPrime()
3.create 120.https://bigfrontend.dev/problem/isPrime
A Prime number is a natural number greater than 1 that is divisible only by itself and 1, such as 2,3,5....
You are asked to implement isPrime() to check if a number is prime.
Follow-up
What is the time cost of your implementation ? can you improve your approach to have the fewest comparisons?
/**
* @param {number} num - positive integer
*/
function isPrime(num) {
if (num <= 1) return false // 0 and 1 are not prime numbers
if (num <= 3) return true // 2 and 3 are prime numbers
// Eliminate multiples of 2 and 3 early
if (num % 2 === 0 || num % 3 === 0) return false
// Check for factors from 5 to sqrt(num), skipping even numbers
for (let i = 5; i * i <= num; i += 6) {
if (num % i === 0 || num % (i + 2) === 0) {
return false
}
}
return true
}
4.A number sequence
121.https://bigfrontend.dev/problem/A-number-sequence
Here is a sequence:
'1', first number is 1 '11', since previous number has One(1) 1 '21', since previous number has Two(2) 1s '1211', since previous number has One(1) 2 and One(1) 1 '111221', since previous number has One(1) 1, One(1) 2, Two(2) 1s '312211', since previous number has Three(3) 1s, Two(2) 2s, One(1) 1 .... As explained above, the sequence is generated by counting the digits of previous number.
Please create getNthNum(n) to return the n-th number string in the sequence, n starts from 1.
/**
* @param {number} n - integer
* @returns {string}
*/
function getNthNum(n) {
let ans = '1'
for (let i = 2; i <= n; i++) {
let i = 0
let j = 0
let temp = ''
while (i < ans.length) {
while (i < ans.length && ans[i] === ans[j]) {
i += 1
}
// [j, i - 1] is all same.
temp += `${i - 1 - j + 1}${ans[j]}`
j = i
}
ans = temp
}
return ans
}
5.find median of two sorted array
136.https://bigfrontend.dev/problem/find-median-of-2-sorted-array
Given two sorted array of integers, please return the median.
median([1, 2], [3, 4, 5])
// 3
If there are even numbers, return the average.
median([1, 2], [3, 4])
// 2.5
follow-up
What is the time & space cost of your approach? Could you do better?
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) {
;[nums1, nums2] = [nums2, nums1] // Ensure nums1 is the smaller array
}
const m = nums1.length
const n = nums2.length
let low = 0
let high = m
while (low <= high) {
const partition1 = Math.floor((low + high) / 2)
const partition2 = Math.floor((m + n + 1) / 2) - partition1
const maxLeft1 = partition1 === 0 ? -Infinity : nums1[partition1 - 1]
const minRight1 = partition1 === m ? Infinity : nums1[partition1]
const maxLeft2 = partition2 === 0 ? -Infinity : nums2[partition2 - 1]
const minRight2 = partition2 === n ? Infinity : nums2[partition2]
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 === 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2
} else {
return Math.max(maxLeft1, maxLeft2)
}
} else if (maxLeft1 > minRight2) {
high = partition1 - 1
} else {
low = partition1 + 1
}
}
throw new Error('Input arrays are not sorted')
}
// Example usage
console.log(findMedianSortedArrays([1, 2], [3, 4, 5])) // 3
console.log(findMedianSortedArrays([1, 2], [3, 4])) // 2.5
6.Intersection of two sorted arrays
138.https://bigfrontend.dev/problem/intersection-of-two0-sorted-Arrays
Given 2 sorted array of integers, find the elements that exist in both arrays.
intersect([1, 2, 2, 3, 4, 4], [2, 2, 4, 5, 5, 6, 2000])
The arrays might have duplicate numbers. The order of returning result doesn't matter. What is the time & space cost of your approach? Could you improve it?
/**
* @param {number[]} arr1 - integers
* @param {number[]} arr2 - integers
* @returns {number[]}
*/
function intersect(arr1, arr2) {
const n1 = arr1.length
const n2 = arr2.length
let i1 = 0
let i2 = 0
if (n1 === 0 || n2 === 0) return []
const ans = []
while (i1 < n1 && i2 < n2) {
if (arr1[i1] === arr2[i2]) {
ans.push(arr1[i1])
i1 += 1
i2 += 1
} else if (arr1[i1] < arr2[i2]) {
// Increase i1 until arr1[i1] >= arr2[i2]
while (i1 < n1 && arr1[i1] < arr2[i2]) {
i1 += 1
}
} else {
// arr1[i1] > arr2[i2]
// Increase i2 until arr1[i1] <= arr2[i2]
while (i2 < n2 && arr1[i1] > arr2[i2]) {
i2 += 1
}
}
}
return ans
}
7.Pick up stones
147.https://bigfrontend.dev/problem/pickup-the-stones
There is a pile of n (n > 0) stones.
Player A and Player B take turns to pick 1 or 2 stones from the pile. A starts first.
Who picks the last stone loses the game.
Now here is the question, is there a winning strategy for A or B ? If so, returns the player name. If there is none, return null.
winningStonePicking(1)
// 'B'
winningStonePicking(2)
// 'A'
winningStonePicking(3)
// 'A'
winningStonePicking(4)
// 'B'
/**
* @param {number} n
* @return {'A' | 'B' | null}
*/
function canWinStonePicking(n) {
const cache = new Map()
const helper = (i, picker) => {
if (i === 1) return picker === 'A' ? 'B' : 'A'
if (i === 2) return picker === 'A' ? 'A' : 'B'
if (cache.has(`${picker}_${i}`)) {
return cache.get(`${picker}_${i}`)
}
const winer1 = helper(i - 1, picker === 'A' ? 'B' : 'A')
const winer2 = helper(i - 2, picker === 'A' ? 'B' : 'A')
let winer = ''
if (picker === winer1 || picker === winer2) {
winer = picker
} else {
winer = picker === 'A' ? 'B' : 'A'
}
cache.set(`${picker}_${i}`, winer)
return winer
}
return helper(n, 'A')
}
console.log(canWinStonePicking(3))
8.Intersection of unsorted arrays
167.https://bigfrontend.dev/problem/array-intersect
Given two arrays, find the intersection(items occur in both arrays)
arrays are not sorted, and might have duplicates. you can modify the arrays you can return the items in any order, but without duplicates. This is an easy problem, What is the time & space complexity of your approach?
/**
* @param {any[]} arr1
* @param {any[]} arr2
* @returns {any[]}
*/
function getIntersection(arr1, arr2) {
const set1 = new Set(arr1)
const set2 = new Set(arr2)
const intersection = []
set1.forEach((item) => {
if (set2.has(item)) {
intersection.push(item)
}
})
return intersection
}
26.move zeros
168.https://bigfrontend.dev/problem/move-zeros
Given an array of integers, move zeros to the end while keeping the order of the rest.
You should make the in-place change.
const list = [1, 0, 0, 2, 3]
moveZeros(list)
console.log(list) // [1,2,3,0,0]
What is the time & space complexity of your approach?
/**
* @param {Array<any>} list
* @returns {void}
*/
function moveZeros(list) {
const n = list.length
let i = 0
let j = 0
while (i < n) {
while (j < n && list[j] !== 0) {
j++
}
// j point at the first 0.
i = j
while (i < n && list[i] === 0) {
i++
}
// i point at the first non-zero after j.
if (i === n) {
break
}
;[list[i], list[j]] = [list[j], list[i]]
}
}
const list = [1, 0, 0, 2, 3]
moveZeros(list)
console.log(list)