QuanticDev

QuanticDev's Engineering and Software Development Resources

Home View on GitHub

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 its 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.

Resources

You can find the video narration of this article on YouTube: https://www.youtube.com/watch?v=1mTGZHcs7zw

Video has additional tips and illustrations. If you want to read the comments or leave a comment, do so under YouTube video. If you want to contribute to the article, make a pull request on GitHub.

Overview

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 an article comping up on general tree structures soon.

Question

Design a tree with nodes that can be locked if none of its ancestors or descendants is locked. Locking/unlocking operations should run in O(h) time (h = height of the tree). Lock/unlock methods do not need to be thread-safe.

Requirements Analysis

Brute Force Approach: lock()

Improvement

Let’s try to implement a basic lock() method with O(h) time complexity target (h = height of the tree):

Solution: Parents Keep Track of Locked Descendants

Store locked and lockedDescendantCount variables in each node.

Method: lock()

Method: unlock()

Tips!