Interview Question for SDE-3s


Country: India
Interview Type: In-Person




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

I am assuming the question was referring a BST. You can store the three basically in pre-order, in-order and post-order.
If you store the Tree in an in-order fashion you are basically storing the values sorted, in that case you can modify the file without having to rewrite the tree again.
Example:

BST:
           6
       3      7
    1    4      8

File:
1 3 4 6 7 8

Let's say you add 2 on the tree in order to update the file you only have to iterate until the number three and add it before.

- Fernando June 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Serialization is to store tree in a file so that it can be later restored. The structure of tree must be maintained. Deserialization is reading tree back from file.

for more see Serialize and Deserialize a Binary Tree in geeksforgeeks

- kuppu612 June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I gave the same answer, But the ineterviewer was specific about not wirting the whole serialized file but writing the exactly changed node.

- Ghosh June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For the second part, if we first update and find the solution (in main memory) and then write only the parts that have been modified by traversing through the entire file. Would that be a possible solution ?

- kr0821 June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well the question is what is changed, if there is a key / value pair, just locate the node and overwrite the value. If there's only one value that defines the trees structure, assuming it's a BST, this will always affect a large part of the tree. B-tree might be a solution then.

- Chris June 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;

public class SerializeAndDeserialize {

    public static void serialize(BufferedWriter writer, Node root) throws IOException {
        if (root == null) return;
        writer.write(root.value);
        if (root.left == null && root.right == null){writer.write('*');writer.write('*'); return;}
        if (root.left == null) writer.write('*'); else serialize(writer, root.left);
        if (root.right == null) writer.write('*'); else serialize(writer, root.right);
    }

    public static Node deserialize(BufferedReader reader) throws IOException {
        int value = reader.read();
        if (value < 0 || value == '*') return null;
        Node temp = new Node (value);
        temp.left = deserialize(reader);
        temp.right = deserialize(reader);
        return temp;
    }

- noname June 21, 2017 | 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