31:T439,md`The first thing we might consider doing is drawing a number line and figuring out some way of producing a visual representation of the sequence in the hopes of recognizing a pattern. Try using a pencil and creating zig zag lines down a piece of paper below the numberline to record each position in the line as the position in the sequence progresses (downwards). If we imagined ourself as an ant marching one step to the next number in the sequence at a time. * We take one step "positive". * We take one step "nowhere". * We take two steps negative. * We take two steps "nowhere". * We take three steps "positive". * We take three steps "nowhere". ... This pattern continues in a predictable manner. We need: 1. A way to limit our generated sequence with an input integer. 2. A way to cycle through postive, zero, negative, and then positive movement. 3. A way to repeat numbers (e.g. 1, 1, 2, 2, 3, 3, 4, 4, ...). 4. A way to store the positions on the number line that are visited; that is, we need to create and return an array of integers representing the sequence. `32:T7c7,// https://en.wikipedia.org/wiki/Disjoint-set_data_structure DisjointSet = { function DisjointSet() { this.index_ = {}; } function Node(id) { this.id_ = id; this.parent_ = this; this.rank_ = 0; } DisjointSet.prototype.makeSet = function(id) { if (!this.index_[id]) { let created = new Node(id); this.index_[id] = created; } } // Returns the id of the representative element of this set that (id) // belongs to. DisjointSet.prototype.find = function(id) { if (this.index_[id] === undefined) { return undefined; } let current = this.index_[id].parent_; while (current !== current.parent_) { current = current.parent_; } return current.id_; } DisjointSet.prototype.union = function(x, y) { let xRoot = this.index_[this.find(x)]; let yRoot = this.index_[this.find(y)]; if (xRoot === undefined || yRoot === undefined || xRoot === yRoot) { // x and y already belong to the same set. return; } if (xRoot.rank < yRoot.rank) { // Move x into the set y is a member of. xRoot.parent_ = yRoot; } else if (yRoot.rank_ < xRoot.rank_) { // Move y into the set x is a member of. yRoot.parent_ = xRoot; } else { // Arbitrarily choose to move y into the set x is a member of. yRoot.parent_ = xRoot; xRoot.rank_++; } } // Returns the current number of disjoint sets. DisjointSet.prototype.size = function() { let uniqueIndices = {}; Object.keys(this.index_).forEach((id) => { let representative = this.find(id); uniqueIndices[representative] = true; }); return Object.keys(uniqueIndices).length; } DisjointSet.prototype.sizeOf = function(member) { let count = 0; let representative = this.find(member); Object.keys(this.index_).forEach((id) => { if (this.find(id) === representative) { count++; } }); return count; } return DisjointSet; }33:T566,function rain(graph) { if (graph.length <= 2) return 0; let n = graph.length // Store the delta between the highest bar to the left of the bar at index i. let leftDelta = [0]; // Store the delta between the highest bar to the right of the bar at index i; let rightDelta = []; rightDelta[n - 1] = 0; // The height of the highest bar to the left (or right during second traversal) // of the bar at the current index. let maxL = 0, maxR = 0; for (let i = 1; i < n; i++) { // Update the highest bar we have seen to th left of the current bar. if (graph[i - 1] > maxL) { maxL = graph[i - 1]; } // Update the highest bar we have seen to the right of the current // bar. if (graph[n - i] > maxR) { maxR = graph[n - i]; } // If the highest bar to the left of the current bar is lower than the // current bar, the delta is "clipped" to zero: no water would be contained // at index i. leftDelta[i] = Math.max(0, maxL - graph[i]); // Clip the values found similarly for the deltas corresponding to our sweep from // right to left through the bars. rightDelta[n - 1 - i] = Math.max(0, maxR - graph[n - 1 - i]); } return graph.reduce((sum, value, i) => { return sum += Math.min(leftDelta[i], rightDelta[i]); }, 0); }34:T6f8,minWindow = function(s, t) { let i = 0, // left cursor j = 0, // right cursor, bestLeft = 0, bestRight = Infinity, required = {}, formed = {}, formedCount = 0, requiredCount = undefined; // Trivial edge case. if (s.length === 0 || t.length === 0) return ''; for (let k = 0; k < t.length; k++) { // Initialize or increment. required[t.charAt(k)] = required[t.charAt(k)] ? required[t.charAt(k)] + 1 : 1; } // The number of required unique keys that we must match. requiredCount = Object.keys(required).length; // Increment window while (j < s.length) { // Include the right cursor's character because it was added in the last iteration of the // loop (we start with both cursors at 0). formed[s.charAt(j)] = formed[s.charAt(j)] ? formed[s.charAt(j)] + 1 : 1; if (required[s.charAt(j)] && formed[s.charAt(j)] === required[s.charAt(j)]) { formedCount++; } // Contract window while we have a valid window. while (formedCount === requiredCount && i <= j) { // Record the best window size if the current valid window is better than the // previously found "best window." We are guaranteed to have a unique // best window in the problem statement. if (j - i < bestRight - bestLeft) { bestRight = j; bestLeft = i; } formed[s.charAt(i)] = formed[s.charAt(i)] - 1; if (required[s.charAt(i)] && formed[s.charAt(i)] < required[s.charAt(i)]) { formedCount--; } i++; } j++; } return (bestRight === Infinity) ? '' : s.substring(bestLeft, bestRight + 1); }35:[] 2f:{"title":"Interview Questions Variety Pack","cells":[{"id":0,"value":"md`# Interview Questions Variety Pack\n\n

