abc Interview Question for Applications Developers


Country: India
Interview Type: Written Test




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

I used a recursion for this:
Start from the root:
while we can go down the tree:
- if the value of the current node is equal to n return current.value
- if it is smaller than n: if the difference with n is smaller than the closest difference update closest, then call recursion on right subtree
- if it is bigger than n, call recursion on left subtree
(closest is initialized to the MAX Integer)

Time complexity O(logn) where n is the number of nodes in the tree.

public static int greatestLessThanN(Node root, int n, int closest) {
		if(root!=null) {
			if(closest==Integer.MAX_VALUE) { //visiting the first node, update closest
				closest=root.getValue();
			}
			if(root.getValue()==n) {
				return root.getValue();
			}
			else if(root.getValue()<n) {
				if((n-root.getValue())<=(n-closest)) {
					closest=root.getValue();
				}
				return greatestLessThanN(root.getRightChild(), n, closest);
			}
			else {
				return greatestLessThanN(root.getLeftChild(), n, closest);
			}
		}
		else {
			if(closest==Integer.MAX_VALUE) {
				System.out.println("Error: No value smaller than "+n);
			}
			return closest;
		}
	}

call the previous method with:

greatestLessThanN(Node root, int n, Integer.MAX_VALUE)

- gigi84 December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Looks legit until you can't have Integer.MAX_VALUE in your tree.
here is my solution

int findBiggest (int limit) {
		Integer retval = findBiggestR (this.root, limit);
		if (retval == null) throw new RuntimeException ("limit is too small!");
		return retval;
	}
	
	Integer findBiggestR (BSTNode root, int limit) {
		if (root == null) return null;
		if (root.value() == limit) return root.value();
		if (root.value() > limit) return findBiggestR (root.left(), limit);
		// root.value() < limit
		Integer retval = findBiggestR (root.right(), limit);
		if (retval == null || retval < root.value()) return root.value();
		return retval;
	}

- anonymous December 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We might also keep a record of the second best choice when making a decision:

TreeNode* findMaxLessThanOrEqualTo(TreeNode* p, int x, TreeNode* pSecondBest = NULL)
{
	if(p == NULL) return pSecondBest;
	if(p->val == x) return p;

	if(p->val > x) return findMaxLessThanOrEqualTo(p->left, x, pSecondBest);
	else if(pSecondBest != NULL && pSecondBest->val > p->val){
		return findMaxLessThanOrEqualTo(p->right, x, pSecondBest);
	}
	else return findMaxLessThanOrEqualTo(p->right, x, p);
}

- uuuouou January 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a in-order traversal (store the last traversed node) of the tree to the point when the current node is greater than the number given, the last traversed node is the answer.

- Anonymous December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) If right sub tree is not null , it is least value in right sub tree.
2) Else find parent for which node is this node is right child. by moving up using parent_ptr present in each node.

- abhinav neela December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not just do a Binary Search for N? Why all the traversal approaches?

//this is the Tree Construction
static class TreeNode{
	TreeNode left, right;
	int value;
}

/*
 * return null if no smaller value could be found
 */
public static Integer getClosestValue(TreeNode node, int n){
	Integer lastSmaller = null;
	while(node != null){
		if(node.value > n){
			//must go left
			node = node.left;
		}
		else if(node.value < n){
			lastSmaller = node.value;
			//must go right
			node = node.right;
		}
		else{
			return node.value;
		}
	}
	return lastSmaller;
}

- zortlord December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution. It returns a pointer to the tree node. It returns null if a node that meets the search criteria doesn't exist.

struct TreeNode {
	TreeNode *left;
	TreeNode *right;
	int val;
};

TreeNode *findNode(TreeNode *node, int val) {
	if(node == null) return null;
	if(val == node->value) return node;
	if(val < node->value && node->left == null) return node;
	if(val < node->value) return findNode(node->left, val);
	if(val > node->value) return findNode(node->right, val);
}

