Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
C++, DFS, O(n log n)
struct Node {
int x;
int y;
Node* child;
Node* sibling;
Node(int vx, int vy): child(NULL), sibling(NULL) {
x = vx;
y = vy;
}
};
struct WorkingNode {
Node* node;
int depth;
int state;
};
bool find(Node* root, int x, int y) {
stack<WorkingNode> stk;
WorkingNode w;
set<int> xs, ys;
w.node = root;
w.depth = 0;
w.state = 0;
stk.push(w);
while (!stk.empty()) {
w = stk.top();
stk.pop();
if (w.node == NULL) continue;
if (w.state == 0) {
if (w.node->x == x) {
if (ys.find(w.depth) != ys.end()) return true;
xs.insert(w.depth);
}
if (w.node->y == y) {
if (xs.find(w.depth) != xs.end()) return true;
ys.insert(w.depth);
}
w.state = 1;
stk.push(w);
w.node = w.node->child;
w.depth++;
w.state = 0;
stk.push(w);
} else {
w.node = w.node->sibling;
w.state = 0;
stk.push(w);
}
}
return false;
}
import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
public class Tree001 {
@Value // Lombok: produce all getters
@RequiredArgsConstructor
// Lombok: produce Node(x,y,Collection<Node>)
class Node {
public Node(int x, int y) {
this(x, y, new ArrayList<>());
}
private final int x, y;
private final Collection<Node> nodes;
}
public boolean find(Node root, int x, int y) {
return find(Arrays.asList(root), x, y);
}
public boolean find(Collection<Node> nodes, int x, int y) {
if (nodes.isEmpty()) return false;
Set<Integer> xSet = nodes.stream().map(Node::getX).collect(Collectors.toSet());
Set<Integer> ySet = nodes.stream().map(Node::getY).collect(Collectors.toSet());
if (xSet.contains(x) && ySet.contains(y)) return true;
return find(nodes.stream().flatMap(n -> n.getNodes().stream()).collect(Collectors.toList()), x, y);
}
@Test
public void test() {
Node root = new Node(1, 120, Arrays.asList(
new Node(5, 15, Arrays.asList(
new Node(35, 40),
new Node(45, 50),
new Node(55, 65))),
new Node(30, 70, Arrays.asList(
new Node(90, 100))),
new Node(80, 110)));
assertThat(find(root, 45, 100), is(Boolean.TRUE));
assertThat(find(root, 30, 100), is(Boolean.FALSE));
assertThat(find(root, 30, 70), is(Boolean.TRUE));
assertThat(find(root, 70, 30), is(Boolean.FALSE));
}
}
import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
public class Tree001 {
@Value // Lombok: produce all getters
@RequiredArgsConstructor
// Lombok: produce Node(x,y,Collection<Node>)
class Node {
public Node(int x, int y) {
this(x, y, new ArrayList<>());
}
private final int x, y;
private final Collection<Node> nodes;
}
public boolean find(Node root, int x, int y) {
return find(Arrays.asList(root), x, y);
}
public boolean find(Collection<Node> nodes, int x, int y) {
if (nodes.isEmpty()) return false;
Set<Integer> xSet = nodes.stream().map(Node::getX).collect(Collectors.toSet());
Set<Integer> ySet = nodes.stream().map(Node::getY).collect(Collectors.toSet());
if (xSet.contains(x) && ySet.contains(y)) return true;
return find(nodes.stream().flatMap(n -> n.getNodes().stream()).collect(Collectors.toList()), x, y);
}
@Test
public void test() {
Node root = new Node(1, 120, Arrays.asList(
new Node(5, 15, Arrays.asList(
new Node(35, 40),
new Node(45, 50),
new Node(55, 65))),
new Node(30, 70, Arrays.asList(
new Node(90, 100))),
new Node(80, 110)));
assertThat(find(root, 45, 100), is(Boolean.TRUE));
assertThat(find(root, 30, 100), is(Boolean.FALSE));
assertThat(find(root, 30, 70), is(Boolean.TRUE));
assertThat(find(root, 70, 30), is(Boolean.FALSE));
}
}
BFS Java Elegant solution
import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
public class Tree001 {
@Value // Lombok: produce all getters
@RequiredArgsConstructor
// Lombok: produce Node(x,y,Collection<Node>)
class Node {
public Node(int x, int y) {
this(x, y, new ArrayList<>());
}
private final int x, y;
private final Collection<Node> nodes;
}
public boolean find(Node root, int x, int y) {
return find(Arrays.asList(root), x, y);
}
public boolean find(Collection<Node> nodes, int x, int y) {
if (nodes.isEmpty()) return false;
Set<Integer> xSet = nodes.stream().map(Node::getX).collect(Collectors.toSet());
Set<Integer> ySet = nodes.stream().map(Node::getY).collect(Collectors.toSet());
if (xSet.contains(x) && ySet.contains(y)) return true;
return find(nodes.stream().flatMap(n -> n.getNodes().stream()).collect(Collectors.toList()), x, y);
}
@Test
public void test() {
Node root = new Node(1, 120, Arrays.asList(
new Node(5, 15, Arrays.asList(
new Node(35, 40),
new Node(45, 50),
new Node(55, 65))),
new Node(30, 70, Arrays.asList(
new Node(90, 100))),
new Node(80, 110)));
assertThat(find(root, 45, 100), is(Boolean.TRUE));
assertThat(find(root, 30, 100), is(Boolean.FALSE));
assertThat(find(root, 30, 70), is(Boolean.TRUE));
assertThat(find(root, 70, 30), is(Boolean.FALSE));
}
}
public class Node
{
int x;
int y;
Node[]children;
}
public boolean find(Node root, int x, int y)
{
if(root == null)
{
return false;
}
int queueCount = 1;
Queueue<Node> childQueue = new LinkedList<Node>();
childQueue.add(root);
while(childQueue.peek()!= null)
{
bool xFound = false;
bool yFound = false;
int newQueueCount = 0;
for(int i = 0; i< queueCount; i++)
{
Node n = childQueue.poll();
if(!xFound)
{
xFound = (n.x == x);
}
else if(!yFound)
{
yFound = (n.y == y);
}
else if(xFound && yFound)
{
return true;
}
for(int j=0; j<n.children.length; j++)
{
newQueueCount++;
childQueue.add(n.children[i]);
}
}
queueCount = newQueueCount;
}
return false;
}
class TreeLevelPrint
{
treeNode root;
int[] left, right; // vaules which are left child are stored in left and right child in right level wise
int lid, rid;
public TreeLevelPrint()
{
treeNode root = null;
MinDiffBst m = new MinDiffBst(ref root);// this creates the tree and returns the root node in rrot variable
this.root = root;
printOrder(root);
}
void printOrder(treeNode root)
{
int i = 0;
int level;
int leftVal, rightVal;
int hiegt = height(root);
Console.WriteLine("Enter left Val :");
leftVal = Int32.Parse(Console.ReadLine()); // value of node which is to found as left child
Console.WriteLine("Enter right Val :");
rightVal = Int32.Parse(Console.ReadLine()); // value of node which is to found as right child
//This loop Traverses the elements of tree level wise
for (level = 1 ; level <= hiegt ; level++)
{
left = new int[(int)Math.Pow(2,level - 2)];
right = new int[(int)Math.Pow(2, level - 2)];
while (i < left.Length)
{
left[i] = 0;
i++;
}
i = 0;
while (i < right.Length)
{
right[i] = 0;
i++;
}
lid = 0;
rid = 0;
printLevel(root, level,"");
if (level > 1)
{
Boolean flag = false;
for (int j = 0; j < left.Length; j++)
{
if (left[j] == leftVal)
flag = true;
}
if (flag == true)
{
flag = false;
for (int j = 0; j < left.Length; j++)
{
if (right [j] == rightVal )
flag = true;
}
if (flag == true)
{
Console.WriteLine("Found at Level " + level);
break;
}
else if (level == hiegt)
Console.WriteLine("Sorry Not Found");
}
else if (level == hiegt )
Console.WriteLine("Sorry Not Found");
}
}
}
void printLevel(treeNode root, int level, string side)
{
if (root == null)
return ;
if (level == 1)
{
if (side == "L")
{
left[lid] = root.value;
lid++;
}
else if (side =="R")
{
right[rid ] = root.value;
rid++;
}
}
else if (level > 1)
{
printLevel(root.left, level - 1,"L");
printLevel(root.right, level - 1,"R");
}
}
int height(treeNode root)
{
if (root == null)
return 0;
else
{
int lht = height(root.left );
int rht = height(root.right);
if (lht > rht)
return lht + 1;
else
return rht + 1;
}
}
}
public class treeNode
{
public int value = 0;
public treeNode left, right;
}
class TreeLevelPrint
{
treeNode root;
int[] left, right; // vaules which are left child are stored in left and right child in right (level wise)
int lid, rid;
public TreeLevelPrint()
{
treeNode root = null;
MinDiffBst m = new MinDiffBst(ref root);// this creates the tree and returns the root node in rrot variable
this.root = root;
printOrder(root);
}
void printOrder(treeNode root)
{
int i = 0;
int level;
int leftVal, rightVal;
int hiegt = height(root);
Console.WriteLine("Enter left Val :");
leftVal = Int32.Parse(Console.ReadLine()); // value of node which is to found as left child
Console.WriteLine("Enter right Val :");
rightVal = Int32.Parse(Console.ReadLine()); // value of node which is to found as right child
//This loop Traverses the elements of tree level wise
for (level = 1 ; level <= hiegt ; level++)
{
left = new int[(int)Math.Pow(2,level - 2)];
right = new int[(int)Math.Pow(2, level - 2)];
while (i < left.Length)
{
left[i] = 0;
i++;
}
i = 0;
while (i < right.Length)
{
right[i] = 0;
i++;
}
lid = 0;
rid = 0;
printLevel(root, level,"");
if (level > 1)
{
Boolean flag = false;
for (int j = 0; j < left.Length; j++)
{
if (left[j] == leftVal)
flag = true;
}
if (flag == true)
{
flag = false;
for (int j = 0; j < left.Length; j++)
{
if (right [j] == rightVal )
flag = true;
}
if (flag == true)
{
Console.WriteLine("Found at Level " + level);
break;
}
else if (level == hiegt)
Console.WriteLine("Sorry Not Found");
}
else if (level == hiegt )
Console.WriteLine("Sorry Not Found");
}
}
}
void printLevel(treeNode root, int level, string side)
{
if (root == null)
return ;
if (level == 1)
{
if (side == "L")
{
left[lid] = root.value;
lid++;
}
else if (side =="R")
{
right[rid ] = root.value;
rid++;
}
}
else if (level > 1)
{
printLevel(root.left, level - 1,"L");
printLevel(root.right, level - 1,"R");
}
}
int height(treeNode root)
{
if (root == null)
return 0;
else
{
int lht = height(root.left );
int rht = height(root.right);
if (lht > rht)
return lht + 1;
else
return rht + 1;
}
}
static void Main(string[] args)
{
new TreeLevelPrint();
Console.Read();
}
}
Breath Search Traversal, without recursion. C# implementation
public bool Find(TreeNode root, int x, int y)
{
if (root == null)
return false;
var current = new List<TreeNode>();
current.Add(root);
while (current.Count > 0)
{
bool foundX = false;
bool foundY = false;
var next = new List<TreeNode>();
foreach(var node in current)
{
foundX |= (node.X == x);
foundY |= (node.Y == y);
if (foundX && foundY)
return true;
foreach (var child in node.Child)
next.Add(child);
}
current = next;
}
return false;
}
import collections
class TreeNode(object):
def __init__(self,x,y):
self.x = x
self.y = y
self.left = None
self.right = None
class Solution(object):
def sameLevel(self,root,x,y):
if not root:
return False
queue = collections.deque([(root,0)])
level = 0
sameLevel = [False,False]
while queue:
node = queue.popleft()
node[1]!=level:
level+=1
sameLevel = [False,False]
if node[0].left:
queue.append((node[0].left,level+1))
if node[0].right:
queue.append((node[0].right,level+1))
if node[0].x == x:
sameLevel[0] = True
if node[0].y == y:
sameLevel[1] = True
if sameLevel == [True,True]:
return True
return False
class Tree:
def __init__(data, children = []):
this.data = data
this.child = children
def pair_tree(root, x, y):
if root:
stack = [root]
while (stack is not []):
next_stack = []
found_x, found_y = False, False
for node in stack:
new_stack += node.children
found_x = node.x == x or found_x
found_y = node.y == y or found_y
if (found_x and found_y):
return True
stack = new_stack
return False
#include <iostream>
#include <queue>
using namespace std;
class node{
public :
int data;
node* left;
node* right;
node(int data, node* left, node* right){
this->data = data;
this->left = left;
this->right = right;
}
};
class tree{
public :
node* insert(int x, node* tree){
if(tree == NULL){
tree = new node(x, NULL, NULL);
}else if(tree->data > x){
tree->left = insert(x, tree->left);
}else if(tree->data < x){
tree->right = insert(x, tree->right);
}
return tree;
}
bool find1(node* root, int x, int y){
if(root == NULL){
return false;
}
if(root->left == NULL && root->right == NULL){
return true;
}
queue<node*> q;
q.push(root);
int length;
while(true){
length = q.size();
if(length == 0){
break;
}
int i=0;
bool found1 = false, found2 = false;
while(i < length){
node* curr = q.front();
if(curr->data == x){
found1 = true;
}
if(curr->data == y){
found2 = true;
}
if(curr->left != NULL){
q.push(curr->left);
}
if(curr->right != NULL){
q.push(curr->right);
}
q.pop();
i++;
}
if(found1 && found2){
return true;
}
}
return false;
}
};
int main()
{
node* root;
tree t;
root = t.insert(6, root);
root = t.insert(3, root);
root = t.insert(13, root);
root = t.insert(10, root);
cout<<t.find1(root, 6, 13)<<endl;
return 0;
}
My method is based on BFS using Queue. It is based on calculating the number of nodes in the next level, decrementing it and we detect that the level is changed once the currentLevelCounter reaches 0.
public boolean find(Node n,int x, int y){
boolean found = false;
int currentLevelCount=1;
int nextLevelCount=0;
Queue toBeDiscovered=new Queue();
toBeDiscovered.enqueue(n);
ArrayList<Node> levelNodes=new ArrayList<Node>();
while (toBeDiscovered.first!=null){
Node current=toBeDiscovered.dequeue();
levelNodes.add(current);
currentLevelCount--;
nextLevelCount=nextLevelCount+current.children.size();
for (int i=0;i<current.children.size();i++){
toBeDiscovered.enqueue(current.children.get(i));
}
if (currentLevelCount==0){
found=false;
currentLevelCount=nextLevelCount;
nextLevelCount=0;
for (int i=0;i<levelNodes.size();i++){
if (levelNodes.get(i).x==x)
found=true;
if (levelNodes.get(i).y==y && found==true)
return true;
}
levelNodes=new ArrayList<Node>();
}
}
return false;
}
}
class Node(object):
def __init__(self, parent, children, x, y):
self.parent = parent
self.children = children
self.x = x
self.y = y
def find(root, x, y):
if not root.children:
return False
children = root.children
while children:
if scan_level(children, x, y):
return True
new_children = []
for node in children:
new_children += node.children
children = new_children
return False
def scan_level(nodes, x, y):
has_x, has_y = False, False
for node in nodes:
if node.x == x:
has_x = True
if node.y == y:
has_y = True
if has_x and has_y:
return True
return False
if __name__ == "__main__":
root = Node(None, None, 1, 120)
n10 = Node(root, None, 5, 15)
n11 = Node(root, None, 30, 70)
n12 = Node(root, [], 80, 110)
n20 = Node(n10, [], 35, 40)
n21 = Node(n10, [], 45, 50)
n22 = Node(n10, [], 55, 65)
n23 = Node(n11, [], 90, 100)
# Add in children
root.children = [n10, n11, n12]
n10.children = [n20, n21, n22]
n11.children = [n23]
assert find(root, 45, 100) == True
assert find(root, 30, 100) == False
assert find(root, 30, 70) == True
assert find(root, 70, 30) == False
with JavaScript
find(root, x, y)
{
root.level = 0;
var queue = [root];
var currentLevel = -1;
var foundX, foundY;
do
{
var node = queue.shift();
if (node.level > currentLevel) {
currentLevel = node.level;
foundX = false;
foundY = false;
}
if (node.x === x) {
foundX = true;
}
if (node.y === y) {
foundY = true;
}
if (foundX && foundY) {
return true;
}
if (node.left) {
node.right.level = node.level + 1;
queue.push(node.left);
}
if (node.right) {
node.right.level = node.level + 1;
queue.push(node.right)
}
} while (queue.length > 0)
return false;
}
find(root, x, y)
{
root.level = 0;
var queue = [root];
var currentLevel = -1;
var foundX, foundY;
do
{
var node = queue.shift();
if (node.level > currentLevel) {
currentLevel = node.level;
foundX = false;
foundY = false;
}
if (node.x === x) {
foundX = true;
}
if (node.y === y) {
foundY = true;
}
if (foundX && foundY) {
return true;
}
if (node.left) {
node.right.level = node.level + 1;
queue.push(node.left);
}
if (node.right) {
node.right.level = node.level + 1;
queue.push(node.right)
}
} while (queue.length > 0)
return false;
}
function find(root, x, y)
{
root.level = 0;
var queue = [root];
var currentLevel = -1;
var foundX, foundY;
do
{
var node = queue.shift();
if (node.level > currentLevel) {
currentLevel = node.level;
foundX = false;
foundY = false;
}
if (node.x === x) {
foundX = true;
}
if (node.y === y) {
foundY = true;
}
if (foundX && foundY) {
return true;
}
if (node.left) {
node.right.level = node.level + 1;
queue.push(node.left);
}
if (node.right) {
node.right.level = node.level + 1;
queue.push(node.right)
}
} while (queue.length > 0)
return false;
}
public class SolutionSameLevelXYTree {
public static boolean find(Node root, int x, int y) {
Map<Integer, Integer> allLevelsX = new HashMap<>();
Map<Integer, Integer> allLevelsY = new HashMap<>();
findAllLevelsOccurenceOfVal(root, x, 0, true, allLevelsX);
findAllLevelsOccurenceOfVal(root, y, 0, false, allLevelsY);
if (allLevelsX.isEmpty() || allLevelsY.isEmpty()) {
return false;
}
for (Entry<Integer, Integer> lX: allLevelsX.entrySet()) {
if (allLevelsY.get(lX.getKey()) != null) {
return true;
}
}
return false;
}
public static void findAllLevelsOccurenceOfVal(Node root, int v, int l, boolean isX, Map<Integer, Integer> levelCount) {
if (root == null) {
return;
}
if (isX && root.x == v || !isX && root.y == v) {
if (levelCount.get(l) == null) {
levelCount.put(l, 1);
} else {
int count = levelCount.get(l);
levelCount.put(l, count + 1);
}
}
if (root.children != null) {
for (Node n : root.children) {
findAllLevelsOccurenceOfVal(n, v, l+1, isX, levelCount);
}
}
}
public static void testSolution() {
Node n1 = new Node(1, 120);
Node n2 = new Node(5, 15);
Node n3 = new Node(30, 70);
Node n4 = new Node(80, 110);
Node n5 = new Node(35, 40);
Node n6 = new Node(45, 50);
Node n7 = new Node(55, 65);
Node n8 = new Node(90, 100);
List<Node> n1List = new ArrayList<>();
n1List.add(n2);
n1List.add(n3);
n1List.add(n4);
n1.children = n1List;
List<Node> n2List = new ArrayList<>();
n2List.add(n5);
n2List.add(n6);
n2.children = n2List;
List<Node> n3List = new ArrayList<>();
n3List.add(n7);
n3.children = n3List;
List<Node> n4List = new ArrayList<>();
n4List.add(n8);
n4.children = n4List;
System.out.println(find(n1, 45, 100));
System.out.println(find(n1, 30, 100));
System.out.println(find(n1, 30, 70));
System.out.println(find(n1, 70, 30));
}
}
class Node {
int x;
int y;
List<Node> children;
public Node(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
/**
* Created by nileshagrawal on 5/22/16.
* BFS on the queue elements
*/
class TreeNode{
private int x;
private int y;
private List<TreeNode> childNodeList;
public TreeNode(int x, int y, List<TreeNode> childNodeList) {
this.x = x;
this.y = y;
this.childNodeList = childNodeList;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public List<TreeNode> getChildNodeList() {
return childNodeList;
}
public void setChildNodeList(List<TreeNode> childNodeList) {
this.childNodeList = childNodeList;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
TreeNode treeNode = (TreeNode) o;
if (x != treeNode.x) return false;
if (y != treeNode.y) return false;
return childNodeList != null ? childNodeList.equals(treeNode.childNodeList) : treeNode.childNodeList == null;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
result = 31 * result + (childNodeList != null ? childNodeList.hashCode() : 0);
return result;
}
}
public class FindingElementWithTwoValues {
public boolean findTheValue(TreeNode root,TreeNode givenNode){
if(root == null){
return false;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
queue.add(null);
boolean leftFound = false;
boolean rightFound = false;
while (!queue.isEmpty()){
TreeNode tempNode = queue.poll();
if(tempNode == null){
System.out.print("end of level.");
if(leftFound && rightFound){
return true;
}else{
leftFound = false;
rightFound = false;
queue.add(null);
}
}else{
for(TreeNode childNode:tempNode.getChildNodeList()){
if(childNode!=null){
queue.add(childNode);
if(childNode.getX() == givenNode.getX()){
leftFound = true;
}
if(childNode.getY() == givenNode.getY()){
rightFound = true;
}
}
}
}
}
return false;
}
}
package test;
public class GoogleFindTwoNodesTree {
Node root;
int size = 0;
private class Node {
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name) {
this.key = key;
this.name = name;
}
public String toString() {
return name + " has the key " + key;
}
}
public void addNode(int key, String name){
Node node = root;
Node newNode = new Node(key, name);
// If there is no root this becomes root
if (root == null) {
root = newNode;
size++;
} else {
while (true){
if (node.key > newNode.key){
if (node.leftChild !=null){
node = node.leftChild;
}else{
node.leftChild = newNode;
size++;
return;
}
}else{
if (node.rightChild !=null){
node = node.rightChild;
}
else{
node.rightChild = newNode;
size++;
return;
}
}
}
}
}
public boolean FindDeephNodesIfExists(Node root, int keyOne, int keyTwo){
int nodeOne = findTwoNodes(root, keyOne, true);
int nodeTwo = findTwoNodes(root, keyTwo, false);
return nodeOne==nodeTwo?true:false;
}
public int findTwoNodes (Node root, int key, boolean isLeftNodeToFind) {
Node node = root;
int depth = -1;
boolean isRigth = false;
if (root == null) {
return -1;
} else {
while (node.key != key){
if (node.key > key){
node = node.leftChild;
isRigth = false;
}else{
node = node.rightChild;
isRigth = true;
}
if (node == null)
return -1;
++depth;
}
if (isRigth && isLeftNodeToFind){
depth = -1;
}
return ++depth;
}
}
public Node findNode(int key) {
Node node = root;
if (root == null) {
return null;
} else {
while (node.key != key){
if (node.key > key){
node = node.leftChild;
}else{
node = node.rightChild;
}
if (node == null)
return null;
}
return node;
}
}
public static void main(String[] args) {
GoogleFindTwoNodesTree theTree = new GoogleFindTwoNodesTree();
theTree.addNode(50, "Boss");
theTree.addNode(25, "Vice President");
theTree.addNode(15, "Office Manager");
theTree.addNode(30, "Secretary");
theTree.addNode(75, "Sales Manager");
theTree.addNode(85, "Salesman 1");
// System.out.println(theTree.findNode(75));
Node rootForSearch = theTree.findNode(50);
System.out.println(theTree.FindDeephNodesIfExists(rootForSearch, 25, 75));
}
}
This is an Objective-C solution, basically, iterate by level using a queue and store in a dictionary the level of the X and Y value found and then check if those has the same level
-(BOOL)find:(TreeNode *)root andX:(int)x andY:(int)y{
if(root == nil){
return false;
}
NSMutableArray *queue = [NSMutableArray new];
NSMutableDictionary *dic = [NSMutableDictionary new];
[queue addObject:root];
while ([queue count] > 0) {
root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
NSLog(@"\n\n%i\nLEVEL: %i\n", root.value, root.level);
if(root.value == x){
[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"X"];
}
if(root.value == y){
[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"Y"];
}
if([dic count] == 2){
if([[dic objectForKey:@"X"] intValue] == [[dic objectForKey:@"Y"] intValue]){
return true;
}
}
if(root.left != nil){
root.left.level = root.level + 1;
[queue addObject:root.left];
}
if(root.rigth != nil){
root.rigth.level = root.level + 1;
[queue addObject:root.rigth];
}
}
return false;
}
This is an Objective-C solution, basically, iterate by level using a queue and store in a dictionary the level of the X and Y value found and then check if those are in the same level
@interface TreeNode : NSObject
@property (nonatomic, assign) int value;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *rigth;
@property (nonatomic, assign) int level;
-(instancetype)initWithValue:(int)value;
@end
-(BOOL)find:(TreeNode *)root andX:(int)x andY:(int)y{
if(root == nil){
return false;
}
NSMutableArray *queue = [NSMutableArray new];
NSMutableDictionary *dic = [NSMutableDictionary new];
[queue addObject:root];
while ([queue count] > 0) {
root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
NSLog(@"\n\n%i\nLEVEL: %i\n", root.value, root.level);
if(root.value == x){
[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"X"];
}
if(root.value == y){
[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"Y"];
}
if([dic count] == 2){
if([[dic objectForKey:@"X"] intValue] == [[dic objectForKey:@"Y"] intValue]){
return true;
}
}
if(root.left != nil){
root.left.level = root.level + 1;
[queue addObject:root.left];
}
if(root.rigth != nil){
root.rigth.level = root.level + 1;
[queue addObject:root.rigth];
}
}
return false;
}
Level tree traversal and check if you can find x and y in current level in specified order.
- EPavlova March 08, 2016Could you tell more for what position is this question - SDE1, SDE2 ...?