JS common interview problems

Exclude items array according excludes array

Implement a function to exclude matching items from all according to excludes array.

Assume there are m items in all, n items in excludes. Below are 3 versions to solve this problem

1. Bad version: O(m*n)
2. Decent version: O(m*n), but can return early in some case
3. Good version: O(max(m, n))

/*
	all: is the original array
	exclude: is the array specifying properties for items to be excluded
	
	The result should be :
 	[
 		{color: "blue", weight: 35, age: 1}
		{color: "green", weight: 10, age: 32}
        {color: "blue", weight: 89, age: 9}
    ]
*/

let all = [
  { color: "red", weight: 14, age: 10 },
  { color: "blue", weight: 35, age: 1 },
  { color: "green", weight: 4, age: 20 },
  { color: "green", weight: 10, age: 32 },
  { color: "red", weight: 89, age:9 },
  { color: "blue", weight: 89, age:9 },
  { color: "red", weight: 9, age:12},
]

let exclude = [ 
  {k: "color",  v: 'red' },
  {k: "weight",  v: 4 },
]


// 1. BAD Version: O(m*n)
function filterBad(all, exclude){
    exclude.forEach(function(pair){
        all = all.filter( (item)=> item[pair.k] !== pair.v )
    })
    return all;
}
console.log("filter bad result: ")
console.log(filterBad(all, exclude))


// 2. Decent Version: O(m*n), but can return early in some case
function filterDecent(all, exclude){
  return all.filter(function(itemAll){
    return !exclude.some(function(itemEx){
      return itemAll[itemEx.k] === itemEx.v
    })
  })
}
console.log("filter decent result: ")
console.log(filterDecent(all, exclude))

// 3. GOOD Version: O(max(m, n))
function filterGood(all, exclude){
  let map = new Map()
  exclude.forEach(function(item){
    let key = item.k
    let val = item.v
    if(!map.has(key))  
        map.set(key, new Set([val]))
    map.get(key).add(val)
  })

  return all.filter(function(item){
    return !Object.keys(item).some(function(key){
      return map.has(key) ? map.get(key).has(item[key]) : false
    })
  })
}
console.log("filter good result: ")
console.log(filterGood(all, exclude))

Create chaining function

Implement a function can take an executor , onSuccess, onFail callbacks, and call them in the right time. For the following example, please finish the exec function

• slow is executor, defined by users
• success(onSuccess): onSuccess also defined by users, to receive the successful generated result
• fail(onFail) : onFail also defined by users, to receive error message

function exec(executor){
    let promise = {
        result: {
            state: "pending",
            data: null,
            error: null,
        },
        doneConsumers:[],
        failConsumers:[],
        done: function(onDone){
            this.doneConsumers.push(onDone)
            return promise
        },
        fail: function(onFail){
            this.failConsumers.push(onFail)
			return promise
        },
        runExecutor: function(){
            executor(this.resultHooks.bind(this))
        },
        resultHooks: function(error, data){
            this.result.data = data
            this.result.error = error
            this.result.state = data===null ? 'failed' : 'done'
            if(this.result.state === 'done'){
                this.doneConsumers.splice(0).forEach((fn)=>{
                    fn(this.result.data)
                })
            }
            if(this.result.state === 'failed'){
                this.failConsumers.splice(0).forEach((fn)=>{
                    fn(this.result.error)
                })
            }
        }
    }
    promise.runExecutor()
    return promise
}

// TEST
function slow(callback) {
    setTimeout(function(){
        if (Math.random() > 0.5) {
            return callback("Error 417",null)
        }
        callback(null, {id:123})
    },500);
}

let p = exec(slow)
.done(function(data){
    console.log("1st cb for DONE: ");  console.log(data);
}).done(function(data){
    console.log("2nd cb for DONE: ");  console.log(data);
}).done(function(data){
    console.log("3rd cb for DONE: ");  console.log(data);
}).fail(function(err){
    console.log("1st cb for Error: " + err);
}).fail(function(err){
    console.log("2nd cb for Error: " + err);
}).fail(function(err){
    console.log("3rd cb for Error: " + err);
})

