Missing level of technical depth (Common Ancestor)

Question

I recently have given a coding test in a reputable IT company. There were three coding questions.

They refused me by saying that

as we felt they didn't demonstrate the level of technical depth we're seeking from candidates

Question 1 : Missing level of technical depth (Recursive to Iterative)

Question 2 : Missing level of technical depth (Flatten Tree)

and this is 3rd question.

Question 3:

Our service provides free git and source code repository hosting. One way to represent the history of a source code repository like git is as a graph of commits. Some examples:

A simple linear commit graph. This is the graph of a repository with no branching or merging

A-B-C-D

The graph of the history of a repository with a single branch. The repository was branched at Commit B. Commits E and F were made against this branch

 E-F
 /
A-B-C-D

The graph of the history of a repository with a single branch which is then later merged back into master. The repository was branched at Commit B. Commits E and F were made against this branch. Commit G resulted from merging commits F and D.

 E-F
 / \
A-B-C-D-G

Implement a function that will find the most recent common ancestor of any two commits from a given commit graph. The commit graph is represented as a String[] called commits containing all commit IDs in sorted date order (most recent first) and a String[][] called parents. The parent IDs for the commit ID at index i can be found at parents[i]. The last item in the parents array is always null since this represents the parent of the root commit. For example, the following commit graph:

 E-F
 / \
A-B-C-D-G

will be represented using:

String[] commits = {"G", "F", "E", "D", "C", "B", "A"};
String[][] parents ={{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null}; 

If one commit is an ancestor of the other, return the commit that is the ancestor.

Your implementation must implement the FindCommonAncestor interface.

Sample input:

String[] commits = {"G", "F", "E", "D", "C", "B", "A"};
String[][] parents ={{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null}; 
String commit1 = "D";
String commit2 = "F";

This is asking for the most recent common ancestor of commits D and F in the following commit graph

 E-F
 / \
A-B-C-D-G

The answer is B

Hint: It is possible to write an \$O(n)\$ solution to this problem.

Your class must be named findcommonancestor.MyFindCommonAncestor.

Answer 3:

package findcommonancestor;
public interface FindCommonAncestor
{
 String findCommmonAncestor(String[] commitHashes, String[][] parentHashes, String commitHash1, String commitHash2);
}

---

package findcommonancestor;
import java.util.HashSet;
import java.util.Set;
public class MyFindCommonAncestor {
 public String findCommmonAncestor(String[] commitHashes, String[][] parentHashes, String commitHash1, String commitHash2) {
 boolean[] indexesCommit1 = markMatchingIndexes(commitHash1, commitHashes, parentHashes);
 boolean[] indexesCommit2 = markMatchingIndexes(commitHash2, commitHashes, parentHashes);
 for (int i = 0; i < commitHashes.length; i++)
 if (indexesCommit1[i] && indexesCommit2[i])
 return commitHashes[i];
 return null;
 }
 private void addToCommitPath(Set<String> commitPathSet, int beginingIndex, String commitHash, String[] commitHashes, String[][] parentHashes) {
 int index = beginingIndex;
 //for (; index < commitHashes.length; index++) {
 while( index < commitHashes.length ) { 
 if (commitHashes[index].equals(commitHash)) { //check if commit exists in the parent's commits array then take out its index from parent
 commitPathSet.add(commitHashes[index]);
 break; //if commit found in parent then get it and break further loop iteration
 }
 index++ ;
 }
 //}//end for loop
 if (parentHashes[index] != null) { //make sure index is not null i.e. before any initial/first commit
 for (String parent : parentHashes[index]) { //loop over and collect all corresponding matching commits from parent's commit array
 if (!commitPathSet.contains(parent))
 addToCommitPath(commitPathSet, index, parent, commitHashes, parentHashes);
 }//end for loop
 }//end if
 }
 private boolean[] markMatchingIndexes(String commitHash, String[] commitHashes, String[][] parentHashes) {
 Set<String> allCommitPathsSet = new HashSet<String>();
 addToCommitPath(allCommitPathsSet, 0, commitHash, commitHashes, parentHashes);
 boolean[] indexesCommit1 = new boolean[commitHashes.length];
 for (int i = 0; i < commitHashes.length; i++) { 
 indexesCommit1[i] = allCommitPathsSet.contains(commitHashes[i]);
 }
 return indexesCommit1;
 }
 public static void main(String[] args) {
 String[] commits = { "G", "F", "E", "D", "C", "B", "A" };
 String[][] parents = { { "F", "D" }, { "E" }, { "B" }, { "C" }, { "B" }, { "A" }, null };
 String commit1 = "G";
 String commit2 = "B";
 MyFindCommonAncestor myFindCommonAncestor = new MyFindCommonAncestor();
 System.out.println("Common Ancestor is " + myFindCommonAncestor.findCommmonAncestor(commits, parents, commit1, commit2));
 } 
}

• gb96: I don't think you should post coding test questions or answers online unless you're sure they are no longer being used by recruiters. In any case, this is a good test of algorithm design. I have implemented an efficient (O(n)) iterative solution you can find here: pastebin.com/VPyChWc6

Answer 1

The while loop in addToCommitPath could be extracted to another method like:

private int getIndex(int beginingIndex, String hash, String[] commitHashes) {
 for(int index = beginingIndex; index < commitHashes.length; index++) {
 if(hash.equals(commitHashes[index])) {
 return index;
 }
 }
 throw new IllegalArgumentException("Hash not found: " + hash);
}

The hint says \$O(n)\$ time but looking up the index in a loop seems to go over that.

You can cache the indexes for each hash at the beginning with:

Map<String, Integer> commitIndexes = new HashMap<>();
for(int i = 0; i < commitHashes.length; i++) {
 commitIndexes.put(commitHashes[i], i);
}

One case would be that: each commit i has commit i+1 as a parent, and each commit i < n/2 has commit i + n/2 as a parent. Then n/2 commits need a n/2 traversal to find its parent. The loop over all parent hashes is potentially inefficient too: can we assume a maximum number of parents for each commit?

markMatchingIndexes converts a Set to an Array but you could just return the set directly. You only need to check the set once for each index which you need to do anyway to convert it to an array, so you're not saving any work.

Commented out code should be removed. Comments like //end if aren't needed with correct indentation and reasonable length blocks. I would also avoid long comments at the end of a line. Put them on a line by themselves instead.

Answer 2

One other thing. The question says

Your implementation must implement the FindCommonAncestor interface.

However you don't implement FindCommonAncestor. To do this you need add implements FindCommonAncestor to your class declaration.

public class MyFindCommonAncestor implements FindCommonAncestor {

And to show that you are actually implementing it you should add the @Override annotation so it tells the compiler to check you are actually overriding something.

@Override
public String findCommmonAncestor(String[] commitHashes, String[][] parentHashes, String commitHash1, String commitHash2) {