Apple Interview Question
Software EngineersCountry: United States
Solution in python
class node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def buildABCString(root, value):
res = ""
if root.value == value: return "Undefined"
node = root
while node != None:
if node.value == value: return res
elif value > node.value:
res += "1"
node = node.right
else:
res += "0"
node = node.left
return "Not Found"
public String bstNotation(int num) {
if (root == null) return "Not Found";
Node curr = root;
StringBuilder notation = new StringBuilder();
if(root.data==num)
return "Undefined";
while (curr != null) {
if (num<curr.data) {
curr = curr.left;
notation.append("0");
} else if (num>curr.data) {
curr = curr.right;
notation.append("1");
} else if (num==curr.data) {
return notation.toString();
}
}
return "Not Found";
}
Not exactly proud of it, but:
def BST : {
$$ : def(){
$.root = null
},
add_node : def(v){
new_node = {'v' : v , 'l' : null , 'r' : null }
if ( empty($.root) ){
$.root = new_node
return $.root
}
parent = $.root
current = v < parent.v ? parent.l : parent.r
while ( current != null ){
parent = current
current = v < parent.v ? parent.l : parent.r
}
if ( v < parent.v ){
parent.l = new_node
} else if ( parent.v < v ){
parent.r = new_node
}
},
find_abc : def(key){
current = $.root
path = ''
while ( current != null && current.v != key ){
if ( key < current.v ){
path += '0'
current = current.l
} else if ( current.v < key ){
path += '1'
current = current.r
}
}
(!empty(current) && current.v == key)? path : 'Not Found'
}
}
//now play
bst = new ( BST )
values = [5,2,8,3,6,9,1]
// add nodes
for ( v : values ){ bst.add_node(v) }
keys = [6, 1, 10, 2]
// print ABC ...
for ( v : keys ){ printf( '%s -> %s%n', v, bst.find_abc(v) ) }
public class ABCNotation
{
class Node<T extends Comparable<T>>
{
T data;
Node<T> lchild = null, rchild = null;
Node(T data)
{
this.data = data;
}
}
class Tree<T extends Comparable<T>>
{
Node<T> root = null;
public Node<T> insert(T data)
{
Node<T> newNode = new Node<T>(data);
if(root == null)
root = newNode;
else
insertAtNode(newNode, root);
return newNode;
}
private void insertAtNode(Node<T> node, Node<T> root)
{
switch (node.data.compareTo(root.data))
{
case 0:
case -1: if(root.lchild != null) insertAtNode(node, root.lchild); else root.lchild = node; break;
case 1: if(root.rchild != null) insertAtNode(node, root.rchild); else root.rchild = node; break;
}
}
}
class BoolRef
{
boolean value = false;
}
private String findABCNotation(Tree<Integer> tree, Integer num)
{
Node<Integer> root = tree.root;
if(root.data == num)
{
return("Undefined");
}
else
{
StringBuilder sb = new StringBuilder();
BoolRef isFound = new BoolRef();
findABCNotation(root, num, sb, isFound);
if(isFound.value)
return sb.toString();
else
return "NotFound";
}
}
private void findABCNotation(Node<Integer> node, Integer num, StringBuilder sb, BoolRef isFound)
{
switch (node.data.compareTo(num))
{
case 0: isFound.value = true; break;
case 1: if(node.lchild != null) {sb.append("0"); findABCNotation(node.lchild, num, sb, isFound);} else isFound.value =false; break;
case -1: if(node.rchild != null) {sb.append("1");findABCNotation(node.rchild, num, sb, isFound);} else isFound.value =false; break;
}
}
public static void main(String[] args)
{
ABCNotation abc = new ABCNotation();
ABCNotation.Tree<Integer> tree = abc.new Tree<>();
tree.insert(5);
tree.insert(2);
tree.insert(8);
tree.insert(3);
tree.insert(6);
tree.insert(9);
tree.insert(1);
System.out.println(abc.findABCNotation(tree, 6));
System.out.println(abc.findABCNotation(tree, 1));
System.out.println(abc.findABCNotation(tree, 10));
System.out.println(abc.findABCNotation(tree, 2));
}
}
package com.prep.tree;
public class BinaryTreeNotationABCQuestion {
Node root;
BinaryTreeNotationABCQuestion()
{
root = null;
}
public void insertRec(int data){
root = insertInTree(root,data);
}
public Node insertInTree(Node root,int data){
if (root == null){
root = new Node(data);
return root;
}
if(data<root.key){
root.left = insertInTree(root.left,data);
}
else if(data>root.key){
root.right = insertInTree(root.right,data);
}
return root;
}
public String findRec(int data){
String a = findAnotations(root,data);
return a;
}
public String findAnotations(Node root,int value){
//return 0 for left
// return 1 for right
//retrun Not Found for item not Found
// return Undefined is root is null
String annotation = "";
if(root==null){
//System.out.println("NotFound");
annotation = "NotFound";
return annotation;
}
if(root.key==value){
return annotation;
}
if(value<root.key){
annotation = annotation+"0";
String a = findAnotations(root.left,value);
if(a!="NotFound"){
annotation = annotation + a;
}
else {
annotation = a;
}
}
if(value>root.key){
annotation = annotation+"1";
String a = findAnotations(root.right,value);
if(a!="NotFound"){
annotation = annotation + a;
}
else {
annotation = a;
}
}
return annotation;
}
public static void main(String[] args)
{
BinaryTreeNotationABCQuestion tree = new BinaryTreeNotationABCQuestion();
// tree.root = new Node(100);
// tree.root.left = new Node(60);
// tree.root.right = new Node(150);
// tree.root.left.left = new Node(45);
// tree.root.left.right = new Node(75);
tree.insertRec(5);
tree.insertRec(2);
tree.insertRec(8);
tree.insertRec(3);
tree.insertRec(6);
tree.insertRec(9);
tree.insertRec(1);
String c = tree.findRec(1);
String d = tree.findRec(6);
String e = tree.findRec(10);
String f = tree.findRec(2);
System.out.println(c);
System.out.println(d);
System.out.println(e);
System.out.println(f);
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
{{ public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
}}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public void getABCNotation(Node n,int no,StringBuilder stb){
if(n == null){
stb.delete(0,stb.length());
stb.append("Not Found");
return;
}
if(n.value == no ){
return ;
}else{
if(n.value > no){
stb.append("0");
getABCNotation(n.left,no,stb);
}else {
stb.append("1");
getABCNotation(n.right,no,stb);
}
}
}
public static String navigate(Node root, int data) {
if (root == null) {
return "NotFound";
}
if (root.data == data) {
return "Undefined";
}
StringBuilder result = new StringBuilder();
while (root != null) {
if ( data < root.data) {
result.append("0");
root = root.left;
} else if ( data > root.data) {
result.append("1");
root = root.right;
} else {
return result.toString();
}
}
return "NotFound";
}
public static String navigate(Node root, int data) {
if (root == null) {
return "NotFound";
}
if (root.data == data) {
return "Undefined";
}
StringBuilder result = new StringBuilder();
while (root != null) {
if ( data < root.data) {
result.append("0");
root = root.left;
} else if ( data > root.data) {
result.append("1");
root = root.right;
} else {
return result.toString();
}
}
return "NotFound";
}
Python solution.
Add the following function to the Tree Class.
{{ def path_to_node(self, value):
result = [None]
def helper(node, string):
if node.value == value:
result[0] = string
return
if node.left:
helper(node.left, string + "0")
if node.right:
helper(node.right, string + "1")
helper(self.root, "")
return "NotFound" if not result[0] else result[0]
}}
{{
def path_to_node(self, value):
result = [None]
def helper(node, string):
if node.value == value:
result[0] = string
return
if node.left:
helper(node.left, string + "0")
if node.right:
helper(node.right, string + "1")
helper(self.root, "")
return "NotFound" if not result[0] else result[0]
}}
- Kush June 18, 2017