## Interview Question

• 1
of 1 vote

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````/*
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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

do the nodes have prent pointers

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are there negative numbers in the BST as well?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.