Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

This can be solved once you make a few observations. Given the example tree:

1
       /  |    \
    2    5    7
  /  \    |     |
3    4  6    8
                |  
                9

pre : 1 2 3 4 5 6 7 8 9
post: 3 4 2 6 5 9 8 7 1

The root for that sequence is always the first in the Pre and the last in the Post -> 1
Everything else should be a child of the specified root. Identifying each of the children branches can be identified by simply seeing where and instance in Pre occurs int Post:
the branch headed by 2 contains the contents:

pre: 2 3 4
post: 3 4 2

we also know that this branch has 2 as it's root since 2 is the first and last item. We can then recurse down and see that 2 would have the a branch with only 3 and a branch with only 4.

Extrapolating this process, the tree should be constructable in O(n^2) time (I like java so I made this in Java):

class Node{
	int data;
	ArrayList<Node> children = new ArrayList<Node>();
}

public static Node buildTree(int[] preOrder, int[] postOrder){
	if(preOrder == null || postOrder == null){
		throw new NullPointerException();
	}
	if(preOrder.length != postOrder.length){
		throw new IllegalArgumentException();
	}
	return buildTree(preOrder, 0, preOrder.length-1, postOrder, 0, postOrder.length -1);
}

private static Node buildTree(int[] preOrder, int preMin, int preMax, int[] postOrder, int postMin, int postMax){
	//construct the root;
	Node root = new Node();
	root.data = preOrder[preMin];
	
	//construct the child branches
	int preIndex = preMin + 1;
	int postIndex = postMin;
	while(preIndex <= preMax &&  postIndex <= postMax -1){
		//preOrder[preIndex] is now the root of the next child branch
		//find where preOrder[preIndex] occurs in postOrder
		int shift = 0;
		while(postOrder[postIndex + shift] != preOrder[preIndex]){
			shift++;
		}
		Node child = buildTree(preOrder, preIndex, preIndex + shift, postOrder, postMin, postMin + shift);
		root.children.add(child);
		shift++;
		preIndex += shift;
		postIndex += shift;
	}
	return root;
}

Part of the slowdown in this code is the frequent lookups of Post values matching a given Pre value. That process could be potentially sped up by using a Map of value to index. And that map could be completed in O(n) time reducing the overall runtime of the application from O(n^2) to O(n).

- zortlord December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def addNode(item, head, dict):
    if not dict.has_key(item):
        head.child = head.child + [item]
        head.child_num += 1
        dict[item] = True



def rebuildTree(preOrder, postOrder):
    head = None
    preHead = None
    postHead = None
    dictNode = {}
    if len(preOrder) != len(postOrder):
        return None
    treeLen = len(preOrder)
    for i in range(treeLen):
        if head == None:
            head = preHead = postHead = preOrder[i]
            dictNode[preOrder[i]] = True
        else:
            addNode(preOrder[i], preHead, dictNode)
            preHead = preOrder[i]
            addNode(postOrder[treeLen-i-1], postHead, dictNode)
            postHead = postOrder[treeLen-i-1]
    return head

- Adi December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the solution is much simpler, start from start of preorder, and end of postorder. keep adding child after wherever last one was added unless its already been added, in which case just add from the existing node.

- Adi December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the clean Java solution:

public static Node constructTree(int[] preorder,int preStart,int preEnd,int[] postorder,int postStart,int postEnd)
	{
		if(preStart>preEnd) return null;
		Node root=new Node(preorder[preStart]);
		int preCur=preStart+1;
		int postCur=postStart;
		while(preCur<=preEnd&&postCur<=postEnd-1)
		{
			//Node child=new Node(preorder[preCur]);
			int length=0;
			while(postorder[postCur]!=preorder[preCur])
			{
				postCur++;
				length++;
			}
			//postorder[postCur]==preorder[preCur]
			Node child=constructTree(preorder,preCur,preCur+length,postorder,postCur-length,postCur);
			root.children.add(child);
			postCur++;
			preCur+=length+1;
		}
		return root;

}

- Lu December 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Given a Pre Order Or Post order we wont be getting exact structure of the tree.
In-Order is a must to figure the exact structure of the tree

- Messi January 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define MAX_CHILD 3

