Case study: Lowest common ancestor

May 1, 2020

Introduction

It is the first interview I got the whole week. I worried about interviewing.io financial situation, and free anonymous interview is no longer affordable since some one has to pay the bill. A lot of layoffs last two months, people are flooding in job market for software engineer positions.

Mock interview case study

Here is the code.

	#include <map>
	#include <unordered_map>
	#include <iostream>
	using namespace std;
	class TreeNode {
	public:
	int value;
	TreeNode *left, *right;
	TreeNode(int v) : value(v) {
	left=right=nullptr;
	}
	};
	pair<TreeNode *,int> findLCA(TreeNode *root, TreeNode *A, TreeNode *B) {
	if (!root) return {nullptr, 0};
	// See whether I have found the LCA on the left tree.
	auto LHS=findLCA(root->left, A, B);
	if (LHS.first) return LHS; //
	// See whether I have found the LCA on the right tree.
	auto RHS=findLCA(root->right, A, B);
	if (RHS.first) return RHS;
	// Left and right both are not found
	// See whether this is the LCA.
	// argue that LHS.second = 0, RH.second = 0
	int count=(root==A || root==B) + LHS.second + RHS.second;
	if (count==2) return {root, count};
	return {nullptr, count};
	// This is not the LCA, return what has been found.
	}
	/*
	Your previous Plain Text content is preserved below:
	Given a binary tree, root node and two nodes which may not be in binary tree, find lowest common ancestor
	1
	/\
	3 5
	/\ \
	7 9 11
	\
	19
	give two nodes node 7 and node 9, lowest common ancestor LCA is node 3
	node 3 and node 7, LCA is node 3
	Node 7 and node 19, LCA is node 3
	Node 7 and node 11, LCA is node 1
	Node 7 and node 8, LCA is null <- assuming that two nodes in the binary tree
	*/
	// To execute C++, please define "int main()"
	int main() {
	unordered_map<int, TreeNode *> hmx;
	TreeNode *one=new TreeNode(1);
	hmx[1]=one;
	TreeNode *three=new TreeNode(3);
	hmx[3]=three;
	TreeNode *five=new TreeNode(5);
	hmx[5]=five;
	TreeNode *seven = new TreeNode(7);
	hmx[7]=seven;
	TreeNode *nine = new TreeNode(9);
	hmx[9]=nine;
	TreeNode *nineteen=new TreeNode(19);
	hmx[19]=nineteen;
	one->left=three;
	one->right=five;
	three->left=seven;
	three->right=nine;
	nine->right=nineteen;
	std::cout << findLCA(hmx[1], hmx[5], hmx[19]).first->value << std::endl;
	return 0;
	}

view raw LowestCommonAncestor.cpp hosted with ❤ by GitHub

Discussion we had on the mock interview:

The clever part is to return two things in recursive function. One is to find lowest common ancestor, if it is found then it should be returned; Second one is supporting role to calculate the node found. As we know, the node can be root node or any child node in binary tree. Using total nodes found is the technique to make it easy to identify the edge case: root node is one of nodes p or q, then another node is in subtree nodes.

One thing to make it more readable is to replace checking of return TreeNode null with node's count comparison to value 2 instead.

Interviewer feedback

Interviewee - an ex-facebook engineer

His second algorithm is also bug-free, here is the link.

Actionable items

May 25, 2020

The interviewee is young and top talent engineer. After the mock interview, he saw my feedback, and then he decided to get connected on interviewing.io. I should ask a linkedin.com connection from him, so I can track his career success later on.