Created
February 4, 2020 15:13
-
-
Save alexandercsmith/85eeb03b8dddf8309838af2b0b9ee6fc to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Smallest Integer from Array | |
| Write a function: function smallestInt(A); | |
| that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A. | |
| Example: given A = [1, 3, 6, 4, 1, 2], the function should return 5. | |
| Given A = [1, 2, 3], the function should return 4. | |
| Given A = [-1, -3], the function should return 1. | |
| Write an efficient algorithm for the following assumptions: | |
| N is an integer within the range [1..100,000]; | |
| each element of array A is an integer within the range [−1,000,000..1,000,000]. | |
| Write test cases to validate that your implementation conforms to the specification. | |
| Additionally, implement the benchmark function to test the performance of your solution. The benchmark should be able to run in the browser and be capable of outputting a reasonably reliable score when comparing solutions in the same environment. | |
| You will be evaluated based on: | |
| - Correctness according to instructions | |
| - Algorithmic efficiency | |
| - Scope of test cases | |
| - Code style and quality | |
| You're advised to include any less efficient solutions or pseudo code definitions of such solutions in your final submission. | |
| */ | |
| function smallestInt(A) { | |
| // Create Object & Set Values with Array | |
| let obj = {}; | |
| for(let num of A) { | |
| obj[num] = 1; | |
| } | |
| // Set Bounds - [1..100000] | |
| let setBounds = (n) => { | |
| n = n >= 1 ? n : 1; | |
| n = n <= 100000 ? n : 100000; | |
| return n; | |
| }; | |
| let min = setBounds(Math.min(...A)); | |
| let max = setBounds(Math.max(...A)); | |
| // Find Missing Int | |
| for (let i = min; i < A.length + max; i++) { | |
| if ( !(i in obj) ) { return i; } | |
| } | |
| } | |
| function runTests() { | |
| describe('smallestInt', function() { | |
| it('should return the first missing positive number', function() { | |
| expect(smallestInt([-1,1,3,4,2])).toBe(5) | |
| }); | |
| it('should return a positive number within range of 1 to 100,000', function() { | |
| expect(smallestInt([99999,100002,100050])).toBe(100000) | |
| }); | |
| }) | |
| } | |
| function runBenchmark() { | |
| // Array Testing - Amount of Int Values in Test Array | |
| const arrMin = 10; | |
| const arrMax = 50; | |
| // Value Bounds | |
| const intMin = -1000000; | |
| const intMax = 1000000; | |
| // Iterations | |
| const iterations = 11; | |
| let opts = []; | |
| // Benchmark Loop Tests | |
| for (let i = 1; i < iterations; i++) { | |
| // Set Amount of Items | |
| let arrCount = Math.floor(Math.random() * (arrMax - arrMin + 1)) + arrMin; | |
| let arr = [] | |
| // Add Items to Array | |
| for (let t = 1; t < arrCount; t++) { | |
| arr.push(Math.floor(Math.random() * (intMax - intMin + 1)) + intMin); | |
| } | |
| // Browser Testing | |
| let start = window.performance.now(); | |
| let num = smallestInt(arr); | |
| let end = window.performance.now(); | |
| let time = end-start; | |
| // Output | |
| opts.push({ | |
| iteration: i, | |
| time: `${time.toFixed(4)}ms`, | |
| size: `${arrCount} Items`, | |
| number: num, | |
| array: arr | |
| }); | |
| } | |
| console.table(opts); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment