31:T595,/** * Returns a list of numbers which are contained in both lists. * * @param {Array.} listA First array of elements. Will be sorted during execution. * @param {Array.} listB Second array of elements. Will be sorted during execution. * @returns {Array.} Array of numbers which are contained in both lists. The items are sorted. */ function intersection(listA, listB) { if (listA == null) throw `listA not defined`; if (listB == null) throw `listB not defined`; const n = listA.length; const m = listB.length; // sort both lists in-place listA.sort(d3.ascending); // <= O(n log n) listB.sort(d3.ascending); // <= O(m log m) const result = []; let i = 0; // to iterate over listA let j = 0; // to iterate over listB // iterate over each array only once while (i < n && j < m) { // <= O(n + m) if (listA[i] < listB[j]) { for (const ai = listA[i++]; i < n && ai == listA[i]; i++); // shift i and skip duplicates } else if (listA[i] > listB[j]) { for (const bj = listB[j++]; j < m && bj == listB[j]; j++); // shift j and skip duplicates } else { // listA[i] == listB[j] => item occurs in both lists result.push(listA[i]); for (const ai = listA[i++]; i < n && ai == listA[i]; i++); // shift i and skip duplicates for (const bj = listB[j++]; j < m && bj == listB[j]; j++); // shift j and skip duplicates } } return result; }32:[{"id":"9bff4aaa848dbd6253d5f5fb279a9b40e50aa84b709141b09ac0ecaea5ddb9a5b4bfae3062fb2f46357e6f220e5720303be65228be5077c0555ac2b28d165685","href":"https://static.observableusercontent.com/files/9bff4aaa848dbd6253d5f5fb279a9b40e50aa84b709141b09ac0ecaea5ddb9a5b4bfae3062fb2f46357e6f220e5720303be65228be5077c0555ac2b28d165685","name":"intersection@3.png","type":"image/png","lastModified":1665919640052.069,"size":102357}] 2f:{"title":"Find common elements of two arrays","cells":[{"id":0,"value":"# Find common elements of two arrays\n\n![](${await FileAttachment(\"intersection@3.png\").url()})\n\nGiven are two arrays ${tex`\\mathrm{A}`} and ${tex`\\mathrm{B}`} of numbers (duplicates are possible). We are looking for a array ${tex`\\mathrm{R}`} which contains the common elements of both arrays. The arrays might be huge, therefore the memory and computational requirements should be minimized.","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"viewof listAExpr = Inputs.text({label: tex`\\mathrm{A}`, placeholder: \"Comma separated integers\", value: \"1, 2, 3, 4, 5, 6\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"viewof listBExpr = Inputs.text({label: tex`\\mathrm{B}`, placeholder: \"Comma separated integers\", value: \"2, 5, 4, 0, 8\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":55,"value":"tex`\\mathrm{R} = \\mathrm{A} \\cap \\mathrm{B} = \\{${intersection(listA, listB).join(\", \")}\\}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":142,"value":"---\n## Tests","pinned":false,"hidden":false,"mode":"md"},{"id":148,"value":"#### Simple tests","pinned":false,"hidden":false,"mode":"md"},{"id":91,"value":"check([1, 2, 3], [2, 4, 5])","pinned":true,"hidden":false,"mode":"ojs"},{"id":153,"value":"check([1, 2, 3], [])","pinned":true,"hidden":false,"mode":"ojs"},{"id":150,"value":"check([10, 1, 2, 3, 4, 5, 6], [2, 4, 5, 10, 8, 1])","pinned":true,"hidden":false,"mode":"ojs"},{"id":167,"value":"check([10, 1, 2, 2, 2, 3, 4, 5, 6], [2, 4, 5, 2, 10, 8, 1])","pinned":true,"hidden":false,"mode":"ojs"},{"id":181,"value":"check([10, -1, 2, 2, -2, 3, 4, -5, 6], [2, 4, 5, -2, 10, 8, 1])","pinned":true,"hidden":false,"mode":"ojs"},{"id":264,"value":"check([], [])","pinned":true,"hidden":false,"mode":"ojs"},{"id":213,"value":"#### Random tests","pinned":false,"hidden":false,"mode":"md"},{"id":209,"value":"viewof generate = Inputs.button(\"Generate\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":173,"value":"viewof randomTestCase = {\n generate;\n \n const maxLength = 10;\n\n const listA = Array.from({length: Math.random() * maxLength}, () => Math.floor(Math.random() * 20 - 10));\n const listB = Array.from({length: Math.random() * maxLength}, () => Math.floor(Math.random() * 20 - 10));\n\n const output = html`listA = [${listA.join(\", \")}]
listB = [${listB.join(\", \")}]`;\n output.value = {listA, listB};\n\n return output;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":199,"value":"check(randomTestCase.listA, randomTestCase.listB)","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"#### Throws if at least one argument is undefined","pinned":false,"hidden":false,"mode":"md"},{"id":128,"value":"throws(() => intersection(null, null))","pinned":true,"hidden":false,"mode":"ojs"},{"id":131,"value":"throws(() => intersection(null, []))","pinned":true,"hidden":false,"mode":"ojs"},{"id":134,"value":"throws(() => intersection([], null))","pinned":true,"hidden":false,"mode":"ojs"},{"id":138,"value":"throws(() => intersection())","pinned":true,"hidden":false,"mode":"ojs"},{"id":140,"value":"throws(() => intersection([]))","pinned":true,"hidden":false,"mode":"ojs"},{"id":162,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":10,"value":"listA = listAExpr.split(',').map(d => parseFloat(d))","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"listB = listBExpr.split(',').map(d => parseFloat(d))","pinned":false,"hidden":false,"mode":"ojs"},{"id":87,"value":"function check(listA, listB) {\n // reference solution\n const expected = [...new Set(listA)].filter(d => listB.indexOf(d) !== -1).sort(d3.ascending);\n\n // solution from the presented implementation\n const actual = intersection(listA, listB);\n\n const errorInfo = `expected: [${expected.join(\", \")}]\\nactual: [${actual.join(\", \")}]`\n\n if (actual.length != expected.length) {\n throw `❌ Lengths do not match (actual: ${actual.length}, expected: ${expected.length})\\n${errorInfo}`;\n }\n \n for (let i = 0; i < actual.length; i++) {\n if (actual[i] != expected[i]) {\n throw `❌ Mismatch at i=${i} (actual: ${actual[i]}, expected: ${expected[i]})\\n${errorInfo}`;\n }\n }\n \n return html`[${actual.join(\", \")}]
✔ passed`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":124,"value":"throws = function (fn) {\n try {\n fn()\n } catch {\n return html`✔ throws`\n }\n throw `❌ failed`\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}