misc: restructure contents

yangshun · Jul 15, 2019 · c19c962 · c19c962
1 parent 2e84bea
commit c19c962
Show file tree

Hide file tree

Showing 83 changed files with 373 additions and 344 deletions.
diff --git a/.editorconfig b/.editorconfig
@@ -8,4 +8,4 @@ trim_trailing_whitespace = true
 [*.{js,py}]
 charset = utf-8
 indent_style = space
-indent_size = 4
+indent_size = 2
diff --git a/.prettierrc b/.prettierrc
@@ -0,0 +1,8 @@
+{
+  "bracketSpacing": false,
+  "jsxBracketSameLine": true,
+  "printWidth": 80,
+  "proseWrap": "never",
+  "singleQuote": true,
+  "trailingComma": "all"
+}
diff --git a/algorithms/README.md → contents/algorithms/README.md b/algorithms/README.md → contents/algorithms/README.md
diff --git a/algorithms/array.md → contents/algorithms/array.md b/algorithms/array.md → contents/algorithms/array.md
diff --git a/algorithms/binary.md → contents/algorithms/binary.md b/algorithms/binary.md → contents/algorithms/binary.md
diff --git a/algorithms/dynamic-programming.md → contents/algorithms/dynamic-programming.md b/algorithms/dynamic-programming.md → contents/algorithms/dynamic-programming.md
diff --git a/algorithms/geometry.md → contents/algorithms/geometry.md b/algorithms/geometry.md → contents/algorithms/geometry.md
diff --git a/algorithms/graph.md → contents/algorithms/graph.md b/algorithms/graph.md → contents/algorithms/graph.md
diff --git a/algorithms/hash-table.md → contents/algorithms/hash-table.md b/algorithms/hash-table.md → contents/algorithms/hash-table.md
diff --git a/algorithms/heap.md → contents/algorithms/heap.md b/algorithms/heap.md → contents/algorithms/heap.md
diff --git a/algorithms/interval.md → contents/algorithms/interval.md b/algorithms/interval.md → contents/algorithms/interval.md
diff --git a/algorithms/linked-list.md → contents/algorithms/linked-list.md b/algorithms/linked-list.md → contents/algorithms/linked-list.md
diff --git a/algorithms/math.md → contents/algorithms/math.md b/algorithms/math.md → contents/algorithms/math.md
diff --git a/algorithms/matrix.md → contents/algorithms/matrix.md b/algorithms/matrix.md → contents/algorithms/matrix.md
diff --git a/algorithms/oop.md → contents/algorithms/oop.md b/algorithms/oop.md → contents/algorithms/oop.md
diff --git a/algorithms/permutation.md → contents/algorithms/permutation.md b/algorithms/permutation.md → contents/algorithms/permutation.md
diff --git a/algorithms/queue.md → contents/algorithms/queue.md b/algorithms/queue.md → contents/algorithms/queue.md
diff --git a/algorithms/sorting-searching.md → contents/algorithms/sorting-searching.md b/algorithms/sorting-searching.md → contents/algorithms/sorting-searching.md
diff --git a/algorithms/stack.md → contents/algorithms/stack.md b/algorithms/stack.md → contents/algorithms/stack.md
diff --git a/algorithms/string.md → contents/algorithms/string.md b/algorithms/string.md → contents/algorithms/string.md
diff --git a/algorithms/topics.md → contents/algorithms/topics.md b/algorithms/topics.md → contents/algorithms/topics.md
diff --git a/algorithms/tree.md → contents/algorithms/tree.md b/algorithms/tree.md → contents/algorithms/tree.md
diff --git a/non-technical/behavioral.md → contents/non-technical/behavioral.md b/non-technical/behavioral.md → contents/non-technical/behavioral.md
diff --git a/non-technical/cover-letter.md → contents/non-technical/cover-letter.md b/non-technical/cover-letter.md → contents/non-technical/cover-letter.md
diff --git a/non-technical/interview-formats.md → contents/non-technical/interview-formats.md b/non-technical/interview-formats.md → contents/non-technical/interview-formats.md
diff --git a/non-technical/negotiation.md → contents/non-technical/negotiation.md b/non-technical/negotiation.md → contents/non-technical/negotiation.md
diff --git a/non-technical/psychological-tricks.md → ...nts/non-technical/psychological-tricks.md b/non-technical/psychological-tricks.md → ...nts/non-technical/psychological-tricks.md
diff --git a/non-technical/questions-to-ask.md → contents/non-technical/questions-to-ask.md b/non-technical/questions-to-ask.md → contents/non-technical/questions-to-ask.md
diff --git a/non-technical/resume.md → contents/non-technical/resume.md b/non-technical/resume.md → contents/non-technical/resume.md
diff --git a/non-technical/self-introduction.md → contents/non-technical/self-introduction.md b/non-technical/self-introduction.md → contents/non-technical/self-introduction.md
diff --git a/preparing/README.md → contents/preparing/README.md b/preparing/README.md → contents/preparing/README.md
diff --git a/contents/preparing/cheatsheet.md b/contents/preparing/cheatsheet.md
@@ -0,0 +1,105 @@
+---
+id: interview-cheatsheet
+title: Interview Cheatsheet
+---
+
+This is a straight-to-the-point, distilled list of technical interview Do's and Don'ts, mainly for algorithmic interviews. Some of these may apply to only phone screens or whiteboard interviews, but most will apply to both. I revise this list before each of my interviews to remind myself of them and eventually internalized all of them to the point I do not have to rely on it anymore.
+
+For a detailed walkthrough of interview preparation, refer to the ["Preparing for a Coding Interview"](./) section.
+
+**Legend:** ✅ = Do, ❌ = Don't, ⚠️ = Situational
+
+### 1. Before Interview
+
+|  | Things |
+| --- | --- |
+| ✅ | Prepare pen, paper and earphones/headphones. |
+| ✅ | Find a quiet environment with good Internet connection. |
+| ✅ | Ensure webcam and audio are working. There were times I had to restart Chrome to get Hangouts to work again. |
+| ✅ | Request for the option to interview over Hangouts/Skype instead of a phone call; it is easier to send links or text across. |
+| ✅ | Decide on and be familiar with a programming language. |
+| ✅ | Familiarize yourself with the coding environment (CoderPad/CodePen). Set up the coding shortcuts, turn on autocompletion, tab spacing, etc. |
+| ✅ | Prepare answers to the [frequently-asked questions](../non-technical/behavioral.md) in an interview. |
+| ✅ | Prepare some [questions to ask](../non-technical/questions-to-ask.md) at the end of the interview. |
+| ✅ | Dress comfortably. Usually you do not need to wear smart clothes, casual should be fine. T-shirts and jeans are acceptable at most places. |
+| ✅ | Stay calm and composed. |
+| ⚠️ | Turn off the webcam if possible. Most remote interviews will not require video chat and leaving it on only serves as a distraction. |
+
+### 2. Introduction
+
+|  | Things |
+| --- | --- |
+| ✅ | Introduce yourself in a few sentences under a minute or two. |
+| ✅ | Mention interesting points that are relevant to the role you are applying for. |
+| ✅ | Sound enthusiastic! Speak with a smile and you will naturally sound more engaging. |
+| ❌ | Spend too long introducing yourself. The more time you spend talking the less time you have to code. |
+
+### 3. Upon Getting the Question
+
+|  | Things |
+| --- | --- |
+| ✅ | Repeat the question back at the interviewer. |
+| ✅ | Clarify any assumptions you made subconsciously. Many questions are under-specified on purpose. A tree-like diagram could very well be a graph that allows for cycles and a naive recursive solution would not work. |
+| ✅ | Clarify input format and range. Ask whether input can be assumed to be well-formed and non-null. |
+| ✅ | Work through a small example to ensure you understood the question. |
+| ✅ | Explain a high level approach even if it is a brute force one. |
+| ✅ | Improve upon the approach and optimize. Reduce duplicated work and cache repeated computations. |
+| ✅ | Think carefully, then state and explain the time and space complexity of your approaches. |
+| ✅ | If stuck, think about related problems you have seen before and how they were solved. Check out the [tips](../algorithms) in this section. |
+| ❌ | Ignore information given to you. Every piece is important. |
+| ❌ | Jump into coding straightaway. |
+| ❌ | Start coding without interviewer's green light. |
+| ❌ | Appear too unsure about your approach or analysis. |
+
+### 4. During Coding
+
+|  | Things |
+| --- | --- |
+| ✅ | Explain what you are coding/typing to the interviewer, what you are trying to achieve. |
+| ✅ | Practice good coding style. Clear variable names, consistent operator spacing, proper indentation, etc. |
+| ✅ | Type/write at a reasonable speed. |
+| ✅ | As much as possible, write actual compilable code, not pseudocode. |
+| ✅ | Write in a modular fashion. Extract out chunks of repeated code into functions. |
+| ✅ | Ask for permission to use trivial functions without having to implement them; saves you some time. |
+| ✅ | Use the hints given by the interviewer. |
+| ✅ | Demonstrate mastery of your chosen programming language. |
+| ✅ | Demonstrate technical knowledge in data structures and algorithms. |
+| ✅ | If you are cutting corners in your code, state that out loud to your interviewer and say what you would do in a non-interview setting (no time constraints). E.g., I would write a regex to parse this string rather than using `split()` which may not cover all cases. |
+| ✅ | Practice whiteboard space-management skills. |
+| ⚠️ | Reasonable defensive coding. Check for nulls, empty collections, etc. Can omit if input validity has been clarified with the interviewer. |
+| ❌ | Remain quiet the whole time. |
+| ❌ | Spend too much time writing comments. |
+| ❌ | Use extremely verbose variable names. |
+| ❌ | Copy and paste code without checking. |
+| ❌ | Interrupt your interviewer when they are talking. Usually if they speak, they are trying to give you hints or steer you in the right direction. |
+| ❌ | Write too big (takes up too much space) or too small (illegible) if on a whiteboard. |
+
+### 5. After Coding
+
+|  | Things |
+| --- | --- |
+| ✅ | Scan through your code for mistakes as if it was your first time seeing code written by someone else. |
+| ✅ | Check for off-by-one errors. |
+| ✅ | Come up with more test cases. Try extreme test cases. |
+| ✅ | Step through your code with those test cases. |
+| ✅ | Look out for places where you can refactor. |
+| ✅ | Reiterate the time and space complexity of your code. |
+| ✅ | Explain trade-offs and how the code/approach can be improved if given more time. |
+| ❌ | Immediately announce that you are done coding. Do the above first! |
+| ❌ | Argue with the interviewer. They may be wrong but that is very unlikely given that they are familiar with the question. |
+
+### 6. Wrap Up
+
+|  | Things |
+| --- | --- |
+| ✅ | Ask questions. More importantly, ask good and engaging questions that are tailored to the company! Pick some questions from [this list](../non-technical/questions-to-ask.md). |
+| ✅ | Thank the interviewer. |
+| ⚠️ | Ask about your interview performance. It can get awkward. |
+| ❌ | End the interview without asking any questions. |
+
+### 7. Post Interview
+
+|  | Things |
+| --- | --- |
+| ✅ | Record the interview questions and answers down as these can be useful for future reference. |
+| ⚠️ | Send a follow up email to your interviewer(s) thanking them for their time and the opportunity to interview with them. |
diff --git a/design/README.md → experimental/design/README.md b/design/README.md → experimental/design/README.md
diff --git a/design/collaborative-editor.md → experimental/design/collaborative-editor.md b/design/collaborative-editor.md → experimental/design/collaborative-editor.md
diff --git a/design/news-feed.md → experimental/design/news-feed.md b/design/news-feed.md → experimental/design/news-feed.md
diff --git a/design/search-engine.md → experimental/design/search-engine.md b/design/search-engine.md → experimental/design/search-engine.md
diff --git a/domain/async-loading/index.html → experimental/domain/async-loading/index.html b/domain/async-loading/index.html → experimental/domain/async-loading/index.html
diff --git a/domain/databases.md → experimental/domain/databases.md b/domain/databases.md → experimental/domain/databases.md
diff --git a/domain/networking.md → experimental/domain/networking.md b/domain/networking.md → experimental/domain/networking.md
diff --git a/domain/pagination-sorting/data.js → ...imental/domain/pagination-sorting/data.js b/domain/pagination-sorting/data.js → ...imental/domain/pagination-sorting/data.js
diff --git a/domain/pagination-sorting/index.html → ...ntal/domain/pagination-sorting/index.html b/domain/pagination-sorting/index.html → ...ntal/domain/pagination-sorting/index.html
diff --git a/domain/security.md → experimental/domain/security.md b/domain/security.md → experimental/domain/security.md
diff --git a/domain/snake-game/snake-game.md → experimental/domain/snake-game/snake-game.md b/domain/snake-game/snake-game.md → experimental/domain/snake-game/snake-game.md
diff --git a/domain/software-engineering.md → experimental/domain/software-engineering.md b/domain/software-engineering.md → experimental/domain/software-engineering.md
diff --git a/domain/tic-tac-toe/index.html → experimental/domain/tic-tac-toe/index.html b/domain/tic-tac-toe/index.html → experimental/domain/tic-tac-toe/index.html
diff --git a/front-end/README.md → experimental/front-end/README.md b/front-end/README.md → experimental/front-end/README.md
diff --git a/interviewers/basics.md → experimental/interviewers/basics.md b/interviewers/basics.md → experimental/interviewers/basics.md
diff --git a/utilities/javascript/binToInt.js → ...rimental/utilities/javascript/binToInt.js b/utilities/javascript/binToInt.js → ...rimental/utilities/javascript/binToInt.js
@@ -1,15 +1,18 @@
 // Does not handle negative binary numbers.
 function binToInt(binary) {
-    let res = 0;
-    for (let i = 0; i < binary.length; i++) {
-        res = res * 2 + (+binary[i]);
-    }
-    return res;
+  let res = 0;
+  for (let i = 0; i < binary.length; i++) {
+    res = res * 2 + +binary[i];
+  }
+  return res;
 }
 
 console.log(binToInt('0') === parseInt('0', 2) && parseInt('0', 2) === 0);
 console.log(binToInt('1') === parseInt('1', 2) && parseInt('1', 2) === 1);
 console.log(binToInt('10') === parseInt('10', 2) && parseInt('10', 2) === 2);
 console.log(binToInt('11') === parseInt('11', 2) && parseInt('11', 2) === 3);
 console.log(binToInt('101') === parseInt('101', 2) && parseInt('101', 2) === 5);
