Description

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example

1
2

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution 1: brute force

Time complexity: O(n^3)

Try all the the possibilities for startIndex and endIndex of subarray, and check the sum to see if equals k

• startIndex: i = 0 ... n
• endIndex: j = i ... n
• sum and check: another loop

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

let subarraySum = function(nums, k) {
    let cnt = 0;
    let n = nums.length;
    for( let i = 0; i < n; i++ ){
        for( let j = i; j < n; j++ ){
            let sum = 0;
            for( let k = i; k <= j; k++ ){
                sum += nums[k];
            }
            if(sum === k) cnt++;
        }
    }
    return cnt;
};

Solution 2: optimize using prefix sum

Time complexity: O(n^2)

1. prefixSum array: Spcae Complexity: O(n)

   For the inner most loop, there are duplicate work for the addition to get sum(i, j). In fact, we can process it beforehand, getting an prefix sum array; Then sum(i,j) will be prefixSum[j]-prefixSum[i-1], using O(1) time

2. do summation in the fly: Spcae Complexity: O(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

// approach #1: prefixSum array
let subarraySum = function(nums, k) {
    let cnt = 0;
    let n = nums.length;
    let prefixSum = [];
    prefixSum.push(0);
    for( let i = 0; i < n; i++ ){
        prefixSum[i+1] = prefixSum[i] + nums[i];
    }
    
    for( let i = 0; i < n; i++ ){
        for( let j = i; j < n; j++ ){
            let sum = prefixSum[j+1] - prefixSum[i];
            if(sum === k) cnt++;
        }
    }
    return cnt;
};


// approach #2: do summation in the fly:
let subarraySum = function(nums, k) {
    let cnt = 0;
    let n = nums.length;
    for( let i = 0; i < n; i++ ){
        let sum = 0;
        for( let j = i; j < n; j++ ){
            sum += nums[j];
            if(sum === k) cnt++;
        }
    }
    return cnt;
};

Solution 3: optimize using HashMap

Time complexity: O(n)

Space complexity: O(1)

Based on Solution 2, we can get the subarray sum in O(n), but still the overall time complexity is O(n^2), that’s because we need to try all the possibilities of the startIndex and endIndex of subarray.

For each startIndex: i, the reason we need to iterate endIndex: j is that we want to find all the possible pair to make the subarray sum equals k.

If we change a direction to think about it, why not directly find all the the prefixSum[i'], making prefixSum[j] - prefixSum[i'] = k, and then we count all the possible i'. Thus, we need a memory to let know who will be the counterpart for the current prefixSum[j]. That’s hashmap~

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

let subarraySum = function(nums, k) {
    let cnt = 0;
    let map = new Map();
    map.set(0, 1); // we use map to store prefixSum values: special case sum=0 in begin
    
    let sum = 0;
    for( let i = 0; i < nums.length; i++ ){
        sum += nums[i];
        let target = sum - k;
        if(map.has(target)) cnt += map.get(target);
        if(!map.has(sum)) map.set(sum, 0);
        map.set(sum, map.get(sum)+1);
    }
    return cnt;
};

Description

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example

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

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution 1:

Time complexity: O(n^2) => for each node, traverse its subtree, and there are n nodes => n^2

For each node, we treat it as the starting node as the path, and count how many paths starting from it.

• we need to call pathSum() for every node in the tree;
• we also need to count how many satisfied paths starting from current node dfs()

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

let pathSum = function(root, sum) {
    if( root === null ) return 0;
    return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);;
};

// dfs() is just the count starting from the specified node, 
// and need to add counts starting from it's children.
function dfs( node, sum ){
    let res = 0;
    if( node === null ) return 0;
    if( node.val === sum ) res++;
    return res + dfs(node.left, sum-node.val) + dfs(node.right, sum-node.val);
}

Solution 2:

Time complexity: O(n)

All the satisfied paths must be encountered when we traversal all the paths from root using dfs.

• while doing DFS, we can make use of the current path, to check if there is a satisfied path on it.
• The checking process is like “LC560. subarray sum equals k”,
  • we maintain a map of <prefixSum, freq>
  • for current node, we check if map has counterpart = curSum+node.val - sum
  • after finishing the visit of current node (i.e. done the visits of its children), we decrease its freq

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

