Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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
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;
}
#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;
}
#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);
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;
}
}
This can be solved once you make a few observations. Given the example tree:
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):
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