## Yahoo Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Using DFS, we can iterate the tree and create a json object. For each parent node create a child json nodes.
{1:{2:{4:4, 5:5}}, 3:{6:6, 7:7}}}

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

Works, but the resulting string is bigger than doing inorder and preorder/postorder.

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

Simple, user in-order and pre-order traversal to serialize and then deserialize tree.

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

In-order traversal is not applicable for non Binary tree

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

This is the correct solution.

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

``````A tree can be constructed unambiguously if we have
in-order & pre-order traversal
in-order & post-order traversal
As this may not be a binary tree, so in-order traversal will not be possible.
For a generic tree, one can use DFS and BFS to construct a tree
EX:
Assume for a given tree
DFS  =  c4 , c5, c6, c1, c7 c2, c8 c9, c10, c3, c0
BFS  =  c0 , c1, c2, c3, c4, c5, c6, c7, c8, c9, c10
If we look at the BFS, the first element will be the root
Root = C0
Remove root from BFS & DFS
C1 is the second element in the BFS.
Locate this C1 in DFS which is at index 3 (index starts at 0),
All elements from 0 to 2 are child of C1
Construct the tree with C1 has child’s (c4,c5,c6)
Remove c4,c5,c6,c1 from DFS
Remove c4,c5,c6,c1 from BFS
Iteration-2:
C2 is the second element in the BFS
(At this stage DFS looks like: c7 c2, c8 c9, c10, c3)
(At this stage BFS looks like: c2, c3, c7, c8, c9, c10)

Clearly C2 & C1 are at same level as C2 is not coming in the left of C1 in DFS.
Locate this C2 in DFS which is at index 1 (index starts at 0),
element 0 in DFS are child of C2
Construct the tree with C2 has child’s (c7)
Remove c2,c7 from DFS
Remove c2,c7 from BFS
Iteration-3:
C3 is the second element in the BFS
(At this stage DFS looks like: c8 c9, c10, c3)
(At this stage BFS looks like:  c3, c8, c9, c10)

Clearly C3 & C1 are at same level as C3 is not coming in the left of C1 in DFS.
Locate this C3 in DFS which is at index 3 (index starts at 0),
element 0 to 2 in DFS are child of C2
Construct the tree with C3 has child’s (c8,c9,c10)
Remove c8,c9,c10,c3  from DFS
Remove c8,c9,c10,c3 from BFS

Input: s1,s2 {s1 is the bfs of the tree, s2 is dfs of the tree}
Output: T (Constructed Tree)
-------------------------------------------------------------
root = s1.first()
remove(root) from s1
remove(root) from s2
T = constructTree(root, null, null) /*construct a tree with only root*/
while (!s1.isEmpty())
{
e = s1.fist(); /* The first element in the bfs sequence*/
child[] = {e}
constructTree(root, child[], T)
i = indexOf(s2,e) /* get the index of the bfs element in dfs */
child[] = {s2.getsubsequence(0,i-1)} /* child of e are the left elements of dfs*/
constructTree(e,child,T)
remove(childs) from s1
remove(childs) from s2
}``````

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

``````private final static String P_LEFT = "{", P_RIGHT="}", SEPARATOR=";";
public String serialize(Node tree){
StringBuilder sb = new StringBuilder();
if(tree != null){
if(tree.value != null){
sb.append(P_LEFT).append(tree.value);
List<Node> children = tree.children;//in width traverse
if(children != null && children.size()>0){
sb.append(SEPARATOR+P_LEFT);
for (Node node : children) {
sb.append(serialize(node));//recursive
sb.append(SEPARATOR);
}
sb.append(P_RIGHT);
}
sb.append(P_RIGHT);
}
}

return sb.toString();
}

public Node deSerialize(String srcStr){
Node tree = null;
if((srcStr != null) && (srcStr.length() >= 2)){
srcStr = srcStr.substring(1, srcStr.length()-1);//strip {}
tree = new Node();

//get value
int firstSeparatorIndx = srcStr.indexOf(SEPARATOR);
if(firstSeparatorIndx >0){
String val = srcStr.substring(0, firstSeparatorIndx);
tree.value = val;

//get children
String childrenStr = srcStr.substring(firstSeparatorIndx+2, srcStr.length()-1);
String[] childrenSrcStrs = childrenStr.split(SEPARATOR);
List<Node> childrenNodes = new ArrayList<Node>();
for (String string : childrenSrcStrs) {
Node child = deSerialize(string);
if(child != null){
}
}
tree.children = childrenNodes;
}else{
tree.value = srcStr;
}
}

return tree;
}

public static class Node{
String value;
List<Node> children;
}``````

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

I just feel the deerialize method is ugly, lot of indexof, substring. Any one have idea to improve? Regex not my favorite.

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

BTW, for node value, during seriliztion and deserialization, may need to escape or encoding. Otherwise may comflict with {} and SEPARATOR.

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

Wouldn the simplest be a non binary, left branch only tree. Basically a singly linked list?

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

Wouldn the simplest be a non binary, left branch only tree. Basically a singly linked list?

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

Serialization could be something like:

<node1>:<node1 children> | <node2>:<node2 children> ....

where <nodeX> is the serialized string form of nodeX

The problem is how to identify a node uniquely when deserializing the string format.

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

C++ serialize/deserialize to/from a stream

