30:T4ac,## Summary Each lesson about an algorithm pattern will be hosted on the HelloInterview website, and will consist of a mix of text, narrated video walkthroughs and interactive visuals rendered by React. (I would love to for each lesson to live in Observable notebooks, but understand why that might not be preferred). * Begin with narrated video walkthrough of the pattern applied to a basic problem. This is meant to illustrate the core concepts of the algorithm pattern at a high level. * Next, expose the "state" of the algorithm, presented in both narrated videos and interactive forms. Also show the synced code trace of the solution with the animation. * From there, have the learner solve 3-4 related problems. Each problem will have an accompanying animation (in a similar style) that the learner will use as a starting point (there is potential for some product integration here, see below). They'll be able to generate the animation of the solution for an arbitrary input, and also interact with the interactive form of the animation to help them implement the solution. Note this is my best guess at what the structure should be, and will change with feedback from actual learners.31:T1273,function interactiveDraw() { const height = width * (1 / 5); const svgWidth = width * (4 / 5); const svg = d3 .create("svg") .attr("viewBox", [0, 0, svgWidth, height]) .attr("width", svgWidth); const { start, end, window, max_length } = interactiveState; const marginX = 15; const xScale = d3 .scaleLinear() .domain([-0.5, chars.length - 1 + 0.5]) // make room for the ends of the window .range([marginX, svgWidth - 2 * marginX]); const windowHeight = height / 2.5; const windowUnit = xScale(1) - xScale(0); const minX = xScale(xScale.domain()[0]); const y = height / 2; const letters = svg .selectAll(".letters") .data(chars) .join("text") .attr("class", "letters") .attr("font-size", 36) .attr("text-anchor", "middle") .attr("dominant-baseline", "middle") .attr("x", (d, i) => xScale(i)) .attr("y", y) .text((d) => d); const variables = svg .selectAll(".variables") .data([[start], [end]]) .join("text") .attr("class", "letters") .attr("font-size", 14) .attr("text-anchor", "middle") .attr("dominant-baseline", "middle") .attr("x", (d, i) => xScale(d)) .attr( "y", (d, i) => y - windowHeight / 2 + windowHeight + 10 + (start === end ? 15 * i : 0) ) .text((d, i) => (i === 0 ? "left" : "right")); const stateSpaceMargin = 75; const stateData = [ { name: "window", value: window }, { name: "max_length", value: max_length } ]; const stateScale = d3 .scaleLinear() .domain([0, stateData.length]) .range([stateSpaceMargin, width - 2 * stateSpaceMargin]); const state = svg .selectAll(".state") .data(stateData) .join("text") .attr("class", "state") .attr("font-size", 18) .attr("text-anchor", "start") .attr("dominant-baseline", "middle") .attr("x", (d, i) => stateScale(i)) .attr("y", height * (19 / 20)) .text((d) => `${d.name}: ${toString(d.value)}`); const expanderWidth = xScale(1 / 4) - xScale(0); const rect = svg .selectAll("rect.window") .data([[start, end]]) .join("rect") .attr("class", "window") .attr("x", ([start, end]) => xScale(start - 0.5)) .attr("y", y - windowHeight / 2) .attr("width", ([start, end]) => Math.max(windowUnit * (end - start), expanderWidth) ) .attr("height", windowHeight) .style("fill", "green") .attr("opacity", 0.5) .attr("rx", 3); const expandable = end < chars.length && !window.has(chars[end]); const expandGroup = svg .selectAll(".expand") .data([[start, end]]) .join("g") .attr("fill", "grey") .attr( "transform", ([_, end]) => `translate(${ xScale(start - 0.5) + Math.max(windowUnit * (end - start), expanderWidth) }, 0)` ); expandGroup .append("text") .attr("class", expandable ? "active sizeIcon" : "sizeIcon") .style("font-family", "Linearicons-Free") .attr("dominant-baseline", "middle") .attr("font-size", ".75em") // .attr("opacity", 0.5) .text("\ue881") // .attr("dx", ) .attr("y", y); const expand = expandGroup .append("rect") .attr("class", expandable ? "active sizeRect" : "sizeRect") .attr("width", expanderWidth) .attr("y", y - windowHeight / 2 + windowHeight / 4) .attr("height", windowHeight * 0.5) .attr("opacity", 0.25) .attr("rx", 1) .style("cursor", expandable ? "pointer" : "default"); if (expandable) expand.on("click", () => mutable index++); if (start !== end) { const shrinkable = end < chars.length && !expandable; const shrinkGroup = svg .selectAll(".shrink") .data([[start, end]]) .join("g") .attr("fill", "grey") .attr( "transform", ([start, _]) => `translate(${xScale(start - 0.5) - expanderWidth}, 0)` ); shrinkGroup .append("text") .attr("class", shrinkable ? "active sizeIcon" : "sizeIcon") .style("font-family", "Linearicons-Free") .attr("dominant-baseline", "middle") .attr("font-size", ".75em") .attr("text-anchor", "middle") // .attr("opacity", 0.75) .text("\ue882") .attr("dx", expanderWidth / 2) .attr("y", y); const shrink = shrinkGroup .append("rect") .attr("class", shrinkable ? "active sizeRect" : "sizeRect") .attr("width", expanderWidth) .attr("y", y - windowHeight / 2 + windowHeight / 4) .attr("height", windowHeight * 0.5) .attr("opacity", 0.25) .attr("rx", 1) .style("cursor", shrinkable ? "pointer" : "default"); if (shrinkable) shrink.on("click", () => mutable index++); } return svg.node(); }32:T49b,function expanderClosure(config) { const { svg, expanderWidth, xScale, windowUnit, selection } = config; function dragstarted(event, d) { d3.select(this).raise().attr("stroke", "black"); selection.select("rect.window").raise().attr("stroke", "black"); } // needs to update mutable when it ends. function dragended(event, d) { d3.select(this).raise().attr("stroke", null); selection.select("rect.window").attr("stroke", null); mutable index++; } function dragged(event, d) { const dragX = d3.select(this).attr("x"); const [[start, end]] = d3.select(this).data(); if (event.x > parseFloat(dragX) + expanderWidth) { const maxX = xScale(end + 0.5) - expanderWidth; d3.select(this).attr("x", (d.x = Math.min(event.x, xScale(end + 0.5)))); const windowX = selection.select("rect.window").attr("x"); const maxWindowWidth = Math.min( windowUnit * (end - start + 1), event.x - windowX ); selection.select("rect.window").attr("width", (d.width = maxWindowWidth)); } } return d3 .drag() .on("start", dragstarted) .on("drag", dragged) .on("end", dragended); }33:T559,function shrinkerClosure(config) { const { svg, expanderWidth, xScale, windowUnit, selection } = config; function dragstarted(event, d) { d3.select(this).raise().attr("stroke", "black"); // selection.select("rect.window").raise().attr("stroke", "black"); } // needs to update mutable when it ends. function dragended(event, d) { d3.select(this).raise().attr("stroke", null); selection.select("rect.window").attr("stroke", null); mutable index++; } function dragged(event, d) { const dragX = d3.select(this).attr("x"); const [[start, end]] = d3.select(this).data(); const newX = Math.max(dragX, Math.min(event.x, xScale(start + 1 - 0.5))); if (event.x <= xScale(start + 1 - 0.5) && event.x > xScale(start - 0.5)) { d3.select(this).attr("x", (d.x = newX - expanderWidth)); const window = selection.select("rect.window"); const windowX = xScale(start - 0.5); const delta = Math.max(event.x - windowX, 0); const windowWidth = windowUnit * (end - start); window .attr("x", (d.x = event.x)) .attr( "width", (d.width = Math.min( windowUnit * (end - start + 1), windowWidth - delta )) ); } } return d3 .drag() .on("start", dragstarted) .on("drag", dragged) .on("end", dragended); }34:[{"id":"7e4c771781c1eb7c0ccebbfcf9797dcf42747189d939e4745f9d1f04824fc14c9661c8b41ec16cd04a21faee15152907884f1c941692475d35b6084fc97a0186","href":"https://static.observableusercontent.com/files/7e4c771781c1eb7c0ccebbfcf9797dcf42747189d939e4745f9d1f04824fc14c9661c8b41ec16cd04a21faee15152907884f1c941692475d35b6084fc97a0186","name":"image.png","type":"image/png","lastModified":1697039243775.205,"size":12074},{"id":"7e4c771781c1eb7c0ccebbfcf9797dcf42747189d939e4745f9d1f04824fc14c9661c8b41ec16cd04a21faee15152907884f1c941692475d35b6084fc97a0186","href":"https://static.observableusercontent.com/files/7e4c771781c1eb7c0ccebbfcf9797dcf42747189d939e4745f9d1f04824fc14c9661c8b41ec16cd04a21faee15152907884f1c941692475d35b6084fc97a0186","name":"image@1.png","type":"image/png","lastModified":1697039303855.051,"size":12074},{"id":"ffc3b57e6b53b13b59cf33c9ccccc4f7af8c342dc1d29b03848c8d0cf45d666c5cec804903633bfbf9c73c7d19382ed9d31060afd2004754010e97919ea4237a","href":"https://static.observableusercontent.com/files/ffc3b57e6b53b13b59cf33c9ccccc4f7af8c342dc1d29b03848c8d0cf45d666c5cec804903633bfbf9c73c7d19382ed9d31060afd2004754010e97919ea4237a","name":"untitled (3).png","type":"image/png","lastModified":1697039334340.212,"size":25649},{"id":"7e4c771781c1eb7c0ccebbfcf9797dcf42747189d939e4745f9d1f04824fc14c9661c8b41ec16cd04a21faee15152907884f1c941692475d35b6084fc97a0186","href":"https://static.observableusercontent.com/files/7e4c771781c1eb7c0ccebbfcf9797dcf42747189d939e4745f9d1f04824fc14c9661c8b41ec16cd04a21faee15152907884f1c941692475d35b6084fc97a0186","name":"image@2.png","type":"image/png","lastModified":1697039340121.526,"size":12074}] 2e:{"title":"Visualizing the Coding Interview","cells":[{"id":0,"value":"# Visualizing the Coding Interview","pinned":false,"hidden":false,"mode":"md"},{"id":962,"value":"The goal of this course is to make the mental models behind the algorithm patterns for the coding interview as accessible as possible. This is different than existing courses which present a few isolated solutions to a given algorithm pattern and expect you to develop those mental models yourself.\n\nThe course will achieve its goal by developing a set of consistent animations for each algorithm pattern. This notebook shows what that might look like for the sliding window pattern, and how interacting with those animations in various forms can help achieve specific learning goals. It ends with a proposal for the initial deliverable.","pinned":false,"hidden":false,"mode":"md"},{"id":997,"value":"## Phase 1: Intuition Building","pinned":false,"hidden":false,"mode":"md"},{"id":1002,"value":"In this initial phase, the learner is trying to gain a high-level understanding of the pattern's core concepts. \n\nThe animation below shows how the sliding window moves to solve the [largest substring without duplicate characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/). ","pinned":false,"hidden":false,"mode":"md"},{"id":327,"value":"viewof string = Inputs.text({ label: \"Input\", value: \"abcdefeghfijki\" })\n// string = \"acecbcbb\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":347,"value":"viewof replay = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"drawWindow({ state, chars })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1499,"value":"When accompanied with narration synced to relevant moments in the animation, we can emphasize the algorithm's core concepts, such as:\n- the window always contains a valid substring (no duplicate characters)\n- we repeatedly try to *expand* the window one character at a time\n- but if expanding will introduce a duplicate, we have to *shrink* the window until it no longer will\n- the algorithm remembers the largest window thus far during the search (not shown in this animation, but should be)","pinned":false,"hidden":false,"mode":"md"},{"id":1077,"value":"To reinforce the core concepts, the same style animation can also be shown for another sliding window problem, such as this one for finding the largest substring with at most 2 distinct characters.","pinned":false,"hidden":false,"mode":"md"},{"id":1257,"value":"viewof replay1 = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1267,"value":"drawWindow({\n state: twoDistinctStates,\n chars: twoDistinctString\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1050,"value":"## Phase 2: Implementation Skills","pinned":false,"hidden":false,"mode":"md"},{"id":1317,"value":"In this phase, the learner develops their ability to implement the algorithm, which we can make easier by exposing the \"state\" that drives the algorithm in the animation (largest substring without duplicate characters)\n. ","pinned":false,"hidden":false,"mode":"md"},{"id":1423,"value":"viewof replay3 = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1313,"value":"drawWindow({ state: state2, chars, showState: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1090,"value":"As before, synced narration can help emphasize what each piece of state represents. \n\nInteractive visuals can provide a more granular view of how the algorithm responds to different states (click on the plus or minus signs at the end of each window to expand or shrink the window and move onto the next step).","pinned":false,"hidden":false,"mode":"md"},{"id":705,"value":"viewof reset = Inputs.button(\"Reset\", { reduce: () => (mutable index = 0) })","pinned":false,"hidden":false,"mode":"ojs"},{"id":680,"value":"\n### Next Step\n\n