console.log(p)

Cache expensive function execution

If a function execution is very expensive, such as encoding function. Cachify the expensive function, so that next time it will instantly return last calculated result, when the same arguments passed in.

1. Barely Workable Version [ can only cache one function ]

   function cachify(fn){
       cache = {}
       return function(){
           let key = [].slice.call(arguments).join(',')
           if(cache[key]) 
               return cache[key]
           else{
               cache[key] = fn.apply(null, arguments)
               return cache[key]
           }
       }
   }
   
   // TEST
   let timeConsumeFun = function( arg1, arg2 ){ 
       for( let i = 0; i < 100000000; i++ ){
           arg1 += 1;
           arg2 += 1
       } 
       return arg1 + arg2
   }
   
   let startTime = Date.now()
   let cachedFun = cachify(timeConsumeFun)
   let result1 = cachedFun(0, 0)
   let timeUsedFirstTime = Date.now() - startTime
   console.log("Result of first call should be 200000000: "+ result1)
   console.log("Time used for first call: "+ timeUsedFirstTime)
   
   startTime = Date.now()
   let result2 = cachedFun(0, 0)
   let timeUsedSecondTime = Date.now() - startTime
   console.log("Result of seconde call should be 200000000: "+ result2)
   console.log("Time used for second call: "+ timeUsedSecondTime)

2. Good Version I : [Can cache any function with different parameters]

   cach all functions and its input/output in only one map

   function cachify(fn) {
   	try {
   		cache // must use this var, in any way
   		console.dir(cache)
   	} catch (e) {
   		if (e.name === "ReferenceError")
   			cache = new Map()
   	} finally {
   		return function () {
   			let params = [].slice.call(arguments).join(',')
   			if (cache.has(fn)) {
   				if (cache.get(fn).has(params))
   					return cache.get(fn).get(params)
   				else {
   					let res = fn.apply(null, arguments)
   					cache.get(fn).set(params, res)
   					return res
   				}
   			} else {
   				let res = fn.apply(null, arguments)
   				cache.set(fn, new Map().set(params, res))
   				return res
   			}
   		}
   	}
   }
   
   // TEST
   let test1 = function (arg1, arg2) {
   	for (let i = 0; i < 10000000; i++) {
   		arg1 += 1;
   		arg2 += 1
   	}
   	return arg1 + arg2
   }
   
   let startTime = Date.now()
   let cachedFun1 = cachify(test1)
   let result11 = cachedFun1(0, 0)
   let timeUsedFirstTime = Date.now() - startTime
   console.log("Result of first call should be 20000000: " + result11)
   console.log("Time used for first call: " + timeUsedFirstTime)
   
   startTime = Date.now()
   let result12 = cachedFun1(0, 0)
   let timeUsedSecondTime = Date.now() - startTime
   console.log("Result of seconde call should be 20000000: " + result12)
   console.log("Time used for second call: " + timeUsedSecondTime)
   
   
   let test2 = (a, b) => a + b
   let cachedFun2 = cachify(test2)
   let result21 = cachedFun2(0, 0)
   console.log(result21)
   let result22 = cachedFun2(1, 1)
   console.log(result22)

3. Good Version II : [Can cache any function with different parameters]

   cache each function and its input/output in separate map, using closure

   function cachify( fn ){
     // <fn, <input, output> >
     let map = new Map()
     return function(...args){
       if( map.has(fn) ){
         let inOutMap = map.get(fn)
         let argsStr = args.join('/')
         if( inOutMap.has(argsStr) ){
           return inOutMap.get(argsStr)
         }
       }
       
       let res = fn(...args)
       if(!map.has(fn)) {
         let inOutMap = new Map()
         map.set(fn, inOutMap)
       }
       map.get(fn).set(args.join('/'), res)
       console.log(map)
       return res
     }
   }

Polyfill Array.prototype.forEach