- Mhret December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static class Node
	{
		Node rightChild;
		Node leftChild;
		int value;
		
		public Node(int v)
		{
			this.value = v;
		}
		
	}
	
	public static class BST
	{
		
		public BST()
		{

		}
		
		
		public void  insert(Node root,Node in)
		{
			
			if(in.value > root.value)
			{
				if(root.rightChild == null)
				{
				  root.rightChild = in;
				  //System.out.println(" right "+root.rightChild.value);
				  return;
				}
				else
				{
				  insert(root.rightChild,in);
				}
			}
			else
			{
				
				if(root.leftChild == null)
				{
					root.leftChild = in;
					//System.out.println(" left "+root.leftChild.value);
					return;
				}
				else
				{
					insert(root.leftChild,in);
				}
			}
		}
		
		public void findNumber(Node rt,int num)
		{
			traverse(rt,num);
		}
		
		public void traverse(Node rt, int num)
		{
			
			if(rt.rightChild == null && rt.leftChild == null)
			{
				System.out.println("Could not find number");
				return;
			}
			
			if(num > rt.value)
			{
				if(rt.rightChild!= null && rt.rightChild.value == num)
				{
					System.out.println(rt.value);
					return;
				}
				traverse(rt.rightChild,num);
			}
			else
			{
				if(rt.leftChild!= null && rt.leftChild.value == num)
				{
					System.out.println(rt.value);
					return;
				}
				traverse(rt.leftChild,num);
			}
		}
	}
	
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Node root = new Node(20);
		BST binTree = new BST();
		Node first = new Node(10);
		Node second = new Node(30);
		Node third = new Node(9);
		Node fourth = new Node(11);
		Node five = new Node(25);
		Node six = new Node(44);
		
		binTree.insert(root,first);
		binTree.insert(root,second);
		binTree.insert(root,third);
		binTree.insert(root,fourth);
	    binTree.insert(root,five);
		binTree.insert(root,six);
		
		binTree.findNumber(root,44);
	}
}

- Himanshu Jain December 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {

    public static Node findValueLessThanOrEqualTo(Node n, int max, Node best) {
        if (n == null)
            return best;
        if (n.val == max)
            return n;
        if (n.val > max)
            return findValueLessThanOrEqualTo(n.left, max, best);
        else if (n.right == null)
            return n;

        return findValueLessThanOrEqualTo(n.right, max, n);
    }

    private static class Node {
        private Node left;
        private Node right;
        private final int val;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {

        // Image
        // cs [dot] cmu [dot] edu/~adamchik/15-121/lectures/Trees/pix/insertEx [dot] bmp

        Node a = new Node(11);

        Node b = new Node(6);
        Node c = new Node(4);
        Node d = new Node(8);
        Node e = new Node(5);
        Node k = new Node(10);

        Node f = new Node(19);
        Node g = new Node(17);
        Node h = new Node(43);
        Node i = new Node(31);
        Node j = new Node(49);

        // left
        a.left = b;
        b.left = c;
        b.right = d;
        c.right = e;
        d.right = k;

        // right
        a.right = f;
        f.left = g;
        f.right = h;
        h.left = i;
        h.right = j;

        Node res = findValueLessThanOrEqualTo(a, 5, null);
        System.out.println(res.val);
    }
}

- Anonymous January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include<bits/stdc++.h>
#define pb push_back

using namespace std;
struct Node
{
    int data;
    Node* left;
    Node* right;
};
Node* newNode(int data)
{
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
Node* insert(Node* root,int k)
{
    if(root==NULL)
    {
        Node* temp = newNode(k);
        return temp;
    }
    if(root->data > k)  root->left = insert(root->left,k);
    else if(root->data < k) root->right = insert(root->right,k);
    return root;
}
void print(Node* root)
{
    if(root==NULL)  return;
    print(root->left);
    cout<<root->data<<"\n";
    print(root->right);
}
int findMaxforN(Node* root,int N)
{
    if(root==NULL)  return -1;
    if(root->data > N)  return findMaxforN(root->left,N);
    if(root->data==N)   return N;
    if(root->data < N && root->right != NULL)
    {
        int k = findMaxforN(root->right,N);
        if(k != -1) return k;
        else return root->data;
    }
    else return root->data;
}
int main()
{
    int N = 30;

    // creating following BST
    /*
                  5
               /   \
             2     12
           /  \    /  \
          1   3   9   21
                     /   \
                    19   25  */
   Node* root = NULL;
    root = insert(root, 5);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 3);
    root = insert(root, 12);
    root = insert(root, 9);
    root = insert(root, 21);
    root = insert(root, 19);
    root = insert(root, 25);
    //cout<<root->data<<"\n";
    //print(root);
    for(int i=0;i<N;i++)    cout<<findMaxforN(root, i)<<"   ";
    return 0;
}

- uddeshya July 06, 2017 | 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