## Microsoft Interview Question for SDE1s

• 0

Country: United States
Interview Type: In-Person

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

``````struct Node
{
int data;
Node* left;
Node* right;
}``````

Use Iteration

``````Node* FindCeiling(Node* head, int key)
{

Stack<Node*> myStack = new Stack();

while(current)
{
if(current->data > key)
{
myStack.push(current);
current = current->left;
}
if(current->data <= key)
current = current->right;
}

return myStack.Pop();
}``````

Use Recursion

``````Node* FindCeiling(Node* head, int key)
{

Node* temp = FindCeiling(head->left, int key);
if(!temp)

return temp;
}``````

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

JSDude why do we need a stack here. We can do it using a integer variable?

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

@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.

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

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 ?

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

@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.

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

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``````

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

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

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

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

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

This solution is incorrect, try (9,(3(1,5)),15,20) for 4.

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

its just INorder Successor :)

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

Inorder takes O(N) time, where as solution by JSDUDE is O(logN)

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

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

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

Smallest integer greater than the key and present in BST.

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

//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 ceil = key;

{
{
}
else
{
}
}

return ceil;
}

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

Iteration:

Node* ceiling(Node* root, int value)
{
Node* ret=NULL;

while(root)
{
if(root->data > value)
{
ret=root;
root=root->left;
}
else
root=root->right;
}
return ret;
}

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

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

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

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

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

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

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.