Let's create something!

Window VS document

1. window: a global object, and everything runs under it, including document
   • global variables,
   • global functions,
   • location
   • history
   • setTimeout
   • ajax call (XMLHttpRequest),
   • console
   • localStorage
2. documnet: represents the DOM and DOM is the object oriented representation of the html markup you have written;
   • All the nodes are part of document. Hence you can use getElementById or addEventListener on document.

window.onload vs document.onload

1. window.onload: When EVERYTHING is loaded. DOM is ready and all the contents including images, css, scripts, sub-frames, etc. finished loaded.
2. document.onload: once the DOM is loaded, regardless of the css, scripts,…

attribute vs property

1. attribute: belongs to HTML tag, is static after being initialized

2. property: belongs to DOM node, is dynamic while interact with its element

3. 1 2 3 4 5 6

   <input id="my-input" type="text" value="Name:"> <script> var myInput = document.getElementById('my-input'); myInput.getAttribute('value'); //"Name:" myInput.value; //'my dude' </script>

Add class to element: classList

1
2
3
4
5
6

function addClass(selector, className){
   var elm = document.querySelector(selector);
   if (elm){
      elm.classList.add(className);
   }
}

Check Descendant

1
2
3
4
5
6
7
8
9

function isDescendant(parent, child){ 
  while(child.parentNode ){ 
    if(child.parentNode == parent)
      return true;
    else
      child = child.parentNode;
  }
  return false;
}

Create DOM element: innerHTML vs appendChild

1. innerHTML: browser removes all the current children of the elements. Parse the string and assign the parsed string to the element as children. So, Slow!

   1. 1 2 3

      var ul = document.getElementById('myList'); el.innerHTML = '<li>Only one item</li>';

2. appendChild: you create a new Element. Since you are creating it, browser doesnt have to parse string and there is no invalid html. so, Fast!

   1. 1 2 3 4 5

      var li = document.createElement("li"); var text = document.createTextNode('Only one Item'); li.appendChild(text); ul.appendChild(li);

CrateDocumentFragment: improve performance

1. documentFragment a lightweight or minimal part of a DOM or a subtree of a DOM tree.

2. It is very helpful when you are manipulating a part of DOM for multiple times.

3. It becomes expensive to hit a certain portion of DOM for hundreds time. You might cause reflow for hundred times. Stay tuned for reflow.

   • BAD practice:

     • 1 2 3 4 5 6 7 8 9

       //bad practice. you are hitting the DOM every single time var list = ['foo', 'bar', 'baz', ... ], el, text; for (var i = 0; i < list.length; i++) { el = document.createElement('li'); text = document.createTextNode(list[i]); el.appendChild(text); document.body.appendChild(el); }

   • GOOD practice:

     • 1 2 3 4 5 6 7 8 9 10 11 12

       //good practice. you causing reflow one time var fragment = document.createDocumentFragment(), list = ['foo', 'bar', 'baz', ...], el, text; for (var i = 0; i < list.length; i++) { el = document.createElement('li'); text = document.createTextNode(list[i]); el.appendChild(text); fragment.appendChild(el); } document.body.appendChild(fragment);

reflow

1. [reflow] : flow of the elements in the page is changed due to change size or position
   • When you change size or position of an element in the page, all the elements after it has to change their position according to the changes you made.
   • For example, if you change height on an element, all the elements under it has to move down in the page to accomodate a change in height.
2. Reasons:
   • change layout (geometry of the page)
   • resize the window
   • change height/width of any element
   • changing font, or font size
   • move DOM element (animation)
   • adding or removing stylesheet
   • calculating offset height or offset width
   • display: none;

repaint

1. It happens when you change the look of an element without changing the size and shape. This doesn’t cause reflow as geometry of the element didn’t changed.
2. Reasons:
   • change background color
   • change text color
   • visibility hidden

destroy button

Create a button that is destroyed by clicking on it but two new buttons are created in it’s place.

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

<div id="wrapper">
    <button id="doubleHolder" class="double">double</button>
</div>
<script>
    document.getElementById('doubleHolder').addEventListener('click', function (e) {   
        var btn = document.createElement('button');
        btn.setAttribute('class', 'double');
        btn.innerHTML = 'double1';

        var btn2 = document.createElement('button');
        btn2.setAttribute('class', 'double');
        btn2.innerHTML = 'double2';
        let wrapper = document.getElementById('wrapper')
        wrapper.appendChild(btn);
        wrapper.appendChild(btn2);
        wrapper.removeChild(e.target);   
    }); 
</script>

Get text of a Node: innerHTML textContent innerText

1. innerHTML parses content as HTML and takes longer. Also vulnerable to XSS attacks

