Microsoft Interview Question for SDE1s


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)
{
  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

Node* 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;
}

- JSDUDE April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- DashDash April 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JSDUDE April 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- ram April 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gen-y-s April 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- m@}{ April 30, 2013 | Flag
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);
}

- Anonymous April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- lyf.pboy April 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

its just INorder Successor :)

- NaMo June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- IntwPrep November 26, 2013 | Flag
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);
}

- lyf.pboy April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Smallest integer greater than the key and present in BST.

- lyf.pboy April 28, 2013 | Flag Reply
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 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;
}

- pkprog April 29, 2013 | Flag Reply
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;
}

- Anonymous May 03, 2013 | Flag Reply
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;
}

- SkyClouds May 06, 2013 | Flag Reply
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;
        }
}

- saurabh June 06, 2013 | Flag Reply
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;
	}

- Implemented in JAVA August 13, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More