Download the 3 files: index.html, flatten.js, and tests.js into 1 directory and open index.html with a web browser.
Open the JavaScript console to see test output.
export default function flatten(arr) { | |
// type checking and edge cases | |
/** | |
Iterable input types | |
We could include a check for iterables here | |
(things that can be iterated like (for const item of list)) | |
to extend this function to handle more input types, | |
and one way is to check it conforms to iteratable protocol | |
and has the Symbol.iterator function slot, | |
and for simplicity I omit that. | |
**/ | |
if ( ! Array.isArray(arr) ) { | |
/** | |
Type checking | |
We could choose to simply return [] here | |
and swallow any error, but if we are explicit | |
then we can see when our function is not getting | |
the argument types we expect it to. | |
**/ | |
throw new TypeError(`function flatten expects 1 argument of type Array`); | |
} | |
if ( arr.length == 0 ) { | |
// return a new array instead of mutate old one | |
return []; | |
} | |
/* | |
Approach like a tree | |
Nested arrays are equal to trees, with the array | |
members being branch nodes and the non-array members | |
being leaf nodes. | |
We want all the leaf nodes, in some order. | |
The easiest traversal is where we push any branch | |
nodes onto a queue, and loop until the queue is empty, | |
which is why I chose it. | |
A LIFO queue, or stack, gives depth first, while | |
a FIFO queue gives breadth first. | |
Depth first gives the correct left-to-right order, so I chose it. | |
After investigating I believe the complexity is O(k+n), where | |
k is the number of arrays and n is the number of numbers, | |
in other words one step for each node in the "tree". | |
*/ | |
// variable declaration | |
const leaves = []; | |
const stack = []; | |
// setup | |
stack.push(arr); | |
// main flatten loop | |
while( stack.length ) { | |
// How does it work? | |
// uncomment the following line to inspect the algorithm progress: | |
// console.log(JSON.stringify(stack)); | |
const next = stack.pop(); | |
if ( Array.isArray(next) ) { | |
stack.push(...next); | |
} else if ( Number.isInteger(next) ) { | |
// we process input end-first so unshift to get correct order: | |
leaves.unshift(next); | |
} else { | |
// if it's not an array or an integer, we ignore it | |
} | |
} | |
return leaves; | |
} |
<meta charset=utf-8> | |
<meta name=viewport content="width=device-width, initial-scale=1.0"> | |
<title>Theorem∎</title> | |
<h1>Theorem∎ Test</h1> | |
<style> | |
main { | |
margin: 0 auto; | |
max-width: 777px; | |
} | |
blockquote { | |
font-family: monospace; | |
} | |
</style> | |
<main> | |
<dl> | |
<dt>Candidate | |
<dd>Cris Stringfellow | |
<dt>Date | |
<dd><time datetime=2019-09-07>September 7, 2019</time> | |
<dt>Task | |
<dd> | |
<blockquote | |
cite=https://theorem.applytojob.com/questionnaire/55e9bb9657b1d/prospect_20190905092917_RDOMQCKKXTWE8OZU/projob_20190905092917_31GJ2NT9WR4SCYJP | |
> | |
<p> | |
Write some code, that will flatten an array of arbitrarily nested arrays of integers into a flat array of integers. e.g. [[1,2,[3]],4] -> [1,2,3,4]. | |
<p> | |
Your solution should be a link to a gist on gist.github.com with your implementation. | |
<p> | |
When writing this code, you can use any language you're comfortable with. The code must be well tested and documented. Please include unit tests and any documentation you feel is necessary. In general, treat the quality of the code as if it was ready to ship to production. | |
<p> | |
Try to avoid using language defined methods like Ruby's Array#flatten. | |
</blockquote> | |
</dd> | |
<dt>Self-test result | |
<dd>Passes all 5 tests | |
<dt>Time to complete | |
<dd>~ approximately 1 hour | |
<dt>Link to GitHub gist: | |
<dd><a target=_blank href=https://gist.github.com/crislin2046/1bde3adc5655f4072c0ec2e92acfb30d>gist</a> | |
<dt>Embedded gist: | |
<dd> | |
<hr> | |
<script src="https://gist.github.com/crislin2046/1bde3adc5655f4072c0ec2e92acfb30d.js"></script> | |
<hr> | |
</dd> | |
</dl> | |
</main> | |
<script type=module> | |
import {tests, run} from './tests.js'; | |
import flatten from './flatten.js'; | |
run(flatten, tests); | |
</script> |
export const tests = [ | |
{ | |
question: [[1,2,[3]],4], | |
answer: [1,2,3,4] | |
}, | |
{ | |
question: [[1,2], [[[3],[[4]]]], 5, 6, [[[7]]], 8, [9,[[10]],11], 12], | |
answer: [1,2,3,4,5,6,7,8,9,10,11,12], | |
}, | |
{ | |
question: [], | |
answer: [] | |
}, | |
{ | |
question: [10, 9, 8, 7, [6,[5],[],[[]],4], [[],3], [], 2, 1], | |
answer: [10,9,8,7,6,5,4,3,2,1] | |
}, | |
{ | |
question: [[],['cris'],[[[[[[[[[[[[[[[[]]]]]], 'awesome' ]]]]], /because/]]]],[undefined]], [],[],[null, [[]],[], Symbol('ok?') ]], | |
answer: [] | |
}, | |
]; | |
export function run(func, tests) { | |
for( const {question, answer} of tests ) { | |
const result = func(question); | |
const score = equal(result, answer); | |
console.log(`Test score: ${score ? 'pass' : 'fail'}`); | |
console.log("Question", question); | |
console.log("Correct answer", answer); | |
console.log("Result obtained", result); | |
console.log("\n"); | |
} | |
} | |
function equal(arr1, arr2) { | |
if ( arr1.length !== arr2.length ) return false; | |
for( let i = 0; i < arr1.length; i++) { | |
if ( arr1[i] != arr2[i] ) return false; | |
} | |
return true; | |
} |