## Josh Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Why isn't 6 included to answer? 126 and 136 fall into range perfectly

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

6 is not a child of 2

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

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) {
i /= 10;
}
Collections.reverse(list);
return list;
}``````

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

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

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

V.V. good suggestion. I could do it with your logic.

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

what if the range is 190 to 200??

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.