Amazon Interview Question for SDE-3s


Country: India
Interview Type: Phone Interview




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

Following are some simpler versions of the problem:

If given Tree is Binary Search Tree?
If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.

If given Binary Tree is Complete Tree?
A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.

If given Binary Tree is Full Tree?
A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.

How to store a general Binary Tree?
A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree.

- vishgupta92 July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

/**
     * Given root, serialize the tree by traversing in pre-order
     * @param root
     * @throws IOException 
     */
    public static void serialize(Node root, PrintWriter pwtr) throws IOException{
        
        if(root == null){
            pwtr.print(Integer.MAX_VALUE + " "); //delimiter
            return;
        }
        else{
            pwtr.print(root.get() + " ");
            serialize(root.left, pwtr);
            serialize(root.right, pwtr);
        }
    }

    /**
     * Read back the pre-order and reconstruct the tree
     * @param fis
     * @return
     * @throws IOException 
     */
    public static Node deserialize(Scanner scanner) throws IOException{
        int value = 0 ;
        
        if(scanner.hasNextInt())        value = scanner.nextInt();
        else            return null;
        
        if(value == Integer.MAX_VALUE)  return null;
        
        Node root = new Node(value);
        root.left = deserialize(scanner);
        root.right = deserialize(scanner);
        
        return root;
    }


    /**
     * Manual serialize/deseialize
     * 
     * @throws IOException
     */
    public static void demo() throws IOException{
        Node root = BinaryTreeUtil.buildTree();
        
        //serialize
        PrintWriter pw = new PrintWriter("binarytree.blob");
        serialize(root, pw);
        pw.close();

        //deserialize
        File file = new File("binarytree.blob");
        Scanner scanner = new Scanner(file);
        root = deserialize(scanner);
        scanner.close();
    }

- X July 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here I've implemented like a graph BFS traversal. I've also implemened the Deserialize.

Probably it would be easier if it was a Binary Search tree.

public static string SerializeBinaryTree(Node root)
{
	if(root == null) 
	{
		return string.Empty();
	}

	var q = new Queue<Node>();
	var sb = new StringBuilder();

	q.Enqueue(root);
	while(q.Count > 0
	{
		Node c = q.Dequeue();
		if(c != null)
		{
			sb.Append(string.Format("{0},", c.Data); 
			q.Enqueue(c.Left);
			q.Enqueue(c.Right);
		}
		else
		{
			sb.Append(",");
		}
	}

	return sb.ToString();	
}

public static Node DeserializeBinaryTree(string S)
{
	if(string.IsNullOrEmpty(S)) return null;
	string[] N = S.Split(",");

	var q = new Queue<Node>();
	int r;
	if(int.TryParse(N[0], out r)
	{
		q.Enqueue(new Node() { Data = r};
	}
	else return null;

	Node result = q.Peek();

	for(int i = 1; i < N.Length; i+= 2)
	{
		int l,r;
		Node c = q.Dequeue();
		if(int.TryParse(N[i], out l)
		{
			c.Left = new Node() { Data = l};
		}

		if((i+1 != N.Length && int.TryParse(N[i+1], out r)
		{
			c.Rigth = new Node(){ Data = r };
		}
	}

	return result;
}

- Nelson Perez July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You have to store the binary tree just using the same format of a heap.
It is, an array where the left and right nodes are positioned at idx * 2 and idx * 2 + 1.

Following a code to serialize a binary Tree. Limitations: Its fills the array with zeros for nulled nodes.

Example:

/*
       10
11          12
                     14

arr[] = 10, 12, 11, 0, 0, 0, 14 
*/

public static final class SerializeBinaryTreeCustom {
        private int[] arr = new int[1];

        public SerializeBinaryTreeCustom(Node root) {
            dfs(root, 0);
        }

        private void dfs(Node node, int idx) {
            if (node == null) return;
            if (arr.length <= idx)
                arr = Arrays.copyOf(arr, idx + 1);

            arr[idx] = node.value;
            dfs(node.left, (idx * 2) + 1);
            dfs(node.right, (idx * 2) + 2);
        }

        public int[] arr() {
            return arr;
        }
    }

- Felipe Cerqueira July 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now imagine if your tree was a root with all children as right child, so essentially a linked list. You've just used 2^n space for n elements.

- alphafalconx July 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes.
But my solution is solving the problem and would be very easy to recreate the binary tree.

- Felipe Cerqueira July 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 
Binary Tree :
      a
     / \ 
    /  right_tree
  /         
left_tree  
*/

tree_pre = "(a (left_tree)(right_tree))"
tree_in =  "((left_tree) a (right_tree))"
tree_post =  "((left_tree) (right_tree) a)"
/* use () to define non existing node */

Any of them would simply work out well. This is a very simple form, isomorphic to a JSON encoding of the same as map of maps.

- NoOne October 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Following are some simpler versions of the problem:

If given Tree is Binary Search Tree?
If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.

If given Binary Tree is Complete Tree?
A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.

If given Binary Tree is Full Tree?
A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.

How to store a general Binary Tree?
A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree.

- vishgupta92 July 09, 2015 | 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