[Microsoft Onsite Interview] A version of Lowest Common Ancestor in my Microsoft on-site interview on Monday (23rd Sep 2019)

I guess most risers will remember the lowest common ancestor problem we tackled in one of the technical sessions with @derrickmar. I found a disguised version of that problem in a very interesting question during my on-site with Microsoft on Mon. I just wanted to share that with fellow risers :slight_smile:

I was interviewing for authentication and authorization teams in Microsoft Azure. The question started with how would you design a data structure and a high level algorithm for checking if a user submitting a query for an operation like read or write has the required access. For example if an employee wants to look up salaries on the salaries of those that report to the employee should be accessible to them.

Eventually after a bit of meandering we converged to modeling the users in the form of a tree that mimicks the org chart with CEO at the top. Now to check if user A has access to user B’s salary all one has to do is check if user B is in user A’s subtree. Of course one can do a dfs starting from user A but that would be O(n) in time complexity.

A better approach is to find the lowest common ancestor of A and B and if the LCA is not A then A can’t access B’s salary. And we can check LCA in ~ O(log(h)) time where h is the higher of the depths of the nodes A and B from their lowest common ancestor :slight_smile:

5 Likes

This is an amazing interview overview @krisranden! Major props to you, and wishing you the best for your onsite outcomes!

:100: :100: :100: :100: :100: :100: :100: :100:

Thanks @brian. It’s my pleasure :slight_smile:

1 Like