let pathSum = function(root, sum) {
    let cnt = 0;
    let map = new Map();
    map.set(0, 1);
    dfs(root, 0);
    return cnt;
    
    
    function dfs( node, curSum ){
        if( node === null ) return;
        
        let counterpart = curSum + node.val - sum;
        if( map.has(counterpart) ) cnt += map.get(counterpart);
        
        if( !map.has(curSum+node.val) ) map.set(curSum+node.val, 0);
        map.set(curSum+node.val, map.get(curSum+node.val)+1);
        
        dfs( node.left, curSum+node.val );
        dfs( node.right, curSum+node.val );
        
        map.set(curSum+node.val, map.get(curSum+node.val)-1);
    }
};

Description

Given a string, find the length of the longest substring without repeating characters.

Example

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

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 


Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.


Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

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

let lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let l = 0, r = 0, max = 0;
    
    while( r < s.length ){
        if( !set.has(s[r]) ){
            set.add(s[r]);
            max = Math.max(max, r-l+1);
            r++;
        }else{
            while( set.has(s[r]) ) {
              set.delete(s[l]);
              l++;
            }
        }
    }
    return max;
};

1. Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

2. Follow up:

Could you do both operations in O(1) time complexity?

3. Example:

1
2
3
4
5
6
7
8
9
10
11

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

4. Solution

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

class LRU{
  