2. textContent uses straight text, does not parse HTML, and is faster.

   1. 1 2 3 4 5 6 7 8 9 10 11 12

      // Given the following HTML fragment: // <div id="divA">This is <span>some</span> text</div> // Get the text content: var text = document.getElementById("divA").textContent; // |text| is set to "This is some text". // Set the text content: document.getElementById("divA").textContent = "This is some text"; // The HTML for divA is now: // <div id="divA">This is some text</div> Polyfill

3. innerText Takes styles into consideration. It won’t get hidden text for instance.: Bad, causing reflow !

defer vs async

1. defer & async are only effective in <script> tag. HTML parser will ignore defer and async keyword for inline script (script that does not have a src attribute).
2. normal: When you have a plain script tag (no defer or async keyword), parser will pause parsing, script would be downloaded and exectuted. After that parsing resume
3. async: downloading script won’t affect HTML paring, but executing will pause HTML parsing. Once downloaded, script begin to executed, will pause HTML parsing
4. defer: downloading script won’t affect HTML paring, also executing won’t affect HTML parsing. The script with defer will executed util HTML finish parsing

Problem

Build a web calculator, that supports the basic operations of add, remove, multiply and divide.

In addition, support resetting the current state, as well as a decimal point button.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

<html>
  <head>
  	<style>
       .wrapper{
          width: 400px;
          height: 400px;
          margin: 15px auto;
          border: 1px solid black;
        }
        .display-panel{
          margin: 10px auto;
          width: 95%;
          height: 60px;
          line-height: 60px;
          font-size: 30px;
          border: 1px solid black;
          text-align: right;
          overflow-y: hidden;
          overflow-x: scroll;
          white-space: nowrap;
        }

        .ctl-panel{
          margin: 5px auto;
          width: 95%;
          height: 300px;
          border: 1px solid black;
          font-size: 30px;
          display: flex;
          flex-flow: row wrap;
          justify-content: space-around;
        }

        .left-part{
          border: 1px solid red;
          flex: 1 1 70%;
          display: grid;
          justify-content: space-around;
          align-content: space-around;
          grid-template-columns: auto auto auto;
          grid-template-rows: auto auto auto auto;
        }


        .right-part{
          flex: 1 1 20%;
          border: 1px solid red;
          display: grid;
          justify-content: space-around;
          align-content: space-around;
          grid-template-columns: auto;
          grid-template-rows: 30% 60%;
        }

        #equal{
          height: 100%;
        }

        button{
          width: 50px;
          height: 50px;
        }
    </style>
  </head>
  <body>
    <div class="wrapper"> 
      <div class="display-panel" id="display">
        display placeholdersdsfsdfsdfsdffsdfsdffsdf
      </div>
      <div class="ctl-panel" id="panel">
        <div class='left-part'>
            <div><button>+</button></div>
            <div><button>-</button></div>
            <div><button>&times;</button></div>
            <div><button>7</button></div>
            <div><button>8</button></div>
            <div><button>9</button></div>
            <div><button>4</button></div>
            <div><button>5</button></div>
            <div><button>6</button></div>
            <div><button>1</button></div>
            <div><button>2</button></div>
            <div><button>3</button></div>
            <div><button>0</button></div>
            <div><button>.</button></div>
            <div><button>C</button></div>
        </div>
        <div class='right-part'>
          <div><button>&divide;</button></div>
          <div><button id="equal">&equals;</button></div>
        </div>
      </div>
    </div>
      
    <script>
        function handleInput(e){
          let val = e.target.textContent
          let display = document.getElementById("display")
          if(isNum(val)){
             handleNum(val, display);
          }else if(isDot(val)){
             handleDot(val, display);      
          }else if(isOperator(val)){
             handleOperator(val, display)
          }else if(isEqual(val)){
             handleCalc(display)
          }else if(isClear(val)){
             handleClear(display)
          }else{
            return 
          }
        }

        function handleClear(display){ 
            display.textContent = "" 
        }
        
        function handleNum(v, display){
          let oldText = display.textContent
          display.textContent += v
        }

        function handleOperator(v, display){
          let oldText = display.textContent
          if( isOperator(oldText[oldText.length-1]) )
              oldText=oldText.substr(0,oldText.length-1)
          display.textContent = oldText+v
        }

        function handleDot(v, display){
          let oldText = display.textContent
          if( isDot(oldText[oldText.length-1]) ) return
          display.textContent += v
        }

        
        function handleCalc(display){
          let oldText = display.textContent
          if( !isNum(oldText[oldText.length-1]) ) {
            display.textContent = 0
            return
          }
          display.textContent = calc(oldText)
        }
		
        function calc( text ){
          let stack = []
          let numbers = text.split(/\+|\-|\×|\÷/)
          let operators =  text.replace(/[0-9]|\./g, "").split("")
          console.log(numbers)
          console.log(operators)

          stack.push(new Number(numbers[0]) )
          for( let i = 0; i < operators.length; i++ ){
            let num = new Number( numbers[i+1] )
            if(operators[i] === "+"){
              stack.push(num)
            }else if(operators[i] === "-"){
              stack.push(-num)
            }else if(operators[i] === "×"){
              let top = stack.pop()
              stack.push(top*num)
            }else if(operators[i] === "÷"){
              let top = stack.pop()
              stack.push(top/num)
            }
          }
          console.log(stack)
          return stack.reduce((item,accum)=>{
               return accum + item
          },0)
        }
        
        
        function isNum(v){  return v >= "0" && v <= "9" }
        function isClear(v){ return v === 'C' }
        function isEqual(v){ return v === '=' }
        function isDot(v){ return v === '.' }
		function isOperator(v){
          return v === '+' ||  v === '-' ||  v === '÷' ||  v === '×'
        }
        
        document.getElementById("panel").addEventListener( "click", handleInput )
    </script>
  </body>
