Two problems: locking a binary tree and regular expressions

This post contains the solutions to two problems, from Daily Coding Problem:

1)

This is your coding interview problem for today.

This problem was asked by Google.

Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.

Design a binary tree node class with the following methods:

• is_locked, which returns whether the node is locked
• lock, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true.
• unlock, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true.

You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree.

2)

This is your coding interview problem for today.

This problem was asked by Facebook.

Implement regular expression matching with the following special characters:

• . (period) which matches any single character
• * (asterisk) which matches zero or more of the preceding element

That is, implement a function that takes in a string and a valid regular expression and returns whether or not the string matches the regular expression.

For example, given the regular expression "ra." and the string "ray", your function should return true. The same regular expression on the string "raymond" should return false.

Given the regular expression ".*at" and the string "chat", your function should return true. The same regular expression on the string "chats" should return false.

SOLUTIONS

For (1), the secret is to do the following:
 - Each node in the tree will have a pointer to its parent
 - In addition to the isLocked boolean, keep track of how many times a subnode has been locked, and unlocked, with a counter
 - Only lock, or unlock, if the counter is zero, and update the counter for the ancestors (O(h))

For (2),
 - Build the base cases trivially
 - Keep in mind that sometimes you'll have a regex that is not empty but can match an empty string, such as "a*.***". Handle that too
 - The induction is relatively straightforward, just the "*" requires a little more code

All code is here:
1) https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10082018.cs
2) https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10092018.cs

Thanks, Marcelo