## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: In-Person

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

In C++:

``````struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v):val(v), left(NULL), right(NULL){}
};
TreeNode* buildBalanceTree(int arr[], int s, int e)
{
if(s == e) return new TreeNode(arr[s]);

int m = (s + e) >> 1;
TreeNode* t = new TreeNode(arr[m]);
if(m > s) t->left = buildBalanceTree(arr, s, m-1);
t->right = buildBalanceTree(arr, m+1, e);
return t;
}``````

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

Nice solution, but you are using the stack memory. So it is O(log(n)) space.

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

MakeTree(Int arr[],int start,int end)
{

}

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

This is not O(1), but O(log n) extra space. I'd like to know how to solve it in O(1) extra space.

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

MakeTree(Int arr[],int start,int end)
{
int mid=(start+end)/2;
node* temp =(node*)malloc(sizeof(node));
temp->val=arr[mid];
if(start==end)
{
temp->left=Null;
temp->right=Null;
}
else
{
temp->left=makeTree(arr,start,mid-1);
temp->right=makeTree(arr,mid+1,end);
}
return temp;
}

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

Isn't a sorted array already a balanced heap. If parent = index i, then left child= 2*1+1, right child =2*i+2. Just traverse array in this this order and populate your BST.

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

balanced heap is not a balanced binary SEARCH tree, i believe

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

``````public static Node ConvertToTree(int[] input, int lowerIndex, int higherIndex)
{
if (lowerIndex < higherIndex)
{
var mid = (higherIndex - lowerIndex) / 2 + lowerIndex;
var n = new Node(input[mid]);
n.left = ConvertToTree(input, lowerIndex, mid);
n.right = ConvertToTree(input, mid + 1, higherIndex);
return n;
}
return null;

}``````

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

I am building the tree from bottom up, and it is non-recursive.
If N = 2^m then the algorithm runs in O(1) space and returns a perfectly balanced tree with "N" elements.
If N = 2^m + k, then the algorithm runs in O(1) space, but first build a tree that might have "m" extra nodes. Then these nodes will be removed.

``````public class Node {
public Node left,  right, parent;
public int key;
public Node(Node parent) {
this.parent = parent;
}
}
public  Node getRoot(int[] sorted_array) {
// Assuming sort is ascending
int N = sorted_array.length;
int count = 0;
int max_h = (int) (Math.log(N) / Math.log(2));
int h = max_h;
Node root = new Node(null);
Node node = root;
// In O(log(N)) time, get the left most

while(count < N) {
if (node.left == null && h == 0) {
node.key = sorted_array[count++];
node = node.parent;
h++;
}
else if (node.left == null) {
node.left = new Node(node);
node = node.left;
h--;
}
else if (node.left != null && node.right == null) {
node.key = sorted_array[count++];
node.right = new Node(node);
node = node.right;
h--;
}
else {
node = node.parent;
h++;
}
}
while (node != root) {
node = node.parent;
if (node.key == 0) {
node.parent.left = node.left;
node.left.parent = node.parent;
}
}
return root;
}``````

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

Take the median of the array as the root of the tree. For sake of clarity let's call it original_median. Now , take the median of the array to the left of the original_median and make it the left child and similarly the median of the array to the right of the original_median and make it the right child. Recursively apply it to the left child and right child.

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

traverse from both ends, and then replace the root

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

So you had 20 Amazon interviews back to back????

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

Yes, you are STOOPEED.

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.