</html>

Problem

Given an original array, and it new position to be. Reposition it according the given indices array. For example:

1
2
3
4

let arr  =    ["a", "b", "c", "d", "e", "f"]
let indices = [ 1,   2,   3,   5,   0,   4 ]

// the new array should be ["e", "a", "b", "c", "f", "d"]

Follow Up

Try to do it in-place, i.e. : Space Complexity O(1)

Solution 1: Space complexity O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function rePosition(arr, indices){
    if( arr.length !== indices.length ) 
        throw new Error("they are not the same length")
    
    let newArr = indices.map((item, index)=>{
        return arr[indices.indexOf(index)]
    })
    return newArr
}

// Tests
let newArr = []
let arr  =     ["a", "b", "c", "d", "e", "f"]

// test 1
let indices1 = [ 1,   2,   3,   5,   0,   4 ]
newArr = rePosition(arr, indices1)
console.log(newArr)  // ["e", "a", "b", "c", "f", "d"]

// test 2
let indices2 = [ 0,   1,   2,   3,   4,   5 ]
newArr = rePosition(arr, indices2)
console.log(newArr) //  ["a", "b", "c", "d", "e", "f"]

// test 3
let indices3 = [ 2,   1,   0,   4,   3,   5 ]
newArr = rePosition(arr, indices3)
console.log(newArr) //  ["c", "b", "a", "e", "d", "f"]

Solution 2: Space complexity O(1)

We need two variables: kickedItem and kickedIndex, to denote the kicked item in arr and kicked index in indices

1. Every time we update an item in its new position, we put item in its new position, and swap the kicked item and index to their counterpart in arr & indices

2. Since the kicked item & its new position are just swapped to previous position, we can keep staring the same position to deal with the chaining update, until there is an end to the chain

3. NOTE: there are also cases (test case 3) that the new indices are not depended upon one another, but instead they are partially dependent. That’s why we need to maintain two variable for both arr & indices, rather than just for arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

function rePosition(arr, indices){
	if( arr.length !== indices.length ) 
        throw new Error("they are not the same length")
    
    for( let i = 0; i < arr.length; i++ ){
        while( i !== indices[i] ){
            let kickedItem = arr[indices[i]]
            let kickedIndex = indices[indices[i]]
            arr[indices[i]] = arr[i]
            indices[indices[i]] = indices[i]
            arr[i] = kickedItem
            indices[i] = kickedIndex
        }
    }
}

// Tests

// test 1
let arr  =     ["a", "b", "c", "d", "e", "f"]
let indices1 = [ 1,   2,   3,   5,   0,   4 ]
rePosition(arr, indices1)
console.log(arr)  // ["e", "a", "b", "c", "f", "d"]

// test 2
arr  =     ["a", "b", "c", "d", "e", "f"]
let indices2 = [ 0,   1,   2,   3,   4,   5 ]
rePosition(arr, indices2)
console.log(arr) //  ["a", "b", "c", "d", "e", "f"]

// test 3
arr  =     ["a", "b", "c", "d", "e", "f"]
let indices3 = [ 2,   1,   0,   4,   3,   5 ]
rePosition(arr, indices3)
console.log(arr) //  ["c", "b", "a", "e", "d", "f"]

Problem

Given an nested array, flatten it to 1-dimension array.

For example:

1
2
3

[1, [2, [ [3, 4], 5], 6], [7, 8], 9]
=> 
[1, 2, 3, 4, 5, 6, 7, 8,  9]

