Amazon Interview Question for SDE-2s

• 3

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

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

``````def addNode(item, head, dict):
if not dict.has_key(item):
dict[item] = True

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

Comment hidden because of low score. Click to expand.
0

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.

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);
postCur++;
preCur+=length+1;
}
return root;``````

}

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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

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);``````

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

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;
}
}
return root;
}
}``````

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.

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.