`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":135,"value":"md`## 1. Number Sequence`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"md`Consider the following sequence:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"tex.block`4, 5, 5, 4, 3, 3, 3, 4, 5, 6, 6, 6, 6, 5, 4, 3, 2, 2, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1`","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"md`Write a function \\`f()\\` that would return the following sequence of numbers as an array of integers when given the following inputs.\n\nfor \\`f(2)\\``","pinned":false,"hidden":false,"mode":"ojs"},{"id":148,"value":"tex`4, 5, 5, 4, 3, 3, 3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":151,"value":"md`and for \\`f(6)\\``\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":153,"value":"tex`4, 5, 5, 4, 3, 3, 3, 4, 5, 6, 6, 6, 6, 5, 4, 3, 2, 2, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1`","pinned":false,"hidden":false,"mode":"ojs"},{"id":161,"value":"md`and for \\`f(8)\\``","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"tex`4, 5, 5, 4, 3, 3, 3, 4, 5, 6, 6, 6, 6, 5, 4, 3, 2, 2, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7...`\n\n\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":178,"value":"tex`... 8, 8, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0`","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"md`One way to achieve (1) is to use a single input integer \\`n\\` that we have been told should be between 0 and 100 (let's assume that's inclusive of 0 and 100).\n\n(2) can be achieved by using [1, 0, -1, 0] as an array to index into in order to pluck the next direction from.\n\n(3) Can make use of an index, let's say \\`k\\`, which counts odd numbers 1, 3, 5, 7, ... as well as another index \\`i\\` which increments from 0 through 3. Using the \\`Math.floor\\` function, we can consider the loop:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":116,"value":"{\n let numbers = [];\n let n = 10;\n \n for (let k = 1; k < n; k += 2) {\n for (let i = 0; i < 4; ++i) {\n numbers.push(k + Math.floor(i / 2));\n }\n }\n \n return numbers;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":132,"value":"md`The above function gives us the repeating pattern we desire for our number of steps taken in a direction or used \"going nowhere\" along the numberline.\n\n(4) Is taken care of with an array. Done.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"f = (n) => {\n // Starting position.\n let d = 4;\n \n // Result we iteratively build up.\n let sequence = [d];\n \n // A cycle of directions.\n let direction = [1, 0, -1, 0];\n \n // K is incremented by 2 to introduce the notion of \"repeating\" the number\n // of steps we take in any direction along the number line.\n // 1, 3, 5, 7, 9, ...\n for (let k = 1; k < n; k += 2) {\n for (let i = 0; i < 4; ++i) {\n // Steps uses the floor function to take odd values of k and repeat them while also\n // adding in repeated even numbers of steps:\n // k: 1, 3, 5, 7\n // becomes\n // steps: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8 \n let steps = k + Math.floor((i / 2));\n for (let j = 0; j < steps; ++j) {\n sequence.push(d += direction[i]);\n }\n }\n }\n \n return sequence;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":44,"value":"f(6)","pinned":true,"hidden":false,"mode":"ojs"},{"id":191,"value":"md`## 2. Histogram`","pinned":false,"hidden":false,"mode":"ojs"},{"id":202,"value":"md`Taken from @yangshun https://github.com/yangshun/tech-interview-handbook/blob/master/algorithms/array.md`","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"md`Given an array of integers, print out a histogram using the said array; include a base layer (all stars)\nE.g. [5, 4, 0, 3, 4, 1]`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"input_2 = [5, 4, 0, 3, 4, 1]","pinned":false,"hidden":false,"mode":"ojs"},{"id":214,"value":"md`Example console output (note the base layer of stars):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":210,"value":"html`

