## Google Interview Question for Software Engineer Interns

• 3

Country: United States

Comment hidden because of low score. Click to expand.
5
of 7 vote

Working code is given below... call function using..
findCeil(root, num, num);

``````void findCeil(node* root, int num, int foundVal)
{
if(*root != NULL)
{
if(num >= root->val)
findCeil(root->right, num, foundVal);
else
findCeil(root->left, num, root->val);
}
else
printf("\n Value : %d", foundVal);
}``````

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

Good......
Working on all cases...

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

It works, but best case would be o(log n). It's arguable whether a node -> node traversal would be better, because the ceil is most likely collocated nearby the original value. Of course the supposes that we already have the node we are looking for, not just its value.

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

Every time we detect a leaf node, this function will print value of 'findval' twice. Its better once we detect the ceil then just return from the function.

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

It doesnt work with only the root node being present
root = 5
find value = 8;

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

``````public Node ceil(int i) {
largest = null;
largest = ceilInt(root,i);
return largest;
}

private Node ceilInt(Node n, int x){
if(n == null) return largest;

if(n.value > x){
largest = n;
return ceilInt(n.left,x);
}else{
return ceilInt(n.right,x);
}
}
private Node root = null;
private Node largest = null;``````

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

Assuming an existing node class with node.left, node.right, and node.value properties, below is a Python solution:

``````def ceil_bst(node, key):
if node is None:
return None
elif node.value == key:
return node.value
elif node.value < key:
return ceil_bst(node.right, key)
else:
left_value = ceil_bst(node.left, key)
return left_value if left_value else node.value``````

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

Similar to search in BST..just keep a reference variable updating the smallest value greater than given node value

see this--
geeksforgeeks.org/floor-and-ceil-from-a-bst/

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

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

Its different from - just finding ceil of a key but it is asked to find ceil of a key even if the key is present in the tree.

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

Since it is a BST, try to find a range where (root)<(target)<(root->right), then find the smallest item(Upper ceiling) in the right subtree. It toke O(logN) time since it is a BST.

To find the smallest, another O(logN) spent, and in sum it still hold O(logN) complexity.

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

Since it is a BST, try to find a range where (root)<(target)<(root->right), then find the smallest item(Upper ceiling) in the right subtree. It toke O(logN) time since it is a BST.

To find the smallest, another O(logN) spent, and in sum it still hold O(logN) complexity.

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

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

// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return -1
int Ceil(node *root, int input)
{
// Base case
if( root == NULL )
return -1;

// We found equal key
if( root->key == input )
return root->key;

// If root's key is smaller, ceil must be in right subtree
if( root->key < input )
return Ceil(root->right, input);

// Else, either left subtree or root has the ceil value
int ceil = Ceil(root->left, input);
return (ceil >= input) ? ceil : root->key;
}

copied from geeksforgeeks, thought will help others..

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

``````TreeNode *findCeiling(TreeNode *curr, int target) {
if (curr == NULL) return NULL;
if (curr->val > target) {
Node *findsmaller = findCeiling(curr->left, target);
if (findsmaller)
return findsmaller;
else
return cure;
} else {
return findCeiling(node->right, target)
}

}``````

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

``````public static int ceilingValue(BTNode node, int value, int currCeil)
{
if(node == null)
return Integer.MIN_VALUE;

int nextCeil = 0;
if(node.data < currCeil && value < node.data)
currCeil = node.data;

if(value >= node.data)
nextCeil = ceilingValue(node.right, value, currCeil);
else
nextCeil = ceilingValue(node.left, value, currCeil);

if(nextCeil == Integer.MIN_VALUE)
return currCeil;
else
return nextCeil;
}``````

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

1. Augment the BST with size field.
2. First find the rank of the given key k, and let it be r.
3. Find the (r+1)st order statistic, which is the ceiling element of the key k.
(Finding rank and selecting the ith order static are standard procedures on a size-field augmented BST)

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

Take coursera.org/course/algs4partI course, Prof. has explained BST Floor and Ceil ling function in a more precise way which is better than all above solution. Its in section 9.5. Before Coursera, you need to put dubdubdub

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

A simple solution would be to find the successor of the key. Well but the given key may exist or may not exist.

case 1: given key exist in the tree... then its simple to find its successor.
case 2: given key doesn't exist in the tree... In this case, we will first try to find the key in the tree and we will find the successor of the last element before we hit the null.