Solution 1: iterative version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 1. iterative [stack]
function flatten1( arr ){
    let res = []
    let stack = []
    stack.push(arr)
    while( stack.length > 0 ){
        let item = stack.pop()
        if( !Array.isArray(item) ){
            res.push(item)
        }else{
            for( let i = item.length-1; i >=0; i-- ){
                stack.push(item[i])
            } 
        }
    }
    return res
}

Solution 2: recursive version

1
2
3
4
5
6

function flatten2(arr){
    if( !Array.isArray(arr) ){
        return [arr]
    }
    return [].concat(...arr.map(flatten2))
}

Solution 3: recursive version [shorter]

1
2
3

function flatten(a) {
	return Array.isArray(a) ? [].concat(...a.map(flatten)) : a;
}

Testing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

let test1 = [1, [2, 3, [4, 5]], 6, [7, [8, 9], 10], 11]
let test2 = []
let test3 = [1]
let test4 = 1
let test5 = [[[1,2,3]]]
let test6 = [[[]],[],[],[],[[[]]]]


// let arrayFlattened1 = flatten1(test1).toString()
// let arrayFlattened2 = flatten1(test2).toString()
// let arrayFlattened3 = flatten1(test3).toString()
// let arrayFlattened4 = flatten1(test4).toString()
// let arrayFlattened5 = flatten1(test5).toString()
// let arrayFlattened6 = flatten1(test6).toString()
let arrayFlattened1 = flatten2(test1).toString()
let arrayFlattened2 = flatten2(test2).toString()
let arrayFlattened3 = flatten2(test3).toString()
let arrayFlattened4 = flatten2(test4).toString()
let arrayFlattened5 = flatten2(test5).toString()
let arrayFlattened6 = flatten2(test6).toString()
console.log(arrayFlattened1)
console.log(arrayFlattened2)
console.log(arrayFlattened3)
console.log(arrayFlattened4)
console.log(arrayFlattened5)
console.log(arrayFlattened6)

0. All credits to ThatJSDude