\n*\n**  *\n** **\n** **\n** ***\n******

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":219,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":220,"value":"// Assume input array is all non-negative integers.\nhistogram = (arr) => {\n let min = Infinity;\n let A = arr.slice(0); // Shallow copy. Don't modify inputs!\n let printed = '\\n';\n \n for (let h = Math.max(...A); h >= 0; h --) {\n for (let i = 0, n = A.length; i < n; i++) {\n printed += (A[i] - h >= 0) ? '*' : ' ';\n }\n printed += '\\n'; // New line.\n }\n \n return printed;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":222,"value":"histogram(input_2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":237,"value":"Math.max(...input_2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":241,"value":"input_2","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"md`## 3. Making Change`","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"md`Find the minimum number of coins needed to make change for an amount n.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":258,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":264,"value":"tex`n = min_{coins}({numCoins(n - coin_i)})`","pinned":false,"hidden":false,"mode":"ojs"},{"id":383,"value":"US_COINS = [1, 5, 10, 25]","pinned":false,"hidden":false,"mode":"ojs"},{"id":435,"value":"input_3 = 63","pinned":false,"hidden":false,"mode":"ojs"},{"id":280,"value":"function numCoins(amount, denominations, memo) {\n let n = amount;\n \n // No change needed, trivial case.\n if (n === 0) return 0;\n \n if (memo[amount] > 0) return memo[amount];\n \n // Exact change.\n if (denominations.includes(n)) return 1;\n \n for (let i = 0; i < denominations.length && amount > denominations[i]; i++) {\n let used = numCoins(amount - denominations[i], denominations, memo) + 1;\n if (used < n) {\n n = used;\n }\n }\n \n memo[amount] = n;\n return n;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":287,"value":"solution_3a = numCoins(input_3, US_COINS, new Array(64))","pinned":true,"hidden":false,"mode":"ojs"},{"id":457,"value":"md`There are a minimum of ${solution_3a} coins needed make change for ${input_3} cents.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":371,"value":"function whichCoins(amount, denominations, memo, coins) {\n let n = amount;\n \n // No change needed, trivial case.\n if (n === 0) return 0;\n \n if (memo[amount] > 0) return memo[amount];\n \n // Exact change.\n if (denominations.includes(n)) {\n coins[amount] = denominations.indexOf(n);\n return 1;\n }\n \n let best = -1;\n \n for (let i = 0; i < denominations.length && amount > denominations[i]; i++) {\n let used = whichCoins(amount - denominations[i], denominations, memo, coins) + 1;\n if (used < n) {\n best = i;\n n = used;\n }\n }\n \n if (best > -1) {\n coins[amount] = best;\n }\n \n memo[amount] = n;\n return n;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":433,"value":"md`We can slightly modify our algorithm to keep another memo of the denominations used in creating an optimal solution. The solution involves iterating back through the optimal choices of denomination (noted by index into an array of denomination values) to find the counts of each denomination used in creating the optimal solution for ${input_3} cents.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":335,"value":"{\n let amount = input_3;\n let solution = (new Array(amount + 1)).fill(-1);\n whichCoins(amount, US_COINS, new Array(64), solution)\n \n let histogram = US_COINS.map(() => 0);\n \n let k = amount;\n \n while (k >= 0) {\n histogram[solution[k]] += 1;\n k -= US_COINS[solution[k]];\n }\n \n let printed = '\\n';\n \n histogram.forEach((count, denomination) => {\n printed += '(' + count + ') ---> ' + US_COINS[denomination] + ' cent coin\\n';\n });\n \n printed += 'yields ' + histogram.reduce((sum, count, denomination) => {\n return sum + count * US_COINS[denomination];\n }, 0) + ' cents';\n \n return printed;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":464,"value":"md`## 4. High Sum`","pinned":false,"hidden":false,"mode":"ojs"},{"id":468,"value":"md`Taken from @yangshun https://github.com/yangshun/tech-interview-handbook/blob/master/algorithms/array.md`","pinned":false,"hidden":false,"mode":"ojs"},{"id":465,"value":"md`Given an array of integers, find a maximum sum of non-adjacent elements.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":473,"value":"md`Example: [1, 0, 3, 9, 2] should return 10, using (1 + 9).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":471,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":479,"value":"function lambda4(arr, i, memo) {\n if (i === 0) return 0;\n\n if (i === 1) return Math.max(arr[0], arr[1]);\n\n return Math.max(\n lambda4(arr, i - 1), // don't include element i\n lambda4(arr, i - 2) + arr[i]); // include element i\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":493,"value":"// We could wrap this function to avoid the need to provide the iterator variable.\nlambda4([1, 0, 3, 9, 2], 4)","pinned":true,"hidden":false,"mode":"ojs"},{"id":505,"value":"md`## 5. Parentheses ()()(())`","pinned":false,"hidden":false,"mode":"ojs"},{"id":507,"value":"md`Print all possible N pairs of balanced parentheses.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":512,"value":"md`E.g. when N is 2, the function should print (()) and ()().`","pinned":false,"hidden":false,"mode":"ojs"},{"id":508,"value":"md`E.g. when N is 3, we should get ((())), (()()), (())(), ()(()), ()()().`","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":546,"value":"md`\n* We observe that we can push an open parenthesis onto a stack and increase our \"depth\" by 1.\n\n* Popping or using a closed parentheses decreases our depth by 1.\n\n* Our depth should never exceed N. For example, let N = 3. The depth of \"((\" is 2. The depth of \"(((\" is 3. We can undo our depth of 3 with 3 more closed parentheses: \"((()))\" and we can also undo a depth of 2 with more open and closed parentheses. \"(()\" has a depth of 1. \"(()())\" has a depth of zero and is therefore a valid example of parentheses for N = 3.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":515,"value":"// N must be a non-negative even integer.\nfunction parentheses(N, n, d, partial, solutions) { \n // There are no more parentheses to add. Add the solution to the solutions\n // we have already found.\n if (n === 0) {\n solutions.push(partial);\n return;\n }\n \n // Add a closed parenthesis as long doing so would not produce a negative depth.\n if (d > 0) {\n parentheses(N, n - 1, d - 1, partial + ')', solutions);\n }\n \n // Add an open parenthesis as long doing so would not prevent closing parentheses with\n // remaining number of parentheses that we have left.\n if (d < Math.floor(n / 2)) {\n parentheses(N, n - 1, d + 1, partial + '(', solutions);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":516,"value":"{\n let N_PAIRS = 4;\n let solutions = [];\n parentheses(2 * N_PAIRS, 2 * N_PAIRS, 0, '', solutions);\n return solutions;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":591,"value":"md`## 6. Disjoint Set`","pinned":false,"hidden":false,"mode":"ojs"},{"id":653,"value":"md`Create a disjoint set data structure which can be used to make sets, union two sets together, and determine the number of sets after a number of sets have been created and had union operations performed. Additionally, discuss and try to implement any additional utility methods this data structure might have. `","pinned":false,"hidden":false,"mode":"ojs"},{"id":732,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":596,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":657,"value":"md`Let's test out the disjoint set data structure that we made:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":610,"value":"{\n let ds = new DisjointSet();\n ds.makeSet(1);\n ds.makeSet(2);\n ds.makeSet(3);\n ds.union(1, 3);\n return ds.size();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":664,"value":"{\n let ds = new DisjointSet();\n \n for (let i = 0; i < 10; i++) {\n ds.makeSet(i);\n }\n \n ds.union(3, 1);\n ds.union(4, 3);\n ds.union(8, 4);\n \n return ds.sizeOf(4); // 1, 3, 4, 8 are in the same set\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":714,"value":"md`## 7. Rainfall`","pinned":false,"hidden":false,"mode":"ojs"},{"id":592,"value":"md`You have a bar graph that is represented by an array of integers. Pour rain all over the bar graph. How much rain will the bar graph hold? Assume that units of rain are integers and that the example input data describes a bargraph that would hold 11 units of rain water.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":716,"value":"input_7 = [1, 2, 4, 0, 2, 3, 0, 4]","pinned":false,"hidden":false,"mode":"ojs"},{"id":727,"value":"md`We can use the histogram function from problem 2 to visualize the bar graph corresponding to the above array of integers.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":718,"value":"histogram(input_7)","pinned":true,"hidden":false,"mode":"ojs"},{"id":730,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":734,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":748,"value":"rain(input_7)","pinned":true,"hidden":false,"mode":"ojs"},{"id":772,"value":"md`## 8. Minimum Window Substring`","pinned":false,"hidden":false,"mode":"ojs"},{"id":782,"value":"md`[From LeetCode:](https://leetcode.com/problems/minimum-window-substring/description/)\n\nGiven a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":773,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":791,"value":"md`Use a sliding window with a left and right cursor. Move the right cursor whenever the window is not valid and move the left cursor whenever we have a valid window in an attempt to find a smaller yet still valid window. Keep track of the best window as you go.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":775,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":785,"value":"minWindow('ADOBECODEBANC', 'ABC')","pinned":true,"hidden":false,"mode":"ojs"},{"id":787,"value":"minWindow('AIRPLANESARECOOL', 'RACE')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}