Last active
June 29, 2019 07:39
-
-
Save huyz/4c8b15bf77fe39f7e525c8d73e07f985 to your computer and use it in GitHub Desktop.
Uber interview question: cardinal constraints
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
// Problem description: https://interviewcache.com/blog/direction-validation/ | |
function areCardinalConstraintsValid(rules) { | |
console.log(rules); | |
console.log(_areCardinalConstraintsValid(rules)); | |
console.log(); | |
} | |
function _areCardinalConstraintsValid(rules) { | |
// We choose N-S and E-W instead of S-N and W-E because of the English idioms "north to south" and "east to west", | |
// so they are more natural to say. | |
let ns = {}; | |
let ew = {}; | |
rules.forEach(rule => { | |
const [a, dir, b] = rule.split(/\s+/); | |
{ | |
let v, w; | |
if (/^N/i.test(dir)) { | |
[v, w] = [a, b]; // Nodes with higher latitudes point to nodes with lower latitudes | |
} else if (/^S/i.test(dir)) { | |
[v, w] = [b, a]; | |
} | |
if (v !== undefined) { | |
ns[v] = ns[v] || {adj: []}; | |
ns[v].adj.push(w); | |
} | |
} | |
{ | |
let v, w; | |
if (/E$/i.test(dir)) { | |
[v, w] = [a, b]; // Nodes with greater longitudes point to nodes with lesser longitudes | |
} else if (/W$/i.test(dir)) { | |
[v, w] = [b, a]; | |
} | |
if (v !== undefined) { | |
ew[v] = ew[v] || { adj: [] }; | |
ew[v].adj.push(w); | |
} | |
} | |
}); | |
// Note: mutates input graph so can only be run once | |
function isAcyclic(g, v = null) { | |
if (!v) { | |
return Object.keys(g).every(k => isAcyclic(g, k)); | |
} | |
if (!g || !g[v]) { | |
return true; | |
} | |
let n = g[v]; | |
// If given node is already in the path, then we have a cycle | |
if (n.inPath) { | |
return false; | |
} | |
// Don't re-search the same sub-graph | |
if (n.visited) { | |
return true; | |
} | |
n.visited = true; | |
try { | |
n.inPath = true; | |
return n.adj.every(w => isAcyclic(g, w)); | |
} finally { | |
n.inPath = false; | |
} | |
} | |
return isAcyclic(ns) && isAcyclic(ew); | |
} | |
/* | |
* Tests | |
*/ | |
let rules; | |
rules = [ | |
'A NW B', | |
'A N B', | |
]; | |
areCardinalConstraintsValid(rules); | |
rules = [ | |
'A N B', | |
'B NE C', | |
'C N A', | |
]; | |
areCardinalConstraintsValid(rules); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment