Linkedin Interview Question Senior Software Development Engineers
Country: United States
Interview Type: Phone Interview
I think G and F are supposed to belong to E but their whitespace was stripped down to one, making it look like they belong to D. That's the only way I can make sense of the examples anyway.
Slightly modified and compresses:
public class Deepest {
static class Node {
Node(Node parent, String x) {
this.parent = parent;this.x =x;
}
String x;
Node left;
Node right;
Node parent;
}
static Node getRoot(Node node) {
while(node.parent != null) {
node = node.parent;
}
return node;
}
static Node deep1(Node a1, Node a2) {
Node tmp = a1;
Node root = getRoot(tmp);
return common(root, a1.x, a2.x);
}
static Node common(Node root, String a, String b) {
if(root == null) return null;
if(root.x == a || root.x == b) {
return root;
}
Node lChild = common(root.left, a, b);
Node rChild = common(root.right, a, b);
if(lChild != null && rChild != null) {
return root;
}
return lChild != null ? lChild : rChild;
}
public static void main(String... args ) {
Node a = new Node(null, "A");
Node b = new Node(a, "B");
Node c = new Node(a, "C");
a.left = b;
a.right = c;
Node d = new Node(b, "D");
Node e = new Node(b, "E");
b.left = d;
b.right = e;
Node h = new Node(c, "H");
c.right = h;
Node g = new Node(d, "G");
Node f = new Node(d, "F");
d.right = f;
d.left = g;
System.out.println(deep1(d,f).x);
System.out.println(deep1(c,g).x);
System.out.println(deep1(e,b).x);
}
}
public class CommonAncestor {
static class Node {
Node(Node parent, Node right, Node left, String label) {
this.parent = parent;
this.right = right;
this.left = left;
this.label = label;
}
String label;
Node left;
Node right;
Node parent;
boolean isRoot() { return parent == null; }
public String toString() {
return label;
}
}
private static Node commonAncestor(Node n1, Node n2) {
Set<Node> n1Ancestors = collectAncestors(n1);
if (n1Ancestors.isEmpty()) return null;
// otherwise
Node n2A = n2.parent;
while(n2A != null) {
if (n1Ancestors.contains(n2A)) return n2A;
// otherwise
n2A = n2A.parent;
}
return null;
}
private static Set<Node> collectAncestors(Node n) {
Set<Node> result = new HashSet<Node>();
Node p = n.parent;
while(p != null) {
result.add(p);
p = p.parent;
}
return result;
}
public static void main(String[] args) {
Node G = new Node(null, null, null, "G");
Node F = new Node(null, null, null, "F");
Node E = new Node(null, null, null, "E");
Node H = new Node(null, null, null, "H");
Node D = new Node(null, G, F, "D"); G.parent = D; F.parent = D;
Node B = new Node(null, D, E, "B"); D.parent = B; E.parent = B;
Node C = new Node(null, null, H, "C"); H.parent = C;
Node A = new Node(null, B, C, "A"); B.parent = A; C.parent = A;
System.out.println(commonAncestor(D, F));
System.out.println(commonAncestor(C, G));
System.out.println(commonAncestor(E, B));
}
}
def parse_word(s):
new_string = ""
reverse_string = ""
convert_to_uppercase = True
for i in range(len(s)):
if s[i].isspace():
if i > 0:
if not s[i - 1].isspace():
if not convert_to_uppercase:
new_string += reverse_string
reverse_string = ""
convert_to_uppercase = not convert_to_uppercase
new_string += s[i]
else:
if convert_to_uppercase:
new_string += s[i].upper()
else:
reverse_string = s[i] + reverse_string
new_string += reverse_string
return new_string
print(parse_word("This is a test String!!"))
struct Node
{
Node *parent;
Node *left;
Node *right;
};
bool isNodeOnTree(Node *tree, Node *previous, Node *look)
{
if ((tree == nullptr) || (tree == previous))
{
return false;
}
if (tree == look)
{
return true;
}
return isNodeOnTree(tree->left, previous, look) ||
isNodeOnTree(tree->right, previous, look);
}
Node* commonAncestor(Node *one, Node *two)
{
while (one != nullptr)
{
if (isNodeOnTree(one->parent, one, two))
{
break;
}
one = one->parent;
}
return one;
}
int CommonAncestor(Node const *n, Node const *n1, Node const *n2, Node const **ancestor)
{
int count = 0;
if (n &&
n1 &&
n2 &&
n1 != n2 &&
*ancestor == NULL)
{
if (n == n1 ||
n == n2)
{
++count;
}
count += CommonAncestor(n->left_, n1, n2, ancestor);
if (count < 2) {
count += CommonAncestor(n->right_, n1, n2, ancestor);
}
if (count == 2) {
*ancestor = n;
count = 0;
}
}
return count;
}
class Node:
d = None
p = None
l = None
r = None
def __init__(self, d, p):
self.d = d
self.p = p
def display(node):
if node != None:
print(node.d)
display(node.l)
display(node.r)
def find_common_ancestor(node1, node2):
if node1 == node2:
return node1
if not node1.p or not node2.p:
return node1
lineage = { }
while node1:
if node1 == node2:
return node1
lineage[node1] = None
node1 = node1.p
while node2:
if node2 in lineage:
return node2
node2 = node2.p
raise Exception("Couldn't find a common ancestor.")
tree = Node("A", None)
tree.l = Node("B", tree)
tree.r = Node("C", tree)
tree.l.l = Node("D", tree.l)
tree.l.r = Node("E", tree.l)
tree.r.r = Node("H", tree.r)
tree.l.r.l = Node("G", tree.l.r)
tree.l.r.r = Node("F", tree.l.r)
print(find_common_ancestor(tree.l.l, tree.l.r.r).d)
print(find_common_ancestor(tree.r, tree.l.r.l).d)
print(find_common_ancestor(tree.l.r, tree.l).d)
Should be O(n) thanks to the usage of dict.
class Node:
d = None
p = None
l = None
r = None
def __init__(self, d, p):
self.d = d
self.p = p
def display(node):
if node != None:
print(node.d)
display(node.l)
display(node.r)
def find_common_ancestor(node1, node2):
if node1 == node2:
return node1
if not node1.p or not node2.p:
return node1
lineage = { }
while node1:
if node1 == node2:
return node1
lineage[node1] = None
node1 = node1.p
while node2:
if node2 in lineage:
return node2
node2 = node2.p
raise Exception("Couldn't find a common ancestor.")
tree = Node("A", None)
tree.l = Node("B", tree)
tree.r = Node("C", tree)
tree.l.l = Node("D", tree.l)
tree.l.r = Node("E", tree.l)
tree.r.r = Node("H", tree.r)
tree.l.r.l = Node("G", tree.l.r)
tree.l.r.r = Node("F", tree.l.r)
print(find_common_ancestor(tree.l.l, tree.l.r.r).d)
print(find_common_ancestor(tree.r, tree.l.r.l).d)
print(find_common_ancestor(tree.l.r, tree.l).d)
Should be O(n) thanks to the usage of dict.
- Weshall December 02, 2016public class Deepest { static class Node { Node(Node parent, String x) { this.parent = parent;this.x =x; } String x; Node left; Node right; Node parent; } static Node deep(Node a1, Node a2) { LinkedList<Node> first = new LinkedList<>(); while(a1 != null) { first.add(a1); a1 = a1.parent; } LinkedList<Node> second = new LinkedList<>(); while(a2 != null) { second.add(a2); a2 = a2.parent; } int c1 = first.size(); int c2 = second.size(); Node common = null; while(c1 > 0 && c2 > 0) { if(first.get(c1-1).x != second.get(c2-1).x ) { common = first.get(c1); break; } c2--; c1--; } if(common == null) { if(c1 == 0) { return first.get(1); } if(c2 == 0) { return second.get(1); } } return common; } public static void main(String... args ) { Node a = new Node(null, "A"); Node b = new Node(a, "B"); Node c = new Node(a, "C"); a.left = b; a.right = c; Node d = new Node(b, "D"); Node e = new Node(b, "E"); b.left = d; b.right = e; Node h = new Node(c, "H"); c.right = h; Node g = new Node(d, "G"); Node f = new Node(d, "F"); d.right = f; d.left = g; System.out.println(deep(d,f).x); System.out.println(deep(c,g).x); System.out.println(deep(e,b).x); } }