Microsoft Interview Question SDE1s
Country: United States
Interview Type: In-Person
@DashDash,
I also thought the same during the interview. But the interviewer posed an example where the int variable wasn't sufficient. I can't remember the example right now. I am trying to remember\find it. Will udpate as soon as I do.
But yes you are correct int will work for most cases.
Good solutions! But, (in your example) according to your algorithm, the ceiling value of 14 returns null. Shouldnt it be 14 ? Or, is ceiling supposed to be greater than (and not equal to) the key ?
@JSDude, DashDash is right there is no need for a stack, since you only use pop once in the end to get the last element pushed into the stack. So all the previous values on the stack will NEVER be used - that's just a fact based on simple code analysis.
You don't need stack to store the ceil value. You can store min value from all values > search_value.
def ceil(self, value):
search_value = value + 1
ceil_candidate = sys.maxsize
cur = self.root
while cur != None:
if search_value == cur.value:
return cur.value
if search_value < cur.value:
ceil_candidate = min(ceil_candidate, cur.value)
cur = cur.left
else:
cur = cur.right
if ceil_candidate == sys.maxsize:
ceil_candidate = None
return ceil_candidate
Correct one:
struct bst {
int data;
struct bst* left;
struct bst* right;
};
Iterative:
int ceiling(struct bst* root, int key) {
if(!root)
return 0;
struct bst* t = root;
while(t) {
if(t->data > key && (!t->left || (t->left && t->left->data <= key)))
return t->data;
else if(t->data > key && t->left && t->left->data > key)
t = t->left;
else if (t->data <= key && t->right)
t = t->right;
else if(t->data <= key && !t->right)
return NULL;
}
}
Recursive:
int ceiling(struct bst* root, int key) {
if(!root)
return 0;
if(root->data > key && (!root->left || (root->left && root->left->data <= key)))
return root->data;
else if(root->data > key && root->left && root->left->data > key)
return ceiling(root->left, int key);
else if(root->data <= key && !root->right)
return NULL;
else if(root->data <= key && root->right)
return ceiling(root->right, int key);
}
Correct one:
struct bst {
int data;
struct bst* left;
struct bst* right;
};
Iterative:
int ceiling(struct bst* root, int key) {
if(!root)
return 0;
struct bst* t = root;
while(t) {
if(t->data > key && (!t->left || (t->left && t->left->data <= key)))
return t->data;
else if(t->data > key && t->left && t->left->data > key)
t = t->left;
else if (t->data <= key && t->right)
t = t->right;
else if(t->data <= key && !t->right)
return 0;
}
}
Recursive:
int ceiling(struct bst* root, int key) {
if(!root)
return 0;
if(root->data > key && (!root->left || (root->left && root->left->data <= key)))
return root->data;
else if(root->data > key && root->left && root->left->data > key)
return ceiling(root->left, int key);
else if(root->data <= key && root->right)
return ceiling(root->right, int key);
else if(root->data <= key && !root->right)
return 0;
}
struct bst {
int data;
struct bst* left;
struct bst* right;
};
Iterative:
int ceiling(struct bst* root, int key) {
if(!root)
return 0;
struct bst* t = root;
while(t->data > key && t->left && t->left->data > key)
t = t->left;
return t->data;
}
Recursive:
int ceiling(struct bst* root, int key) {
if(!root)
return 0;
if(root->data > key && root->left && root->left->data <= key)
return root->data;
return ceiling(root->left, int key);
}
//finds the smallest integer greater than the key and present in BST
//if return value is same as key, there is value in the tree that is greater than the key
int find_ceiling(node *head, int key)
{
int ceil = key;
while (head)
{
if (head->data >= key)
{
if ((head->data > key) && (head->data < ceil)) ceil = head->data;
head = head->right;
}
else
{
head = head->left;
}
}
return ceil;
}
Implemented by C#.
public class BinaryTree {
public BinaryTree Left;
public BinaryTree Right;
public int Value;
}
public BinaryTree FindCeilingRecursively(BinaryTree node, int n) {
if(node == null) return null;
if(n >= node.Value) {
return FindCeiling(node.Right, n);
} else {
BinaryTree result = FindCeiling(node.Left, n);
return result == null ? node : result;
}
}
public BinaryTree FindCeilingReitoratively(BinaryTree node, int n) {
if(node == null) return null;
BinaryTree result = null, p = node;
while (p != null) {
if(n >= node.Value) {
p = p.Right;
} else {
result = p;
p = p.Left;
}
}
return result;
}
Both iterative & recursive version :
int node_ceiling_iterative (tree *root, int value)
{
if (!root)
{
return -1;
}
int result = -1;
while (root)
{
if (value < root->key)
{
result = root->key;
root = root->l_child;
}
else if (value > root->key)
{
root = root->r_child;
}
else
{
result = root->key;
break;
}
}
return result;
}
void node_ceiling (tree *root, int value, int *result)
{
if (!root)
{
return;
}
if (root->key > value)
{
*result = root->key;
node_ceiling (root->l_child, value, result);
}
else if (root->key < value)
{
node_ceiling (root->r_child, value, result);
}
else
{
*result = root->key;
return;
}
}
private Node celling(Node node,Key key){
if(node==null) return null;
int cmp=key.compareTo(node.key);
if(cmp==0) return node;
if(cmp>0) return floor(node.right, key);
Node temp=floor(node.left, key);
if(temp!=null) return temp;
return node;
}
public Key celling(Key key){
Node temp=celling(root, key);
if(temp==null) return null;
return temp.key;
}
struct Node { int data; Node* left; Node* right; }Use Iteration
Node* FindCeiling(Node* head, int key) { if(!head) return head; Stack<Node*> myStack = new Stack(); Node* current = head; while(current) { if(current->data > key) { myStack.push(current); current = current->left; } if(current->data <= key) current = current->right; } return myStack.Pop(); }Use Recursion
- JSDUDE April 27, 2013Node* FindCeiling(Node* head, int key) { if(!head) return head; if(head->data <= key) return FindCeiling(head->right, key); Node* temp = FindCeiling(head->left, int key); if(!temp) return head; return temp; }