techInterview Discussion

Here's a nice puzzle I came across recently.

You are given a rooted, ordered, but not necessarily binary, tree.  Each node can be in one of two states: either "on" or "off."
Initially all nodes are off.
The rule is that you can switch a node on only if none of its descendants and none of its ancestors are already on.
The tree structure is fixed.  Only the nodes' states may change.

The problem:  devise an efficient data structure to support the following two operations.  (You may need to do some preprocessing.)

SwitchOn(nd):  If the node pointed to by nd is already on, or one of its ancestors or descendant is on, do nothing.  Otherwise switch it on.

SwitchOff(nd): If the node pointed to by nd is on, switch it off.  Otherwise do nothing.

Assume you can navigate the tree freely: every node holds a pointer to its parent, and an array of pointers to its children.  You may augment the nodes with whatever additional fields you like.

O(log n) amortized is pretty routine. Is something better known?

Yes, you can do better than O(logn).

Better than Theta(h) where h = o(log n) is the height of the tree?

if nd is pointer, why do we need to navigate the tree to find the node?
Just dereference the pointer to do the job, anything I missed?

@Yaxiong, you are missing the fact that you need to discover/update whether any of the node's ancestors/descendants are on.  This may require navigation of the tree.

Here's a little hint: you may want to do some preprocessing.

@d, yes.  (And not amortized, btw.)  The solution I have in mind is O(f(n)) for some function f(n) that is o(log n).  So as long as h=\omega(f(n)), the solution is going to be o(h).  For h=O(f(n)) we can obviously switch to the naive method in order to remain O(h). 

I Haven't thought about it, but if we concentrate on h as the complexity parameter, I wouldn't be surprised if o(h) is possible.  I'll give it some thought.

OK, O(log log n), and that's my final answer.

Indeed.