Hey, I just wanted to say thank you for Interview Cake in general. Your approach of unravelling the solution gradually really helped me think about these problems.
While it wasn't my only resource, it helped me a lot interviewing for Facebook and Google recently, and I got offers from both.
Hi. I got an interview question a little while ago that the interviewer said “was not a datasteuctures/algorithm question” because it was too specific. I call bullshit, but I don’t actually know what the algorithm would be called.
Problem:
A tree of resources that you can get granted access rights to. When you get access to a node in the tree, you inherit rights to children transitivley. You can also have rights explicitly blocked. The ordering is important. An example, you start of as head of IT and have all the IT stuff granted, but explicitly no access to the IT security department. Then you make CEO and are granted right to everything, so that should overrule your previous restriction for the IT security department.
The problem you described doesn't ask a question. What are they asking you to do: implement the described data structure (not enough information), or untangle their department hierarchy?
I think the correct answer is "IT Security should be a peer of IT, not a subdepartment."
Hmmm. Can't get in your interviewer's head, but here's my guess: this might be one of those questions where the bulk of the discussion is supposed to be about weighing tradeoffs of different choices for the data model.
For example: how do you store the explicit blocks? More specifically, how do you articulate that head of IT is blocked from this subtree, but the CEO isn't? Some options:
- store the block as pairwise (individual, subtree)
- same idea, but instead of blocks you store explicit /allowances/ (and allow a tree node to have a flag set of "ignore the tree-based permission system here, and just lock everyone out who doesn't have an explicit permission")
- instead of blocking individuals, you could add an abstraction layer, e.g. user_groups, and assign permissions to /groups/.. You could also add an abstraction layer on top of the treenodes themselves (object_permission_groups?). Different tradeoffs with these options.
Again, hard to know exactly where your interviewer was trying to steer the conversation. But that'd be my guess!
The more I think about it, the less I understand why you'd ever need to explicitly block permissions. Permission groups are a good idea, but since the interviewer said it's not a data structure or algorithm question, I think it's trying to elicit problem analysis from the interviewee. What are the use-cases for blocking permissions? Why can't you just refactor the tree so that all assignments are allow? Using a mix of allow and deny is convoluted.
It seems like a trick question designed to see if the candidate is willing to question assumptions.
It seems pretty similar to how aws access controls work. By default everything is disallowed. Then you can gain more permissions explicitly. But an explicity deny overrides all explicit allows
Hmmm, since they specifically said it's not a data structures/algorithm thing, maybe they're looking for other aspects?
One potential that springs to mind is (say) governance or oversight considerations of the given situation?
Not sure how that'd apply directly either though. Feels like there's more info needed from the interviewer first, to give a hint as to the direction. :)
That would be an access control list (ACL). Find all the matching rules then process them top to bottom keeping track of whether access to the specific resource is allowed or not. Runtime is O(n) where n is the number of rules. There could be improvements but this is pretty straight-forward.
It’s pretty much your meat and potatoes data structures, excepting hash maps. I think a basic understanding of them and collision resolution strategies would benefit a learning developer. (And I'd suggest considering adding them.)
And, as an aside, I’ve found in practice that combining these lego blocks, allows you to build the sorts of specialized, efficient solutions you need.
Perhaps you could add an example of doing that, such as combining a queue with a binary search tree map to emit minimal values over a window. This would be a case where the sorted property of the tree is actually useful, as well.
While it wasn't my only resource, it helped me a lot interviewing for Facebook and Google recently, and I got offers from both.
(throwaway account for obvious reasons)