Skip to content

Instantly share code, notes, and snippets.

@stephenh
Created November 2, 2018 14:29
Show Gist options
  • Save stephenh/87f940a1f1356f5ab9f4a8579c567443 to your computer and use it in GitHub Desktop.
Save stephenh/87f940a1f1356f5ab9f4a8579c567443 to your computer and use it in GitHub Desktop.
role1 = { name, perms: [p1, p2, p3] }
role2 = { name, perms: [p3, p4] }
roles = [role1, role2, ...]
# put lists in sorted sort
# O(N_roles * N_permissions log N_permissions)
roles.forEach { sortInPlace(_.perms) }
# compare each role to the other, N^2 = 16m comparison
# perms overlap is O(N_perms) = O(300)
# 16m * 300 == still doabled
roles.each { r1 =>
roles.each { r2 =>
intersect(r1.perms, r2.perms)
}
}
intersect(l1, l2) {
// https://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment