Google Mock Interview Experience | Bangalore SDE II (L4)

Question

Suppose you have a graph of organizational structure where each node N corresponds to a person

• If N reports to M, then M is the parent of N
• If P reports to N, P is the child of N

Someone's "employee score" is the total number of reports (including themselves) and you have to write a function to compute anyone's employee score.

So it was pretty basic graph question where we could store empployee in graph and then calculate score for any Node. We discussed a bit and finalised on a structure to store employee and focus on calculating for one employee.

class Employee {
	int id;
	String name;
	List<Employee> reportees;
}

Map<Integer, Employee> graph;

int calculateScore(Employee employee) {
	int score = 1;
	for(Employee reportee : employee.getReportees()) {
            score += calculateScore(reportee);
    }
    return score;
}

Follow up 1

Suppose the graph has already been precomputed with everyone's employee score. Write a function to recompute these employee scores should someone move teams.

• Assume that if an individual moves teams, their reports do not move with them, and simply start directly reporting to an individual's former boss.
• Assume that a function to perform the actual team movement already exists, and the new children / parent of this node have been updated accordingly.

We discussed this and made the strcture better to store not just employees but their score too. Then a reference to whom they report and when updating any score, we can simply propagate upwards.

class Employee {
	int id;
	String name;
	List<Employee> reportees;
	Employee reportingTo;
	int score = 1;
}


void cascadeScore(Employee employee, int score) {
	if(employee == null) {
        return; 
    }
    employee.setScore(employee.getScore() - score);
    cascadeScore(employee.getReportingTo(), score);
}

void removeEmployee(Employee employee) {
    // Moved children
	cascadeScore(employee.getReportingTo(), -1);
    employee.setReportingTo(null);
    employee.setScore(1);
}

void addEmployee(Employee employee, Employee reportingTo) {
	reportingTo.add(employee);
	employee.setReportingTo(reportingTo);
	cascadeScore(employee.getReportingTo(), 1);
}

void moveEmployee(Employee employee, Employee newReport) {
    removeEmployee(employee);
    addEmployee(employee, newReport);
}

Follow up 2

Same as 1st followup, but instead of an individual moving teams write a function to recompute employee scores in the event of a reorganization: that is, have an employee and everyone underneath them move teams.

This was a simple change as well, were we just reorganise the graph.

void cascadeScore(Employee employee, int score) {
	if(employee == null) {
        return; 
    }
    employee.setScore(employee.getScore() - score);
    cascadeScore(employee.getReportingTo(), score);
}

void removeEmployee(Employee employee) {
	cascadeScore(employee.getReportingTo(), -employee.getScore());
    employee.setReportingTo(null);
}

void addEmployee(Employee employee, Employee reportingTo, int score) {
	reportingTo.add(employee);
	employee.setReportingTo(reportingTo);
	cascadeScore(employee.getReportingTo(), score);
}

void moveEmployee(Employee employee, Employee newReport, boolean reorg) {
    if(regorg) {
        removeEmployee(employee);
    }
    addEmployee(employee, newReport, employee.getScore());
}