-console.log(binToInt('1100011') === parseInt('1100011', 2) && parseInt('1100011', 2) === 99);
+console.log(
+  binToInt('1100011') === parseInt('1100011', 2) &&
+    parseInt('1100011', 2) === 99,
+);
diff --git a/utilities/javascript/binarySearch.js → ...ntal/utilities/javascript/binarySearch.js b/utilities/javascript/binarySearch.js → ...ntal/utilities/javascript/binarySearch.js
@@ -1,18 +1,18 @@
 function binarySearch(arr, target) {
-    let left = 0;
-    let right = arr.length - 1;
-    while (left <= right) {
-        const mid = left + Math.floor((right - left) / 2);
-        if (arr[mid] === target) {
-            return mid;
-        }
-        if (arr[mid] < target) {
-            left = mid + 1;
-        } else {
-            right = mid - 1;
-        }
+  let left = 0;
+  let right = arr.length - 1;
+  while (left <= right) {
+    const mid = left + Math.floor((right - left) / 2);
+    if (arr[mid] === target) {
+      return mid;
     }
-    return -1;
+    if (arr[mid] < target) {
+      left = mid + 1;
+    } else {
+      right = mid - 1;
+    }
+  }
+  return -1;
 }
 
 console.log(binarySearch([1, 2, 3, 10], 1) === 0);

diff --git a/experimental/utilities/javascript/deepEqual.js b/experimental/utilities/javascript/deepEqual.js
@@ -0,0 +1,43 @@
+function deepEqual(val1, val2) {
+  if (typeof val1 !== typeof val2) {
+    return false;
+  }
+
+  // Array comparison.
+  if (Array.isArray(val1) && Array.isArray(val2)) {
+    if (val1.length !== val2.length) {
+      return false;
+    }
+    for (let i = 0; i < val1.length; i++) {
+      if (!deepEqual(val1[i], val2[i])) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  // Object comparison.
+  if (
+    typeof val1 === 'object' &&
+    typeof val2 === 'object' &&
+    val1 !== null &&
+    val2 !== null
+  ) {
+    const keys1 = Object.keys(val1),
+      keys2 = Object.keys(val2);
+    if (keys1.length !== keys2.length) {
+      return false;
+    }
+    for (let i = 0; i < keys1.length; i++) {
+      if (!deepEqual(val1[keys1[i]], val2[keys2[i]])) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  // Primitive comparison.
+  return val1 === val2;
+}
+
+module.exports = deepEqual;
diff --git a/experimental/utilities/javascript/graphTopoSort.js b/experimental/utilities/javascript/graphTopoSort.js
@@ -0,0 +1,35 @@
+function graphTopoSort(numberNodes, edges) {
+  const nodes = new Map();
+  const order = [];
+  const queue = [];
+  for (let i = 0; i < numberNodes; i++) {
+    nodes.set(i, {in: 0, out: new Set()});
+  }
+
+  edges.forEach(edge => {
+    const [node_id, pre_id] = edge;
+    nodes.get(node_id).in += 1;
+    nodes.get(pre_id).out.add(node_id);
+  });
+
+  for (let [node_id, value] of nodes.entries()) {
+    if (value.in === 0) {
+      queue.push(node_id);
+    }
+  }
+
+  while (queue.length) {
+    const node_id = queue.shift();
+    for (let outgoing_id of nodes.get(node_id).out) {
+      nodes.get(outgoing_id).in -= 1;
+      if (nodes.get(outgoing_id).in === 0) {
+        queue.push(outgoing_id);
+      }
+    }
+    order.push(node_id);
+  }
+
+  return order.length == numberNodes ? order : [];
+}
+
+console.log(graphTopoSort(3, [[0, 1], [0, 2]]));
diff --git a/experimental/utilities/javascript/intToBin.js b/experimental/utilities/javascript/intToBin.js
@@ -0,0 +1,21 @@
+// Does not handle negative numbers.
+function intToBin(number) {
+  if (number === 0) {
+    return '0';
+  }
+  let res = '';
+  while (number > 0) {
+    res = String(number % 2) + res;
+    number = parseInt(number / 2, 10);
+  }
+  return res;
+}
+
+console.log(intToBin(0) === (0).toString(2) && (0).toString(2) === '0');
+console.log(intToBin(1) === (1).toString(2) && (1).toString(2) === '1');
+console.log(intToBin(2) === (2).toString(2) && (2).toString(2) === '10');
+console.log(intToBin(3) === (3).toString(2) && (3).toString(2) === '11');
+console.log(intToBin(5) === (5).toString(2) && (5).toString(2) === '101');
+console.log(
+  intToBin(99) === (99).toString(2) && (99).toString(2) === '1100011',
+);
diff --git a/utilities/javascript/intervalsIntersect.js → ...tilities/javascript/intervalsIntersect.js b/utilities/javascript/intervalsIntersect.js → ...tilities/javascript/intervalsIntersect.js
@@ -1,6 +1,6 @@
 // Interval: [start, end].
 function intervalsIntersect(a, b) {
-    return a[0] < b[1] && b[0] < a[1];
+  return a[0] < b[1] && b[0] < a[1];
 }
 
 console.log(intervalsIntersect([1, 2], [3, 4]) === false);

diff --git a/utilities/javascript/intervalsMerge.js → ...al/utilities/javascript/intervalsMerge.js b/utilities/javascript/intervalsMerge.js → ...al/utilities/javascript/intervalsMerge.js
@@ -1,7 +1,7 @@
 // Interval: [start, end].
 // Merges two overlapping intervals into one.
 function intervalsMerge(a, b) {
-    return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
+  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
 }
 
 const deepEqual = require('./deepEqual');

diff --git a/utilities/javascript/isSubsequence.js → ...tal/utilities/javascript/isSubsequence.js b/utilities/javascript/isSubsequence.js → ...tal/utilities/javascript/isSubsequence.js
@@ -1,14 +1,14 @@
 function isSubsequence(s, t) {
-    if (s.length > t.length) {
-        return false;
+  if (s.length > t.length) {
+    return false;
+  }
+  let matchedLength = 0;
+  for (let i = 0; i < t.length; i++) {
+    if (matchedLength < s.length && s[matchedLength] === t[i]) {
+      matchedLength += 1;
     }
-    let matchedLength = 0;
-    for (let i = 0; i < t.length; i++) {
-        if (matchedLength < s.length && s[matchedLength] === t[i]) {
-            matchedLength += 1;
-        }
-    }
-    return matchedLength === s.length;
+  }
+  return matchedLength === s.length;
 }
 
 console.log(isSubsequence('abc', 'abcde') === true);

diff --git a/utilities/javascript/matrixClone.js → ...ental/utilities/javascript/matrixClone.js b/utilities/javascript/matrixClone.js → ...ental/utilities/javascript/matrixClone.js
@@ -1,7 +1,9 @@
 function matrixClone(matrix, defaultValue) {
-    return matrix.map(row => {
-        return defaultValue === undefined ? row.slice(0) : Array(row.length).fill(defaultValue);
-    });
+  return matrix.map(row => {
+    return defaultValue === undefined
+      ? row.slice(0)
+      : Array(row.length).fill(defaultValue);
+  });
 }
 
 const deepEqual = require('./deepEqual');
@@ -15,4 +17,6 @@ console.log(deepEqual(matrixClone([[1]]), [[1]]));
 
 // Test clone with default value.
 console.log(deepEqual(matrixClone([[1, 2], [1, 4]], 1), [[1, 1], [1, 1]]));
-console.log(deepEqual(matrixClone([[1, 2], [1, 4]], null), [[null, null], [null, null]]));
+console.log(
+  deepEqual(matrixClone([[1, 2], [1, 4]], null), [[null, null], [null, null]]),
+);
diff --git a/utilities/javascript/matrixTranspose.js → ...l/utilities/javascript/matrixTranspose.js b/utilities/javascript/matrixTranspose.js → ...l/utilities/javascript/matrixTranspose.js
@@ -1,11 +1,12 @@
 function matrixTranspose(matrix) {
-    return matrix[0].map((col, i) => matrix.map(row => row[i]));
+  return matrix[0].map((col, i) => matrix.map(row => row[i]));
 }
 
 const deepEqual = require('./deepEqual');
 
 console.log(deepEqual(matrixTranspose([[1]]), [[1]]));
 console.log(deepEqual(matrixTranspose([[1, 2]]), [[1], [2]]));
 console.log(deepEqual(matrixTranspose([[1, 2], [1, 4]]), [[1, 1], [2, 4]]));
-console.log(deepEqual(matrixTranspose([[1, 2, 3], [4, 5, 6]]), [[1, 4], [2, 5], [3, 6]]));
-
+console.log(
+  deepEqual(matrixTranspose([[1, 2, 3], [4, 5, 6]]), [[1, 4], [2, 5], [3, 6]]),
+);
diff --git a/experimental/utilities/javascript/matrixTraverse.js b/experimental/utilities/javascript/matrixTraverse.js
@@ -0,0 +1,30 @@
+function traverse(matrix) {
+  const DIRECTIONS = [[0, 1], [0, -1], [1, 0], [-1, 0]];
+  const rows = matrix.length;
+  const cols = matrix[0].length;
+  const visited = matrix.map(row => Array(row.length).fill(false));
+  function dfs(i, j) {
+    if (visited[i][j]) {
+      return;
+    }
+    visited[i][j] = true;
+    DIRECTIONS.forEach(dir => {
+      const row = i + dir[0],
+        col = j + dir[1];
+      // Boundary check.
+      if (row < 0 || row >= rows || col < 0 || col >= cols) {
+        return;
+      }
+      // Valid neighbor check.
+      if (matrix[row][col] !== 1) {
+        return;
+      }
+      dfs(row, col);
+    });
+  }
+  for (let i = 0; i < rows; i++) {
+    for (let j = 0; j < cols; j++) {
+      dfs(i, j);
+    }
+  }
+}