Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
@oOZz
It's O(N^2) in the worst case: finding maximum for each recursion takes O(N), in the worst case O(N) recursions; O(N lg N) on average: O(lg N) recursions = height of the tree when input is randomized.
my solution is....o(n)..
struct node *sbt(struct node **tree,int *a,int i,int n){
struct node *temp=(struct node*)malloc(sizeof(struct node));
if(i>n)
return NULL;
temp->data=a[i];
if((*tree)->data<a[i]){
temp->left=*tree;
*tree=temp;}
else temp->left=new(a[i-1]);
if(i==n){ temp->right==NULL ; return;}
if(a[i+2]>a[i]){
temp->right=new(a[i+1]);
sbt(tree,a,i+2,n);
}
else
temp->right=sbt(tree,a,i+2,n);
return temp;
}
struct node{
int data;
struct node *left;
struct node *right;
};
struct node *new(int x){
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int main(){
//int a[]={5,10,8,20,6,7,4};
int a[]={10};
struct node *tree=new(a[0]);
sbt(&tree,a,1,sizeof(a)/sizeof(int)-1);
printf("\n");
inorder(tree);
printf("\n");
}
Find the max element in the array and it is the root
a. Recursively call for the left side of the array and find max which comes in the left subtree of the root.
b. Recursively call for the right side of the array and that again comes in the right subtree of the root.
c. If there is only one element make the tree node of it and return.
d. If there are two nodes then 2 scenarios arise:
1. If the first element is larger than the other so as it is inorder traversal the first element becomes the root and the next one comes in the right subtree.
2. If the first element is smaller than the other so the other becomes the root and this element comes in the left subarray.
Here is the code:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
int data;
tree_t *left;
tree_t *right;
};
tree_t *newNode(int data)
{
tree_t *n=(tree_t *)malloc(sizeof(tree_t));
n->data=data;
n->left=n->right=NULL;
return n;
}
int findMax(int arr[],int low,int high,int *max)
{
int i,index;
*max=arr[0];
for(i=low;i<=high;i++)
{
if(*max<arr[i])
{
*max=arr[i];
index=i;
}
}
return index;
}
tree_t *constructTree(int arr[],int low,int high,int n)
{
if(low==high)
{
tree_t *root=newNode(arr[low]);
return root;
}
else if(low+1==high)
{
if(arr[low]<arr[high])
{
tree_t *root=newNode(arr[high]);
root->left=newNode(arr[low]);
return root;
}
else if(arr[high]<arr[low])
{
tree_t *root=newNode(arr[low]);
root->right=newNode(arr[high]);
return root;
}
}
int max;
int index=findMax(arr,low,high,&max);
tree_t *root=newNode(max);
if(index<n)
{
root->left=constructTree(arr,low,index-1,n);
root->right=constructTree(arr,index+1,high,n);
}
return root;
}
void inorder(tree_t *root)
{
if(root==NULL)
return;
inorder(root->left);
printf(" %d ",root->data);
inorder(root->right);
}
int main()
{
int arr[]={1,5,3,6,4,2};
int n=sizeof(arr)/sizeof(arr[0]);
int *max;
tree_t *root=constructTree(arr,0,n-1,n);
inorder(root);
}
Can you please give me test case for the below step...
d. If there are two nodes then 2 scenarios arise:
1. If the first element is larger than the other so as it is inorder traversal the first element becomes the root and the next one comes in the right subtree.
2. If the first element is smaller than the other so the other becomes the root and this element comes in the left subarray.
@yogi
The test case is above in the code. Suppose the array is:
array=1,5,3,6,2,4. Notice the difference here it is 2,4 instead of 4,2 and it is also a valid inorder traversal as here now 2 becomes the left node of the root 4.
Whereas in the original condition the node 2 comes in the right subtree of root node 4.
@vgeek
Hi, sorry I still do not understand your algorithm, could you explain it more please? Also, what's your time complexity? Thanks.
@Chih.Chiu.19
You have to construct the tree from inorder traversal.
So root would obviously the max element in the array. Then the elements on the left hand side will be on the left subtree and on the right hand side will be on the right subtree. Now to get the root of the left subtree find the max in the left subarray. And to get the root in right find the root in right subarray. Then do this recursively until you get the tree.
@vgeek
Thanks! So your solution is essentially the same as blackfever's one, right? (Well, he gives no code but...) So the time complexity is O(N^2) in the worst case, O(N lg N) on average, right? How can I improve it?...
@Chih
Yes the complexity that you mentioned is same. Here i dont think that it can be improved further because in order to construct the tree efficiently that is with right left and right childs you have to find first the max element in the array and the same in the left half and the right half of the array. If you can think of any other approach then it is most welcomed.
@vgeek
How about building the tree bottom up ;)
The idea is to have a helper function
buildStartingAt(int[] entries, int i, int capacity)
that reads the array left to right starting from location i and build the tree bottom-up, but when the next read entry exceeds the given "capacity", it stops and returns the index to the next entry, as well as the tree that it has built. What it does is to keep reading entries until the "capacity" is exceeded or the array is exhausted. It keeps the maximum of all the elements it has read so far, and for each newly read entry it compares it with the stored maximum:
Case 1) The new entry is larger than the maximum. Then the new entry should be used as the root to a bigger tree, and the so-far accumulated tree should be its left subtree.
Case 2) The new entry is smaller than the maximum. Then the new entry belongs to the right subtree of the node that contains the current maximum. Call the helper function recursively to generate the right subtree, using the stored maximum as the capacity for this call, then move on.
This only takes O(N) time!
@ Chih.Chiu.19
The above mention ur logic will also take o(n2) . Because it may possible that again for each new node u need to start traversing from root and move the existing node from right to left. E.g:
e.g : 5,10,8,20,6,7,4
for 5,10,8,20,6 : 20
/ \
10 6
/ \
5 8
For 5,10,8,20,6,7 =>
20
/ \
10 7
/ \ /
5 8 6
Please let me know if I am wrong
@om
Hi, well, to be honest I am a bit puzzled by your comment, lol. Ok, maybe I did not express myself clearly, let me use your example for illustration.
So the tree we want to construct is 5, 10, 8, 20, 6, 7, 4.
1) Get 5, update max=5.
5
2) Get 10, put the previous tree as the left subtree of it, update max=10.
10
/
5
3) Get 8, recursively call itself to construct a tree with capacity=8. Now we have two trees, although the second one only exists in the recursive call. For the second tree max=8.
10 8
/
5
4) Peek at 20. 20 is larger than the capacity 8 for the current recursive call, so the call finishes, and it returns the tree it generated, which (8) here, and the upper level function will put this tree as the right subtree for its max=10.
10
/ \
5 8
5) Get 20. The previous tree will be used as its left subtree. Update max=20.
20
/
10
/ \
5 8
6) Get 6. 6<20, so again a recursive call is made to construct a tree, capacity=20.
20 6
/
10
/ \
5 8
7) Get 7. 7>6 so 6 is the left subtree of it. Also updates the max for the second tree to be 7.
20 7
/ /
10 6
/ \
5 8
8) Get 4. 4<7, so another recursive is called to generate tree starting with entry 4.
20 7 4
/ /
10 6
/ \
5 8
9) No more entries. The bottom level call finishes, and the tree {4} will be used as the right subtree for the tree {7,6}.
20 7
/ / \
10 6 4
/ \
5 8
10) The next recursive call finishes, and the subtree it returns {7,6,4} will be used as the right subtree of 20.
20
/ \
10 7
/ \ | \
5 8 6 4
I hope this is clear :)
int FindMax(int arr[],int start,int end)
{
int index=-1;
int max=-999;
if(start == end)
{
max=arr[start];
return start;
}
for(int i=start;i<=end;i++)
{
if(max < arr[i])
{
max=arr[i];
index=i;
}
}
return index;
}
struct Node *BuildTree(int arr[],int start,int end)
{
if(start > end)
return NULL;
int index=FindMax(arr,start,end);
struct Node *temp=NewNode(arr[index]);
temp->left=BuildTree(arr,start,index-1);
temp->right=BuildTree(arr,index+1,end);
return temp;
}
//Updated FindMax function previous will fail few cases
int FindMax(int arr[],int start,int end)
{
int index=start;
int max=arr[start];
if(start == end)
{
max=arr[start];
return start;
}
for(int i=start+1;i<=end;i++)
{
if(max < arr[i])
{
max=arr[i];
index=i;
}
}
return index;
}
struct Node *BuildTree(int arr[],int start,int end)
{
if(start > end)
return NULL;
int index=FindMax(arr,start,end);
struct Node *temp=NewNode(arr[index]);
temp->left=BuildTree(arr,start,index-1);
temp->right=BuildTree(arr,index+1,end);
return temp;
}
// Order -> T(n) = 2*T(n/2) + O(N) - > O(Nlogn) if complete binary tree
{{
TreeNode* construct(int a[], int n)
{
if (n==0) return NULL;
int max_ele_id = find_max(in, 0, n);
TreeNode* root = new TreeNode(in[max_ele_id]);
root->left = construct(in, max_ele_id);
root->right = construct(in+max_ele_id+1, n-max_ele_id-1);
return root;
}
}}
How about two pointers for the array from either side.
When left and the right pointers meet you can expect them to meet at the root. So you can create the tree bottom up.
So taking the 'famous' example of 5, 10, 8, 20, 6, 7, 4
take 'left' and 'right' pointers at 5 and 4.
Now based in inorder traversal we know that 5 and 4 are leaves of the tree and the next node in the both pointer movement will be the first level root.
so left pointer moves once to the right building 5, 10 and the right pointer moves left building 4 and 7. Continue this process while left < right handling cases for even and odd number of elements.
This is a O(n) solution
How about two pointers for the array from either side.
When left and the right pointers meet you can expect them to meet at the root. So you can create the tree bottom up.
So taking the 'famous' example of 5, 10, 8, 20, 6, 7, 4. Take 'left' and 'right' pointers at 5 and 4.
Now based in inorder traversal we know that 5 and 4 are leaves of the tree and the next node in the both pointer movement will be the first level root.
So left pointer moves once to the right building 5, 10 and the right pointer moves left building 4 and 7. Continue this process while left < right handling cases for even and odd number of elements.
This is a O(n) solution
Here is the Code#
private static Link inOrderTreeCreation(int[] inO,int min,int max) {
if(max-min==0)
return null;
int maxValue=0;int i=min;int index=0;
for(;i<max;i++){
if(maxValue<inO[i]) {
maxValue=inO[i];
index=i;
}
}
Link l = new Link(maxValue,null,null);
l.left=inOrderTreeCreation(inO,min,index);
l.right=inOrderTreeCreation(inO,index+1,max);
return l;
}
Here goes the algo
- blackfever July 25, 20131. Find the max element in the series and that element becomes root.
2.elements which are in the series to the left of root is in left subtree and on the right belongs to right subtree
do it recursively for left and right subtree
for eg:-
Inorder traversal- 5 10 8 20 6 7 4
so 20 is the root
and left subtree {5,10,8}
right subtree {6,7,4}}
no do it recursively for (5,10,8)
here 10 becomes the root and 5 it's left child and 8 it's right child