John.hzs1988
BAN USERThanks for pointing that out. You are right. Will modify my solution.
- John.hzs1988 January 27, 2015Time O(n * logn) space O(logn) (recursion stack size)
private TreeNode[] res = new TreeNode[2];
public void bstTwoSum(TreeNode root, int target) {
// assume root.val is one of the 2 numbers:
if (root.val < target) {
int tar = target - root.val;
if (tar == root.val) return; // if root.val = target/2 we won't find the other node
TreeNode theOther = search(tar, root);
if (theOther != null) {
res[0] = root.val > theOther.val ? theOther : root;
res[1] = res[0] == root ? theOther : root;
} else {
// root is not one of the numbers, try it's both subtrees
bstTwoSum(root.left, target);
bstTwoSum(root.right, target);
}
} else {
// if current value not less then target value, two numbers must all be in left sub tree.
bstTwoSum(root.left, target);
}
Note: search(int val, TreeNode root) do binary tree search for val, in BST rooted at root, takes O(logn) time.
- John.hzs1988 January 27, 2015
Abstract message service to a MessageCenter class.
}
Catalog manager will push diff. kind of events when data updated. Other backends register to events they are interested in. Like
}
- John.hzs1988 January 29, 2015Where to put message queue depends on which part have larger amount of transaction and need less delay. e.g. queueing message in each backend will make CatalogManager faster: it will just keep fireing events, and each backend will deal with eventually consistency. Given in your description, CatalogManager seems to touch all transactions, it'll easily become a bottleneck, I'd recommand queueing message in all other backends. Note for CatalogManager pushing events are async, so it won't block at all.