Last active
December 23, 2015 21:09
-
-
Save landau/6694436 to your computer and use it in GitHub Desktop.
Longest interval in random array
This file contains 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
/** | |
* Longest interval in an array | |
* Implemented with that graph algo BFS | |
* [1, 3, 7, 4, 2, 10, 8] should ouput [1, 4] | |
**/ | |
'use strict'; | |
var log = console.log; | |
// Builds a undirected graph based on an interval value | |
// 1 <-> 2 <-> 3 | |
var buildGraph = function (arr) { | |
var graph = {}; | |
var visited = {}; | |
arr.forEach(function (vertex) { | |
if (graph[vertex + 1] !== undefined) { | |
if (!graph[vertex]) { | |
graph[vertex] = []; | |
} | |
// This is the next vertex to point to | |
graph[vertex].push(vertex + 1); | |
} else { | |
graph[vertex] = []; | |
} | |
// Check if the previous vertex needs to point | |
// to the current vertex | |
if (graph[vertex - 1] !== undefined) { | |
graph[vertex - 1].push(vertex); | |
} | |
// Need this to track if a vertex is visited | |
visited[vertex] = false; | |
}); | |
return [graph, visited]; | |
}; | |
function Queue(values) { | |
values.forEach(function (val) { | |
this.insert(val); | |
}, this); | |
} | |
Queue.prototype = { | |
length: 0, | |
insert: function (val) { | |
return Array.prototype.push.call(this, val); | |
}, | |
dequeue: function () { | |
return Array.prototype.shift.call(this); | |
} | |
}; | |
var bfs = function (graph, visited, vertex) { | |
visited[vertex] = true; | |
var path = [vertex]; | |
var q = new Queue(path); | |
while (q.length) { | |
var v = q.dequeue(); | |
graph[v].forEach(function (v2) { | |
if (!visited[v2]) { | |
visited[v2] = true | |
q.insert(v2); | |
path.push(v2); | |
} | |
}); | |
} | |
return path; | |
}; | |
var getLongestInterval = function (arr) { | |
var built = buildGraph(arr); | |
var visited = built.pop(); // Could use vertex obj with visited key, but w/e | |
var graph = built.pop(); | |
var longest = null; | |
arr.forEach(function (vertex) { | |
var path = bfs(graph, visited, vertex); | |
if (!longest) { | |
longest = path; | |
} else if (path.length > longest.length) { | |
longest = path; | |
} | |
}); | |
// find lowest and highest vals to create interval | |
return [Math.min.apply(null, longest), Math.max.apply(null, longest)]; | |
}; | |
var tests = [ | |
{ | |
test: [1, 7, 3, 8, 2 ,4, 10], | |
expect: [1, 4] | |
}, | |
{ | |
test: [1, 2, 3, 4, 5], | |
expect: [1, 5] | |
}, | |
{ | |
test: [1, 3, 4, 5, 6, 9], | |
expect: [3, 6] | |
} | |
] | |
var assert = require('assert'); | |
tests.forEach(function (test) { | |
var interval = getLongestInterval(test.test); | |
assert(interval.toString() == test.expect.toString()); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment