/** * @param { (...args: any[]) => any }fn * @returns { (...args: any[]) => any } */ functioncurry(func) { // here ...args collects arguments as array (rest) returnfunctioncurriedFunc(...args) { // Here we check if current args passed equals the number of args func expects if(args.length >= func.length) { // if yes, we spread args elements to pass into func (spread). This is our base case. return func(...args) } else { /* if not, we return a function that collects the next arguments passed in next and we recursively call curriedFunc, accumalating and spreading the values of args first and then the values of next. next will take into consideration a variable amount of next arguments e.g (1, 2) (1) (1,2,3) */ returnfunction(...next) { return curriedFunc(...args,...next); } } } }
/** * @param { Function }func */ functioncurry(func) { returnfunctioncurried(...args) { // we need to return a function to make it curry-able. // 1. If the arguments are extra then eliminate them // we don't want to pass 6 arguments when the expected is 3. // it will interfere with our placeholder logic const sanitizedArgs = args.slice(0, func.length); // see if placeholder is available in arguments const hasPlaceholder = sanitizedArgs.some(arg => arg == curry.placeholder);
// if no placeholder and arguements are equal to what expected then it is normal function call if(!hasPlaceholder && sanitizedArgs.length == func.length) { return func.apply(this, sanitizedArgs); } // else we need to replace placeholders with actual values // we call helper function `mergeArgs` for this // we pass first and next arguments to helper function returnfunctionnext(...nextArgs) { return curried.apply(this, mergeArgs(sanitizedArgs, nextArgs)); } } }
functionmergeArgs(args, nextArgs) {
let result = [];
// iterate over args (because we need to replace from it) // in each iteration, if we find element == curry.placeholder // then we replace that placeholder with first element from nextArgs // else we put current element args.forEach((arg, idx) => { if(arg == curry.placeholder) { result.push(nextArgs.shift()); } else { result.push(arg); } });
// we merge both, because there might be chance that args < nextArgs return [...result, ...nextArgs]; }
Throttling is a common technique used in Web Application, in most cases using lodash solution would be a good choice.
could you implement your own version of basic throttle()?
In case you forgot, throttle(func, delay) will return a throttled function, which will invoke the func at a max frequency no matter how throttled one is called.
Here is an example.
Before throttling we have a series of calling like
─A─B─C─ ─D─ ─ ─ ─ ─ ─ E─ ─F─G
After throttling at wait time of 3 dashes
─A─ ─ ─C─ ─ ─D ─ ─ ─ ─ E─ ─ ─G
Be aware that
call A is triggered right way because not in waiting time
function call B is swallowed because B, C is in the cooling time from A, and C is latter.
notes
please follow above spec. the behavior is not exactly the same as lodash.throttle()
because window.setTimeout and window.clearTimeout are not accurate in browser environment, they are replaced to other implementation when judging your code. They still have the same interface, and internally keep track of the timing for testing purpose.
/** * @param {(...args:any[]) => any}func * @param {number}wait * @returns {(...args:any[]) => any} */ functionthrottle(func, wait) { // Track if we are waiting. Initially, we are not. let isWaiting = false; // Track arguments of last call let lastCallArgs = null;
returnfunctionthrottled(...args) { // If we are waiting, if (isWaiting) { // ...store arguments of last call lastCallArgs = args; return; } // If we are not waiting, execute 'func' with passed arguments func.apply(this, args); // Prevent future execution of 'func' isWaiting = true;
// After wait time, setTimeout(() => { // ...allow execution of 'func' isWaiting = false;
// If arguments of last call exists, if (lastCallArgs) { // ...execute function throttled and pass last call's arguments // to it. Since now we are not waiting, 'func' will be executed // and isWaiting will be reset to true. throttled.apply(this, lastCallArgs); // ...reset arguments of last call to null. lastCallArgs = null; } }, wait); } }
for the previous example of throttling by 3 dashes
─A─B─C─ ─D─ ─ ─ ─ ─ ─ E─ ─F─G
with {leading: true, trailing: true}, we get as below
─A─ ─ ─C─ ─ ─D ─ ─ ─ ─ E─ ─ ─G
with {leading: false, trailing: true}, A and E are swallowed.
─ ─ ─ ─C─ ─ ─D─ ─ ─ ─ ─ ─ ─G
with {leading: true, trailing: false}, only A D E are kept
─A─ ─ ─ ─D─ ─ ─ ─ ─ ─ E
with {leading: false, trailing: false}, of course, nothing happens.
notes
please follow above spec. the behavior is not exactly the same as lodash.throttle()
because window.setTimeout and window.clearTimeout are not accurate in browser environment, they are replaced to other implementation when judging your code. They still have the same interface, and internally keep track of the timing for testing purpose.
returnfunctionthrottled(...args) { // If we are waiting, if (isWaiting) { // ...store arguments of last call lastCallArgs = args; return; } // If we are not waiting, execute 'func' with passed arguments if (option.leading) { func.apply(this, args); } // Prevent future execution of 'func' isWaiting = true;
// After wait time, setTimeout(handleTimer, wait); } }
Debounce is a common technique used in Web Application, in most cases using lodash solution would be a good choice.
could you implement your own version of basic debounce()?
In case you forgot, debounce(func, delay) will returned a debounced function, which delays the invoke.
Here is an example.
Before debouncing we have a series of calling like
─A─B─C─ ─D─ ─ ─ ─ ─ ─E─ ─F─G
After debouncing at wait time of 3 dashes
─ ─ ─ ─ ─ ─ ─ ─ D ─ ─ ─ ─ ─ ─ ─ ─ ─ G
notes
please follow above spec. the behavior might not be exactly the same as lodash.debounce()
because window.setTimeout and window.clearTimeout are not accurate in browser environment, they are replaced to other implementation when judging your code. They still have the same interface, and internally keep track of the timing for testing purpose.
/** * @param {(...args: any[]) => any}func * @param {number}wait * @returns {(...args: any[]) => any} */ functiondebounce(func, wait) { // definition: invoke function only when the last function has passed `wait` time let timer = null; returnfunctiondebounced(...args) { // clear timer (doesn't matter if the execution is going or has completed) // 1. nothing will happen in the case when execution has completed // 2. it will clear the timer and restart if an ongoing timer was running if (timer) clearTimeout(timer);
// call supplied function `func` after `wait` time timer = setTimeout(() => { func.apply(this, args); }, wait) } }
for the previous example of debouncing by 3 dashes
─A─B─C─ ─D─ ─ ─ ─ ─ ─ E─ ─F─G
with {leading: false, trailing: true}, we get as below
─ ─ ─ ─ ─ ─ ─ ─D─ ─ ─ ─ ─ ─ ─ ─ ─ G
with {leading: true, trailing: true}:
─A─ ─ ─ ─ ─ ─ ─D─ ─ ─E─ ─ ─ ─ ─ ─G
with {leading: true, trailing: false}
─A─ ─ ─ ─ ─ ─ ─ ─ ─ ─E
with {leading: false, trailing: false}, of course, nothing happens.
notes
please follow above spec. the behavior might not be exactly the same as lodash.debounce()
because window.setTimeout and window.clearTimeout are not accurate in browser environment, they are replaced to other implementation when judging your code. They still have the same interface, and internally keep track of the timing for testing purpose.
/** * @param {Function}func * @param {number}wait * @param {boolean}option.leading * @param {boolean}option.trailing */ functiondebounce(func, wait, option = {leading: false, trailing: true}) { // in basic debounce, we kept only timerId // here, we will keep lastArgs too as we trailing function call with last arguments let timerId = null; let lastArgs = null;
returnfunctiondebounced(...args) {
// if timer is over and leading is true // then immediately call supplied function // else capture arguments in lastArgs if(!timerId && option.leading) { func.apply(this, args); } else { lastArgs = args; }
// clear timer so that next call is exactly after `wait` time clearTimeout(timerId);
timerId = setTimeout(() => { // invoke only if lastArgs is present and trailing is true if(option.trailing && lastArgs) func.apply(this, lastArgs); // reset variables as they need to restart new life after calling this function lastArgs = null; timerId = null; }, wait); } }
In order to have a uniform distribution after shuffle, the probability of picking any items in the array should be the same. That means if there are n items, the probability should be 1/n
The probability of picking 1st random item when we use getRandomInt helper by passing arguments (0, n-1) is 1/n. Simple math.
The probability of picking 2nd random item when we use getRandomInt helper by passing arguments (1, n-1) is 1/n as well. Why? Because the 2nd item was not picked at the first iteration and that probability is n-1/n. Multiplying those give us 1/n by n-1/n * 1/n-1 => 1/n
The probability of picking 3rd item is 1/n as you expect already n-1/n * n-2/n-1 * 1/n-2 => 1/n
Now all we need do is set the incremental insert position (starting form 0) and pick a random item, then swap them.
采用从后向前的顺序
1 2 3 4 5 6 7 8 9 10 11
/** * @param {any[]}arr */ functionshuffle(arr) { // modify the arr inline to change the order randomly const length = arr.length; for (let i = length - 1; i >= 0; i--) { let random = Math.floor((i + 1) * Math.random()); [arr[i], arr[random]] = [arr[random], arr[i]]; } }
/* type TypIsBad = (version: number) => boolean */
/** * @param {TypIsBad}isBad */ functionfirstBadVersion(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 low = 0; let high = version;
In JavaScript, we could use array to work as both a Stack or a queue.
1 2 3 4
const arr = [1, 2, 3, 4]
arr.push(5) // now array is [1, 2, 3, 4, 5] arr.pop() // 5, now the array is [1, 2, 3, 4]
Above code is a Stack, while below is a Queue
1 2 3 4
const arr = [1, 2, 3, 4]
arr.push(5) // now the array is [1, 2, 3, 4, 5] arr.shift() // 1, now the array is [2, 3, 4, 5]
now suppose you have a stack, which has only follow interface:
1 2 3 4 5 6
classStack{ push(element) { /* add element to stack */ } peek() { /* get the top element */ } pop() { /* remove the top element */} size() { /* count of elements */} }
Could you implement a Queue by using only above Stack? A Queue must have following interface
1 2 3 4 5 6
classQueue{ enqueue(element) { /* add element to queue, similar to Array.prototype.push */ } peek() { /* get the head element*/ } dequeue() { /* remove the head element, similar to Array.prototype.pop */ } size() { /* count of elements */ } }
note
you can only use Stack as provided, Array should be avoided for the purpose of practicing.
/* you can use this Class which is bundled together with your code class Stack { push(element) { // add element to stack } peek() { // get the top element } pop() { // remove the top element} size() { // count of element } } */
/* Array is disabled in your code */
// you need to complete the following Class classQueue{ constructor() { this.stack1 = new Stack(); this.stack2 = new Stack(); } enqueue(element) { // add new element to the rare this.stack1.push(element); } peek() { // get the head element if (this.stack2.size() > 0) { returnthis.stack2.peek(); } while(this.stack1.size() > 0){ this.stack2.push(this.stack1.pop()); } returnthis.stack2.peek(); } size() { // return count of element returnthis.stack1.size() + this.stack2.size(); } dequeue() { // remove the head element if (this.stack2.size() > 0) { returnthis.stack2.pop(); } while(this.stack1.size() > 0){ this.stack2.push(this.stack1.pop()); } returnthis.stack2.pop(); } }
[14. Implement a general memoization function - memo()](https://bigfrontend.dev/problem/implement-general-memoization-function)
题目
Memoization is a common technique to boost performance. If you use React, you definitely have used React.memo before.
Memoization is also commonly used in algorithm problem, when you have a recursion solution, in most cases, you can improve it by memoization, and then you might be able to get a Dynamic Programming approach.
So could you implement a general memo() function, which caches the result once called, so when same arguments are passed in, the result will be returned right away.
const contextMap = cache.get(cacheKey); // If there is a corresponding context map to cachekey // Check if context is in the map, if so, return value. // Else if no corresponding add contextMap, add new entry to the context map if (!contextMap) { const value = func.apply(this, arguments); cache.set(cacheKey, newMap([[ this, value ]])); return value; }
if (contextMap.has(this)) { return contextMap.get(this); } // If context not in the map, calculate and add to context map. const value = func.apply(this, arguments); contextMap.set(this, value); return value; } }
// please complete the implementation classEventEmitter{ constructor () { // 维护一个订阅该对象的map // map: (eventName,[callback...]),key为eventName，value是由相同eventName的回调函数组成的数组 // key: eventName,value: An array of callback functions with the same eventName this.callbacks = newMap(); } subscribe(eventName, callback) { if (this.callbacks.has(eventName)) { // 存在则向对应value里增加callback // eventName exists,add callback to the corresponding value const callbacks = this.callbacks.get(eventName); callbacks.push(callback) } else { // eventName不存在，则添加 // eventName does not exist,add this.callbacks.set(eventName, [callback]); }
return { // 返回一个包含release方法的对象 // return an object containing the release method release: () => { // 找到对应的callback，删除 // find the corresponding callback and delete it // 此时利用闭包，使用的是第10行的watcher // At this point,the Closures is used,and the watcher on line 10 is used const callbacks = this.callbacks.get(eventName); const index = callbacks.indexOf(callback); callbacks.splice(index, 1); } } } emit(eventName, ...args) { const callbacks = this.callbacks.get(eventName); if (!callbacks.length) return; // eventName存在则依此调用watcher里的callback // if eventName exists,call the callback in watcher accordingly for (const callback of callbacks) { callback.apply(this, args); } } }
//Approach 2: Iterative DFS: Using stack const findCorrespondingNode = (rootA, rootB, target) => { const stack = [[rootA, rootB]]; while(stack.length > 0) { const [leftNode, rightNode] = stack.pop(); if (leftNode === target) return rightNode; for (let i = 0; i < leftNode.children.length; i++) { stack.push([leftNode.children[i], rightNode.children[i]]); } } }
/** * Approach 3: Iterative BFS: Using Queue */ const findCorrespondingNode = (rootA, rootB, target) => { if (rootA === target) { return rootB; } const queueA = [rootA]; const queueB = [rootB]; while(queueA.length) { // removes the first element from an array and returns that removed element const currentElementA = queueA.shift(); const currentElementB = queueB.shift(); if (currentElementA === target) { return currentElementB; } // adds one or more elements to the end of an array and returns the new length of the array. queueA.push(...currentElementA.children); queueB.push(...currentElementB.children); } returnnull; }
/** * Approach 4: Using DOM API */
const findCorrespondingNode = (rootA, rootB, target) => { // if 'target' is itself rootA then directly return rootA, this will make 'path' array empty, and it will return rootB in reduceRight if (rootA === target) return rootB; // we can track 'target' in rootB using indexes stored during tracing 'target' in rootA let path = getRootAPath(rootA, target); // reduceRight is same as reduce but it iterate values from right to left // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduceRight return path.reduceRight((accumulator, currentValue, index) => { return accumulator.children[currentValue]; }, rootB) // rootB pointing to initialValue from where start the processing, this will be the accumulator when we start }
// get path from target to rootA in the form of index arr, index pointing to position of a node in its parent HTML collection functiongetRootAPath(rootA, target) { let path = []; let node = target; while (node !== rootA && node.parentNode) { // we will iterate till we reach top of the DOM tree const children = Array.from(node.parentNode.children); // convert HTMLCollection into Array path.push(children.indexOf(node)); // push index where 'node' found node = node.parentNode; // this will make sure we move from down to top } return path; }
/** * Approach 5: Using Tree Walker API * https://developer.mozilla.org/en-US/docs/Web/API/Document/createTreeWalker */ const findCorrespondingNode = (rootA, rootB, target) => { const rootAWalker = document.createTreeWalker(rootA, NodeFilter.SHOW_ELEMENT); const rootBWalker = document.createTreeWalker(rootB, NodeFilter.SHOW_ELEMENT); let currentNodes = [rootAWalker.currentNode, rootBWalker.currentNode]; while (currentNodes[0] !== target) { currentNodes = [rootAWalker.nextNode(), rootBWalker.nextNode()]; } return currentNodes[1]; }
I believe you’ve used JSON.stringify() before, do you know the details of how it handles arbitrary data?
Please have a guess on the details and then take a look at the explanation on MDN, it is actually pretty complex.
In this problem, you are asked to implement your own version of JSON.stringify().
In a real interview, you are not expected to cover all the cases, just decide the scope with interviewer. But for a goal of practicing, your code here will be tested against a lot of data types. Please try to cover as much as you can.
Attention to the circular reference.
note
JSON.stringify() support two more parameters which is not required here.
Don’t use JSON.stringify() in your code here, it doesn’t help you practicing coding skills.
I believe you’ve used JSON.stringify() before, do you know the details of how it handles arbitrary data?
Please have a guess on the details and then take a look at the explanation on MDN, it is actually pretty complex.
In this problem, you are asked to implement your own version of JSON.stringify().
In a real interview, you are not expected to cover all the cases, just decide the scope with interviewer. But for a goal of practicing, your code here will be tested against a lot of data types. Please try to cover as much as you can.
Attention to the circular reference.
note
Don’t use JSON.parse() in your code here It doesn’t help you practicing your skills.
/** * @param {number}num */ functionsum(num) { const func = function(num2) { // #4 return num2 ? sum(num + num2) : num; // #3 } func.valueOf = () => num; // #2 return func; // #1 } /*** ==== Explanation ==== We know that `sum(1)(2)` can be done by returning a function from a function. Example: function sum(num) { return function(num2) { return num+num2; } } but we can have `sum(1)(2)....(n)` up to `n`. How do we solve such problems? We first see a pattern, the pattern is that we need to return function `n` times. When we see a pattern then we can write concise code using recursion. <br /> So I solved this problem using recursion. But before that let's demystify these 8 lines of code. <br /> #1: Why do we need to use `func` variable, why can't we just directly return `function(num2)...` (#4)? <br /> Because we are comparing non-primitive (Object, functions are Objects in JS) value against a primitive value (Number). <br /> `sum(1)(2)(3) == 6` When we do such comparisons then JS has to do "type coercion". How does JS do this? It has `valueOf` and `toString` to do that. Essentially, one of them will be called. What we do here is that we override that method and tell the JS engine to return our custom value (which is `num`) in our case. That's why we needed to store #4 in a variable so that we can override the `valueOf` method. #2: Okay, I get it that you wanted to use the `valueOf` method, but why do you on this beautiful earth want to do that? Because if `sum(1)(2)` will return us another function and we can't compare below - `function(num2) { return num2 ? sum(num+num2) : num } == 3` So what we do is we tell the JS engine to use our `valueOf` method to return value, which is 'num'. So we can now compare `3 == 3` #3: Okay, then why do we have ternary on #3? Because in case you want to use call `sum` function normally and get value out of it. `sum(1)(2)()` will return 3 ***/
Priority Queue is a commonly used data structure in algorithm problem. Especially useful for Top K problem with a huge amount of input data, since it could avoid sorting the whole but keep a fixed-length sorted portion of it.
Since there is no built-in Priority Queue in JavaScript, in a real interview, you should tell interview saying that “Suppose we already have a Priority Queue Class I can use”, there is no time for you to write a Priority Queue from scratch.
But it is a good coding problem to practice, so please implement a Priority Queue with following interface
classPriorityQueue{ // compare is a function defines the priority, which is the order // the elements closer to first element is sooner to be removed. constructor(compare) { } // add a new element to the queue // you need to put it in the right order add(element) {
const pq = new PriorityQueue((a, b) => a - b) // (a, b) => a - b means // smaller numbers are closer to index:0 // which means smaller number are to be removed sooner
pq.add(5) // now 5 is the only element
pq.add(2) // 2 added
pq.add(1) // 1 added
pq.peek() // since smaller number are sooner to be removed // so this gives us 1
pq.poll() // 1 // 1 is removed, 2 and 5 are left
pq.peek() // 2 is the smallest now, this returns 2
The key insight is that you have to swap the newOrder array when you swap the items array so that order information is preserved. Notice the inner while loop as well, the current testcase is not the best
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/** * @param {any[]}items * @param {number[]}newOrder * @return {void} */ functionsort(items, newOrder) { for (let i = 0; i < newOrder.length; i++) { while (newOrder[i] !== i) { swap(items, i, newOrder[i]); swap(newOrder, i, newOrder[i]); } } }
functionswap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]]; }
The Object.assign() method copies all enumerable own properties from one or more source objects to a target object. It returns the target object. (source: MDN)
It is widely used, Object Spread operator actually is internally the same as Object.assign() (source). Following 2 lines of code are totally the same.
1 2
let aClone = { ...a }; let aClone = Object.assign({}, a);
This is an easy one, could you implement Object.assign() with your own implementation ?
note
Don’t use Object.assign() in your code It doesn’t help improve your skills
If we call Object.assign() with source of above, we get:
1 2 3 4
Object.assign({}, source)
// {b: 4, e: undefined} // e is undefined because `this._e` is undefined
Rather than above result, could you implement a completeAssign() which have the same parameters as Object.assign() but fully copies the data descriptors and accessor descriptors?
In case you are not familiar with the descriptors, this page from MDN might help.
This problem is solely checking your understanding of how property descriptors work.
You are asked to implement an async function helper, parallel() which works like Promise.all(). Different from sequence(), the async function doesn’t wait for each other, rather they are all triggered together.
All async functions have following interface
1 2 3 4 5 6
type Callback = (error: Error, data: any) =>void
type AsyncFunc = ( callback: Callback, data: any ) => void
Your parallel() should accept AsyncFunc array, and return a new function which triggers its own callback when all async functions are done or an error occurs.
You are asked to implement an async function helper, race() which works like Promise.race(). Different from parallel() that waits for all functions to finish, race() will finish when any function is done or run into error.
All async functions have following interface
1 2 3 4 5 6
type Callback = (error: Error, data: any) =>void
type AsyncFunc = ( callback: Callback, data: any ) => void
Your race() should accept AsyncFunc array, and return a new function which triggers its own callback when any async function is done or an error occurs.
The Promise.all() method takes an iterable of promises as an input, and returns a single Promise that resolves to an array of the results of the input promises
The Promise.allSettled() method returns a promise that resolves after all of the given promises have either fulfilled or rejected, with an array of objects that each describes the outcome of each promise.
Promise.any() takes an iterable of Promise objects and, as soon as one of the promises in the iterable fulfils, returns a single promise that resolves with the value from that promise
Can you implement a any() to work the same as Promise.any()?
note
AggregateError is not supported in Chrome yet, but you can still use it in your code since we will add the Class into your code. Do something like following:
1 2 3 4
new AggregateError( 'No Promise in Promise.any was resolved', errors )
The Promise.race() method returns a promise that fulfills or rejects as soon as one of the promises in an iterable fulfills or rejects, with the value or reason from that promise. source: MDN
Can you create a race() which works the same as Promise.race()?
Could you implement your own setTimeout() and clearTimeout() to be sync? so that they have accurate timing for test. This is what FakeTimes are for.
By “accurate”, it means suppose all functions cost no time, we start our function at time 0, then setTimeout(func1, 100) would schedule func1 exactly at 100.
You need to replace Date.now() as well to provide the time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classFakeTimer{ install() { // setTimeout(), clearTimeout(), and Date.now() // are replaced }
uninstall() { // restore the original APIs // setTimeout(), clearTimeout() and Date.now() }
tick() { // run all the schedule functions in order } }
/** * @param {integer}from * @param {integer}to */ functionrange(from, to) { // The iterator object that will be returned // when calling the Symbol.iterator method of an object. // The iterator object has a method named next which // generates values for the iteration. const iterator = { from, to, next() { if(this.from > this.to) { return { done: true, } } const value = { value: this.from, done: false }; this.from++; return value; } };
// Return an object that has a method named // Symbol.iterator for the for...of to work. // When for..of starts, it calls that method once. return { [Symbol.iterator]() { return iterator; } } }
利用generator生成器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/** * @param {integer}from * @param {integer}to */ functionrange(from, to) { function* gen() { let i = from; while (i <= to) { yield i; i++; } }
functionpartition(arr, lo, hi) { const value = arr[lo]; let i = lo, j = hi + 1; while (true) { while (++i <= hi && arr[i] > value); while (--j >= i && arr[j] < value); if (i >= j) break; let t = arr[i]; arr[i] = arr[j]; arr[j] = t; } arr[lo] = arr[j]; arr[j] = value; return j; }
/** * class Node { * new(val: number, next: Node); * val: number * next: Node * } */
/** * @param {Node}list * @return {Node} */ const reverseLinkedList = (list) => { let pre = null; let curr = list;
while (curr) { const next = curr.next; curr.next = pre; pre = curr; curr = next; }
return pre; }
用解构赋值非常优雅的一版
In this problem, temporary variables are required so you don’t overwrite variable values that you still need later on in the loop. (e.g. (1) prev = node; (2) node.next = prev; Here, prev was overwritten in (1), therefore node.next is incorrectly assigned).
Notice the use of array destructuring here to efficiently store temporary variables: The array on the right is a ‘temporary variable array’, which holds the references stored in the currentprev, node.next, and node variables. For each iteration of the while loop:
the node.next variable points to the temporary prev reference - i.e. the current node’s next will point to the previous node, reversing the link
the node variable points to the temporary node.next reference - the ‘node’ runner variable will progress to the next node in the linked list
the prev variable points to temporary node reference - the ‘prev’ runner variable will progress to the previous node.
Following this process to the end of the list will reverse all the links, hence reversing the linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/** * class Node { * new(val: number, next: Node); * val: number * next: Node * } */
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.
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.
classMiddleware{ use(func: MiddlewareFunc | ErrorHandler) { // do any async operations // call next() to trigger next function } start(req: Request) { // trigger all functions with a req object } }
Notice that use() could also accept an ErrorHandler which has 3 arguments. The error handler is triggered if next() is called with an extra argument or uncaught error happens, like following.
classMiddleware{ /** * @param {MiddlewareFunc}func */ constructor() { // Create a function queue to help with execution this.funcs = []; this.req = null; } use(func) { // Push the function into Queue this.funcs.push(func); }
next = (err) => { // take out the function to execute from the queue const toExecute = this.funcs.shift(); // Catch execution error when a function throw an error try { // args length tells us if its a normal call or an error call if (toExecute.length === 2) { // there is no error, execute the function with current request and next() if (!err) { toExecute(this.req, this.next); } // There is an error, call next() immediately for error handling. This will now keep on dequeuing funs queue // till we get an error handler function with 3 args else{ this.next(err); } } // There's an error and now we got a func with more than 2 args, i.e. an error handler else { toExecute(err, this.req, this.next); } } catch (e) { this.next(e); }
Suppose you are implementing an auto-complete in search input.
When keywords are typed, you need to highlight the keywords, how would you do that?
To simplify things, you need to create a function highlightKeywords(html:string, keywords: string[]), which wraps the keywords in html string, with <em> tag.
Have you ever met some APIs with pagination, and needed to recursively fetch them based on response of previous request ?
Suppose we have a /list API, which returns an array items.
1 2 3
// fetchList is provided for you const fetchList = (since?: number) => Promise<{items: Array<{id: number}>}>
for initial request, we just fetch fetchList. and get the last item id from response.
for next page, we need to call fetchList(lastItemId).
repeat above process.
The /list API only gives us 5 items at a time, with server-side filtering, it might be less than 5. But if none returned, it means nothing to fetch any more and we should stop.
You are asked to create a function that could return arbitrary amount of items.
1
const fetchListWithAmount = (amount: number = 5) { }
// fetchList is provided for you // const fetchList = (since?: number) => // Promise<{items: Array<{id: number}>}>
/** * Using async/await loop */ // you can change this to generator function if you want const fetchListWithAmount = async (amount = 5) => { const items = []; let lastItemId = null;
// fetchList is provided for you // const fetchList = (since?: number) => // Promise<{items: Array<{id: number}>}>
/** * Using async iterator */ // you can change this to generator function if you want const fetchListWithAmount = async (amount = 5) => { const result = [];
functionfetchListIterator() { let totalAmountFetched = 0; let cursor;
return { [Symbol.asyncIterator]() { return { asyncnext() { const { items } = await fetchList(cursor); // If API is exhausted OR we reached desired amount -> stop if (items.length === 0 || totalAmountFetched > amount) { return { done: true }; }
// fetchList is provided for you // const fetchList = (since?: number) => // Promise<{items: Array<{id: number}>}>
/** * Using async generator */ // you can change this to generator function if you want const fetchListWithAmount = async (amount = 5) => { const result = [];
asyncfunction* fetchListGenerator() { let totalAmountFetched = 0; let cursor;
// fetchList is provided for you // const fetchList = (since?: number) => // Promise<{items: Array<{id: number}>}>
/** * Using recursion and Promise */ // you can change this to generator function if you want const fetchListWithAmount = async (amount = 5) => { returnnewPromise((resolve) => { const result = []; getItems();
If you were not familiar with Observable pattern like me, I think it’s important to have a good understanding of how Observable works. Then looking at this question, it’s just adding a wrapper function to present a different interface mentioned below
After watching Javascript Design Patterns #5 - Observer Pattern, by DevSage on Youtube, it helped me understand the basics
Now looking at the problem prompt, I realized that observer and subscriber are exactly the same thing.
So the problem now is, how can we add some functionalities (unsubscribe) and state (unsubscribed) to the subscriber provided to us via the subscribe method? We use a wrapper function (or decorator for fancy name) -> I read https://javascript.info/call-apply-decorators to understand what a decorator is.
classObservable{ constructor(setup) { this.setup = setup; } subscribe(subscriber) { // equivalent to fire // a wrapper function/ object // is used to share the closure of outer function and modify the logics const subscriberWrapper = { unsubscribed: false, next(value) { if (this.unsubscribed) return; // we are relying on the scope of subscriber if (subscriber instanceofFunction) { return subscriber(value); } return subscriber.next ? subscriber.next(value) : null; }, error(value) { if (this.unsubscribed) return; this.unsubscribe(); return subscriber.error ? subscriber.error(value) : null; }, complete() { if (this.unsubscribed) return; this.unsubscribe(); return subscriber.complete ? subscriber.complete() : null; }, unsubscribe() { this.unsubscribed = true; } } this.setup(subscriberWrapper); return subscriberWrapper; } }
** [if you watched the youtube video and can’t figure out how that applies to the problem] In the video, the subscribers/observers is an array of functions, which are iterated to trigger the observer to do its thing. the reason that observers is an array is because observable pattern is a one to many pattern, meaning one observable can be subscribed by many observers. We should note that for this question, we are implementing a 1-1 relationship, with the only subscriber provided to you
let maxHeight = 0; // Use .children instead of .childNodes to ignore TextNodes. for (const child of tree.children) { maxHeight = Math.max(maxHeight, getHeight(child)); }
classBrowserHistory{ /** * @param {string}url * if url is set, it means new tab with url * otherwise, it is empty new tab */ constructor(url) { // Store the url, since the method `goBack()` should // return the initial url if it is out of bounds. /** For instance, * const bh = new BrowserHistory('X') * bh.visit('A') * bh.goBack() * bh.goBack() * console.log(bh.current); // should be be 'X' rather than undefined. */ this.initialUrl = url; this.urls = url ? [url] : []; this.currentIndex = this.urls.length - 1; } /** * @param { string }url */ visit(url) { this.currentIndex++; this.urls[this.currentIndex] = url; } /** * @return {string}current url */ getcurrent() { returnthis.currentIndex >= 0 ? this.urls[this.currentIndex] : this.initialUrl; } // go to previous entry goBack() { this.currentIndex--; } // go to next visited url forward() { this.currentIndex = Math.min(this.urls.length - 1, this.currentIndex + 1); } }
/** * @param {Function}constructor * @param {any[]}args - argument passed to the constructor * `myNew(constructor, ...args)` should return the same as `new constructor(...args)` */ const myNew = (constructor, ...args) => { // The `Object.create()` method creates a new empty object, using the // specified object as the prototype of the newly created object. const obj = Object.create(constructor.prototype);
// The `Object.create()` method creates a new empty object, using the // specified object as the prototype of the newly created object. const returnValue = constructor.apply(obj, args);
// If returnValue is an object, return returnValue, otherwise return obj. // Usually, constructors do not have return statement. The new operator // creates an object, assign it to this, and automatically returns that // object as a result. If a constructor has return statement and the return // value is an object, the object is returned instead of the newly created // object, otherwise the return value is ignored. return returnValue instanceofObject ? returnValue : obj; }
[61. create your own Function.prototype.call](https://bigfrontend.dev/problem/create-call-method)
/** * @param {string}num1 * @param {string}num2 * @return {string} */ functionadd(num1, num2) { // Use two pointers to keep track of the digit in the strings, // set both pointers to the end of the strings. let i = num1.length - 1; let j = num2.length - 1; // Keep track of the carry. let carry = 0; let result = '';
// Iterate through both strings backwards, // until the beginning of both strings is reached and there // is no carry that needs to add to the result. while (i >= 0 || j >= 0 || carry > 0) { // Get digits at current position in both strings. // If undefined, set to zero. const digit1 = Number(num1[i] || 0); const digit2 = Number(num2[j] || 0); // Add both digits and previous carry. let sum = digit1 + digit2 + carry; // If the sum "overflows", bring over the carry to the next iteration. carry = sum >= 10 ? 1 : 0; // Get the ones digit of the sum. sum = sum % 10; // Add the ones digit to the beginning of the result. result = String(sum) + result; i--; j--; }
// Use WeakMap that stores cloned results to handle circular reference. functioncloneDeep(data, map = newWeakMap()) { if (data === null || typeof data !== 'object') { return data; }
// If the source object is already in the WeakMap, // its corresponding copy is returned instead of recursing // further. if (map.has(data)) { return map.get(data); }
const res = Array.isArray(data) ? [] : {}; // Store the source object and its clone in the WeakMap. map.set(data, res);
This is a challenging problem. Recommend you read about Promise thoroughly first.
答案
Explanation
The Constructor of MyPromise
The promise object created by the class Promise has a state property. The state is initially pending. So in the constructor of the MyPromise class, I need to define a property state and set it to pending.
Handling the function that is passed to new Promise
The function is called the executor. It is executed immediately and automatically by new Promise and is able to resolve or reject the promise. So I should call it in the constructor of the MyPromise class with the arguments resolve and reject.
🙋♀️🙋♂️ Error thrown by the executor function should be handled. If there is an error, the promise should be rejected.
resolve and reject are both functions which receive one argument. So I should define the two methods in the class MyPromise.
When resolve is called, the state of the promise is changed to fulfilled; when reject is called, the state is changed to rejected.
Besides the state property, the promise object should also have a result property to store the promise result. Initially, it is set to undefined. Its value changes either to the resolved value if resolve(value) is called, or to the rejected value if reject(error) is called.
A Promise can only be resolved or rejected once.
Thus, I can define my resolve and reject like the following:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
_resolve(value) { // Ensure Promise is only resolved or rejected once. if (this.state !== 'pending') return;
this.state = 'fulfilled'; this.result = value; }
_reject(error) { // Ensure Promise is only resolved or rejected once. if (this.state !== 'pending') return;
this.state = 'rejected'; this.result = error; }
Since MyPromise will also have two static methods resolve and reject, use underscores to differentiate them.
Because class methods are not bound by default and _resolve or _reject will be called in the executor function with a plain, undecorated function reference, this inside both methods will be lost. Therefore I need to bind both methods in the constructor or use the experimental fat arrow class methods.
Implementing then method
Promise.prototype.then() takes up to two arguments:
The first argument is a function that is invoked when the promise is resolved, and receives the result. If it is not a function, it is replaced with a function that simply returns the received result.
The second argument is a function that runs when the promise is rejected, and receives the error. If it is not a function, it is replaced with a “Thrower” function.
The syntax is:
1 2 3 4 5 6 7 8
promise.then( (result) => { // handle a successful result }, (error) => { // handle an error } );
const p = new MyPromise((resolve) => { resolve(10); }).then((result) => { console.log(result); // 10 });
Although the code above seems to work, it doesn’t work as intended when the promise is resolved asynchronously, even if the onFulfilled is called asynchronously:
1 2 3 4 5 6 7
const p = new MyPromise((resolve) => { setTimeout(() => { resolve(10); }, 0); }).then((result) => { console.log(result); // undefined });
Therefore, the onFulfilled function should be called in the _resolve method, and the then method just registers the onFulfilled function. The onFulfilled function is like a subscriber, subscribing to the promised result, and the then method is kind of like the function subscribe in the Publisher/Subscriber Pattern, which receives subscriber callbacks and stores/registers them in certain data structures.
then(onFulfilled) { // If onFulfilled is not a function, replace it with a function // that simply returns the received result. const isOnFulfilledFunction = typeof onFulfilled === 'function'; this.onFulfilled = isOnFulfilledFunction ? onFulfilled : (value) => value;
returnnewPromise((resolve, reject) => {}); } }
Although the then method will be triggered instantly, the callback functions (handlers) will be invoked asynchronously. Promise uses the microtask queue to run the callbacks. When a promise is settled, its .then handlers are add into the microtask queue. Immediately after every macrotask, all tasks from microtask queue get executed, prior to any other macrotask runs.
throws an error, the promise returned by then gets rejected with the error as its value.
1 2 3 4 5 6 7 8 9 10 11 12 13
const promise = Promise.resolve('from promise');
const thenPromise = promise.then((result) => { thrownewError('error from then handler'); });
setTimeout(() => { console.log(thenPromise); }); // Promise { // [[PromiseState]]: 'rejected', // [[PromiseResult]]: Error: error from then handler. // }
returns an already fulfilled promise, the promise returned by then gets resolved with that promise’s value as its value.
1 2 3 4 5 6 7 8 9 10 11 12 13
const promise = Promise.resolve('from promise');
const thenPromise = promise.then((result) => { returnPromise.resolve('resolved promise returned by then handler'); });
setTimeout(() => { console.log(thenPromise); }); // Promise { // [[PromiseState]]: 'fulfilled', // [[PromiseResult]]: 'resolved promise returned by then handler', // }
returns an already rejected promise, the promise returned by then gets rejected with that promise’s value as its value.
1 2 3 4 5 6 7 8 9 10 11 12 13
const promise = Promise.resolve('promise');
const thenPromise = promise.then((result) => { returnPromise.reject('rejected promise returned by then handler'); });
setTimeout(() => { console.log(thenPromise); }); // Promise { // [[PromiseState]]: 'rejected', // [[PromiseResult]]: 'rejected promise returned by then handler', // }
returns a pending promise, the promise returned by then gets resolved or rejected after the the promise returned by the handler gets resolved or rejected. The resolved value of the promise returned by then will be the same as the resolved value of the promise returned by the handler.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
const promise = Promise.resolve('promise');
const thenPromise = promise.then((result) => { returnnewPromise((resolve, reject) => { setTimeout(() => { resolve('resolved promise returned by then handler'); }, 3000); }); });
setTimeout(() => { console.log(thenPromise); // Promise {<fulfilled>: "resolved promise returned by then handler"} }, 4000);
Therefore, I need to make the resolve and reject of the promise returned by then available in _resolve method, so that they can be invoked after the onFulfilled function is completed and receive the value returned by the onFulfilled function. We can create two properties in current promise object to store both functions:
In _resolve I can use try...catch to catch the error thrown by the onFulfilled method. In the catch block, call this.thenPromiseReject() with the error as argument to reject the promise returned by then. In the try block, store the value returned by the onFulfilled method. If the returned value is a promise, the promise returned by then will only get fulfilled or rejected once that promise gets resolved or rejected. To accomplish this, I can call the then method of the returned value and pass this.thenPromiseResolve() and this.thenPromiseReject() as the then handlers. If the return value is not a promise, call this.thenPromiseResolve() with the return value as argument to resolve the promise returned by then.
In addition, before I call this.onFulfilled, I also need to ensure it is not undefined, since .then() might not be called:
1 2 3 4 5 6 7 8 9
const promise = Promise.resolve('foo');
promise.then((result) => { return'bar'; }); // The promise returned by `then` is resolved, but there // is no further action with the promise. Therefore, when // the method `_resolve` of the returned promise runs, // `this.onFulfilled` is undefined.
The second callback function runs when the promise is rejected. Like the first argument, then should register the second callback function, so that _reject can execute it asynchronously whenever the promise is rejected.
Now I need to handle the consequences of calling onRejected. In the Promise, if the onRejected :
is not a function, the onRejected is replaced with a function that throws the received argument, and the promise returned by then gets rejected with that promise’s value as its value.
1 2 3 4 5 6 7 8 9 10 11 12
const promise = Promise.reject('error from promise');
const thenPromise = promise.then((result) => {});
setTimeout(() => { console.log(thenPromise); }); // Uncaught (in promise) error from promise // Promise { // [[PromiseState]]: 'rejected', // [[PromiseResult]]: 'error from promise', // }
throws an error, the promise returned by then gets rejected with the thrown error as its value.
1 2 3 4 5 6 7 8 9 10 11 12 13
const promise = Promise.reject('error from promise');
And in my _reject method, I first try to call this.onRejected() and store its return value. If the returned value is not an instance of MyPromise, resolve the promise returned by then by calling this.thenPromiseResolve() with the returned value as argument. Otherwise call the then method of the returned value with this.thenPromiseResolve() and this.thenPromiseReject() as arguments. Catch any errors thrown by this.OnRejected(); call this.thenPromiseReject() and pass the error. I also need to ensure this.onRejected is not undefined.
In MyPromise.resolve, first check if the value received is a promise; if it is a promise, return the promise; otherwise return a new instance of MyPromise and resolve the promise with the given value.
1 2 3 4 5 6 7 8 9 10 11
staticresolve(value) { const isValuePromise = value instanceof MyPromise;
returnnew MyPromise((resolve, reject) => { // Register `resolve` and `reject`, so that we can // resolve or reject this promise in `_resolve` // or `_reject`. this.thenPromiseResolve = resolve; this.thenPromiseReject = reject; }); }
_.isEqual is useful when you want to compare complex data types by value not the reference.
Can you implement your own version of deep equal isEqual? The lodash version covers a lot of data types. In this problem, you are asked to support :
primitives
plain objects (object literals)
array
Objects are compared by their own, not inherited, enumerable properties
1 2 3 4 5 6 7 8 9 10 11
const a = {a: 'bfe'} const b = {a: 'bfe'}
isEqual(a, b) // true a === b // false
const c = [1, a, '4'] const d = [1, b, '4']
isEqual(c, d) // true c === d // false
Lodash implementation has some strange behaviors. (github issue, like following code
1 2 3 4 5 6 7
const a = {} a.self = a const b = {self: a} const c = {} c.self = c const d = {self: {self: a}} const e = {self: {self: b}}
lodash.isEqual gives us following result. Notice there is a case that resulting in false.
1 2 3 4 5 6 7 8 9 10 11
// result from lodash implementation _.isEqual(a, b) // true _.isEqual(a, c) // true _.isEqual(a, d) // true _.isEqual(a, e) // true _.isEqual(b, c) // true _.isEqual(b, d) // true _.isEqual(b, e) // false _.isEqual(c, d) // true _.isEqual(c, e) // true _.isEqual(d, e) // true
Setting aside the performance concerns mentioned by lodash, your implement should not have above problem, which means above all returns true and call stack should not exceed the maximum.
Now the logs are different! That is because Subject first works as a observer, get the values, then works as an Observable and dispatch the value to different observers.
Cool right? Ok, you are asked to implement a simple Subject Class.
Observable is given for you, you can just use it.
you can use new Observer({next,error,complete}) or new Observer(function) to create an observer.
// You can use Observer which is bundled to your code
// class Observer { // // subscriber could one next function or a handler object {next, error, complete} // constructor(subscriber) { } // next(value) { } // error(error) { } // complete() {} // }
// You can use Observer which is bundled to your code
// class Observer { // // subscriber could one next function or a handler object {next, error, complete} // constructor(subscriber) { } // next(value) { } // error(error) { } // complete() {} // }
There are a lot of operators for Observable, if we think of Observable as event stream, then modifying the stream is a common task, transformation operators are useful at this.
In this problem, you are asked to implement map(), as the name indicates, it maps the value to another value thus creating a new event stream.
Here is an example.
1 2 3 4 5 6 7
const source = Observable.from([1,2,3])
map(x => x * x)(source) // this transformer doubles numbers and create a new stream .subscribe(console.log) // 1 // 4 // 9
Observable has pipe() method which could make this more readable.
/** * @param {string}num1 * @param {string}num2 * @return {string} */ functionadd(num1, num2) { const isNum1Negative = num1[0] === '-'; const isNum2Negative = num2[0] === '-'; // remove sign num1 = num1.replace(/^[+|-]/, ''); num2 = num2.replace(/^[+|-]/, ''); //case 1: Both same sign we just add numbers // 1.1: +,+ // 1.2: -,- mark result -
// case 2: Diff sign we subtract // 2.1 : (-,+) // 2.1.1 (n1 < n2) : subtractAbs result will be - , Ex: (-8)+(9) = + (remove '-' sign from final res) // 2.1.2 (n1 > n2) : subtractAbs result will be + , Ex: (-9)+(8) = - (add '-' sign to final res) // 2.2 : (+,-) // 2.2.1 (n1 < n2) : subtractAbs result will be - , Ex: (8)+(-9) = - (keep subtractAbs result as it is) // 2.2.2 (n1 > n2) : result will be - , Ex: (9)+(-8) = + (keep subtractAbs result as it is)
if (isNum1Negative === isNum2Negative) { return (isNum1Negative ? '-' : '') + addAbs(num1, num2); // case 1.1, 1.2 } else { const res = subtractAbs(num1, num2);
if (res[0] === '-' && isNum1Negative) { // case: 2.1.1 return res.slice(1); } // case 2.1.2 & case 2.2.1/2.2.2 return (isNum1Negative ? '-' : '') + res; } }
// prb: 62 functionaddAbs(num1, num2) { num1 = num1.split(''); num2 = num2.split(''); let res = [], carry = 0; while (num1.length || num2.length || carry) { let sum = (Number(num1.pop()) || 0) + (Number(num2.pop()) || 0) + carry; carry = Math.floor(sum / 10); res.unshift(sum % 10); } return res.join(''); }
// prb: 75 functionsubtractAbs(num1, num2) { let negative = false; // Before proceeding further, make sure num1 is bigger if (isSmaller(num1, num2)) { negative = true; [num1, num2] = [num2, num1]; } num1 = num1.split(''); num2 = num2.split(''); let borrow = 0, result = []; while (num1.length || num2.length || borrow) { // Check the value of 1st number after it has been borrowed from const val1 = Number(num1.pop() || 0) - borrow; const val2 = Number(num2.pop()) || 0; borrow = val2 > val1 ? 1 : 0; // if num2 is smaller then no need for another borrow and we can set it as zero // Difference would be borrow*10 with val1 const diff = ((borrow * 10) + val1) - val2; //Add the result to start of array; result.unshift(diff); } // Remove leading zeroes, if numbers are equal we add 0 to result so remove them now // we can do like this too // result = result.replace(/^0*/g, ''); result = !!result ? result : '0'; while (result[0] === 0 && result.length !== 1) { result.shift(); }; result = result.join('') return negative ? '-' + result : result; }
// Returns true if num1 is smaller than num2. functionisSmaller(num1, num2) { // Calculate lengths of both string let n1 = num1.length, n2 = num2.length; if (n1 < n2) returntrue; if (n2 < n1) returnfalse; // if we are here num1 and num2 have same length, we start comparring from MSB for (let i = 0; i < n1; i++) { if (num1[i] < num2[i]) returntrue; elseif (num1[i] > num2[i]) returnfalse; } returnfalse; }
// prb: 75 functionsubtractAbs(num1, num2) { let negative = false; // Before proceeding further, make sure num1 is bigger if (isSmaller(num1, num2)) { negative = true; [num1, num2] = [num2, num1]; } // your code here num1 = num1.split(''); num2 = num2.split(''); let borrow = 0, result = []; while (num1.length || num2.length || borrow) { // Check the value of 1st number after it has been borrowed from const val1 = Number(num1.pop() || 0) - borrow; const val2 = Number(num2.pop()) || 0; borrow = val2 > val1 ? 1 : 0; // if num2 is smaller then no need for another borrow and we can set it as zero // Difference would be borrow*10 with val1 const diff = ((borrow * 10) + val1) - val2; //Add the result to start of array; result.unshift(diff); } // Remove leading zeroes, if numbers are equal we add 0 to result so remove them now // we can do like this too // result = result.replace(/^0*/g, ''); result = !!result ? result : '0'; while (result[0] === 0 && result.length !== 1) { result.shift(); }; result = result.join(''); return negative ? '-' + result : result; }
// Returns true if num1 is smaller than num2. functionisSmaller(num1, num2) { // Calculate lengths of both string let n1 = num1.length, n2 = num2.length; if (n1 < n2) returntrue; if (n2 < n1) returnfalse; // if we are here num1 and num2 have same length, we start comparring from MSB for (let i = 0; i < n1; i++) { if (num1[i] < num2[i]) returntrue; elseif (num1[i] > num2[i]) returnfalse; } returnfalse; }
/** * @param {string}str * @return {string} */ functionsnakeToCamel(str) { let result = str[0]; // in any case we want to keep first char as it is
for (let i = 1; i < str.length; i++) { // begin from i=1 as we already have 0th index char
/** main logic: Details explanation is coming soon. 1. current char `i` must be '_' 2. previous char must not be '_' 3. next char must not be '_' 4. current char must less than 2nd last of string **/ if (str[i] === '_' && str[i - 1] !== '_' && str[i + 1] !== '_' && i < str.length - 1) { result += str[i+1].toUpperCase(); i++; // increment because we already consider i+1 in previous line. } else { result += str[i]; // else just add in the result string } } return result; // 🍻 return the camelCase because that's the way }
You are asked to create a new mySetInterval(a, b) which has a different behavior from window.setInterval, the time between calls is a linear function, growing larger and larger period = a + b * count.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
let prev = Date.now() const func = () => { const now = Date.now() console.log('roughly ', Date.now() - prev) prev = now }
Interface is mySetInterval(delay, period), the first delay is used for the first call, and then period is used.
because window.setTimeout and window.setInterval are not accurate in browser environment, they are replaced to other implementation when judging your code. They still have the same interface, and internally keep track of the timing for testing purpose.
Something like below will be used to do the test. (You don’t need to read following code to accomplish this task)
Like setTimeout, setInterval also is not accurate. (please refer Event Loop for detail).
This is OK in general web application, but might be problematic in test.
Could you implement your own setInterval() and clearInterval() to be sync? so that they have accurate timing for test. This is what FakeTimes are for.
By “accurate”, it means suppose all functions cost no time, we start our function at time 0, then setInterval(func1, 100) would schedule func1 exactly at 100, 200, 300 .etc.
You need to replace Date.now() as well to provide the time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classFakeTimer{ install() { // replace window.setInterval, window.clearInterval, Date.now // with your implementation } uninstall() { // restore the original implementation of // window.setInterval, window.clearInterval, Date.now } tick() { // run the scheduled functions without waiting } }
**Be careful about the infinite loops **. Your code is tested like this:
[_.get(object, path, defaultValue]) is a handy method to help retrieving data from an arbitrary object. if the resolved value from path is undefined, defaultValue is returned.
/** * @param {string}str * @return {string} */ functionlongestUniqueSubstr(str) { let map = newMap(); let start = 0, end = 0, len = 0, i = 0;
while (end < str.length) { if (map.has(str[end])) { // move start to repeating char indx +1 as one by one reducing window size is not optimized start = map.get(str[end]) + 1; } map.set(str[end], end); end++;
if (len < (end - start)) { len = end - start; i = start; }
/** * @param {any}obj * @param {target}target * @return {boolean} */ functionmyInstanceOf(obj, target) { // If the object does not exist or we've reached the base Object constructor, return false if (!obj || typeof obj !== "object") returnfalse;
// Check if the target is a valid object if (!target.prototype) throwError;
// If the object's prototype matches our target's prototype, return true // Otherwise, recurse down the prototypal chain if (Object.getPrototypeOf(obj) === target.prototype) { returntrue; } else { return myInstanceOf(Object.getPrototypeOf(obj), target); } }
Say you need to fetch some data through 100 APIs, and as soon as possible.
If you use Promise.all(), 100 requests go to your server at the same time, which is a burden to low spec servers.
Can you throttle your API calls so that always maximum 5 API calls at the same time?
You are asked to create a general throttlePromises() which takes an array of functions returning promises, and a number indicating the maximum concurrent pending promises.
1 2 3 4 5
throttleAsync(callApis, 5).then((data) => { // the data is the same as `Promise.all` }).catch((err) => { // any error occurs in the callApis would be relayed here })
By running above code, at any time, no more than 5 APIs are requested, so low spec servers are saved.
There are many ways to do it, can you think of different approaches?
答案
正则表达式
‘/s’ => it indicates single white space character ‘/s+’ => here ‘+’ is a greedy character that indicates one or more For example ‘a+’ signifies one or more a ‘^’ indicates starting/leading characters of the expression ‘$’ indicates end/trailing characters of the expression ‘|’ similar to logical OR operator
An IPv4 Address is represented in dot-decimal notation, consisting of 4 numbers( called ‘octet’), each ranging from 0 to 255, like 1.22.33.255. It has 32 bit, so there are maximum 2^32 = 4,294,967,296 IPv4 addresses.
Leading zeroes are not allowed in IPv4, like 01.01.01.01 is invalid.
IPv6
An IPv6 Address have 128 bits (which is a lot), separated by 8 groups (called ‘hexadectet’, or ‘hextet’, not fixed yet). Each group has 16 bits, so could be represented by a hexadecimal string at 4 digits, such as 2001:0db8:85a3:0000:0000:8a2e:0370:7334.
Notice that leading zeroes are allowed in IPv6.
There are other valid format of IPv6 addresses, like Zero compression, but it is beyond the scope here, you can ignore them.
Task
You are given some random string, please write a function if it is valid IPv4 or IPv6 address.
It works great. Util the UI become so complicated that same API might be called for multiple time within a relatively short period of time.
You want to avoid the unnecessary API calls, based on following assumption:
GET API call response hardly changes within 1000ms.
So identical GET API calls should return the same response within 1000ms. By identical, it means path and config are deeply equal.
You create getAPIWithMerging(path: string, config: SomeConfig), which works like following.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
getAPIWithMerging('/list', { keyword: 'bfe'}).then(...) // 1st call, this will call getAPI
getAPIWithMerging('/list', { keyword: 'bfe'}).then(...) // 2nd call is identical to 1st call, // so getAPI is not called, // it resolves when 1st call resolves
getAPIWithMerging('/list', { keyword: 'dev'}).then(...) // 3rd call is not identical, so getAPI is called
// after 1000ms getAPIWithMerging('/list', {keyword: 'bfe'}).then(...) // 4th call is identical to 1st call, // but since after 1000ms, getAPI is called.
Attention for memory leak!
Your cache system should not bloat. For this problem, you should have 5 cache entries at maximum, which means:
// getAPI is bundled with your code, config will only be some plain objects. // const getAPI = <T>(path: string, config: SomeConfig): Promise<T> => { ... }
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?
1 2 3 4 5 6 7 8
largestDiff([-1, 2,3,10, 9]) // 11, obviously Math.abs(-1 - 10) is the largest
largestDiff([]) // 0
largestDiff([1]) // 0
答案
找最大值和最小值，相减
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/** * @param {number[]}arr * @return {number} */ functionlargestDiff(arr) { if (!arr) return0; const n = arr.length; if (n < 2) return0; let min = Infinity; let max = -Infinity;
for (let i = 0; i < n; i++) { min = Math.min(arr[i], min); max = Math.max(arr[i], max); }
In JavaScript, we could use array to work as both a Stack or a queue.
1 2 3 4
const arr = [1, 2, 3, 4]
arr.push(5) // now array is [1, 2, 3, 4, 5] arr.pop() // 5, now the array is [1, 2, 3, 4]
Above code is a Stack, while below is a Queue
1 2 3 4
const arr = [1, 2, 3, 4]
arr.push(5) // now the array is [1, 2, 3, 4, 5] arr.shift() // 1, now the array is [2, 3, 4, 5]
now suppose you have a Queue, which has only follow interface:
1 2 3 4 5 6
classQueue{ enqueue(element) { /* add element to queue, similar to Array.prototype.push */ } peek() { /* get the head element*/ } dequeue() { /* remove the head element, similar to Array.prototype.pop */ } size() { /* count of elements */ } }
Could you implement a Stack by using only above Queue? A Stack must have following interface
1 2 3 4 5 6
classStack{ push(element) { /* add element to stack */ } peek() { /* get the top element */ } pop() { /* remove the top element */} size() { /* count of elements */} }
note
you can only use Queue as provided. Don’t use Array, it is not what this is for.
/* you can use this Queue which is bundled together with your code class Queue { enqueue(element) { // add new element to the queue } peek() { // return the head element } dequeue() { // remove head element from the queue } size() { // return the queue size } } */
// you need to complete the following Stack, using only Queue classStack{ constructor() { this.queue = new Queue(); } push(element) { // push an element into the stack let rotations = this.size(); this.queue.enqueue(element); while (rotations > 0) { this.queue.enqueue(this.queue.dequeue()); rotations--; } } peek() { // get the top element returnthis.queue.peek(); } pop() { // remove top element from stack returnthis.queue.dequeue(); } size() { // return count of elements returnthis.queue.size(); } }
Can you write your own Math.pow() ? The power would only be integers.
1 2 3 4 5 6 7 8
pow(1, 2) // 1
pow(2, 10) // 1024
pow(4, -1) // 0.25
All inputs are safe.
Follow-up
You can easily solve this problem by multiplying the base one after another, but it is slow. For power of n, it is needed to do the multiplication n times, can you think of a faster solution ?
Can you transform(serialize) a binary tree into a string and restore(deserialize) a binary tree from the string? Just like what JSON.stringify() and JSON.parse() do.
Above all substrings subsequences (*) contains unique characters, but you need to return the smallest one in lexicographical order( ‘a’ -> ‘z’), which is 'abcxyz'.
All input only contains valid lowercase alphabets only.
// add className if (className) ele.classList.add(className);
// append children if (children) { // make sure children is Array if (!(children instanceofArray)) { children = [children]; } // render each child and append it to parent children.forEach(child => { // text node if (typeof child === 'string') { ele.append(document.createTextNode(child)); } else { ele.append(render(child)); } }) }
// add rest props to ele if (restProps) { Object.entries(restProps).forEach(([key, value]) => { ele.setAttribute(key, value); }); } return ele; }
Object.is() is similar to === except following cases
1 2 3 4 5
Object.is(0, -0) // false 0 === -0// true
Object.is(NaN, NaN) // true NaN === NaN// false
Here is the detailed spec, can you implement your own is()?
答案
特别判断一下类型
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/** * @param {any}a * @param {any}b * @return {boolean} */ functionis(a, b) { if (typeof a === 'number' && typeof b === 'number') { if (Number.isNaN(a) && Number.isNaN(b)) { returntrue; }
// 区分正负0 if (a === 0 && b === 0 && 1 / a !== 1 / b) { returnfalse; } } return a === b; }
大佬的巧妙方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/** * @param {any}a * @param {any}b * @return {boolean} */ functionis(a, b) { if (a !== a) { // Only NaN is not equal to itself return b !== b; // returns true if the second parameter is NaN too }
if (a === 0 && b === 0) { // -0 === 0 is true, so when both parameters equals to 0 return1 / a === 1 / b; // 1 / -0 is -Infinity and -Infinity === -Infinity }
return a === b; // All other cases with regular === comparison }
Can you create a function which works like jQuery.on(), that attaches event listeners to selected elements.
In jQuery, selector is used to target the elements, in this problem, it is changed to a predicate function.
1 2 3 4 5 6 7 8 9 10
onClick( // root element document.body, // predicate (el) => el.tagName.toLowerCase() === 'div', function(e) { console.log(this); // this logs all the `div` element } )
First argument is type, it could be set to Custom Component, but here in this problem, it would only be HTML tag name
Second argument is props, here in this problem, it would only be the (common) camelCased HTML attributes
the rest arguments are the children, which in React supports many data types, but in this problem, it only has the element type of MyElement, or string for TextNode.
You are asked to create your own createElement() and render(), so that following code could create the exact HTMLElement in 113. Virtual DOM I.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
const h = createElement
render(h( 'div', {}, h('h1', {}, ' this is '), h( 'p', { className: 'paragraph' }, ' a ', h('button', {}, ' button '), ' from ', h('a', { href: 'https://bfe.dev' }, h('b', {}, 'BFE'), '.dev') ) ))
Notes
The goal of this problem is not to create the replica of React implementation, you can have your own object representation format other than the one in 113. Virtual DOM I.
Details about ref, key are ignored here, they will be put in other problems. Re-render is not covered here, it will be in another problem as well.
Given a character sequence and a defined document unit, tokenization is the task of chopping it up into pieces, called tokens , perhaps at the same time throwing away certain characters, such as punctuation. (ref)
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
1 * (20 - 300 )
before we implement the logic, first we need to get the “keywords”(tokens) and ignore the spaces, like following:
1
'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:
1 2 3 4 5 6 7 8 9 10
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
1 2 3
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.
/** * @param {number}n - integer * @returns {string} */ functiongetNthNum(n) { let num = "1"; while (n > 1) { num = transform(num); n--; } return num; }
const transform = (num) => { let currentDigit = ''; let currentCount = 0; let result = ''; for (let i = 0; i <= num.length; i++) { if (num[i] === currentDigit) { currentCount ++; } else { if (currentCount > 0) { result += currentCount + currentDigit; }
As you know, number data type in JavaScript cannot represent (all) float numbers accurately due to binary nature.
For some basic calculations, you might use Number.prototype.toFixed() to overcome this, yet for more extreme cases that requires perfect accuracy, it is not enough.
Proposal of BigDecimal to JavaScript is still at an early stage, before it is adopted, you can use other libraries like Big.js.
In this problem, you are asked to implement the addition of two decimals with arbitrary digits.
He also sleep(time: number), time is based on seconds.
1 2 3 4 5 6 7 8
LazyMan('Jack', console.log).eat('banana').sleep(10).eat('apple').sleep(1) // Hi, I'm Jack. // Eat banana. // (after 10 seconds) // Wake up after 10 seconds. // Eat Apple. // (after 1 second) // Wake up after 1 second.
He can sleepFirst(time: number), which has the highest priority among all tasks, no matter what the order is.
1 2 3 4 5 6 7 8
LazyMan('Jack', console.log).eat('banana').sleepFirst(10).eat('apple').sleep(1) // (after 10 seconds) // Wake up after 10 seconds. // Hi, I'm Jack. // Eat banana // Eat apple // (after 1 second) // Wake up after 1 second.
Roman numerals are represented by combinations of following seven symbols, each with a fixed integer value.
Symbol
I
V
X
L
C
D
M
Value
1
5
10
50
100
500
1000
For Standard form, subtractive notation is used, meaning 4 is IV rather than IIII, 9 is IX rather than VIIII. Same rule applies to 40(XL) and 900(CM) .etc.
Simply speaking, the roman numerals in standard form follow these rules.
symbols are listed from highest to lowest, from left to right
from left to right, if the next symbol value is bigger than current one, it means subtracting, otherwise adding.
Please implement romanToInteger(). The input are all valid strings.
let value = 0; for (let i = 0; i < str.length; i++) { const cur = numerals.get(str[i]); const next = i + 1 < str.length ? numerals.get(str[i + 1]) : 0;
if (cur < next) { value -= cur; } else { value += cur; } }
there a few options to cookie, but in this problem, you only need to support max-age which means the cookie should be deleted after certain time(in seconds).
Also Safari’s ITP actually deletes client-side script-writable storage after 7 days of Safari use without interacting on your website, and localStorage is included.
Unlike Cookie, localStorage doesn’t expire.
In this problem, please create a localStorage wrapper with expiration support
Traverse a binary tree vertically from left to right, from top to bottom, the binary tree contains positive integers as node values.
For above binary tree, vertical traversal should return
1
[6,4,2,7,1,9,10,3,8,5]
If two nodes are at the same position, their order should inherit from their parent node. For example, 9 and 10 are at the same position, since 7 is before 8, so 9 should be before 10.
