This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,
"
This was the first round. A written test. I was asked to write a complete program that can execute with proper syntax. Also comment on the complexity and add comments to code where necessary. And i had to write it on Paper. Three questions were given and was asked to answer any two. I was given 1hr time for this.
This was one of the questions
Q) You are given a BST and a number k. Find the node in the tree which has the value closest to k.
".
2. Data Structure and Algorithm
This is binary search tree question. The data structure is binary tree and the algorithm is binary search. The idea to find the closest value in the tree is similar to binary search to spot the exact value in the tree. The extra thing need to be done is to keep the lower bound and the upper bound when the search process goes on.
In the binary search algorithm the range of search space is gradually narrowed down as each step goes deep into the tree. Finding the closest value is similar but need to keep tracking the range - the lower and upper bound. In the case of the the value appearing in the tree, this is exactly like binary search. If not, then keep tracking the range - lower/upper bound. When hitting the bottom level (leaf nodes), compare the distance between value and lower bound, and the distance between the value and the upper bound, Pick the bound with the smaller distance.
Pseudo-code:
1. Start from root, curNode = root, lowerBound = NULL, upperBound = NULL
2. Go to step 6, if cureNode is NULL
3. Return curNode if it has the same value we are searching
4. upperBound = curNode, if curNode has larger value
curNode = curNode->left and go to Step 2
5. lowerBound = curNode, if curNode has smaller value
curNode = curNode->right and go to Step 2
6. Return Null if both lowerBound and upperBound are NULL
Return lowerBound if lowerBound is not NULL and upperBound is NULL
Return upperBound if lowerBound is NULL and upperBound is not NULL
Return lowerBound if distance(val, lowerBound) <= distance(val, upperBound)
Return upperBound otherwise.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
TreeNode<T>* FindClosetNode_R_Internal(TreeNode<T> *root,
const T& val,
TreeNode<T>* lowerBound,
TreeNode<T>* upperBound)
{
if (!root) {
if (lowerBound && upperBound) {
// TODO: To cope other T type, implement a its own "closest" function
T toLowerBound = abs(val - *lowerBound->data);
T toUpperBound = abs(*upperBound->data - val);
return toLowerBound <= toUpperBound ? lowerBound : upperBound;
}
else if (lowerBound) {
return lowerBound;
}
else if (upperBound) {
return upperBound;
}
return NULL;
}
if (*root->data == val) {
return root;
}
else if (*root->data > val) {
return FindClosetNode_R_Internal(root->left, val, lowerBound, root);
}
else {
return FindClosetNode_R_Internal(root->right, val, root, upperBound);
}
}
// Recursive implementation
template <typename T>
TreeNode<T>* FindClosetNode_R(TreeNode<T> *root, const T& val)
{
return FindClosetNode_R_Internal<T>(root, val, NULL, NULL);
}
// Non-recursive implementation
template <typename T>
TreeNode<T>* FindClosetNode(TreeNode<T> *root, const T& val)
{
TreeNode<T> *lowerBound = NULL;
TreeNode<T> *upperBound = NULL;
TreeNode<T> *curNode = root;
while (curNode) {
if (*curNode->data == val) {
return curNode;
}
else if (*curNode->data > val) {
upperBound = curNode;
curNode = curNode->left;
}
else {
lowerBound = curNode;
curNode = curNode->right;
}
}
if (lowerBound && upperBound) {
// TODO: To cope other T type, implement a its own "closest" function
T toLowerBound = abs(val - *lowerBound->data);
T toUpperBound = abs(*upperBound->data - val);
return toLowerBound <= toUpperBound ? lowerBound : upperBound;
}
else if (lowerBound) {
return lowerBound;
}
else if (upperBound) {
return upperBound;
}
return NULL;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestFindCloesetNode_R()
{
TreeNode<double> *root = NULL;
assert(FindClosetNode_R(root, 0.0) == NULL);
std::vector<double> input = { 1.0 };
root = ConstructTreeRecursive(input);
assert(root);
TreeNode<double> *foundNode = FindClosetNode_R(root, 1.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode_R(root, 100.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode_R(root, -100.0);
assert(*foundNode->data == 1.0);
DeleteTree_BU(&root);
input = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0 };
root = ConstructTreeOnSortedValueBFS(input);
assert(root);
foundNode = FindClosetNode_R(root, -100.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode_R(root, -1.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode_R(root, -1.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode_R(root, 1.2);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode_R(root, 1.6);
assert(*foundNode->data == 2.0);
foundNode = FindClosetNode_R(root, 2.0);
assert(*foundNode->data == 2.0);
foundNode = FindClosetNode_R(root, 2.1);
assert(*foundNode->data == 2.0);
foundNode = FindClosetNode_R(root, 2.6);
assert(*foundNode->data == 3.0);
foundNode = FindClosetNode_R(root, 3.0);
assert(*foundNode->data == 3.0);
foundNode = FindClosetNode_R(root, 3.4);
assert(*foundNode->data == 3.0);
foundNode = FindClosetNode_R(root, 3.6);
assert(*foundNode->data == 4.0);
foundNode = FindClosetNode_R(root, 4.0);
assert(*foundNode->data == 4.0);
foundNode = FindClosetNode_R(root, 4.4);
assert(*foundNode->data == 4.0);
foundNode = FindClosetNode_R(root, 4.6);
assert(*foundNode->data == 5.0);
foundNode = FindClosetNode_R(root, 5.0);
assert(*foundNode->data == 5.0);
foundNode = FindClosetNode_R(root, 5.3);
assert(*foundNode->data == 5.0);
foundNode = FindClosetNode_R(root, 5.6);
assert(*foundNode->data == 6.0);
foundNode = FindClosetNode_R(root, 6.0);
assert(*foundNode->data == 6.0);
foundNode = FindClosetNode_R(root, 6.3);
assert(*foundNode->data == 6.0);
foundNode = FindClosetNode_R(root, 6.6);
assert(*foundNode->data == 7.0);
foundNode = FindClosetNode_R(root, 7.0);
assert(*foundNode->data == 7.0);
foundNode = FindClosetNode_R(root, 7.3);
assert(*foundNode->data == 7.0);
foundNode = FindClosetNode_R(root, 7.6);
assert(*foundNode->data == 8.0);
foundNode = FindClosetNode_R(root, 8.0);
assert(*foundNode->data == 8.0);
foundNode = FindClosetNode_R(root, 8.3);
assert(*foundNode->data == 8.0);
foundNode = FindClosetNode_R(root, 8.6);
assert(*foundNode->data == 9.0);
foundNode = FindClosetNode_R(root, 9.0);
assert(*foundNode->data == 9.0);
foundNode = FindClosetNode_R(root, 9.3);
assert(*foundNode->data == 9.0);
foundNode = FindClosetNode_R(root, 9.6);
assert(*foundNode->data == 10.0);
foundNode = FindClosetNode_R(root, 10.0);
assert(*foundNode->data == 10.0);
foundNode = FindClosetNode_R(root, 10.3);
assert(*foundNode->data == 10.0);
foundNode = FindClosetNode_R(root, 10.6);
assert(*foundNode->data == 11.0);
foundNode = FindClosetNode_R(root, 11.0);
assert(*foundNode->data == 11.0);
foundNode = FindClosetNode_R(root, 11.3);
assert(*foundNode->data == 11.0);
foundNode = FindClosetNode_R(root, 11.6);
assert(*foundNode->data == 12.0);
foundNode = FindClosetNode_R(root, 12.0);
assert(*foundNode->data == 12.0);
foundNode = FindClosetNode_R(root, 12.3);
assert(*foundNode->data == 12.0);
foundNode = FindClosetNode_R(root, 12.6);
assert(*foundNode->data == 13.0);
foundNode = FindClosetNode_R(root, 13.0);
assert(*foundNode->data == 13.0);
foundNode = FindClosetNode_R(root, 13.3);
assert(*foundNode->data == 13.0);
foundNode = FindClosetNode_R(root, 13.6);
assert(*foundNode->data == 14.0);
foundNode = FindClosetNode_R(root, 14.0);
assert(*foundNode->data == 14.0);
foundNode = FindClosetNode_R(root, 14.3);
assert(*foundNode->data == 14.0);
foundNode = FindClosetNode_R(root, 14.6);
assert(*foundNode->data == 15.0);
foundNode = FindClosetNode_R(root, 15.0);
assert(*foundNode->data == 15.0);
foundNode = FindClosetNode_R(root, 15.3);
assert(*foundNode->data == 15.0);
foundNode = FindClosetNode_R(root, 15.6);
assert(*foundNode->data == 16.0);
foundNode = FindClosetNode_R(root, 16.0);
assert(*foundNode->data == 16.0);
foundNode = FindClosetNode_R(root, 16.3);
assert(*foundNode->data == 16.0);
foundNode = FindClosetNode_R(root, 100.0);
assert(*foundNode->data == 16.0);
DeleteTree_TD(&root);
}
void TestFindCloesetNode()
{
TreeNode<double> *root = NULL;
assert(FindClosetNode(root, 0.0) == NULL);
std::vector<double> input = { 1.0 };
root = ConstructTreeRecursive(input);
assert(root);
TreeNode<double> *foundNode = FindClosetNode(root, 1.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode(root, 100.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode(root, -100.0);
assert(*foundNode->data == 1.0);
DeleteTree_BU(&root);
input = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0 };
root = ConstructTreeOnSortedValueBFS(input);
assert(root);
foundNode = FindClosetNode(root, -100.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode(root, -1.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode(root, -1.0);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode(root, 1.2);
assert(*foundNode->data == 1.0);
foundNode = FindClosetNode(root, 1.6);
assert(*foundNode->data == 2.0);
foundNode = FindClosetNode(root, 2.0);
assert(*foundNode->data == 2.0);
foundNode = FindClosetNode(root, 2.1);
assert(*foundNode->data == 2.0);
foundNode = FindClosetNode(root, 2.6);
assert(*foundNode->data == 3.0);
foundNode = FindClosetNode(root, 3.0);
assert(*foundNode->data == 3.0);
foundNode = FindClosetNode(root, 3.4);
assert(*foundNode->data == 3.0);
foundNode = FindClosetNode(root, 3.6);
assert(*foundNode->data == 4.0);
foundNode = FindClosetNode(root, 4.0);
assert(*foundNode->data == 4.0);
foundNode = FindClosetNode(root, 4.4);
assert(*foundNode->data == 4.0);
foundNode = FindClosetNode(root, 4.6);
assert(*foundNode->data == 5.0);
foundNode = FindClosetNode(root, 5.0);
assert(*foundNode->data == 5.0);
foundNode = FindClosetNode(root, 5.3);
assert(*foundNode->data == 5.0);
foundNode = FindClosetNode(root, 5.6);
assert(*foundNode->data == 6.0);
foundNode = FindClosetNode(root, 6.0);
assert(*foundNode->data == 6.0);
foundNode = FindClosetNode(root, 6.3);
assert(*foundNode->data == 6.0);
foundNode = FindClosetNode(root, 6.6);
assert(*foundNode->data == 7.0);
foundNode = FindClosetNode(root, 7.0);
assert(*foundNode->data == 7.0);
foundNode = FindClosetNode(root, 7.3);
assert(*foundNode->data == 7.0);
foundNode = FindClosetNode(root, 7.6);
assert(*foundNode->data == 8.0);
foundNode = FindClosetNode(root, 8.0);
assert(*foundNode->data == 8.0);
foundNode = FindClosetNode(root, 8.3);
assert(*foundNode->data == 8.0);
foundNode = FindClosetNode(root, 8.6);
assert(*foundNode->data == 9.0);
foundNode = FindClosetNode(root, 9.0);
assert(*foundNode->data == 9.0);
foundNode = FindClosetNode(root, 9.3);
assert(*foundNode->data == 9.0);
foundNode = FindClosetNode(root, 9.6);
assert(*foundNode->data == 10.0);
foundNode = FindClosetNode(root, 10.0);
assert(*foundNode->data == 10.0);
foundNode = FindClosetNode(root, 10.3);
assert(*foundNode->data == 10.0);
foundNode = FindClosetNode(root, 10.6);
assert(*foundNode->data == 11.0);
foundNode = FindClosetNode(root, 11.0);
assert(*foundNode->data == 11.0);
foundNode = FindClosetNode(root, 11.3);
assert(*foundNode->data == 11.0);
foundNode = FindClosetNode(root, 11.6);
assert(*foundNode->data == 12.0);
foundNode = FindClosetNode(root, 12.0);
assert(*foundNode->data == 12.0);
foundNode = FindClosetNode(root, 12.3);
assert(*foundNode->data == 12.0);
foundNode = FindClosetNode(root, 12.6);
assert(*foundNode->data == 13.0);
foundNode = FindClosetNode(root, 13.0);
assert(*foundNode->data == 13.0);
foundNode = FindClosetNode(root, 13.3);
assert(*foundNode->data == 13.0);
foundNode = FindClosetNode(root, 13.6);
assert(*foundNode->data == 14.0);
foundNode = FindClosetNode(root, 14.0);
assert(*foundNode->data == 14.0);
foundNode = FindClosetNode_R(root, 14.3);
assert(*foundNode->data == 14.0);
foundNode = FindClosetNode(root, 14.6);
assert(*foundNode->data == 15.0);
foundNode = FindClosetNode(root, 15.0);
assert(*foundNode->data == 15.0);
foundNode = FindClosetNode(root, 15.3);
assert(*foundNode->data == 15.0);
foundNode = FindClosetNode(root, 15.6);
assert(*foundNode->data == 16.0);
foundNode = FindClosetNode(root, 16.0);
assert(*foundNode->data == 16.0);
foundNode = FindClosetNode(root, 16.3);
assert(*foundNode->data == 16.0);
foundNode = FindClosetNode(root, 100.0);
assert(*foundNode->data == 16.0);
DeleteTree_TD(&root);
}
No comments:
Post a Comment