  constructor(v){
    this.size = v;
    this.map = new Map();
    this.head = new Node(0,0);
    this.tail = new Node(0,0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  
  put( key, val ){
    let node = new Node(key, val);
    this.map.set( key, node );
    this.insertFront( node );
    
    if( this.size < this.map.size ){
      this.removeLast();
    }
  }
  
  get( key ){
    if( !this.map.has(key) ) return -1;
    let node = this.map.get(key);
    this.breakAndLink(node);
    this.insertFront(node);
    return node.val;
  }
  
  breakAndLink(node){
    let p = node.prev;
    let n = node.next;
    p.next = n;
    n.prev = p;
    node.next = null;
    node.prev = null;
  }
  
  insertFront(node){
    let h2 = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    h2.prev = node;
    node.next = h2;
  }
  
  removeLast(){
    // remove from linklist
    let node = this.tail.prev;
    this.breakAndLink(node);
    // remove from map
    this.map.delete(node.key);
  }  
}

class Node{
  constructor(key, val){
    this.key = key;
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}


// test
let cache = new LRU( 2 );
cache.put(1, 1);
cache.put(2, 2);

console.log( cache.get(1) );       // returns 1
cache.put(3, 3);    // evicts key 2
console.log( cache.get(2) );       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
console.log( cache.get(1) );       // returns -1 (not found)
console.log( cache.get(3) );       // returns 3
console.log( cache.get(4) );       // returns 4

I. Concepts

PKI: A security architecture that consists of several entities: Certificate Authority (CA), server, client; and covers following techs: public-private key pair, digital certificate, encryption algorithm, hash algorithm, asymmetric/ symmetric encryption

Encryption algorithm: paired with a key to encrypt original message; to decrypt already encrytped message to original message

symmetric encryption: use the same key for encryption/decryption

asymmetric encryption: use public key for encryption; use private key for decryption

hash algorithm: used to convert original message to a fixed length hashed string, which will be used as a unique fingerprint for this particular message. [data integrity]

digital certificate: a certificate like ID, issued by CA, to prove the holder is the real one as it claims

CA: a well-known, trusted entity, issuing digital certificates/ID to web servers, in order to grant trust to them

server: web servers like amazon.com, being visited by consumers via client; also being issued digital certificate by CA

client: web browsers like Chrome, Firefox, make HTTP request to web server as the client for consumers

II. Why do we need PKI

In many cases, like email transportation, money transaction, we want the sensitive information to be secure, intact; We also want the two entities involved to be authenticated to be the real ones. Thus we have 3 requirements:

• data security: encryption algorithm
• data integrity: hash algorithm
• identity authentication: digital certificate / CA

III. Steps to evolve PKI

Senario: A customer using Chrome as client, want to make transaction with web server bank.com. To make sensitive info secure, we evolve our PKI to provide data security, then data integrity, and identity authentication.

IV. symmetric encryption

• client & server use symmetric encryption with a same key to communicate
• drawback:
  • Hackers can get the shared key when server sends the key to client
  • Server cannot safely distribute the shared key to client

V. asymmetric encryption (RSA)

• RSA algorithm: use public key and private key to encrypt info
  • generated at server,
  • beginning with 2 large prime numbers, results with 3 prime numbers: n, a, b
  • public key: n, a
  • private key: n, b
  • How to use RSA?
    • original message om, encrypted message em
    • em = om^a % n for encryption using public key: n, a
    • om = em^b % n for decryptin using private key: n, b

• Feature:

  • only private key can decrypt, public key can only used to encrypt info
  • In fact, any one of the two keys can be used to encrypt, but only the other one can decrypt the encrypted message
  • private key can also encrypt info, now only public key can decrypt info

• Steps:

  1. client request public key from server
  2. server response the same public key to anyone who request it
  3. client encrypt original info with public key, send encrypted message to server. Even though intercepted by hacker, he doesn’t have private key, can’t decrypt
  4. server receive the encrypted info, use private key to decrypt
• Solution to first problem: cannot distribute symmetric key securely
  1. client & server can use asymmetric encryption to distribute symmetric key
  2. client request public key from server
  3. server response the same public key to anyone who request it
  4. client encrypt symmetric key (symmetric encryption) with public key (asymmetric encryption), send encrypted message to server. Even though intercepted by hacker, he doesn’t have private key, can’t get symmetric key
  5. server receive the encrypted info (symmetric key), use private key to decrypt
  6. Now, only client (browser) and server know symmetric key, which can be used to communicate.

VI. identity authentication

• Problem above: client cannot assert the server is the real server it expect. If the conversation is hacked by hacker when client want to request public key from server, then the sensitive info of client will leak to hacker
• So, before we request public key from server, we first authenticate the server is the real one we expect
• How?
  • CA is the authority, trusted by browser/server. It signs certificate for server who apply for, by encrypting certificate info (subject+issuer+valid time+public key of subject) with its own private key. Then encrypted info is the signature
  • web server has a digital certificate (ID) issued by CA, used for client/browser to check its identity. Server will first send its digital signature to client before sending its public key
  • client/browser has a local list of CA and its public key. When request public key from server, it first check the validity of server’s digital certificate, using the public key of the issuer listed on the certificate. If the decrypted info matches, it trust the server. Otherwist, the server is bad!

VII. data integrity

• another problem: even though hackers cannot see the original info, they can still modify encrypted info, sometimes the modified info is still meaningful, but is not what we want
• Solution: fingerprint
  • human kind uses fingerprint to uniquely identify a person, instead of all kinds of features of this person. It is short, and easy to check
  • In fact, it is a way to convert massive info to unique short info
  • For message, we use hash algorithm to get the fingerprint of that message. 4 features of hash algorithm:
    • fixed length, short
    • avalanche effect: minor different in original message can lead to significant difference in fingerprints
    • no collision: two different messages shouldn’t share same fingerprint
    • uniqueness: two fingerprints shouldn’t be calculted by one message
• Steps:
  1. server hashes message using a hash algorithm, then append the hashed fingerprint and hash algorithm. It then encryptes the 3 items using private key, and sends to clients
  2. clients receive message from server, decrypt message using public key, obtaining original message, hashed result, hash algorithm. Client use the same algorithm to hash original message, and compared the result with the hashed result calculated by server. If they are the same, the message is intact.
  3. Even though hacker can modify message, we can use hash result as fingerprint to check if the message is intact

VIII. Summary

PKI provides secure information transfer, used in either SSL(Secure Socket Layer) or TLS(Transport Layer Security). It involves 3 technologies:

• symmetric/asymmetric encryption: secured information transfer
• hash algorithm: data integrity
• digital certificate: server authentication, to prove the server is the authentic one

When you request a HTTPS connection to a webpage, the website will initially send its SSL certificate to your browser. This certificate contains the public key needed to begin the secure session. Based on this initial exchange, your browser and the website then initiate the ‘SSL handshake’. The SSL handshake involves the generation of shared secrets to establish a uniquely secure connection between yourself and the website.

When a trusted SSL Digital Certificate is used during a HTTPS connection, users will see a padlock icon in the browser address bar. When an Extended Validation Certificate is installed on a web site, the address bar will turn green.

IX. References

1. https://www.instantssl.com/ssl-certificate-products/https.html
2. https://en.wikipedia.org/wiki/Public_key_infrastructure

Introduction

Vigenere Cipher is used to encode original string to random string, with a given keyword.

Components

1. Keyword Input Component
2. Keywords Display Component
3. Source Text Input Component
4. Source Text Display Component
5. Cipher Text Display Component

Model & Events

1. Model

   1 2 3 4 5 6 7

   let valid = true let kw_to_be = [] let kw = [] let kw_idx = 0 let kw_char_row = [] let kw_num_row = [] let ciph_row = []

2. Events

   1 2 3 4 5 6 7 8 9 10 11

   // 2.1 keyword input event handler function inputHandler(e){} // 2.2 source click button event handler function clickHandler(id){} // 2.3 update button event handler function updateBtnHandler(){} // 2.4 clear button event handler function clearBtnHandler(){}

Layout & Logic

Code Implementation

1. HTML

   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

   <!DOCTYPE html> <html> <head> <link rel="stylesheet" href="style.css"> </head> <body> <!-- 1. Keyword Input Component --> <h1><span>Configuration</span></h1> <p>Keyword</p> <div className="comp"> <input id="inputBox" type="text" /> <button id="updateBtn" >Update</button> <ul id="validation"> <li>Length of keyword should be in range: 3~8 </li> <li>Characters should be uppercase</li> </ul> </div> <!-- 2. Keyword Display Component --> <table class="comp"><tbody> <tr id="kwCharRow"></tr> <tr id="kwNumRow"></tr> </tbody></table> <!-- 3. Source Text Input Component --> <h1><span>Encoding</span></h1> <p>Source Text</p> <table class="comp"><tbody> <tr id="srcTextRow"></tr> <tr id="ciphTextRow"></tr> </tbody></table> <!-- 4. Source Text Display Component --> <div class="comp"> <input id="srcText" type="text" disabled /> <button id="clearBtn">Clear</button> </div> <!-- 5. Cipher Text Display Component --> <div class="comp"> <p>Cipher Text</p> <input id="ciphText" type="text" disabled /> </div> <script src="script.js"></script> </body> </html>

2. JS

   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

   (function (){ // 0.1 const const CHAR_NUM = 26 const CHAR_CODE_A = 65 const CHAR_CODE_Z = 90 const CHAR_CODE_ALL = new Array(CHAR_NUM).fill(1).map( ( _, i ) => (CHAR_CODE_A+i) ) const CHAR_ALL = CHAR_CODE_ALL.map(item=>String.fromCharCode(item)) // 0.2 helper functions const getEle = (id) => document.getElementById(id) const setEleVal = (ele, val)=> {ele.value = val} const creatEle = (tag) => document.createElement(tag) const creatText = (str) => document.createTextNode(str) const generateEle = ( tag, data, parent )=>{ let tempNode = document.createDocumentFragment() data.forEach((item, index)=>{ const td = creatEle('TD') const text = creatText(item) if( tag === 'srcTextRow' ){ const btn = creatEle('BUTTON') btn.appendChild(text) btn.onclick = function(){clickHandler(index)} td.appendChild(btn) }else{ td.appendChild(text) } tempNode.appendChild(td) }) while (parent.firstChild) { parent.removeChild(parent.firstChild) } parent.appendChild(tempNode) } const updateCiphTextRow = (kw_idx)=>{ const offset = kw[kw_idx].charCodeAt(0) - CHAR_CODE_A return CHAR_CODE_ALL.map(item=>{ const code = (item+offset <= CHAR_CODE_Z) ? (item+offset) : (item+offset-CHAR_NUM) return String.fromCharCode(code) }) } const updateHighlightIndex = (id)=>{ kwCharRow.childNodes.forEach( function(item, index){ item.className = id===index ? "highlight" : "" }) kwNumRow.childNodes.forEach( function(item, index){ item.className = id===index ? "highlight" : "" }) } // 0.3 DOM Elements const inputBox = getEle("inputBox") const errorHint = getEle("validation") const updatBtn = getEle("updatBtn") const kwCharRow = getEle("kwCharRow") const kwNumRow = getEle("kwNumRow") const srcTextRow = getEle("srcTextRow") const ciphTextRow = getEle("ciphTextRow") const srcText = getEle("srcText") const clearBtn = getEle("clearBtn") const ciphText = getEle("ciphText") /* 1. models */ let valid = true let kw_to_be = [] let kw = [] let kw_idx = 0 let kw_char_row = [] let kw_num_row = [] let ciph_row = [] /* 2. event handlers & DOM manipulation */ // 2.1 keyword input event handler function inputHandler(e){ kw_to_be = e.target.value.split("") const len = kw_to_be.length const lenValid = (len>=3 && len<=8) const caseValid = kw_to_be.every( item => item==item.toUpperCase() ) const validNew = lenValid && caseValid if(valid!==validNew){ valid = validNew errorHint.classList.toggle("invalid") } } inputBox.oninput=inputHandler // 2.2 source click button event handler function clickHandler(id){ if(kw.length === 0 ) return srcText.value = srcText.value + CHAR_ALL[id] ciphText.value = ciphText.value + ciph_row[id] kw_idx = kw_idx+1 < kw.length ? kw_idx+1 : kw_idx+1-kw.length ciph_row = updateCiphTextRow(kw_idx) generateEle("ciphTextRow", ciph_row, ciphTextRow) updateHighlightIndex(kw_idx) } // 2.3 update button event handler function updateBtnHandler(){ if(!valid) return kw = kw_to_be kw_idx = 0 const kw_num = kw.map(item=>item.charCodeAt(0)-CHAR_CODE_A) ciph_row = kw.length===0 ? [] : updateCiphTextRow(kw_idx) generateEle("kwCharRow", kw, kwCharRow) generateEle("kwNumRow", kw_num, kwNumRow) generateEle("ciphTextRow", ciph_row, ciphTextRow) updateHighlightIndex(kw_idx) srcText.value = "" ciphText.value = "" } updateBtn.onclick=updateBtnHandler // 2.4 clear button event handler function clearBtnHandler(){ kw_idx = 0 ciph_row = updateCiphTextRow(kw_idx) updateHighlightIndex(kw_idx) generateEle("ciphTextRow", ciph_row, ciphTextRow) srcText.value = "" ciphText.value = "" } clearBtn.onclick=clearBtnHandler // populate 'A'~'Z' in srcTextRow let tempNode = document.createDocumentFragment() generateEle("srcTextRow", CHAR_ALL, srcTextRow) })();

3. CSS

   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

   table{ border: 1px solid black; border-collapse:collapse; text-align: center; } table td { border: 1px solid black; padding: 5px; width: 20px; height: 20px; } h1{ margin-top: 30px; } h1 span{ color: grey; border-bottom: 1px solid ; } input[disabled]{ background-color:#F5F5DC; width: 200px; } ul{ display: none; } .invalid{ display: block; color: red; } .highlight{ background-color: yellow; } .comp{ margin: 5px 0; }

Introduction

Vigenere Cipher is used to encode original string to random string, with a given keyword.

Components

1. App (main component)
2. KeywordInputComp
3. KeywordsDisplayComp
4. SourceTextInputComp
5. SourceTextDisplayComp
6. CipherTextDisplayComp

Layout

1
2
3
4
5
6
7
8
9
10
11

App Comp 
 |
 |__Keyword Input Comp 
 |
 |__Keyword Display Comp
 |
 |__Source Text Input Comp
 |
 |__Source Text Display Comp
 |
 |__Cipher Text Display Comp

Model & Actions

1. App state:

   • 1.1 keyword
   • 1.2 keyword_index
   • 1.3 cipher_array
   • 1.4 source_text

   • 1.5 cipher_text

   • 1.6 keyword_input

   • 1.7 update
   • 1.8 sourceClick
   • 1.9 clear

2. KeywordInputComp props:

   • keep keyword_to_be as App’s instance variable

   • 1.6

   • 1.7

3. KeywordsDisplayComp props:

   • 1.1
   • 1.2

4. SourceTextInputComp props:

   • 1.3

   • 1.8

5. SourceTextDisplayComp props:

   • 1.4

   • 1.9

6. CipherTextDisplayComp props:

   • 1.5

Layout & Logic

Code Implementation

1. HTML

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

   <!DOCTYPE html> <html> <head> <script src="https://unpkg.com/babel-standalone@6/babel.min.js"></script> <script data-require="react@*" data-semver="0.14.0" src="https://cdnjs.cloudflare.com/ajax/libs/react/0.14.0/react.js"></script> <script data-require="react@*" data-semver="0.14.0" src="https://cdnjs.cloudflare.com/ajax/libs/react/0.14.0/react-dom.js"></script> <link rel="stylesheet" href="style.css" /> </head> <body> <div id="root"></div> <script src="script.js"></script> </body> </html>

2. JSX

   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 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236

   const Component = React.Component const CHAR_CODE_A = 65 const CHAR_CODE_Z = 90 const CHAR_CODE_ALL = new Array( 26 ).fill(1).map( ( _, i ) => (65+i) ) // 1. Keyword Input Component class KeywordInputComp extends Component{ constructor(props){ super(props) this.state={ valid: true } this.inputHandler = this.inputHandler.bind(this) this.updateHandler = this.updateHandler.bind(this) } inputHandler(e){ const valid = this.props.keywordInput(e) this.setState({valid}) } updateHandler(){ if( this.state.valid ) this.props.update() } render(){ return( <div className="comp"> <input onInput={this.inputHandler} type="text" /> <button onClick={this.updateHandler}>Update</button> <ul className={this.state.valid ? "valid":"invalid"}> <li>Length of keyword should be in range: 3~8 </li> <li>Characters should be uppercase</li> </ul> </div> ) } } // 2. Keyword Display Component const KeywordDisplayComp = (props)=>{ const {keyword, keyword_index} = props const td_char_arr = keyword.map((item,id)=>( <td className={id===keyword_index?'highlight':''} key={id}>{item}</td>) ) const td_offset_arr = keyword.map((item,id)=>( <td className={id===keyword_index?'highlight':''} key={id}> {item.charCodeAt(0)-CHAR_CODE_A} </td>) ) return ( <table className="comp"><tbody> <tr>{td_char_arr}</tr> <tr>{td_offset_arr}</tr> </tbody></table> ) } // 3. Source Text Input Component const SourceTextInputComp = (props)=>{ const {cipher_array, sourceClick} = props const td_source_arr = CHAR_CODE_ALL.map((item,id)=>( <td key={item}> <button onClick={function(){sourceClick(id)}} > {String.fromCharCode(item)} </button> </td>) ) const td_cipher_arr = cipher_array.map((item,id)=><td key={id}>{item}</td>) return( <table className="comp"><tbody> <tr>{td_source_arr}</tr> <tr>{td_cipher_arr}</tr> </tbody></table> ) } // 4. Source Text Display Component const SourceTextDisplayComp = (props)=>( <div className="comp"> <input type="text" value={props.source_text} disabled /> <button onClick={props.clear}>Clear</button> </div> ) // 5. Cipher Text Display Component const CipherTextDisplayComp = (props)=>( <div className="comp"> <p>Cipher Text</p> <input type="text" value={props.cipher_text} disabled /> </div> ) // 6. Main Component class App extends Component{ constructor(){ super() this.state={ keyword: [], keyword_index: 0, cipher_array: [], source_text: "", cipher_text: "", } this.keyword_to_be = [] this.keywordInput = this.keywordInput.bind(this) this.update = this.update.bind(this) this.sourceClick = this.sourceClick.bind(this) this.clear = this.clear.bind(this) this.calc_cipher_array = this.calc_cipher_array.bind(this) } // keyword input handler keywordInput(e){ this.keyword_to_be = e.target.value.split("") const len = this.keyword_to_be.length const lenValid = (len>=3 && len<=8) const caseValid = this.keyword_to_be.every( item => item==item.toUpperCase() ) return (lenValid && caseValid) } // helper function: // calc cipher chars on source text input interface calc_cipher_array(kw, id){ if(kw.length===0) return [] const offset = kw[id].charCodeAt(0) - CHAR_CODE_A return CHAR_CODE_ALL.map(function(item,index){ const code = (item+offset) <= CHAR_CODE_Z ? (item+offset) : (item+offset-CHAR_CODE_Z+CHAR_CODE_A-1) return String.fromCharCode(code) }) } // update handler update(){ const {keyword, keyword_index } = this.state const cipher_array = this.calc_cipher_array(this.keyword_to_be, 0) this.setState({ keyword: this.keyword_to_be, keyword_index: 0, cipher_array, source_text:"", cipher_text:"", }) } // click handler for source text input interface sourceClick(id){ let { keyword, keyword_index, cipher_array, source_text, cipher_text } = this.state if(keyword.length===0) return keyword_index = (keyword_index+1) < keyword.length ? (keyword_index+1) : (keyword_index+1-keyword.length) const cipher_array_new = this.calc_cipher_array(keyword, keyword_index) this.setState({ keyword_index, cipher_array:cipher_array_new, source_text:source_text+String.fromCharCode(id+CHAR_CODE_A), cipher_text:cipher_text+cipher_array[id], }) } // clear handler clear(){ const {keyword} = this.state const cipher_array_new = this.calc_cipher_array(keyword, 0) this.setState({ keyword_index: 0, cipher_array:cipher_array_new, source_text: "", cipher_text: "", }) } render(){ const { keyword, keyword_index, cipher_array, source_text, cipher_text, } = this.state return ( <div> <h1><span>Configuration</span></h1> <p>Keyword</p> <KeywordInputComp keywordInput={this.keywordInput} update={this.update} /> <KeywordDisplayComp keyword={keyword} keyword_index={keyword_index} /> <h1><span>Encoding</span></h1> <p>Source Text</p> <SourceTextInputComp cipher_array={cipher_array} sourceClick={this.sourceClick} /> <SourceTextDisplayComp source_text={source_text} clear={this.clear} /> <CipherTextDisplayComp cipher_text={cipher_text} /> </div> ) } } ReactDOM.render( <App / > , document.getElementById('root') );

3. CSS

   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

   table{ border: 1px solid black; border-collapse:collapse; text-align: center; } table td { border: 1px solid black; padding: 5px; width: 20px; height: 20px; } h1{ margin-top: 30px; } h1 span{ color: grey; border-bottom: 1px solid ; } input[disabled]{ background-color:#F5F5DC; width: 200px; } .valid{ display: none; } .invalid{ display: block; color: red; } .highlight{ background-color: yellow; } .comp{ margin-bottom: 5px; }

I. Problem

Given a random number, count how many holes in total. Note: the holes for each digits are listed below

• 0: 1hole
• 1: 0 hole
• 2: 0 hole
• 3: 0 hole
• 4: 1 hole
• 5: 0 hole
• 6: 1 hole
• 7: 0 hole
• 8: 2 holes
• 9: 1 hole

II. Solution

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

// Test
let n = getHoles(1234567)    
console.log(n)			// 2

n = getHoles(1)    
console.log(n)			// 0

n = getHoles(0)    
console.log(n)			// 1

n = getHoles(9)    
console.log(n)			// 1

n = getHoles(12)    
console.log(n)			// 0

n = getHoles(-14)    
console.log(n)			// 1


function getHoles( num ){
    if(num === 0) return 1

    const map = new Map([[0,1],[1,0],[2,0],[3,0],[4,1],[5,0],[6,1],[7,0],[8,2],[9,1]])
    let res = 0
    num = Math.abs(num)
    
    while( num > 0 ){
        let lastDigit = num % 10
        res += map.get(lastDigit)
        num = Math.floor(num/10)
    }
    return res
}

III. Complexity

• Time: O(n)
• Space: O(1)

I. Problem

Count how many trailing ‘0’ for the result of n!

II. Solution

The 0 are only contributed by both factor 2 and 5, which means the number of trailing 0 equals the number of pairs of 2 & 5

Thus, we only need to find out how many times of the factor 2 and factor 5 in this n! is good enogh; and then min(num_2, num_5)

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

// // Test
let res = trailing_zeros_for_factorial_of(5)
console.log(res)	// 1

res = trailing_zeros_for_factorial_of(8)
console.log(res)    // 1

res = trailing_zeros_for_factorial_of(10)
console.log(res)    // 2

res = trailing_zeros_for_factorial_of(15)
console.log(res)    // 3

function trailing_zeros_for_factorial_of(n){
    let num_2 = 0    
    let num_5 = 0
    
    let d = 5
    while(n >= d){
        num_5 += Math.floor(n / d)
        d *= 5 
    }
    
    d = 2
    while(n >= d){
        num_2 += Math.floor(n / d)
        d *= 2 
    }
    return Math.min(num_2, num_5)
}

III. Complexity

1. Time: O(n)
2. Space: O(1)

I. Problem

Given a map, whose key are integer, sort map entries by the order of its key

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

Map:[
    [2, 'c'],
    [1, 'a'],   
    [4, 'a'],
    [3, 'e'],
]

res: [
    [1, 'a'],    
    [2, 'c'],
    [3, 'e'],
    [4, 'a'],
]

II. Solution

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

// Test
let map = new Map([[2, 'c'], [1, 'a'], [4, 'a'], [3, 'e']])

function sortMap(map){
    let resKey = []
    map.forEach((val, key)=>{
        resKey.push(key)
    })
    resKey.sort()
    return resKey.map(item=> [item, map.get(item)])
}
                   
console.log(sortMap(map))

III. Complexity

1. Time: O(N*logN)
2. Space: O(N)