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

- alisovenko October 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

6 is not a child of 2

- Fung October 09, 2014 | Flag
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) {
            list.add(i);
            i /= 10;
        }
        Collections.reverse(list);
        return list;
    }

- alisovenko October 03, 2014 | Flag Reply
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.

- GAURAV October 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sri October 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if the range is 190 to 200??

- Anonymous October 10, 2014 | Flag
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

- Suren October 08, 2014 | Flag Reply
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);

- SK October 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- SK October 12, 2014 | Flag
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);
}

- Anonymous August 29, 2016 | Flag Reply
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);
}

- Anonymous February 11, 2018 | Flag Reply
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);
}

- Anshik NIgam February 11, 2018 | Flag Reply
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);
}

- anshik124 February 11, 2018 | Flag Reply
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; 
}

- atinchauhan August 20, 2019 | 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