## abc Interview Question for Applications Developers

• 0

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

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

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

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

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.

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.

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

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

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

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

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

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.