Josh Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I use preorder traversal here and on each level check whether the new sum for node is in ranges for the matching sum for max/min numbers. To do this I precompute all the possible combinations of numbers of min/max range (123 -> 1, 12, 123) and pass this list to recursive method together with level indication. If any non-leaf node is outside the range, I pass through the "marked" attribute to mark all descendants as though.
Also some big optimization: if some number at some level is exclusively inside ranges (not equal to any border), than we may skip further recursion as it will also be in ranges.
public static void checkAndMark(Node node, int curValue, List<Integer> from, List<Integer> to, int level, boolean markAll) {
if (markAll
|| from.size() <= level || curValue < from.get(level)
|| to.size() <= level || curValue > to.get(level)) {
node.mark();
markAll = true;
}
// Special case: if our number is exclusively inside the range - we don't need to recurse any more
if (node.value > from.get(level) && node.value < to.get(level)) {
return;
}
if (node.left != null) {
checkAndMark(node.left, curValue * 10 + node.left.value, from, to, level + 1, markAll);
}
if (node.right != null) {
checkAndMark(node.right, curValue * 10 + node.right.value, from, to, level + 1, markAll);
}
}
public static void main(String[] args) {
Node root = new Node(null, 1);
/// initialize tree here
int min = 124;
int max = 145;
checkAndMark(root, root.value, split(min), split(max), 0, false);
}
private static List<Integer> split(int min) {
int i = min;
List<Integer> list = new ArrayList<>();
while (i > 0) {
list.add(i);
i /= 10;
}
Collections.reverse(list);
return list;
}
simple but tricky, right now lets assume that the range would be of positive numbers only.
store the given upper value and lower value in an array eg. in given case arr1[ ]={1,2,5} and arr2[ ]={1,3,6}, now do a level order traversal of tree and check whether corresponding nodes are in the range of array elements considering each level as the array index. Example,
level 1-> 1 1 is in range of arr1[0] and arr2[0]
level 2-> 2 ,3 2 and 3 are in range of arr1[1] and arr2[1]
level 3->4, 5, 6, 7 5 and 6 are in range but 4 and 7 are out of
range in arr1[2] and arr2[2] thus nullify them.
free_subtree: Will free the left and right sub trees as well the root.
struct node * rbt (struct node * root, int l, int r, int v) {
if(!root) {
return NULL;
} else {
v = v*10 + root->data;
if(v > r) {
free_subtree(root);
return(root = NULL);
} else if (v < l && !root->left && !root->right) {
free(root);
return (root = NULL);
} else if (root->left) {
root->left = rbt(root->left, l, r, v);
} else if (root->right) {
root->right = rbt(root->right, l, r, v);
}
return root;
}
}
: frees
static boolean func (TreeNode root, int M, int num, Pair<Integer,Integer> minMax) {
if (root == null) {
return true;
}
int newNum = num * 10 + root.key;
if (checkRange(newNum, minMax, M) == false) {
return false;
}
if (func (root.left, M/10, newNum, minMax) == false)
root.left = null;
if (func (root.right, M/10, newNum, minMax) == false)
root.right = null;
return true;
}
static boolean checkRange (int N, Pair<Integer,Integer> minMax, int M) {
if (M <= 0) {
return false;
}
int min = minMax.getFirst() / M;
int max = minMax.getSecond() / M;
if (N < min
|| N > max) {
return false;
}
return true;
}
static int multipier (int num) {
int orig = num;
int multipier = 1;
while (num/10 > 0) {
multipier = multipier * 10;;
num = num/10;
}
System.out.println("Multiplier for Num: " + orig + " is : " + multipier);
return multipier;
}
calling function () {
Pair<Integer, Integer> minMax = new Pair<Integer, Integer> (125, 136);
int M = multipier (minMax.getFirst());
func (t.root, M, 0, minMax);
Its a running code, except you have to create your own tree and pair class or you can use min and max separate variable in place of minMax.
Algo:
1. While following inorder traversal, at every node of tree calculate the value formed from root to till that node.
2. compare that value with minMax value till that digit position. If number lies in range then continue, else return false.
3. If a node gets false from either of its subtree, it updates that subtree to null.
#include<iostream>
#include<string>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
node* newNode(int data,node *left=NULL,node *right=NULL){
node *nn=new node();
nn->data=data;
nn->left=left;
nn->right=right;
return nn;
}
node* createTree(){
node *n4=newNode(4,NULL,NULL);
node *n5=newNode(5,NULL,NULL);
node *n6=newNode(6,NULL,NULL);
node *n7=newNode(7,NULL,NULL);
node *n2=newNode(2,n4,n5);
node *n3=newNode(3,n6,n7);
node *n1=newNode(1,n2,n3);
return n1;
}
void printInorder(node *root){
if(root==NULL) return;
printInorder(root->left);
cout<<root->data<<" ";
printInorder(root->right);
}
node* modifyTree(node *root,string beg,string end,string val){
if(root==NULL) return NULL;
val+='0'+root->data;
if(!modifyTree(root->left,beg,end,val))
root->left=NULL;
if(!modifyTree(root->right,beg,end,val))
root->right=NULL;
if(root->left==NULL && root->right==NULL){
if(val.compare(beg)>=0 && val.compare(end)<=0) return root;
else return NULL;
}
return root;
}
node* modify(node *root,string beg,string end){
string s="";
return modifyTree(root,beg,end,s);
}
int main(){
node *root=createTree();
string r1="125";
string r2="136";
root=modify(root,r1,r2);
printInorder(root);
}
A recursive approach would do it easily.
void minMax(node* root,int min,int max,int num,node* prev)
{
num = num*10 + root->data;
if(root->left==NULL)
{
if(num<min || num>max)
{
if(num%10==prev->right->data)
prev->right = nullptr;
else
prev->left = nullptr;
}
return;
}
prev = root;
minMax(root->left,min,max,num,prev);
minMax(root->right,min,max,num,prev);
}
A recursive approach
void minMax(node* root,int min,int max,int num,node* prev)
{
num = num*10 + root->data;
if(root->left==NULL)
{
if(num<min || num>max)
{
if(num%10==prev->right->data)
prev->right = nullptr;
else
prev->left = nullptr;
}
return;
}
prev = root;
minMax(root->left,min,max,num,prev);
minMax(root->right,min,max,num,prev);
}
A Recursive approach would do it...
void minMax(node* root,int min,int max,int num,node* prev)
{
num = num*10 + root->data;
if(root->left==NULL)
{
if(num<min || num>max)
{
if(num%10==prev->right->data)
prev->right = nullptr;
else
prev->left = nullptr;
}
return;
}
prev = root;
minMax(root->left,min,max,num,prev);
minMax(root->right,min,max,num,prev);
}
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct node
{
int data;
struct node* left, *right;
};
node* root;
// Utility function to create new node
node *newNode(int data)
{
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
// Returns count of nodes in BST in range [low, high]
bool range(int N,int low,int high,int M)
{ if (M<= 0) {
return false;
}
int min = low / M;
int max = high / M;
if (N < min
|| N > max) {
return false;
}
return true;
}
bool fun(node* root,int M,int num,int low,int high)
{
if (root == NULL) {
return true;
}
int newNum = num * 10 + root->data;
if (range(newNum, low,high, M) == false) {
return false;
}
if (fun (root->left, M/10, newNum, low,high) == false)
root->left = NULL;
if (fun (root->right, M/10, newNum, low,high) == false)
root->right = NULL;
return true;
}
int multiplier(int l)
{
int m=1;
while(l/10)
{
m=m*10;
l=l/10;
}
return m;
}
void getCount(node *root, int low, int high)
{
int M=multiplier(low);
fun(root,M,0,low,high);
}
void inorder(node* root)
{
if(root)
{
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
// Driver program
int main()
{
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
int l = 125;
int h = 136;
getCount(root, l, h);
inorder(root);
return 0;
}
Why isn't 6 included to answer? 126 and 136 fall into range perfectly
- alisovenko October 03, 2014