Lockable Tree - Google Interview Question
Lockable tree is a great programming interview question asked by Google, and it is a very well thought out one. A lockable tree is a tree with nodes that can be locked if none of the ancestors or descendants is locked. In the question, we are asked to implement locking/unlocking operations that should run in O(h) time where h is the height of the tree. Lock/unlock methods do not need to be thread-safe.
This is a very well-crafted interview question by Google. Both the requirements and the question itself are quite clear, which is a rarity in the industry. Often, the interviewers will intentionally make the question a little obscure, so they can observe how you do your requirements analysis and if you can communicate with the interviewers clearly. However, in this case, the requirements are clear cut, which I think reflects how Google operates. It is a medium difficulty question. But a fair knowledge of tree data structures is necessary to come up with a clean and concise solution. Do not worry though, I have a video comping up on general tree structures soon. And finally, solution code for this problem (along with its tests) is on GitHub, and the link is below.
Note: A real-world implementation of tree locking in databases would mostly have to be thread-safe, but I think it would be very domain-specific to be a general interview question.
Solution code to examples are available on:
• https://github.com/soygul/QuanticDev/...
If you can read the article version of this video at:
• http://quanticdev.com/algorithms/tree...
My "Algorithms" Playlist for all other algorithm questions & answers:
• • Algorithms
- - - - - - - - - -
/ quanticdev
/ quantic_dev
https://quanticdev.com
