## Oracle Interview Question for Software Engineer / Developers

• 0

Interview Type: In-Person

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

``````Node makeTree(int a[],int start,int end)
{
if(start>end)
return null;
//to keep overflow away
int mid=start+(end-start)/2;
Node n=new Node();
n.info=a[mid];
n.left=makeTree(a,start,mid-1);
n.right=makeTree(a,mid+1,end);
return n;

}``````

.

1. Recursively calculate mid
2. Make it root node.
3. Nd keep doing this process for other two halves of array

T(n)=2T(n/2)+1
it will give us o(n) time complexity

space complexity-o(n) for recursive stack

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

``````public static TNode insert(TNode node, int value){
if(node == null){
node = new TNode(value);
}else{
if(value > node.value)
node.right = insert(node.right,value);
else
node.left = insert(node.left,value);
}
return node;
}``````

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

``````public static TNode createTree2(int array[], int start, int end, TNode root){

if(start < 0 || end >= array.length || start > end){
return root;
}else{
int middle = ((end - start)/2)+start;  // middle Index

root =insert(root,array[middle]);
createTree2(array,start,middle-1,root);
createTree2(array,middle+1,end,root);
}
return root;

}``````

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

Complexity:
Tree Insert O(n log n) + Iterate array O (n ) = O( 2n log n) ~ O (n log n )

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

I think it is just to insert n elements , so the complexity should only be O(n log n)
correct me if I am wrong

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

Every time find the mid of the array/sub-array and make it as root.
e.g. array is 1,2,3,4,5,6,7,8,9
1. Find mid i.e. 5 which will be root.
2. Elements at the left hand side of 5 will be left sub tree and rest will be right sub tree.
3. Recursively call left and right sub array.

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

can we also use red-black tree instead and start inserting the first element from the beginning?

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

AVL tree implementation will suffice here.

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.