Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Which traversal algorithm do we use when serializing the tree? Both in-order and pre-order or just post-order? After you transfer the tree to an array, how do you save it in a file and deserialize it back?
Its preOrder traversal and use Buffered Writer in Java to write to an output file see java documentation for BufferedWriter
Danish is pretty much creating a heap out of the tree since we need to flatten out the tree before copying it.
Interesting how languages like PHP do this with their serialize function. serialize(tree); and then unserialize(tree); it works on any object type.
get the in-order and pre-order traversals in a file and use the binary tree reconstruction algorithm.
Complexity : O(n)+O(n) to write to a file and reconstruction O(n log n)
So we have to do both in-order and pre-order? Can't just do one of them or post-order? When we traverse the tree, how do we copy it to a file? I haven't had experience with serialize/deserialize before.
Yes, in-order and pre-order or in-order and post-order. You need two representations to uniquely reconstruct the tree.
A. What kind of machines are we talking about (Linux to Windows for example)
B. Serializing in one language and deserializing in another will not work (Think Java and .NET)
C. The best way (inefficient ofcourse) is to serialize a stream in XML. That way all objects will get serialized properly and any client can deserialize them.
With that in mind, I would propose the following algorithm:
A. Write out the BST using in-order traversal to an XML file
B. Add attributes to the XML file indicating what traversal is used
C. If security is of concern, add security parameters
class MyTree implements Externalizable{
class Node implements Serializable{...}//Assuming the memebr objects implement Serializable too
@Override
public void writeExternal(ObjectOutput out) throws IOException
{
out.writeObject(root);
}
@Override
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
{
root = (Node)in.readObject();
}
}//MyTree
public static void storeRestoreTest(Node root)
{
try{
//print the tree for testing
FileOutputStream fos = new FileOutputStream("TreeDatafile.XYZ");
ObjectOutputStream oos = new ObjectOutputStream(fos);
oos.writeObject(root);
oos.flush();
oos.close();
MyBinaryTree btRead;
FileInputStream fis = new FileInputStream("TreeDatafile.XYZ");
ObjectInputStream ois = new ObjectInputStream(fis);
btRead = (MyBinaryTree) ois.readObject();
ois.close();
//print the new tree
} catch (Exception ex)
{
ex.printStackTrace();
}
}
Serialize the tree in an array.And then transfer the array ...deserialize it back .
for example 1
2 4
5 6 7 8
you will store the above tree in an array starting at index 1 with left child at 2i and right child at 2i+1 and then deserialize the array back in the machine..
- Danish Shaikh February 11, 2014