``````class Node {
public:
Data d;
list<Node*> children;

void Serialize() {
// write my data
cout << d;

// write the number of children
cout << children.size();

// write my children
for(auto itr=children.begin(); itr != children.end(); ++itr) itr->serialize();
}

void deserialize() {
cin >> d;

// read my number of children
int num_children;
cin >> num_children;

while(num_children-- > 0) {
Node* pNode = new Node();
pNode->deserialize();
children->push_back(pNode);
}
}
};``````

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

Everyone seems to assume tree consists of integer or char data.
In practical applications, lots of times data structures hold some complex objects. Your algorithm should you be able to efficiently serialize and deserialize and so your approach should depend on the type of data it holds and how sparse the tree can be.
What if the tree is like a social graph? You can't hold it in memory?
What if this tree has to be sent over the wire? optimize for size of the object there even if it takes little more time to do the serialization and deserialization. etc etc..
These are the things the interviewer will be looking for.

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

public class Tree {

Tree left;
Tree right;
int val;

static final char START = '[', END = ']', SEPERATOR = ':';
static final String LEAF = "*";

Tree(int val, Tree left, Tree right){
this.val = val;
this.left = left;
this.right = right;
}

String serialize(){
StringBuilder sb = new StringBuilder();
sb.append(START);
sb.append(val);
sb.append(SEPERATOR);
if(left!=null)
sb.append(left.serialize());
else
sb.append(LEAF);
sb.append(SEPERATOR);
if(right!=null)
sb.append(right.serialize());
else
sb.append(LEAF);
sb.append(END);
return sb.toString();
}

static Tree deserialize(String str){
if(str.equals(LEAF)) return null;
int indexSep1 = str.indexOf(SEPERATOR);
int indexSep2 = getMiddleSeperatorIndex(str,indexSep1+1);
int val = Integer.parseInt(str.substring(1, indexSep1));
String leftStr = str.substring(indexSep1+1, indexSep2);
String rightStr = str.substring(indexSep2+1, str.length()-1);
return new Tree(val,deserialize(leftStr), deserialize(rightStr));
}

private static int getMiddleSeperatorIndex(String str, int startIndex) {
int counter = 0;
for (int i = startIndex; i < str.length(); i++) {
char c = str.charAt(i);
if(c == START){
counter++;
}
if(c == END){
counter--;
}
if(c == SEPERATOR && counter == 0){
return i;
}
}
return -1; //error
}

public String toString(){
return serialize();
}

public static void main(String[] args) {
Tree root = new Tree(1, new Tree(2, new Tree(4,new Tree(2,new Tree(1,null,null),null),null), new Tree(5, null, null)),new Tree(3, new Tree(6,null,new Tree(10,null,null)), new Tree(7, null, null)));
System.out.println(root.toString());
Tree root2 = deserialize(root.toString());
System.out.println(root2.toString());
}

}

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

``````public class Tree {

Tree left;
Tree right;
int  val;

static final char START = '[', END = ']', SEPERATOR = ':';
static final String LEAF = "*";

Tree(int val, Tree left, Tree right){
this.val = val;
this.left = left;
this.right = right;
}

String serialize(){
StringBuilder sb = new StringBuilder();
sb.append(START);
sb.append(val);
sb.append(SEPERATOR);
if(left!=null)
sb.append(left.serialize());
else
sb.append(LEAF);
sb.append(SEPERATOR);
if(right!=null)
sb.append(right.serialize());
else
sb.append(LEAF);
sb.append(END);
return sb.toString();
}

static Tree deserialize(String str){
if(str.equals(LEAF)) return null;
int indexSep1 = str.indexOf(SEPERATOR);
int indexSep2 = getMiddleSeperatorIndex(str,indexSep1+1);
int val = Integer.parseInt(str.substring(1, indexSep1));
String leftStr = str.substring(indexSep1+1, indexSep2);
String rightStr = str.substring(indexSep2+1, str.length()-1);
return new Tree(val,deserialize(leftStr), deserialize(rightStr));
}

private static int getMiddleSeperatorIndex(String str, int startIndex) {
int counter = 0;
for (int i = startIndex; i < str.length(); i++) {
char c = str.charAt(i);
if(c == START){
counter++;
}
if(c == END){
counter--;
}
if(c == SEPERATOR && counter == 0){
return i;
}
}
return -1; //error
}

public String toString(){
return serialize();
}

public static void main(String[] args) {
Tree root = new Tree(1, new Tree(2, new Tree(4,new Tree(2,new Tree(1,null,null),null),null), new Tree(5, null, null)),new Tree(3, new Tree(6,null,new Tree(10,null,null)), new Tree(7, null, null)));
System.out.println(root.toString());
Tree root2 = deserialize(root.toString());
System.out.println(root2.toString());
}

}``````

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

can we save the tree structure by saving as pairs of nodes ( parent, child) in the case where a parent can have multiple children ? then, we can serialize each object separately.

(root, a1) <-- root has 2 children a1 and a2
(root, a2)
(a1, b1) <-- a1 has 2 children b1 and b2
( a1, b2)
( a2, b3)
...
then deal with serializing all nodes indiviually as a list or so ?

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

If the tree is binary tree, then level order traversal is easy for serialize and deserialize.

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

Serialize:
Do DFS while doing so maintain map table so that key is node and value list of immediate children
Desrialize:
Read each key in map table create node and recursively create it's children

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.