Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

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..

public void serialize(Node root,int[] a,int index)
{
if(root !=null)
{
if (index ==0) index=1;
a[index]=root.data;
serialize(root.left,a,2*index);
serialize(root.right,a,2*index +1);
}

- Danish Shaikh February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Guy February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its preOrder traversal and use Buffered Writer in Java to write to an output file see java documentation for BufferedWriter

- Danish Shaikh February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- morezaei00 February 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You cannot flatten it like a heap because there might be null values at some index.
for example node 5 (index i) has left child null and right child as 10. Then 2i+1 is null and 2i+2 is 6

- springs November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Rave February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Guy February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, in-order and pre-order or in-order and post-order. You need two representations to uniquely reconstruct the tree.

- Murali Mohan February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But how do we write it to a file?

- Guy February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

GZ_Penny: read en.wikipedia.org/wiki/Serialization

- Anonymous February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mo February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

__3__
/ \
_2_ _1_
/ \ / \
null nullnull null
pre-order way encounter null then insert "#"
->: 32##1##

using this way you can make a tree into file, this String can reconstruct only tree you want, whatever you use pre-order way or in-order way.

- chengyunzuo February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What really is a binary tree containing? Is it just integers? if yes, then integers can be directly written to a file. If there are complex objects serialize them and write them into a file.

- confused_banda February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }
}

- Anonymous February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

GZ/Kevin/whatever.

Please stop posting questions you were not asked.

- Anonymous February 11, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More