// 1. Example to use forEach()
let arr = [1, 2, 3]
arr.forEach(function(item, index){
    console.log("item: "+ item +", index: "+index)
})

if(typeof Array.prototype.forEach !== "function"){
    Array.prototype.forEach = function(cb){
        for( let i = 0; i < this.length; i++ ){
            cb(this[i], i)
        }
    }
}

Polyfill Array.prototype.reduce

// if(Array.prototype.reduce){
    Array.prototype.reduce = function(reducer, initial){
        if (this.length === 0) {
            if( typeof initial === 'undefined' ) 
                throw new Error("No initial value provided")
            else return initial
        }
        
        let accum = typeof initial === 'undefined' ? this[0] : initial
        let startIndex = typeof initial === 'undefined' ? 1 : 0
        for( let i = startIndex; i < this.length; i++ ){
            accum = reducer(accum, this[i])
        }
        return accum
    }
// }
   
    
// TEST    
let reducer = (accum, item)=>{ return accum+item }
let arr = [1, 2, 3]
let res = arr.reduce(reducer, 1) 
console.log(res)				 // 7

arr = []
res = arr.reduce(reducer, 1)
console.log(res)				 // 1

arr = [10]
res = arr.reduce(reducer)
console.log(res)				 // 10

arr = [10]
res = arr.reduce(reducer, 1)
console.log(res)				 // 11


arr = []
res = arr.reduce(reducer)
console.log(res)	   // Uncaught Error: No initial value provided

Closure: a comparison

• ONLY variable inside a function can form into closure scope
• only variable itself cannot be updated or

// Version 1: `countVal` is a function
function Counter(start) {
    var count = start;
    return {
        increment: function() { count++; },
        countVal: function() { return count; }
    }
}

var foo = Counter(4);
foo.increment();
foo.get(); // 5


// Version 2: `countVal` is a variable
function Counter(start) {
    var count = start;
    return {
        increment: function() { count++; },
        countVal: count
    }
}

var foo = Counter(4);
foo.increment();
foo.get(); // 4

Variable Hoisting

This following code snippet will parsed firstly into next code snippet

bar();
var bar = function() {};
var someValue = 42;

test();
function test(data) {
    if (false) {
        goo = 1;

    } else {
        var goo = 2;
    }
    for(var i = 0; i < 100; i++) {
        var e = data[i];
    }
}

The snippet will convert to the following: 上面代码在运行之前将会被转化。JavaScript 将会把 var 表达式和 function 声明提升到当前作用域的顶部。

// var 表达式被移动到这里
var bar, someValue; // 缺省值是 'undefined'

// 函数声明也会提升
function test(data) {
    var goo, i, e; // 没有块级作用域，这些变量被移动到函数顶部
    if (false) {
        goo = 1;

    } else {
        goo = 2;
    }
    for(i = 0; i < 100; i++) {
        e = data[i];
    }
}

bar(); // 出错：TypeError，因为 bar 依然是 'undefined'
someValue = 42; // 赋值语句不会被提升规则（hoisting）影响
bar = function() {};

test();

Type conversion: string to number

• Number("10"): return a primitive number

• new Number("10"): return a number object

  new Number(10) === 10;     // False, 对象与数字的比较
  Number(10) === 10;         // True, 数字与数字的比较
  new Number(10) + 0 === 10; // True, 由于隐式的类型转换

LeetCode: word break

Given an array of strings and a target string, determin whether the target string can be formed using strings from the given array.

1. BAD version : many duplicate check for substrings

   function canFormTarget( arr, target ){
       if( target.length === 0 ) return true
       
       for( let i = 0; i < target.length; i++ ){
           let prefix = target.substr(0,i+1)
           let suffix = target.substr(i+1)
           if( arr.includes(prefix) && canFormTarget(arr, suffix) )
               return true
       }
       return false
   }
   
   // Test
   let arr = ["l", "e", "ee", "et", "co", "d", "e"]
   let target = "leetcode"
   
   
   console.time("test")
   let result = canFormTarget(arr, target)
   console.timeEnd("test")

