Interview Question
Country: India
Interview Type: In-Person
class Node
{
public int Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
class Program
{
// 8
// / \
// 4 12
// / \ \
// 2 7 14
// / / \
// 5 13 15
static Node n15 = new Node { Value = 15, Left = null, Right = null };
static Node n13 = new Node { Value = 13, Left = null, Right = null };
static Node n14 = new Node { Value = 14, Left = n13, Right = n15 };
static Node n5 = new Node { Value = 5, Left = null, Right = null };
static Node n7 = new Node { Value = 7, Left = n5, Right = null };
static Node n2 = new Node { Value = 2, Left = null, Right = null };
static Node n12 = new Node { Value = 12, Left = null, Right = n14 };
static Node n4 = new Node { Value = 4, Left = n2, Right = n7 };
static Node root = new Node { Value = 8, Left = n4, Right = n12 };
static bool FindValue(int n, Node node)
{
if (null == node) return false;
if (n == node.Value) return true;
if (n >= node.Value)
{
return FindValue(n, node.Right);
}
else
{
return FindValue(n, node.Left);
}
}
static bool FindSum(int n)
{
for (int i=0; i<n/2; ++i)
{
int k = n - i;
if (true == FindValue(k, root) && true == FindValue(i, root)) return true;
}
return false;
}
static void Main()
{
//test
//Console.WriteLine(FindValue(4, root));
//Console.WriteLine(FindValue(7, root));
Console.WriteLine(FindSum(26));
}
}
- Chris August 24, 2016/* Linear Solution (O(N)): - at start, let a be minimum of BST and b the maximum of BST while(a <= b): - If a+b > desired sum: decrease b to the next lower value why: because if the smallest and the largest overshoot the desired sum, every combination with the largest element will overshoot, so we can ignore it in the future. - If a+b < desired sum: increase a to the next higher value why: because if the largest and the smallest will not reach the desired sum, the smallest will not be of any help to ever reach the sum, so we can ignor it in the future. - If a+b = desired sum: return a,b if loop terminates without having found anything, there is no pair that has as sum the desired sum the "=" in the while loop assumes taking two times the same node to build a sum is correct either. O(N) because finding min and max takes O(lg(N)) if BST is balanced and O(N) if it's a chain but finding aprox. N-k Predessors and k Successors takes O(N) amortized. so it's O(N). It does not matter if BST is balanced or not. Logarithmic solution (O(Lg(N))): - Make a to be minimum of BST - Make b to be maximum of BST while (a <= b) if a = b: return a,b if a+b > desired sum: find bigest b that satisfies b <= desired sum - a if a+b < desired sum: find smallest a that that satisfies a >= desired sum - b reasoning is the same as with linear solution, just that finding those limitting values is faster if we use binary search in a supposedly balanced BST . The question here is how many tries are required until it converges or knows it doesn't. I assume it is logarithmic, but I haven't managed to come up with a prove or disprove in the time taken for this problem. */ #include <utility> #include <iostream> using namespace std; class Node { private: int _value; Node* _left; Node* _right; Node* _parent = nullptr; public: Node(int v, Node* left, Node* right) : _value{ v }, _left{ left }, _right{ right } { if (left != nullptr) left->_parent = this; if (right != nullptr) right->_parent = this; } Node(int v) : Node(v, nullptr, nullptr) {} int get_Value() const { return _value; } pair<Node*, Node*> FindSumLinear(int sum) { Node *a = Min(); Node *b = Max(); while ((a != nullptr) && (b != nullptr) && (a->_value <= b->_value)) { int s = a->_value + b->_value; if (s > sum) b = b->Predecessor(); else if (s < sum) a = a->Successor(); else return pair<Node*, Node*>(a, b); } return pair<Node*, Node*>(nullptr, nullptr); } pair<Node*, Node*> FindSumLogarithmic(int sum) { Node *a = Min(); Node *b = Max(); while ((a != nullptr) && (b != nullptr) && (a->_value <= b->_value)) { int s = a->_value + b->_value; if (s > sum) { int db = sum - a->_value; b = BinarySearchAprox(db); if (b->_value > db) b = b->Predecessor(); } else if (s < sum) { int da = sum - b->_value; a = BinarySearchAprox(da); if (a->_value < da) a = a->Successor(); } else { return pair<Node*, Node*>(a, b); } } return pair<Node*, Node*>(nullptr, nullptr); } private: // returns the min note of this subtree Node * Min() { Node *c = this; while (c->_left != nullptr) c = c->_left; return c; } // returns the max node of this subtree Node * Max() { Node *c = this; while (c->_right != nullptr) c = c->_right; return c; } // returns predecessor or null if none Node *Predecessor() { Node *c = this; if (_left != nullptr) return _left->Max(); while (c->_parent != nullptr && c->_parent->_left == c) c = c->_parent; return c->_parent; } // resturns successor or null if none Node *Successor() { Node *c = this; if (_right != nullptr) return _right->Min(); while (c->_parent != nullptr && c->_parent->_right == c) c = c->_parent; return c->_parent; } // the function returns either the node with it's value or if that value // doesn't exist in the tree a node with it's next higher or next lower value Node* BinarySearchAprox(int value) { Node *n = this; while (true) { if (value > n->_value && n->_right != nullptr) n = n->_right; else if (value < n->_value && n->_left != nullptr) n = n->_left; else return n; // either a match or we just can't get any closer } } }; int main() { const char* tree = "\n"\ " 8\n"\ " / \ \n"\ " 4 12\n"\ " / \\ \\\n"\ " 2 7 14\n"\ " / / \\\n"\ " 5 13 15\n"; Node n2 = Node(2); Node n5 = Node(5); Node n7 = Node(7, &n5, nullptr); Node n4 = Node(4, &n2, &n7); Node n13 = Node(13); Node n15 = Node(15); Node n14 = Node(14, &n13, &n15); Node n12 = Node(12, nullptr, &n14); Node root = Node(8, &n4, &n12); cout << "tree: " << tree << endl << endl; for (int i = 1; i < 32; ++i) { auto result = root.FindSumLinear(i); auto result2 = root.FindSumLogarithmic(i); cout << endl << "result for sum " << i << ": " << endl; if (result.first == nullptr) cout << "LIN: no two nodes found that sum up to " << i << endl; else cout << "LIN: " << i << " = " << result.first->get_Value() << " + " << result.second->get_Value() << endl; if (result2.first == nullptr) cout << "LOG: no two nodes found that sum up to " << i << endl; else cout << "LOG: " << i << " = " << result2.first->get_Value() << " + " << result2.second->get_Value() << endl; } }