Time complexity: O(log n)

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

//just do a inorder traversal and then store collection in an array, and then traverse over it
//O(n) time and O(n) space
vector<int > vec;

int *inorder(node *root)
{
if(root ==NULL) return;
else
{
inorder(root->left);
vec.push_back(root->data);
inorder(root->right);
}
return vec;
}
vector<int>::const_iterator it;

//now traverse the vec

int trave(vector *vec,int key)
{
it=vec.begin();
while(*it <=key)
{
it++;
}
cout<<*it++;
}

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

It can be done in-place without taking extra variable and in o(log n) time.

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

If it's a binary search tree, then by "ceil" and the example given, i assume that you are looking for the element which immediately succeeds the given value. i.e.: 13 => 15

You have to handle two cases:

1.) The successor is your right child
2.) The successor is your ancestor

This assumes that we already have a pointer to the target node we are trying to get the ceil of. It's just a way to do an inorder traversal given a start-node, and not a traversal of the entire tree.

``````int ceil(const node* n){
// Handle our right child
node* curr = n;
if(curr->right){
while(curr->right){
curr = curr->right
}
return curr;
}

// Get our ancestor.  We go up until we are no longer a left child
while(curr->parent && curr->parent->left != curr){
curr = curr->parent;
}
return curr;	// Would return NULL if it's invalid
}``````

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

Here is my non-recursive solution. Note: It assumes that we are asked to return the successor even if the given key is in the tree.

``````int GetSuccessor (CNode* root, int key)
{
int lastBig = Int32.Max;
CNode* current = root;
while ( current != null )
{
if (key < current->data)
{
lastBig = current->data;
current = current->left;
}
else
{
current = current->right;
}
}

return lastBig;
}``````

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

``````TreeNode* ceilNode(TreeNode* root, int key)
{
TreeNode* ans;
while (root)
{
if (root->val > key) {
ans = root;
root = root->left;
}
else root = root->right;
}
return ans;
}``````

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

Java solution using static variable and in order traversal

``````private static boolean done = false;
public void findCeil(Node root, int key){
if(root == null)
return;
findCeil(root.getLeft(), key);
if(!done){
if(root.getData() > key){
System.out.println("The ceiling of " + key + " is: " +  root.getData());
done = true;
}
}
findCeil(root.getRight(), key);
}``````

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

With python and lazy evaluation

``````class Node(object):
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right

def ceiling(node, val):
"""Celing value

>>> tree = Node(8,
...             Node(3,
...                  Node(2, None, None),
...                  Node(6, Node(4, None, None), None)),
...             Node(12,
...                  Node(10, None, None),
...                  Node(15, None, None)))
>>> ceiling(tree, 13)
15
>>> ceiling(tree, 4)
6
>>> ceiling(tree, 8)
10
"""
def greater(node, val):
if node is None:
return
if node.value > val:
for left in greater(node.left, val):
yield left
yield node
for right in greater(node.right, val):
yield right
try:
return next(greater(node, val)).value
except StopIterator:
return``````

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

``````CeilVal=INT_MAX;
struct bst *CielNode=NULL;
if(node==NULL)
return CeilNode;
while(node!=NULL)
{
if(node->data > givenValue)
{
if(node->data < CeilVal)
{
CeilNode=b;
CielVal=node->data;
}
node=node->lc;
}
else
node=node->rc;
}
return CeilNode;``````

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

``````if(b==NULL)
return NULL;
struct bst *CeilVal=NULL;
while(b!=NULL)
{
if(b->data>GivenValue)
{
if (CeilVal==NULL || b->data < CeilVal->data)
CeilVal=b;
b=b->lc;
}
else
b=b->rc;
}
return CeilVal;``````

It is an O(lg n)

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

``````if(b==NULL)
return NULL;
struct bst *CeilVal=NULL;
while(b!=NULL)
{
if(b->data>GivenValue)
{
if (CeilVal==NULL || b->data < CeilVal->data)
CeilVal=b;
b=b->lc;
}
else
b=b->rc;
}
return CeilVal;``````

It is an O(lg n)

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

Call this function Ceil(root,input, -1)

``````//If input is more than the max key in BST, return -1
int Ceil(node *root, int input, int ans)
{
// Base case
if( root == NULL )
return ans;

// If root's key is equal or smaller, ceil must be in right subtree
// So iterate with previous value - possibly minus one if its going right.
if( root->key <= input )
return Ceil(root->right, input, ans);

// Else, either left subtree or root has the ceil value
// parent must be a possible candidate - iterate further
// to left to find smaller value than parent
return Ceil(root->left, input, root->key);
}``````

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

