I recently have given a coding test in a reputable IT company. There were three coding questions.They refused me by saying thatas we felt they didn't demonstrate the level of technical depth we're seeking from candidatesQuestion 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 mergingA-B-C-DThe 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-DThe 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-GImplement 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-Gwill 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-GThe answer is BHint: 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));    } }
Missing level of technical depth (Common Ancestor)
java;interview questions;graph;git
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 correctindentation and reasonable length blocks. I would also avoid long comments at the end of a line. Put them on a line by themselves instead.