Missing level of technical depth (Common Ancestor)

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.

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 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.

StackExchange Code Review Q#51547, answer score: 7