1. Verify a prime number?

   1. version 1: not too good

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

         function isPrime( num ){ let i = 2 while( i <= num/2 ){ if( num % 2 === 0 ) return false i += 1 } return true } // Test console.log(isPrime(1)) // true console.log(isPrime(2)) // true console.log(isPrime(4)) // false console.log(isPrime(7)) // true console.log(isPrime(101)) // true

   2. Improved Version

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

         function isPrime(n) { let divisor = 3, let limit = Math.sqrt(n); //check simple cases if (n == 2 || n == 3) return true; if (n % 2 == 0) return false; while (divisor <= limit) { if (n % divisor == 0) return false; else divisor += 2; } return true; } > isPrime(137); = true > isPrime(237); = false

2. Find all prime factors of a number?

   1. Find all prime factors

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

         function findAllPrimeFactors( num ){ let factors = [] let i = 2 while( num > 2 ){ if( num % i === 0 ){ factors.push(i) num /= i }else{ i += 1 } } return factors } // test console.log(findAllPrimeFactors(420)) // 2 2 3 5 7

   2. Find distinct prime factors

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

         function findDistinctPrimeFactors( num ){ let factors = [] let i = 2 let temp = num while( i <= num/2 ){ if( temp % i === 0 ) { factors.push(i) while(temp % i === 0) temp /= i } i += 1 } return factors } // test console.log(findDistinctPrimeFactors(420)) // 2 3 5 7

3. Get nth Fibonacci number?

   1. f(n) = f(n-1) + f(n-2)

   2. Give n, print fibonacci sequence from 0 ~ n

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

         // 1. Iterative function f(n){ let fb = [] fb[0] = 1 fb[1] = 1 for( let i = 2; i <= n; i++ ){ fb[i] = fb[i-1] + fb[i-2] } return fb; } // 2. recursive function wrapperFb(n){ let memo = new Array(n+1).fill(0) memo[0] = 1 memo[1] = 1 function f(n){ if( n===0 || n===1 ) return 1 if( memo[n] !== 0 ) return memo[n] else memo[n] = f(n-1) + f(n-2) return memo[n] } f(n) return memo } console.log(wrapperFb(5)) // 1 1 2 3 5 8

   3. Give n, print the nth fibonacci number

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

         // 1. iterative function fth(n){ let fb = [] fb[0] = 1 fb[1] = 1 for( let i = 2; i <= n; i++ ){ fb[i] = fb[i-1] + fb[i-2] } return fb[n]; } console.log(fth(5)) // 8 // 2. recursive function wrapperFb(n){ let memo = new Array(n+1).fill(0) memo[0] = 1 memo[1] = 1 function f(n){ if( n===0 || n===1 ) return 1 if( memo[n] !== 0 ) return memo[n] else memo[n] = f(n-1) + f(n-2) return memo[n] } return f(n) } console.log(wrapperFb(5)) // 8

4. Find the greatest common divisor of two numbers?

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14

      function greatCommonDevisor ( n1, n2 ){ let res = 1 let i = 2 while( i <= n1 || i <= n2 ){ while( n1%i === 0 && n2%i === 0 ){ res *= i n1 /= i n2 /= i } i += 1 } return res } console.log(greatCommonDevisor(36,48)) // 12

5. Remove duplicate members from an array?

   1. 1 2 3 4 5 6 7 8 9 10 11

      function removeDup(arr){ let set = new Set() return arr.filter( item =>{ if( !set.has(item) ){ set.add(item) return item } }) } let arr = [3,2,3,3,1,2,2,4,4,3,5] console.log(removeDup(arr)) // [3,2,1,4,5]

6. Merge two sorted array?

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

      function merge( arr1, arr2 ){ let arr = [] let i = 0, j = 0 while( i < arr1.length && j < arr2.length ){ if( arr1[i] < arr2[j] ){ arr.push(arr1[i]) i += 1 }else{ arr.push(arr2[j]) j += 1 } } if( i < arr1.length ) arr.push(...arr1.slice(i)) if( j < arr2.length ) arr.push(...arr2.slice(j)) return arr } let arr1 = [ 1, 3, 5, 5, 6, 8 ] let arr2 = [ 1, 2, 2, 4, 7, 8, 9 ] console.log(merge(arr1, arr2)) // [1,1,2,2,3,4,5,5,6,7,8,8,9]

7. Swap two numbers without using a temp variable?

   1. using diff

      1. 1 2 3 4 5

         function swap(a, b){ a = a - b b = a + b a = b - a }

   2. using XOR

      1. 1 2 3 4 5

         function swap(a, b){ a = a ^ b b = a ^ b a = a ^ b }

8. Reverse a string in JavaScript?

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

      // 1. recursive version function reverseStr( str ){ if( str === "" ) return "" return reverseStr(str.substring(1)) + str.charAt(0) } console.log(reverseStr("abcdef")) // "fedcba" // 2. built-in method function reverse(str){ if(!str || str.length <2) return str; return str.split('').reverse().join(''); } console.log(reverseStr("abcdef")) // "fedcba" // 3. string util method String.prototype.reverse = function(){ if(!this || this.length <2) return this; return this.split('').reverse().join(''); } let str = "abcdef" console.log(str.reverse()) // "fedcba"

9. Find the first non repeating char in a string?

   1. Using Map instead of object to collect the frequency for each char

   2. Since we want to iterate the map in-order, while object cannot guanrentee this

      1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

         // In the end, we need to iterate the key in-order, so we cannot count on object, but instead of Map, which give in-order traverse function firstNonRepeat(str){ let map = new Map() for( let i = 0; i < str.length; i++ ){ let char = str[i] if( map.has(char) ){ map.set( char, map.get(char)+1 ) }else{ map.set( char, 1 ) } } let arr = Array.from(map) for( let i = 0; i < arr.length; i++ ){ if( arr[i][1] === 1 ) return arr[i][0] } return -1; } let str = "the quick brown fox jumps then quickly blow air" console.log(firstNonRepeat(str))

10. Match substring of a sting?

    1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

       // aaabc // aab function subStringFinder(str, subStr){ let index = 0 while( index <= str.length-subStr.length ){ let sub = str.substring(index, index+subStr.length) if( sub === subStr ) return index else index += 1 } return -1 } // test console.log(subStringFinder("aaabc", "aab")) // 1 console.log(subStringFinder('abbcdabbbbbck', 'bbbck') ) // 8

11. Create all permutation of a string?

    1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

       /* 0 1 2 3 1 2 3 2 3 3 2 */ // [version 1.1 recursive]: String with no-dup character function permutations(str){ let perm = [] let prefix = "" function dfs(str){ if( prefix.length === str.length ){ perm.push(new String(prefix)) return } for( let i = 0; i < str.length; i++ ){ if( prefix.indexOf(str[i]) === -1 ){ prefix += str[i] dfs(str) prefix = prefix.substring(0, prefix.length-1) } } } dfs(str) return perm } console.log(permutations("abc")) // [version 1.2 iterative]: String with no-dup character function permutations(str){ let queue = [] queue.push("") let level = 0 while( level < str.length ){ let size = queue.length for( let k = 0; k < size; k++ ){ let prefix = queue.shift() for( let i = 0; i < str.length; i++ ){ if( prefix.indexOf(str[i]) === -1 ){ queue.push(prefix+str[i]) } } } level += 1 } return queue } console.log(permutations("abc")) // [version 2.1-recursive]: string with duplicate character function permutations(str){ let map = new Map() let perm = [] let prefix = "" for( let i = 0; i < str.length; i++ ){ if( map.has(str[i]) ){ map.set( str[i], map.get(str[i])+1 ) }else{ map.set( str[i], 1 ) } } function dfs(str){ if( prefix.length == str.length ){ perm.push(prefix) return } let freqArr = Array.from(map) console.log(freqArr) for( let i = 0; i < freqArr.length; i++ ){ let char = freqArr[i][0] let freq = freqArr[i][1] if( map.get(char) > 0){ prefix += char map.set(char, freq-1 ) dfs(str) map.set(char, freq ) prefix = prefix.substring(0, prefix.length-1) } } } dfs(str) return perm } console.log(permutations("abc")) console.log(permutations("aac"))

Stack

1. interfaces:

   • stack.size
   • stack.peek()
   • stack.push
   • stack.pop()
   • stack.isEmpty()
   • stack.clear()

2. implementation:

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

      /* * Note: this version use `null` as Error symbol, * so you cannot push null into the stack */ class Stack{ constructor(){ this.data = [] } get size(){ return this.data.length } isEmpty(){ return this.data.length === 0 } peek(){ return this.data[this.data.length-1] } push(item){ if( typeof item ==="undefined" || item === null ) return false this.data.push(item) return true } pop(item){ if(this.data.length === 0) return null return this.data.pop(); } clear(){ this.data = [] } } /* ---- Testing ---- */ let s = new Stack() console.log("size: ",s.size) // 0 console.log(s.pop()) // null console.log(s.push()) // false console.log(s.push(null)) // false console.log(s.push(1)) // true console.log(s.push(1)) // true console.log("size: ",s.size) // 2 console.log(s.push(2)) // true console.log("size: ",s.size) // 3 console.log(s.pop()) // 2 console.log("size: ", s.size) // 2 console.log(s.pop()) // 1 console.log(s.pop()) // 1 console.log("size: ", s.size) // 0 console.log(s.pop()) // null console.log("size: ", s.size) // 0 console.log(s.isEmpty()) // true

Queue

1. interfaces:

   • queue.size
   • queue.peek()
   • queue.push
   • queue.pop()
   • queue.isEmpty()
   • queue.clear()

2. implementation:

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

      /* * Note: this version can add any object into Queue * But need to call `isEmpty()` when necessary */ class Queue{ constructor(){ this.items = [] } get size(){ return this.items.length; } isEmpty(){ return this.items.length === 0 } offer(item){ this.items.push(item) } poll(){ return this.items.shift() } peek(){ return this.items[0] } clear(){ this.items = [] } } /* ---- Testing ---- */ let q = new Queue() console.log("size: ", q.size)// 0 console.log(q.offer(null)) console.log(q.offer(null)) console.log(q.items) // [null, null] console.log(q.offer(1)) console.log(q.items) // [null, null, 1] console.log(q.poll()) // null console.log(q.offer(2)) // [null, 1, 2] console.log("size: ",q.size)// 3 console.log(q.poll()) console.log(q.items) // [1, 2] console.log(q.poll()) // 1 console.log(q.items) // [2] console.log("size: ", q.size)// 1 console.log(q.poll()) // 2 console.log("size: ", q.size)// 0 console.log(q.isEmpty()) // true

I. Logic

1. For each input, wait 500ms to make API call, to load 40 items
2. scroll down close to bottom ( less than 20px left ), make API call to load another 40 items
3. could add local cache, to speed up response

II. code

1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144

   <!DOCTYPE html> <html> <head> <style> #wrapper { margin-top: 10px; overflow: auto; width: 250px; display: inline-block; border: 1px solid red; overflow: hidden; } .listWrapper{ border: 1px solid blue; height: 200px; width: 140px; overflow: auto; scroll: auto; } </style> </head> <body> <div id="wrapper"> <div> <input id="inputText" /> <button>submit</button> </div> </div> <script> let body = document.getElementsByTagName("BODY")[0] let data = Array.from({length: 40}, () => "recommdation"+Math.floor(Math.random() * 40)); const API = "https://www.demo.com/potentialList" let isFetching = false // used for scroll let isEnd = false // used for scroll // create new element below <input> inside div wrapper. For both 'input' & 'scroll' function appendList(elementCollection, wrapper, isScroll){ if(isScroll){ let listWrapper = document.getElementsByClassName("listWrapper")[0] data.forEach( ele=>{ let itemNode = document.createElement("DIV") let textNode = document.createTextNode(ele) itemNode.appendChild(textNode) listWrapper.appendChild(itemNode) }) return } let oldlistWrapper = document.getElementsByClassName("listWrapper") if(oldlistWrapper.length > 0){ wrapper.removeChild(oldlistWrapper[0]) } let listWrapper = document.createElement("DIV") listWrapper.setAttribute("class", "listWrapper") let list = Array.prototype.slice.call(elementCollection) data.forEach( ele=>{ let itemNode = document.createElement("DIV") let textNode = document.createTextNode(ele) itemNode.appendChild(textNode) listWrapper.appendChild(itemNode) }) listWrapper.addEventListener("click", putToInput) listWrapper.addEventListener("scroll", scrollHandler) wrapper.appendChild(listWrapper) } // onclick callback for items provided function putToInput(e){ let input = document.getElementById("inputText") let wrapper = document.getElementById("wrapper") let listWrapper = document.getElementsByClassName("listWrapper")[0] input.value = e.target.innerHTML console.log(e.target) wrapper.removeChild(listWrapper) } // make API call function makeAPICall(API, val, isScroll){ console.log("val: ", val) // 1. first check local cache // 2. hit fail, call API let ajax = new XMLHttpRequest() ajax.open("GET", "https://www.w3schools.com/js/ajax_info.txt", true) ajax.onreadystatechange = function(){ if(this.readyState === 4 && this.status === 200 ){ console.log(this.responseText) let parser = new DOMParser() let a = parser.parseFromString(this.responseText, "text/html") console.log(a) let body = a.getElementsByTagName("BODY")[0] let wrapper = document.getElementById("wrapper") if(val.localeCompare("scroll made request")===0){ isFetching = false } appendList(data, wrapper, isScroll) } } ajax.send() } // scroll handler for listWrapper function scrollHandler(e){ let listWrapper = e.target let boxHeight = listWrapper.clientHeight let scrollTop = listWrapper.scrollTop let scrollHeight = listWrapper.scrollHeight let remainder = scrollHeight - scrollTop let diff = remainder - boxHeight console.log("box height: ", boxHeight) console.log("scrollTop: ", scrollTop) console.log("scrollHeight: ", scrollHeight) console.log("diff: ", diff) if( diff < 20 && !isFetching && !isEnd ){ isFetching = true makeAPICall(API, "scroll made request", true) } } // debounce 500ms to make API call let timeHandler = null function inputHandler(e){ clearTimeout(timeHandler) let val = e.target.value timeHandler = setTimeout( function(){makeAPICall(API, "keypress made request", false)} ,500 ) } let input = document.getElementById("inputText") addEventListener("input", inputHandler) </script> </body> </html>

Problem

Given two DOM trees with the same structure, and one node in tree1, try to find its symmetric node in tree2

Solution 1

If we are not so familiar with DOM API, we might forget there is an attribute for each DOM element: parentNode. Then we might just traverse both trees at the same time, when we encounter the node in tree1, the node in tree2 is what we want.

1
2
3
4
5
6
7
8
9
10
11

function getSymmetricNode(target, root1, root2){
    if( target === root1 ) return root2
    
    for( let i = 0; i < root1.childNodes.length; i++ ){
        let node1 = root1.childNodes[i]     
        let node2 = root2.childNodes[i]
        if( node1 === target ) return node2
		getSymmetricNode(target, node1, node2 )
    }
    return null
}

1. Time Complexity: O(b^d) [d: depth, b: branches], which is BAD!

Solution 2 [Improved ]

Actually there is an convenient attribute we could utilize, that is parentNode

1. First, we could go up to find that path from root1 to target
   • The path is consist of indices of node on that path
2. Using that path of indices, we could go downwards from root2 to find the desired node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

let getSymmetricNode = (target, root1, root2) => {
    let path = getIndexPath( target, root1 )
    return getNode( path, root2 )
}

let getIndexPath = (target, root1)=>{
    let path = []
    let curNode = target
    while( curNode && curNode.parentNode ){
        let index = curNode.parentNode.indexOf(curNode)
        path.push(index)
        curNode = curNode.parentNode
    }
    return path
}

let getNode =(path, root)=>{
    let node
    while( path.length > 0 ){
        node = root.childNodes[path.pop()]
    }
    return node
}

Testing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

// Testing
<!doctype html>

<html>
  <head>
    <meta charset="UTF-8" />
    <title>Hello World</title>
  </head>
  <body>
    <div id="root1">
      <div>
        <div></div>
      </div>
      <div>
        <div id="node1"></div>
        <div></div>
      </div>
    </div>

    <div id="root2">
      <div>
        <div></div>
      </div>
      <div>
        <div id="node2"></div>
        <div></div>
      </div>
    </div>
    <script>
      
      
      // --------------- 1: O(b^d) --------------
      function getSymmetricNode1(target, root1, root2){
          if( target === root1 ) return root2
          for( let i = 0; i < root1.childNodes.length; i++ ){
              let node1 = root1.childNodes[i]     
              let node2 = root2.childNodes[i]
              let res = getSymmetricNode1(target, node1, node2)
              if( null !== res ) return res
                
          }
          return null
      }
      
      
      
      
      // -------------- 2: O(b*d) ---------------
      function getSymmetricNode(target, root1, root2){
          let path = getIndexPath( target, root1 )
          return getNode( path, root2 )
      }

      function getChildNodesArray(node){
        return Array.prototype.slice.call(node.childNodes)
      }
      
      
      function getIndexPath(target, root1){
          let path = []
          let curNode = target
          while( curNode !==root1 && curNode && curNode.parentNode ){
              let index = getChildNodesArray(curNode.parentNode).indexOf(curNode)
              path.push(index)
              curNode = curNode.parentNode
          }
          return path
      }

      
      function getNode(path, root){
          let node = root
          while( path.length > 0 ){
              node = getChildNodesArray(node)[path.pop()]
          }
          return node
      }

      const root1 = document.getElementById('root1');
      const root2 = document.getElementById('root2');
      const node1 = document.getElementById('node1');
      const node2 = document.getElementById('node2');

      const nodeX = getSymmetricNode(node1, root1, root2 );
      console.log(nodeX)
      console.log(nodeX === node2); // true
    </script>
  </body>
</html>

All Credit to: Learning JavaScript Design Patterns

Constructor Pattern

1. What: a constructor is a special method used to initialize a newly created object once memory has been allocated for it

2. Why need it

   • e.g.: create different student with: name, age, eat method

   • without constructor : each time we create a new student again and again

     • 1 2 3

       let alice ={name: "alice", age: 12, eat: function(){ ... } } let bob = {name: "bob", age: 15, eat: function(){ ... } } let carol ={name: "carol", age: 11, eat: function(){ ... } }

   • with constructor [BAD] : each time we create a new student trivially

     • 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

       /* BAD: each object will take a copy of `eat()` from memory, which is in fact not necessary */ function Student( name, age ){ let student = {} student.name = name student.age = age student.eat = function(){ console.log(name, " is eating")} return student } let alice = new Student("alice", 12) let bob = new Student("bob", 15) let carol = new Student("carol", 11) alice.eat()

   • with constructor [GOOD] : see next section Prototype pattern

     • 1

Prototype Pattern

1. what: view prototype pattern as being based on prototypal inheritance where we create objects which act as prototypes for other objects.

2. improvement of Student class, using prototype.eat()

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13

      /* GOOD: each object will share `eat()` of Student prototype */ function Student( name, age ){ this.name = name this.age = age } Student.prototype.eat = function(){console.log(this.name, " is eating")} let alice = new Student("alice", 12) let bob = new Student("bob", 15) let carol = new Student("carol", 11) alice.eat()

Factory Pattern

1. what : combine similar classes together into a factory, to make code more compact

2. Implement one!

   1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

      // Types.js - Constructors used behind the scenes // A constructor for defining new cars function Car( options ) { // some defaults this.doors = options.doors || 4; this.state = options.state || "brand new"; this.color = options.color || "silver"; } // A constructor for defining new trucks function Truck( options){ this.state = options.state || "used"; this.wheelSize = options.wheelSize || "large"; this.color = options.color || "blue"; } // FactoryExample.js // Define a skeleton vehicle factory function VehicleFactory() {} // Define the prototypes and utilities for this factory // Our default vehicleClass is Car VehicleFactory.prototype.vehicleClass = Car; // Our Factory method for creating new Vehicle instances VehicleFactory.prototype.createVehicle = function ( options ) { switch(options.vehicleType){ case "car": this.vehicleClass = Car; break; case "truck": this.vehicleClass = Truck; break; //defaults to VehicleFactory.prototype.vehicleClass (Car) } return new this.vehicleClass( options ); }; // Create an instance of our factory that makes cars var carFactory = new VehicleFactory(); var car = carFactory.createVehicle( { vehicleType: "car", color: "yellow", doors: 6 } ); // Test to confirm our car was created using the vehicleClass/prototype Car // Outputs: true console.log( car instanceof Car ); // Outputs: Car object of color "yellow", doors: 6 in a "brand new" state console.log( car );