Amazon Interview Question for SDE1s


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

- uuuouou March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ehsan March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- PL March 05, 2014 | Flag
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;
}

- Anonymous March 05, 2014 | Flag Reply
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.

- Anonymous March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ninhnnsoc March 06, 2014 | Flag
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;
            
        }

- Anonymous March 06, 2014 | Flag Reply
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;
    }

- Ehsan March 09, 2014 | Flag Reply
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.

- praveenkcs28 March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

traverse from both ends, and then replace the root

- Viky May 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Stop posting your study questions!

- ARE YOU STUPID March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are STOOPEED.

- Anonymous March 06, 2014 | Flag


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