Q2) The is a binary tree, which has string values only on leaf nodes and all other nodes have empty values. Example is below.
When you sum all the leaf node values from left to right. the values will be : example: abcdefghblahblahblahblah etc.
Implement the below method that will give 'n'th character of the result.
Example: find the 5th character. here it will be 'e'.

(BLANK)
|---------------------------^---------------------------|
(BLANK) (BLANK)
|-------------^-------------| |-------------^-------------|
abc (BLANK) ijklmnopq rstuvwxyz
|------|
defgh

// Strucutre of the Node with below implemented methods.
class Node {
Node getLeft();
Node getRight();
boolean isBlank();
String getData();
}

Question

Q2) The is a binary tree, which has string values only on leaf nodes and all other nodes have empty values. Example is below.
When you sum all the leaf node values from left to right. the values will be : example: abcdefghblahblahblahblah etc.
Implement the below method that will give 'n'th character of the result.
Example: find the 5th character. here it will be 'e'.

                                                    (BLANK)                                                   
                            |---------------------------^---------------------------|                           
                         (BLANK)                                                 (BLANK)                       
              |-------------^-------------|                           |-------------^-------------|             
             abc                       (BLANK)                    ijklmnopq                    rstuvwxyz          
                                   |------|                                                                     
                                 defgh                  
								 
// Strucutre of the Node with below implemented methods.
class Node {
	Node getLeft();
	Node getRight();
	boolean isBlank();
	String getData();
}

Sigiloso · Accepted Answer

Solution:

// My approach
Character findNthChar(Node root, int n) {
	Stack stack = new Stack();
	stack.push(root);
	
	StringBuilder sb = new StringBuilder();
	while(!stack.isEmpty()) {
		Node node = stack.pop();
		if(!node.isBlank()) {
			sb.append(node.getData());
			if(sb.toString().length >= n) {
				return sb.toString().charAt(n - 1);
			}
		}
		stack.push(node.right);
		stack.push(node.left);
	}
	
	return null;
}

// Interviewer approach
int findNthChar(Node node, int n) {
	if(n <= 0) {
		return n;
	} else if(!node.isBlank()) {	
		return n - node.getData();
	}
	
	int updatedN = findNthChar(node.getLeft(), n);
	return findNthChar(node.getRight(), updatedN);
}

With the interviewer's approach, we only will get an integer in negative, zero or positive(when the sum of all leaf nodes are less than 'n').
Not sure what he was trying to do !!! Although the time complexity on both approaches is same.

Groupon

Pergunta de entrevista da empresa Groupon

Resposta da entrevista

Empresas seguidas

Buscas de vagas