IBM Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

The iterative solution -

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	
	public TreeNode(int val){
		this.val = val;
	}
}

public static TreeNode buildTreeIterative(int[] nums) {
		Stack<int[]> pos = new Stack<>();
		Stack<TreeNode> nodes = new Stack<>();
		
		TreeNode root = new TreeNode(-1);
		
		pos.push(new int[] {0, nums.length - 1});
		nodes.push(root);
		
		while(!nodes.isEmpty()) {
			// Get the current node
			TreeNode node = nodes.pop();
			
			// Pop an element from the stack
			int[] range = pos.pop();
			int start = range[0];
			int end = range[1];
			int mid = range[0] + (range[1] - range[0])/2;
			node.val = nums[mid];
			
			if(start < mid) {
				// There exists a left child for the node
				node.left = new TreeNode(-1);
				pos.push(new int[] {start, mid - 1});
				nodes.push(node.left);
			}
			
			if(end > mid) {
				// There exists a right child for the node
				node.right = new TreeNode(-1);
				pos.push(new int[] {mid + 1, end});
				nodes.push(node.right);
			}
		}
		
		return root;
	}

- anshul.chandra October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

from binaryTree import BinaryTree

def arrayBST(l,start,end):
	mid=(start+end)/2
	if start<=end:
		tree=BinaryTree(l[mid])
		tree.left=arrayBST(l,start,mid-1)
		tree.right=arrayBST(l,mid+1,end)
		return tree

def inorder(tree):
	if tree!=None:
		inorder(tree.left)
		print tree.key
		inorder(tree.right)

def preorder(tree):
	if tree!=None:
		print tree.key
		preorder(tree.left)
		preorder(tree.right)

t=arrayBST([1,2,3,4],0,3)

inorder(t)
print 
preorder(t)

- Yash Katariya January 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Suppose we need to build a balanced binary search tree T for the elements in sorted array A, from index "lo" to "hi".

build(A, lo, hi):
The root of T must be the middle element: T.root = A[mid], where mid = (lo+hi)/2

The left subtree of T must be built from A[lo, mid), recursively:
T.left = build(A, lo, mid-1)

The right subtree of T must be built from A[mid+1, hi), recursively:
T.right = build(A, mid+1, hi)

Remember the basecase is when hi-lo <=1.

Complexity:
Since each element of the array A is accessed once, the complexity is O(N), N = length of array A.

- ninhnnsoc January 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

TreeNode* BuildMinimalTreeFromArr(int* arr , int left, int right){
if(left > right){
return NULL;
}
else{
int mid = (left+right)/2;
TreeNode* root = new TreeNode;
root->data = arr[mid];
root->left = BuildMinimalTreeFromArr(arr,left,mid-1);
root->right = BuildMinimalTreeFromArr(arr,mid+1,right);
return root;
}

}

- zen January 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Building balanced BST from sorted array (Swift):

class Node {
    var data: Int
    var left: Node?
    var right: Node?
    
    init(data: Int, left: Node?, right: Node?) {
        self.data = data
        self.left = left
        self.right = right
    }
}

var arr = [1,2,3,4,5,6,7,8,9]

func buildTree(arr: [Int]) -> Node? {
    if arr.count == 0 {
        return nil
    }
    
    var mid = arr.count / 2
    
    var left : Node? = nil
    if mid > 0 {
        left = buildTree(Array(arr[0..<mid]))
    }
    var right : Node? = nil
    if mid < arr.count - 1 {
        right = buildTree(Array(arr[mid+1..<arr.count]))
    }
    let node = Node(data: arr[mid], left: left, right: right)
    return node
}

var root = buildTree(arr)

- aquio July 19, 2016 | Flag Reply


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