This is can be done in big-oh(log n) complexity.

The question needs to return the strictly next larger but smaller than anything for a given element.

And finding next larger takes big-oh (h).

``````find_node_closer_to_k(self,k,closer_value):
if self.value == k
self.value = closer_value
next_larger(self)
else:
if self.value > k:
if self.value <= closer_value:
closer_value = self.value
find_node_closer_to_k(self.left,k,closer_value)
else:
outcome = next_larger(self.parent)
else:
if self.value <= closer_value:
closer_value = self.value
find_node_closer_to_k(self.right,k,closer_value)
else:
outcome = next_larger(self.parent)

def next_larger(self):
if self.right is not None:
return self.right.find_min()
current = self
while current.parent is not None and current is current.parent.right:
current = current.parent
return current.parent``````

find_node_closer_to_k takes big-oh(log n) and next_larger takes(log n)

so overall time complexity is big-oh(log n)

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

O(NLogN) - Using In-Order Traversal

``````Given the Key find the Ceiling Value in BST

Step1 : Use In-order Traversal to Traverse the entire Tree into a List - O(NLogN)

Step 2: Use Binary search on the List to find the first Number Greater than the Given Key. - O(N)

The First Number you find in the List will be your Ceiling Value.

Time Complexity =  O(NLogN) + O(N) =  O(NLogN)``````

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

Here's my iterative solution:

``````public class Main {
static class Node {
int x;
Node left;
Node right;

Node(int x) {
this.x = x;
}
}

public static void main(String[] args) {
Node root = new Node(8);

root.left = new Node(4);
root.right = new Node(12);

root.left.left = new Node(2);
root.left.right = new Node(6);

root.right.left = new Node(10);
root.right.right = new Node(14);

for(int i = 0; i < 16; i++) {
System.out.println(String.format("%d  %d", i, ceil(root, i)));
}
}

public static int ceil(Node root, int x) {
Node current = root;
int c = -1;
while (current != null) {
if (current.x == x) {
return current.x;
}
if (current.x < x) {
current = current.right;
} else {
c = current.x;
current = current.left;
}
}
return c;
}
}``````

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

There will be three cases
input <--value whose ceil is to be searched

1) either the root.key == input --> in this case return the root.key
2) either the root.right < input --> in this case root will be in the right subtree
3) else the root will be in the left subtree or will be equal to root.key

``````class node{
int key;
node left;
node right;

public node(int val){
key = val;
left = null;
right = null;
}
}

public class ceil{

public static int Ceil(node root, int input){
if(root == null)
return -1;
if(root.key == input)
return root.key;
if(root.key < input)
return Ceil(root.right, input);

int ceil = Ceil( root.left , input);
return (ceil >= input) ? ceil : root.key;
}
}``````

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

this part of code will satisfy all the cases for sure:
int findCeil(node* root, int num, int foundVal=-1)
{
if(root)
{
if(num > root->data)
findCeil(root->right, num, foundVal);
else if(num==root->data)
return root->data;
else
findCeil(root->left, num, root->data);
}
else
return foundVal;
}

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

this piece of code will satisfy all the cases:

``````int findCeil(node* root, int num, int foundVal=-1)
{
if(root)
{
if(num > root->data)
findCeil(root->right, num, foundVal);
else if(num==root->data)
return root->data;
else
findCeil(root->left, num, root->data);
}
else
return foundVal;
}``````

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

inorder successor ?

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

It will take O(n) time. I am looking for O(log n) answer.

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

Assume all node values are positive. -1 is an unvalid node value.

``````void findCeiling(node n, int key) {
if (n == NULL) return;
if (key < n.value) {
finalResult = n.value;
findCeiling(n.left, key);
} else {
findCeiling(n.right, key);
}
}``````

To call this:

``````int finalResult = -1;
findCeiling(root, key);
std::cout << (finalResult == -1) ? "No ceiling value exists" : finalResult;``````

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

just traverse in reverse of inorder starting from right most. Store the immediate greater value known. When the first node you hit less then the input print the immediate greater value.

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

if i want the ceil of smallest value ??
that would result in O(n) again.

