Linkedin Interview Question for Testing / Quality Assurances

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

O(n) solution using a map [O(n) memory]

public Node buildTree(List<Relation> data)
{
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
Node root = null;

for(Relation r: data) {
Node parent, child;

if ((child = map.get(r.child)) == null) {
System.out.println("Here");
child = new Node();
child.data = r.child;
map.put(r.child, child);
}
if (r.parent == 0) {
root = child;
continue;
}
if ((parent = map.get(r.parent)) == null) {
parent = new Node();
parent.data = r.parent;
map.put(r.parent, parent);
}

if (r.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

this is the best solution.

Comment hidden because of low score. Click to expand.
1
of 1 vote

One simple approach to this problem can be: we know the ROOT of the tree is the one where the parent is null in the list. Once we figure out the parent, we can iteratively figure out its children and their children- by looping over the complete list and finding out the ones that point the current node as its parent. To build tree efficiently, we can use queue to keep track of the tree built till then. The running time would be O(n^2), with constant space (not really, we are keeping a queue as well)

``````public static Node buildTree(List<Relation> data){
if(data==null) return new Node();
Node root=new Node();
int children=0;
for(int i=0;i<data.size();i++){
Relation x=data.get(i);
if(x.parent==null){
root=new Node(x.child,null,null);
break;
}
}
if(root==null) return root;
while(!q.isEmpty()){
Node x=q.poll();
for(int i=0;i<data.size();i++){
Relation y=data.get(i);
if(y.parent==x.id){
Node n=new Node(y.child,null,null);
if(y.isLeft)
x.left=n;
else x.right=n;
children++;
if(children==2){
children=0;
break;
}
}
}
}
return root;
}``````

Another way to approach this problem for a better running time could be by using a HashMap. We can hash the list with key as the parent and value as a list of its children. And then iteratively generating the tree. This solution would be O(n) time complexity and O(n) space complexity.

``````public static Node buildTree(List<Relation> data){
if(data==null) return new Node();
Node root=new Node();
HashMap<Integer,ArrayList<Relation>> tree = new HashMap<Integer,ArrayList<Relation>>();
for(Relation d:data){
if(d.parent==null)
root=new Node(d.child,null,null);
else{
if(tree.containsKey(d.parent)){
ArrayList<Relation> value=tree.get(d.parent);
} else {
ArrayList<Relation> value = new ArrayList<Relation>();
tree.put(d.parent,value);
}
}
}
if(root==null) return root;
while(!q.isEmpty()){
Node x = q.poll();
if(tree.containsKey(x.id)){
ArrayList<Relation> value=tree.get(x.id);
for(Relation v:value){
Node child = new Node(v.child,null,null);
if(v.isLeft)
x.left=child;
else x.right=child;
}
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static Node buildTree(List<Relation> data) {
if (data == null || data.isEmpty()) {
return null;
}

Node root = null;
Map<Integer, Node> mapNode = new HashMap<Integer, Node>();
for (Relation relation : data) {
if (relation.parent == null) {
if (mapNode.containsKey(relation.child)) {
root = mapNode.get(relation.child);
} else {
root = new Node(relation.child);
mapNode.put(root.val, root);
}
continue;
}

Node parent;
if (mapNode.containsKey(relation.parent)) {
parent = mapNode.get(relation.parent);
} else {
parent = new Node(relation.parent);
mapNode.put(parent.val, parent);
}
}

return root;
}

private static void addChild(Map<Integer, Node> mapNode, Relation relation, Node parent) {
Node childNode = mapNode.containsKey(relation.child) ? mapNode.get(relation.child) : new Node(relation.child);
if (relation.isLeft) {
parent.left = childNode;
} else {
parent.right = childNode;
}
mapNode.put(childNode.val, childNode);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

We know the head will have a null parent. Now that we have a head, we will know the 2nd level of the tree will be the nodes that have the head as a parent, so organize the tree by how those nodes are organized.

You can keep a queue- put 50 into it first, then search the list for nodes that attach to 50. add those to the queue. dequeue 50. search the list for nodes that attach to the nodes in the queue, add to the queue and dequeue the lists you found nodes for. continue this process until both the list and the queue are empty.

Some very loose pseudocode:

``````buildTree(list) {

Queue treeQueue = ;// initializeQueue

for (info in list) {

head = node who's parent is null;
}

Node current;
while(list != empty) {

current = treeQueue.dequeue();

for (node in list) {

if (node's parent is current) {

enqueue(node);

if (node.isLeft) {	current.left = node;} else {	current.right = node}
}
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a C# solution written as an xUnit test. Idea is to iterate once over the relations and then keep all Nodes in a dictionary and then stitch them together as we iterate over the relations.

``````using System.Collections.Generic;
using System.Diagnostics;
using Xunit;
namespace CareerCupSolutions {
public class BinaryTree_20150318 {
public class Relation {
public Relation(int child, int parent, bool isLeft) {
Parent = parent;
Child = child;
IsLeft = isLeft;
}
public int Parent { get; private set; }
public int Child { get; private set; }
public bool IsLeft { get; private set; }
}

public class Node {
public Node(int id, Node left, Node right) {
Id = id;
Left = left;
Right = right;
}
public int Id { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}

public Node BuildTree(List<Relation> data) {
var _nodes = new Dictionary<int, Node>();
Node root = null;
foreach (var relation in data) {
Node parentNode;
Node childNode;
if (!_nodes.TryGetValue(relation.Parent, out parentNode)) _nodes[relation.Parent] = parentNode = new Node(relation.Parent, null, null);
if (!_nodes.TryGetValue(relation.Child, out childNode)) _nodes[relation.Child] = childNode = new Node(relation.Child, null, null); ;
if (relation.IsLeft) {
Debug.Assert(parentNode.Left == null);
parentNode.Left = childNode;
}
else {
Debug.Assert(parentNode.Right == null);
parentNode.Right = childNode;
}
if (relation.Parent == 0) root = _nodes[relation.Child];
}
return root;
}

[Fact]
public void Test() {
var list = new List<Relation> {
new Relation(15, 20, true),
new Relation(19, 80, true),
new Relation(17, 20, false),
new Relation(16, 80, false),
new Relation(80, 50, false),
new Relation(50, 0, false),
new Relation(20, 50, true),
};
var root = BuildTree(list);
Assert.Equal(50, root.Id);
Assert.Equal(20, root.Left.Id);
Assert.Equal(80, root.Right.Id);
Assert.Equal(15, root.Left.Left.Id);
Assert.Equal(17, root.Left.Right.Id);
Assert.Equal(19, root.Right.Left.Id);
Assert.Equal(16, root.Right.Right.Id);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a C# solution as an xUnit test which iterate over the relations, keeps nodes in a dictinary and stitches them together according to the relations:

``````using System.Collections.Generic;
using System.Diagnostics;
using Xunit;
namespace CareerCupSolutions {
public class BinaryTree_20150318 {
public class Relation {
public Relation(int child, int parent, bool isLeft) {
Parent = parent;
Child = child;
IsLeft = isLeft;
}
public int Parent { get; private set; }
public int Child { get; private set; }
public bool IsLeft { get; private set; }
}

public class Node {
public Node(int id, Node left, Node right) {
Id = id;
Left = left;
Right = right;
}
public int Id { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}

public Node BuildTree(List<Relation> data) {
var _nodes = new Dictionary<int, Node>();
Node root = null;
foreach (var relation in data) {
Node parentNode;
Node childNode;
if (!_nodes.TryGetValue(relation.Parent, out parentNode)) _nodes[relation.Parent] = parentNode = new Node(relation.Parent, null, null);
if (!_nodes.TryGetValue(relation.Child, out childNode)) _nodes[relation.Child] = childNode = new Node(relation.Child, null, null); ;
if (relation.IsLeft) {
Debug.Assert(parentNode.Left == null);
parentNode.Left = childNode;
}
else {
Debug.Assert(parentNode.Right == null);
parentNode.Right = childNode;
}
if (relation.Parent == 0) root = _nodes[relation.Child];
}
return root;
}

[Fact]
public void Test() {
var list = new List<Relation> {
new Relation(15, 20, true),
new Relation(19, 80, true),
new Relation(17, 20, false),
new Relation(16, 80, false),
new Relation(80, 50, false),
new Relation(50, 0, false),
new Relation(20, 50, true),
};
var root = BuildTree(list);
Assert.Equal(50, root.Id);
Assert.Equal(20, root.Left.Id);
Assert.Equal(80, root.Right.Id);
Assert.Equal(15, root.Left.Left.Id);
Assert.Equal(17, root.Left.Right.Id);
Assert.Equal(19, root.Right.Left.Id);
Assert.Equal(16, root.Right.Right.Id);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Each node is either a left child or a right child. Make two hashmaps, one for lefts and one for rights; key is the parent id, and value is the child id.
Figure out which one the head is while you're adding all of the relations (O(n)). Then, starting with the head, do a DFS with the help of a stack and figure out the children accordingly!

``````public LINode buildTree(List<Relation> data) {
HashMap<Integer, Integer> leftMap = new HashMap<>();
HashMap<Integer, Integer> rightMap = new HashMap<>();
for (Relation i:data) {
if (i._isLeft) {
leftMap.put(i._parent, i._child);
} else {
rightMap.put(i._parent, i._child);
}
}

java.util.Stack<LINode> stack = new Stack<>();
while (!stack.empty()) {
LINode tracker = stack.pop();
if (rightMap.containsKey(tracker._id)) {
tracker._right = new LINode();
tracker._right._id = rightMap.get(tracker._id);
stack.push(tracker._right);
}
if (leftMap.containsKey(tracker._id)) {
tracker._left = new LINode();
tracker._left._id = leftMap.get(tracker._id);
stack.push(tracker._left);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````"""
20: [15, None]
15: [None, 7]
7: [1, 2]
1: [None, None]
2: [None, None]
Root => 20
"""

def print_tree(node):
if node is not None:
print_tree(node.left)
print node.value
print_tree(node.right)

def get_binary_tree():
data = [
(50, None, False),
(15, 50, False),
]
parent_to_children_map = {}
root = None
for (child, parent, is_left) in data:
if parent is None:
root = child
else:
if parent not in parent_to_children_map:
parent_to_children_map[parent] = [None, None]
if is_left:
parent_to_children_map[parent][0] = child
else:
parent_to_children_map[parent][1] = child
tree = create_tree(root, parent_to_children_map)
print_tree(tree)

class Node(object):

def __init__(self, value):
self.value = value
self.left = None
self.right = None

def create_tree(node_id, parent_to_children_map):
if node_id is None:
return None
if node_id not in parent_to_children_map:
return Node(node_id)
n = Node(node_id)
[left_id, right_id] = parent_to_children_map[node_id]
n.left = create_tree(left_id, parent_to_children_map)
n.right = create_tree(right_id, parent_to_children_map)
return n

get_binary_tree()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static Node buildTree(List<Relation> data)
{
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
Node root = null;

for(Relation r: data) {
Node parent, child;

if ((child = map.get(r.child)) == null) {
System.out.println("Here");
child = new Node();
child.data = r.child;
map.put(r.child, child);
}
if (r.parent == 0) {
root = child;
continue;
}
if ((parent = map.get(r.parent)) == null) {
parent = new Node();
parent.data = r.parent;
map.put(r.parent, parent);
}

if (r.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution.
I used HashTable to store and search the node that had been created.
Running time is O(M), where M is number of relationships.
Assumption is that HashTable is real hash table.
Give the implementation I used std::map which gives O(logn) search time.

I would implement HashTable to get O(1) search time if time is allowed.
Space complexity is O(N), where N is number of nodes.

``````Node * buildTree(Relation * data, int len)
{
Node * root = 0;
map<int, Node*> nodemap;
for (int i = 0; i < len; i++)
{
Node * p = 0;
Node * c = 0;

int pid = data[i].parent;
int cid = data[i].child;

if (pid != INT_MIN)
{
if (nodemap.find(pid) != nodemap.end())
{
p = nodemap[pid];
} else {
p = new Node(pid);
nodemap[pid] = p;
}

}
if (nodemap.find(cid) != nodemap.end())
{
c = nodemap[cid];
} else {
c = new Node(cid);
nodemap[cid] = c;
}

if (pid == INT_MIN)
{
root = c;
}

if (p) {
if (data.isLeft)
p->left = c;
else
p->right = c;
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

public Node buildTree (List<Relation> data) {
Node root = null;
for (Relation relation : data) {
//parent exists
Node parent;
Node child;
if (relation != null && relation.child != null) {
if (nodeMap.get(relation.child) != null) {
child = nodeMap.get(relation.child);
} else {
child = new Node(relation.child, null, null);
nodeMap.put(relation.child, child);
}
if (relation.parent == null) {
root = child;
} else {
if (nodeMap.get(relation.parent) != null) {
parent = nodeMap.get(relation.parent);
} else {
parent = new Node(relation.parent, null, null);
nodeMap.put(relation.parent, parent);
}
if (relation.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

public Node buildTree (List<Relation> data) {
Node root = null;
for (Relation relation : data) {
//parent exists
Node parent;
Node child;
if (relation != null && relation.child != null) {
if (nodeMap.get(relation.child) != null) {
child = nodeMap.get(relation.child);
} else {
child = new Node(relation.child, null, null);
nodeMap.put(relation.child, child);
}
if (relation.parent == null) {
root = child;
} else {
if (nodeMap.get(relation.parent) != null) {
parent = nodeMap.get(relation.parent);
} else {
parent = new Node(relation.parent, null, null);
nodeMap.put(relation.parent, parent);
}
if (relation.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static TreeNode<Integer> buildTree(final List<Relation> data) {
Map<Integer, TreeNode<Integer>> hashMap = new HashMap<>();

TreeNode<Integer> root = null;

for (final Relation r : data) {
TreeNode<Integer> parent = hashMap.containsKey(r._parent) ? hashMap.get(r._parent) : new TreeNode<>(r._parent);
hashMap.put(r._parent, parent);

TreeNode<Integer> child = hashMap.containsKey(r._child) ? hashMap.get(r._child) : new TreeNode<>(r._child);
hashMap.put(r._child, child);

if (r._parent == null) {
root = child;
continue;
}

if (r._isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static TreeNode<Integer> buildTree(final List<Relation> data) {
Map<Integer, TreeNode<Integer>> hashMap = new HashMap<>();

TreeNode<Integer> root = null;

for (final Relation r : data) {
TreeNode<Integer> parent = hashMap.containsKey(r._parent) ? hashMap.get(r._parent) : new TreeNode<>(r._parent);
hashMap.put(r._parent, parent);

TreeNode<Integer> child = hashMap.containsKey(r._child) ? hashMap.get(r._child) : new TreeNode<>(r._child);
hashMap.put(r._child, child);

if (r._parent == null) {
root = child;
continue;
}

if (r._isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
}

Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}

private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);

if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
}

Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}

private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);

if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
}

Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}

private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);

if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
}

Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}

private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);

if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}``````

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.

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.