Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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),
Add C1 child of C0
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),
Add C2 child of C0
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),
Add C3 child of C0
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
}
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){
childrenNodes.add(child);//recursive
}
}
tree.children = childrenNodes;
}else{
tree.value = srcStr;
}
}
return tree;
}
public static class Node{
String value;
List<Node> children;
}
I just feel the deerialize method is ugly, lot of indexof, substring. Any one have idea to improve? Regex not my favorite.
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() {
// read my data
cin >> d;
// read my number of children
int num_children;
cin >> num_children;
// read the children
while(num_children-- > 0) {
Node* pNode = new Node();
pNode->deserialize();
children->push_back(pNode);
}
}
};
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.
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());
}
}
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());
}
}
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 ?
Using DFS, we can iterate the tree and create a json object. For each parent node create a child json nodes.
- Nikhil June 25, 2014{1:{2:{4:4, 5:5}}, 3:{6:6, 7:7}}}