But i think we could do it like this,search for the given value and once found , find the next greatest value.
that would be the right child of the given node or the root of the given node if right child is null...

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

``````public class BinarySearchTree {

private class Node {
int value;
Node left;
Node right;

public Node(int val) {
value = val;
left = null;
right = null;
}
}
Node root = null;

private int keyCeiling(int key, Node currNode) {
if(currNode == null) return -1;
int ceiling = -1;
if(key == currNode.value) ceiling = currNode.value;
else if(key < currNode.value) {
ceiling = currNode.value;
int ceil = keyCeiling(key, currNode.left);
ceiling = (ceil == -1) ? ceiling : ceil;
}
else {
int ceil = keyCeiling(key, currNode.right);
ceiling = (ceil == -1) ? ceiling : ceil;
}
return ceiling
}

public void findCeiling(int key) {
if(root == null) {
System.out.println("Empty binary search tree");
return;
}
int ceilValue = keyCeiling(key, root);
if(ceilValue == -1)
else
System.out.println("Ceiling value for " + key + " is " + ceilValue);
}
}``````

Please let me know if I have missed out any corner cases.

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

to keep stuff simplier, you have to use recursion:
assuming

``````typedef struct binNode{
struct binNode* left
struct binNode* right
}* Node;``````

my solution is

``````findceil(Node node, searchValue, foundValue){
if(node!=NULL){
/*watchout: you want keep MAX value*/
else findceil(node.left,searchValue,foundValue);

}``````

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

Obviously last line of code is wrong,
correct one is the following

``else printf("Ceiling value: %d",foundValue);``

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

``````int func(int key,node* root)
{
int ceil=32767;//or MAX_INT
while(root!=NULL)
{
if(root->val > key)
{
if(root->val < ceil)
{
ceil=root->val;
}
root=root->left;
}
else  //both cases of equal and lesser
root=root->right;
}
return ceil;
}``````

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

I think it can simply be done using recursion in the following way.It just traverse the bst in a recursive way which will take the same time as that required to traverse a bst. You can test the below code:

``````#include <stdio.h>
#include <stdlib.h>

typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
}
void findCeil(node_t *root,int data)
{
if(root->data==data)
findCeil(root->right,data);
else if(root->data<data)
findCeil(root->right,data);
else if(root->data>data)
{
printf("The value found is %d ",root->data);
return;
}
}
int main()
{
node_t *tree=newNode(3);
tree->left=newNode(2);
tree->left->left=newNode(1);
tree->right=newNode(6);
tree->right->right=newNode(7);
tree->right->left=newNode(5);
findCeil(tree,6);
}``````

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

What if you call findCeil(tree, 1)? In this case your code would return 3 when the answer should be 2.

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

#include <stdio.h>
#include <stdlib.h>

typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
return n;
}
bool findCeil(node_t *root,int data)
{
if(root == NULL)
return false;

if(findCeil(root->left, data))
return true;

if(root->data > data) {
cout << "ciel = " << root->data << endl;
return true;
}
if(findCeil(root->right, data))
return true;

return false;
}
int main()
{
node_t *tree=newNode(8);
tree->left=newNode(3);
tree->left->left=newNode(2);
tree->left->right=newNode(6);
tree->right=newNode(12);
tree->right->right=newNode(15);
tree->right->left=newNode(10);
findCeil(tree,4);
}

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

#include <stdio.h>

typedef struct node node_t;

struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
return n;
}
int findCeil(node_t *root,int data,int result)
{
if(root == NULL) return result;
if(root->data > data)
result = findCeil(root->left,data,root->data);
else if(root->data <= data)
result = findCeil(root->right,data,result);
return result;
}
int main()
{
node_t *tree=newNode(3);
//tree->left=newNode(2);
//tree->left->left=newNode(1);
tree->right=newNode(6);
tree->right->right=newNode(7);
tree->right->left=newNode(5);
printf("The value found 1 is %d\n",findCeil(tree,1,-32760));
printf("The value found 2 is %d\n",findCeil(tree,2,-32760));
printf("The value found 3 is %d\n",findCeil(tree,3,-32760));
printf("The value found 4 is %d\n",findCeil(tree,4,-32760));
printf("The value found 5 is %d\n",findCeil(tree,5,-32760));
printf("The value found 6 is %d\n",findCeil(tree,6,-32760));
printf("The value found 7 is %d\n",findCeil(tree,7,-32760));
return 0;
}

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.