Microsoft | SDE 2 | India | Reject

The interview rounds (3-4) where supposed to be done on the same day.

Timings for first 2 rounds were given while the remaining rounds would be scheduled based on feedback from first two.

Round 1:

• The question was a basic tree serialisation problem where you would just need to do a BFS travsersal across the tree and print the nodes in the order of traversal.

• I was able to solve it with ease.

• The second question was on identifying substrings from a given string.

• I provided different algorithms like Aho Corasick, Rolling hash (Rabin karp), KMP etc and mentioned how different algorithms would be ideal for different scenarios. The interviewer seemed to be satisfied with the answer here as well.

Round 2:

• This was an 'LLD' round.

• The question was somewhat vague with missing details.

• The question was on maintaining directory permissioning system where users can check, grant and revoke permissions.

• There needs to be 3 APIs:

  • checkAccess(UserId, DorectoryPath): Check whether given user has access to directory path.
  • grantAccess(UserId, DirectoryPath): Provide access to user for the given directory path. Note that the access permissions would be granted to all the subtree directories of the affected directory as well.
  • revokeAccess(UserId, DirectoryPath): Revoke access of the user from the mentioned directory along with the subtree directories as well.

• If a user has permissions to a certain directory then all the directories in subtree should be giving access unless revokeAccsss operation was done to any sibtree directory for that user.
  Ex:
  grantAccess(U1, '/a/b/')
  checkAccess(U1, '/a/b/c') -> True
  revokeAccess(U1, '/a/b/d')
  checkAccess(U1, '/a/b/d/e') -> False
  checkAccess(U1, '/a/b/f/g') -> True

• I had provided some Trie structure (which is an in memory solution that I don't think is a good/correct one) but was not able to explain properly.

• Note that we are only dealing with directories and not files.

• No file system is provided to identify whether any directory even exists or not.

• I have thought about utilising some persistent storage (relational, graph, document) but all of them have something missing/unoptimised to handle all the operations efficiently.

• It would be really helpful if someone could provide any designs for this problem since I am not able to find this specific/related question in any system design articles, books or videos.

Haven't received any invitations for follow up rounds yet, so I guess it's a reject :(