2. GOOD version : use DP with memoization to speed up process

   let strChecked = new Map()
   function canFormTarget( arr, target ){
       if( target.length === 0 ) return true
       if( strChecked.has(target) ) return strChecked.get(target)
       for( let i = 0; i < target.length; i++ ){
           let prefix = target.substr(0,i+1)
           let suffix = target.substr(i+1)
           if( arr.includes(prefix) && canFormTarget(arr, suffix) ){
               strChecked.set(target, true)
               return true
           }
       }
       strChecked.set(target, false)
       return false
   }
   
   // Test
   let arr = ["l", "e", "ee", "et", "co", "d", "e"]
   let target = "leetcode"
   
   console.time("test")
   let result = canFormTarget(arr, target)
   console.timeEnd("test")

Curry Function

Implement a curry function addToBase will return another function take an argument to be added on the base.

function addToBase(base){
    return function(addOn){
        return base+addOn
    }
}

// TEST
let addToTen = addToBase(10)
console.log(addToTen(1)) // 11
console.log(addToTen(3)) // 13

let addToHundred = addToBase(100)
console.log(addToHundred(1)) // 101
console.log(addToHundred(3)) // 103

Counting frequency of values in an object

var names = ['Alice', 'Bob', 'Tiff', 'Bruce', 'Alice'];
let res = names.reduce((accum, item, index, names)=>{
  if( accum[item] ){
    accum[item]++
  }else{
    accum[item] = 1
  }
  return accum
},{})
console.log(res)

Group objects by a certain property

let people = [
    {name: "a", age: 10},    
    {name: "b", age: 10},
    {name: "c", age: 12},
    {name: "d", age: 12},
    {name: "e", age: 12},
    {name: "f", age: 14},
    {name: "g", age: 15},
]

/*
	OUTPUT should be: 
 { 
   10: [
         {name: "a", age: 10},    
         {name: "b", age: 10},
       ],
   12: [
          {name: "c", age: 12},
          {name: "d", age: 12},
          {name: "e", age: 12},
       ],
   14: [
   		  {name: "f", age: 14}
       ],
   15: [
     	  {name: "g", age: 15}
       ]
 }
*/

function groupByAge(accum, item, index, arr){
    if(item.age in accum){
         accum[item.age].push(item)
    }else{
        accum[item.age] = [item]
    }
    return accum
}
let groupedPeople = people.reduce(groupByAge)
console.log(groupedPeople)

Function composition enabling piping

const double = x => x + x;
const triple = x => 3 * x;
const quadruple = x => 4 * x;

// Function composition enabling pipe functionality
const pipe = (...funcs)=>{
  return function(input){
    return funcs.reduce((accum, fun)=>{
      accum = fun(accum)
      return accum
    }, input)
  }
}


// Composed functions for multiplication of specific values
const multiply6 = pipe(double, triple);
const multiply9 = pipe(triple, triple);
const multiply16 = pipe(quadruple, quadruple);
const multiply24 = pipe(double, triple, quadruple);

// Usage
console.log(multiply6(6)); // 36
console.log(multiply9(9)); // 81
console.log(multiply16(16)); // 256
console.log(multiply24(10)); // 240

Another composition / pipe example

const compose = (...args)=>{
    return function(x){
        return args.reduce( function(accum, item){
            return item(accum)
        }, x)
    }
}

let pipe = (...args)=>{
    return function(x){
        return args.reduceRight( function(accum, item){
            return item(accum)
        }, x)
    }
}

// TEST
console.log(" TEST: compose & pipe: ")
const add = x => y => x + y
const multiply = x => y => x * y

const testCompose = compose(add(2), multiply(3), add(2), multiply(3))
console.log(testCompose(1)) // ( (2+1) * 3 + 2 )*3 = 9

const testPipe = pipe(add(2), multiply(3), add(2), multiply(3))
console.log(testPipe(1))     //( ( ( 1 * 3) + 2) * 3) + 2

