|
Given a BST and integer value K.....
Microsoft Interview Questions and Answers
(Continued from previous question...)
76. Given a BST and integer value K.....
Question:
Given a BST and integer value K.
Find two nodes x and y such that x->data + y->data = K
Time O(n), space O(1)
maybe an answer:
public static void sumSearch(Node nd1, Node nd2, sum){
if(nd2 == null){
search sum - nd1 in tree nd1;
if (found)
print;
else{
searchSum(nd1.left, nd1.right, sum);
}
}
if(nd1 == null){
search sum - nd2 in tree nd2;
if (found)
print;
else{
searchSum(nd2.left, nd2.right, sum);
}
}
if(nd1 + nd2 > sum){
sumsearch(nd1.left, nd2);
sumsearch(nd1, nd2.left);
} else if(nd1 + nd2 == sum){
print
} else {
sumSearch(nd1.right, nd2);
sumSearch(nd1, nd2.right);
}
}
maybe an answer2:
Step 1: Do Inorder traversal in O(n) to convert to array which will be sorted since it is BST.
Step 2 :: Use the sorted array:: Code in C#
class Program
{
static void Main(string[] args)
{
int[] a = new int[] {1,2,3,5,6,8,10,13,14,15,18,20,29,30};
OutputNode o = Search2BSTNode(a, 0, a.Length - 1,29);
if (o == null)
{
Debug.WriteLine("Value not found");
return;
}
Debug.WriteLine(String.Format(" start:{0} value:: {1} end: {2} value:: {3}",o.StartIndex,o.StartValue,o.EndIndex,o.EndValue));
}
private static OutputNode Search2BSTNode(int[] a, int start, int end, int k)
{
int mid = (start + end)/2;
int x = a[start], y = a[mid];
if( (x + y) == k)
{
if (start == mid) return null; //Because only one value is found.
return new OutputNode(start,x,mid,y); //Good
}
if (start < end)
{
if (y > k) // sum is less than middle element so on left half.
{
end = mid;
return Search2BSTNode(a, start, end, k);
}
if ((x + y) > k) // shift middle towards left.
{
end--;
return Search2BSTNode(a, start, end, k);
}
// (x+y) < k
{
start++; //shift middle towards right.
return Search2BSTNode(a, start, end, k);
}
}
return null;
}
public class OutputNode
{
private int _startIndex;
private int _startValue;
private int _endIndex;
private int _endValue;
public OutputNode(int startIndex, int startValue, int endIndex, int endValue)
{
_startIndex = startIndex;
_startValue = startValue;
_endIndex = endIndex;
_endValue = endValue;
}
#region Properties
public int StartIndex {get { return _startIndex; }}
public int StartValue { get { return _startValue; }}
public int EndIndex { get { return _endIndex; }}
public int EndValue { get { return _endValue; }}
#endregion
}
}
(Continued on next question...)
Other Interview Questions
| 