abc Interview Question
Applications DevelopersCountry: India
Interview Type: Written Test
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;
}
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);
}
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;
}
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);
}
/* 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);
}
}
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);
}
}
#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;
}
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.
call the previous method with:
- gigi84 December 21, 2014