Data Structures and Algorithm: Find longest interviewer chain
In an organization employees are interviewed with one or more previous employees. Those previous employees are also interviewed by some other employees during their joining. In this way an interview chain is formed, where every node in the chain has been interviewed by the next node in the chain. You are given such information of interviewers for every employees. Given any employee in the organization find the longest such chain possible.
Solution
Every employee maintains a list of interviewers. We recursively find the longest chain. We call the same function to find the longest chain of all of its interviewers. Whichever path has the highest length, we append the current employee to that list and return. If the employee has no interviewers then the recursion ends there and we return a single element list which contain only that particular employee.
private static List findLongestInterviewChain(Employee employee) { int maxLength = -1; List longestPath = new ArrayList (); for (Employee interviewer : employee.getInterviewers()) { List path = findLongestInterviewChain(interviewer); if (path.size() > maxLength) { maxLength = path.size(); longestPath = path; } } longestPath.add(0, employee); return longestPath; }