\n${index < allStates.length - 1 ? \n`The next character to be added into the window is string[right], or *${chars[allStates[index].end]}*. Since our window ${allStates[index].window.has(chars[allStates[index].end]) ? \" contains \" : \" does not contain \"} ${chars[allStates[index].end]}, the next step is to ${allStates[index].window.has(chars[allStates[index].end]) ? \"shrink our window by incrementing left by 1\" : \" expand our window by incrementing right by 1\"}.` : \"We've reached the end of our string. We compare the length of the current window with the stored greatest length, update if necessary, and return.\"}

","pinned":false,"hidden":false,"mode":"md"},{"id":473,"value":"interactiveDraw()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1169,"value":"From there, we can sync the animation with a code trace of the actual solution to make the connection between the animation and the code implementation clear (think Linked List two pointer TikTok video). The state labels in the animation become variables in the implementation, while the steps in the interactive animations are expressed by the algorithm's control-flow.","pinned":false,"hidden":false,"mode":"md"},{"id":1094,"value":"## Phase 3: Knowledge Consolidation","pinned":false,"hidden":false,"mode":"md"},{"id":1199,"value":"In this phase, the learner applies what they learned about the sliding window pattern for the specific example to solve different problems. We can \"scaffold\" this process by using the same style to animate the solutions to those problems.\n\nFor example, we can show this animation for how the sliding window moves to find the largest substring with at most two distinct characters, and have the learner practice translating what they see in the animation into code:","pinned":false,"hidden":false,"mode":"md"},{"id":1414,"value":"viewof replay2 = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1334,"value":"drawWindow({\n state: twoDistinctStates2,\n chars: twoDistinctString,\n showState: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1332,"value":"twoDistinctStates2 = {\n replay2;\n return twoDistinctStateGenerator(twoDistinctString);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1454,"value":"Here's the animation for [finding the start indexes of all anagrams of \"abc\" in the input string](https://leetcode.com/problems/find-all-anagrams-in-a-string/):","pinned":false,"hidden":false,"mode":"md"},{"id":1441,"value":"viewof replay4 = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1450,"value":"drawWindow({ state: anagramStates, chars: \"cbaebabacd\", showState: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1446,"value":"anagramStates = {\n replay4;\n return anagramStateGenerator(\"cbaebabacd\", \"abc\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1476,"value":"Here's the animation for [finding the start indexes of all substrings in the input string which are a concatenation of \\['bar', 'foo', 'the'\\]](https://leetcode.com/problems/substring-with-concatenation-of-all-words/) (Leetcode hard):","pinned":false,"hidden":false,"mode":"md"},{"id":1467,"value":"viewof replay5 = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1472,"value":"drawWindow({\n state: substringStates,\n chars: \"barfoofoobarthefoobarman\",\n showState: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1465,"value":"substringStates = {\n replay5;\n return substringConcatenationGenerator(\"barfoofoobarthefoobarman\", [\n \"bar\",\n \"foo\",\n \"the\"\n ]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1341,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":1348,"value":"## Potential Product Integration\n\nHere are some possibilities for how these animations can be integrated within the HelloInterview coding platform: \n\n* Better Hints: We can generate these animations on-demand for whatever input the user specifies while working on a particular problem in the platform, which will help with understanding.\n* Visual debugging: We can generate animations of the user's solutions if they emit \"traces\" in their code that follow a specific format.","pinned":false,"hidden":false,"mode":"md"},{"id":1386,"value":"## Initial Deliverable\n\nThe first stage of this project will be to take this prototype for the sliding window pattern and turn it into a \"production-ready\" lesson on the HelloInterview site according to the structure above. I can be responsible for getting feedback on the lesson content by leveraging my TikTok following.","pinned":false,"hidden":false,"mode":"md"},{"id":1393,"value":"## Further Work\n\nThere is further work to categorize each lesson into some type of graph showing the relationships between patterns, and also to compile a canonical list of questions (Blind75, Neetcode) that are tagged by each pattern.","pinned":false,"hidden":false,"mode":"md"},{"id":1126,"value":"## Design Principles\n* Make state explicit. People understand what they can see, so make sure they always see what they need to see in order to understand the algorithm.\n \n* At the same time, be extremely intentional about what gets included in the visuals. The ideal visual includes the correct amount of detail and not a single detail more, as anything beyond what is correct introduces more cognitive load.\n\n* Aesthetics are important. The visuals should look and feel \"nice\".","pinned":false,"hidden":false,"mode":"md"},{"id":749,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1241,"value":"import { drawWindow } from \"@jzhang621/sliding-window-layout\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1250,"value":"import { stateGenerator as twoDistinctStateGenerator } from \"@jzhang621/sliding-window-largest-substring-with-at-most-2-distinct-ch\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1461,"value":"import { stateGenerator as substringConcatenationGenerator } from \"252ee278249d6b62\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1438,"value":"import { stateGenerator as anagramStateGenerator } from \"48488a17995568ed\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"chars = Array.from(string)","pinned":false,"hidden":false,"mode":"ojs"},{"id":478,"value":"mutable index = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":652,"value":"allStates = generateAllStates(string)","pinned":false,"hidden":false,"mode":"ojs"},{"id":344,"value":"state = {\n replay;\n return stateGenerator(chars);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":538,"value":"interactiveState = allStates[index]","pinned":false,"hidden":false,"mode":"ojs"},{"id":821,"value":"function toString(input) {\n if (typeof input === \"string\" || typeof input === \"number\") return input;\n\n // for sets. will need a different one for a map.\n return `{ ${Array.from(input).join(\", \")} }`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":461,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":295,"value":"async function* stateGenerator(inputString, tick = 500) {\n const allStates = generateAllStates(inputString);\n\n for (let i = 0; i < allStates.length; i++) {\n yield allStates[i];\n await Promises.delay(tick);\n }\n yield {};\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1420,"value":"state2 = {\n replay3;\n return stateGenerator(chars);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1255,"value":"twoDistinctStates = {\n replay1;\n return twoDistinctStateGenerator(twoDistinctString);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1272,"value":"twoDistinctString = \"cabcacca\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":526,"value":"function generateAllStates(inputString) {\n const states = [];\n const state = {\n start: 0,\n end: 0,\n window: new Set(),\n max_length: 0\n };\n\n states.push({ ...state, window: new Set(state.window) });\n\n while (state.end < inputString.length) {\n const { window, length } = state;\n\n while (window.has(inputString[state.end])) {\n window.delete(inputString[state.start]);\n state.start += 1;\n states.push({ ...state, window: new Set(state.window) });\n }\n\n window.add(inputString[state.end]);\n\n state.end += 1;\n state.max_length = Math.max(state.max_length, state.end - state.start);\n\n states.push({ ...state, window: new Set(state.window) });\n }\n return states;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":80,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":574,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":603,"value":"html`