Composition vs Inheritance

Here we compare 2 ways to make an Employee object, using Composition and Inheritance

1. make employee using Inheritance

   function Person(fn, ln){
     this.firstName = fn;
     this.lastName = ln;
   };
    
   Person.prototype.getInfo = function(greetStr){
     //In real life this method/function will be bigger
     return `${greetStr}, I am ${this.firstName} ${this.lastName}.`
   }
    
   function Employee(fn, ln, empid){
     Person.call(this, fn, ln);
     this.empid = empid;
   };
    
   Employee.prototype = Object.create(Person.prototype);
   Employee.prototype.getId = function(greetStr){
     return return `${greetStr}, my employee id is ${this.empid}.`;
   }s
   var e1 = new Employee("John", "Doe", 123);
   console.log( e1.getInfo('Hi') ); // Hi, I am John Doe.
   console.log( e1.getId('Hello') ); // Hello, my employee id is 123.

2. make employee using Composition [ Closure applied ]

   function getInfo(firstName, lastName, greetStr){
     return `${greetStr}, I am ${firstName} ${lastName}.`
   }
    
   function getId(empid, greetStr){
     return `${greetStr}, my employee id is ${empid}.`;
   }
    
   function createEmployee(fn, ln, empid){
     return {
       empid: empid,
       getId : (greetStr) => getId(empid, greetStr),
       getInfo: (greetStr) => getInfo(fn, ln, greetStr) 
     };
   }
   
   var e1 = createEmployee("john", "doe", 123);
   console.log( e1.getInfo('Hi') ); // Hi, I am John Doe.
   console.log( e1.getId('Hello') ); // Hello, my employee id is 123.

CSS: width:100% for parent with position:relative & position:absolute

1. will escape from normal document flow:

   • position: absolute: Note, if no top, left, right, bottom specified, it will stay at its original position
   • postion:fixed

2. won’t escape from normal document flow:

   • position: relative
   • float

3. width:100% : the percentage means relative to its parents

   • If still in normal document flow: parent is its container

   • if not in normal document flow: parent is the element it positioned relative to

     <!DOCTYPE html>
     <html>
         <head>
             <style>
                 #outer{
                     width: 100px;            
                     height: 100px;
                     border: 1px red solid;
                 }
     
                 #inner1{
                     position: relative;
                     width:100%;
                     height:100%;
                     border: 1px green solid;
                 }
     
                 #inner2{
                     position: absolute;
                     width:100%;
                     height:100%;
                     border: 1px blue solid;
                 }
     
             </style>
         </head>
         
         <body>
             <div id="outer">
                 <div id="inner1">
                 </div>
                 <div id="inner2">
                 </div>
             </div>
         </body>
     </html>

Add, Remove& Toggle Classes With classList in JavaScript

Say we have an element like this:

<div class="cool new shades">
  	content
</div>

We can get all class names using 2 ways:

1. element.classList

   let shadesEl = document.querySelector('.cool');
   
   console.log(shadesEl.classList);
   // ["cool", "new", "shades", value: "cool new shades"]
   
   console.log(shadesEl.classList[1]); // new

2. element.className

   let shadesEl = document.querySelector('.cool');
   
   console.log(shadesEl.className);
   // "cool new shades"

   add

   shadesEl.classList.add('make', 'me', 'look', 'rad');
   // <div class="cool new shades make me look rad">content </div>

   contains

   console.log(shadesEl.classList.contains('look')); // true

   item

   console.log(shadesEl.classList.item(3));   // make
   // equals way
   console.log(shadesEl.classList[3]);  	   // make

   remove

   shadesEl.classList.remove('cool', 'make', 'me');
   // <div class="new shades look rad">content </div>

   toggle

   // GOOD version
   coolButton.addEventListener('click', () => {
     shadesEl.classList.toggle('cool');
   });
   
   // BAD toggle
   if (shadesEl.classList.contains('rad')) {
     shadesEl.classList.remove('rad');
   } else {
     shadesEl.classList.add('rad');
   }