typedef struct __TreeNode { 
	int data; 
	__TreeNode *children[MAX_CHILD]; 
	int childCount; 
	__TreeNode(int data = 0) : data(data), childCount(0) {}
}TreeNode;

int search(int *arr, int n, int target, int start) {
	while(start < n && arr[start] != target)
		++start;
	return start;
} 

TreeNode* generateTree(int *preArr, int *postArr, int n) {
	if(n == 0) return NULL;
	TreeNode *root = new TreeNode(preArr[0]);
	int curChildPre = 1, curChildPost = 0, curChildLen = 0;
	while(curChildPre < n) {
		curChildPost = search(postArr, n, preArr[curChildPre], curChildPre - 1);
		assert(curChildPost < n - 1);
		curChildLen = curChildPost - curChildPre + 2;
		root->children[root->childCount++] = generateTree(preArr + curChildPre, postArr + curChildPre - 1, curChildLen);
		curChildPre += curChildLen;
	}
	return root;
}

int main() {
	int preArr[] = {1, 2, 5, 3, 6, 7, 4, 8, 9, 10};
	int postArr[] = {5, 2, 6, 7, 3, 8, 9, 10, 4, 1};
	int n = sizeof(preArr) / sizeof(preArr[0]);

	TreeNode * root = generateTree(preArr, postArr, n);
	return 0;
}

- T_Dog January 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

http: //ideone .com/K604Ay

pre & post order to Nary tree.
much cleaner

- SK January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define MAX 3

struct node {
	int data;
	struct node *child[MAX];
	int num_child;
};

typedef struct node node_t;

// create tree from post order and pre order
node_t* get_tree(int pre[], int post[], int pre_start, int pre_end, int post_start, int post_end)
{
	if (pre_start > pre_end || post_start > post_end || pre[pre_start] != post[post_end] || pre_end - pre_start != post_end - post_start) throw std::exception("Invalid input");
	auto rv = new node_t;
	rv->data = pre[pre_start];
	rv->num_child = 0;
	auto next_pre_start = pre_start + 1;
	auto next_pre_end = next_pre_start; // will find this;
	auto next_post_end = post_end - 1; // will find this;
	auto next_post_start = post_start;
	for (auto i = 0; i < MAX; ++i)
	{
		if (next_pre_start > pre_end)
		{
			// no more children, fill the rest with nulls
			for (auto j = i; j < MAX; ++j)
			{
				rv->child[j] = nullptr;
			}
			return rv;
		}

		for (; next_post_end >= next_post_start; --next_post_end)
		{
			if (post[next_post_end] == pre[next_pre_start]) break;
		}
		if (next_post_end < next_post_start) throw std::exception("Invalid input");
		auto range = next_post_end - next_post_start;
		next_pre_end += range;
		rv->child[i] = get_tree(pre, post, next_pre_start, next_pre_end, next_post_start, next_post_end);
		++rv->num_child;
		next_pre_start = ++next_pre_end;
		next_post_start = next_post_end + 1;
		next_post_end = post_end - 1;
	}
	return rv;
}


// usage 

	/*
		    3
		   / \
		  5   4
		 / \
		6   7
	*/

	int pre[] = { 3, 5, 6, 7, 4 };
	int post[] = { 6, 7, 5, 4, 3 };

	auto n = get_tree(pre, post, 0, 4, 0, 4);

- Omri.Bashari May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static class Node {
    private final List<Node> children = new ArrayList<Node>();
    public final String data;
    public Node(String data) {
        this.data = data;
    }
    public void addChild(Node child) {
        children.add(child);
    }
}

static class TreeBuilder {
    private int idxPre, idxPost;
    private final String[] preOrder;
    private final String[] postOrder;
    public TreeBuilder(String preOrder, String postOrder, String delimiter) {
        this.preOrder = preOrder.split(delimiter);
        this.postOrder = postOrder.split(delimiter);
    }
    public Node buildTree() {
        Node root = new Node(preOrder[idxPre++]);
        while(true) {
            if(root.data.equals(postOrder[idxPost])) {
                idxPost++;
                break;
            }
            root.addChild(buildTree());
        }
        return root;
    }
}

- theclish August 14, 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