Google Interview Question for Software Engineers


Country: India
Interview Type: In-Person




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

The solution is Morris Traversal i.e to do the inorder traversal without extra space, We just need to do inorder traversal using morris traversal till we find the median which can be n/2 for even count and (n-1)/2 when count is odd

- jerry April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Step 1 is the count of the number of nodes in the BST.

public static int GetNodeCountBST(Node root)
{
	if(root == null)
	{
		return 0;
	}
	Node currentNode = root;
	return GetNodeCountBSTRec(currentNode);
}
private static int GetNodeCountBST(Node node)
{
	if(node == null)
	{
		return 0;
	}
	return GetNodeCountBST(node.left) + 1 + GetNodeCountBST(node.right);
}

Step 2 is to find the median

public static double? FindMedian(Node root, int nodeCount)
{
	if(root == null || nodeCount <= 0)
	{
		return null;
	}
	Int median= 0;
	Node currentNode = root;
	FindMedianRec(currentNode, nodeCount, 0, out median);
	return median;
}

private static int FindMedianRec(Node node, int totalCount, int nodeCount, out double median)
{
	if(node == null)
	{
		return nodeCount;
	}
	int leftNodeCount = FindMedianRec(node.left, totalCount, nodeCount, out median);
	if(leftNodeCount == (TotalCount-1)/2)
	{
		median = node.data;
	}
	if(leftNodeCount == (TotalCount/2))
	{
		if(TotalCount % 2 == 0)
		{
			median = (median + (double)node.data)/2;
		}
	}
	return FindMedianRec(node.right, totalCount, nodeCount + 1 + leftNodeCount, out median);
}

Complexity of both the steps is O(N) and space complexity is O(1) only.

- sonesh April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Perform an inorder traversal and then look at the middle element.

- Dhruva.Bharadwaj April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find total node count, then do an inorder traversal of the bst and have an index which increments for each node visited. If total node count was even then stop when you reach idx = n/2, otherwise stop at (n-1)/2.

- Anonymous April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If it is a balanced bst, I think you could simply return the root or the one right before or after it. What do you think?

- bean June 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do an inorder traversal twice, first to find the count. Second to get the median based on that count using an array with single element.

- Ahmed.Ebaid August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static float findMedianOfTree(TreeNode root){
        int count = findnumOfNodes(root);
        if(count == 1){
            return root.val;
        }
        
        if(count%2==1){
            return findkthEleTree(root,count/2+1);
        }else{
            return (findkthEleTree(root,count/2)+findkthEleTree(root,count/2+1))/(float)2;
        }
    }
 
    public static int findkthEleTree(TreeNode root,int k){
        
        int left_count = findnumOfNodes(root.left);
        if(left_count+1==k){
            return root.val;
        }else if(left_count+1<k){
            return findkthEleTree(root.right,k-left_count-1);
        }else{
            return findkthEleTree(root.left,k);
        }
    }
    
 
    public static int findnumOfNodes(TreeNode root){
        if(root==null) return 0;
        
        return findnumOfNodes(root.left)+1+findnumOfNodes(root.right);
    }

- tiandiao123 August 30, 2017 | 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