google logo
Google· SDE II (L4)

Google Mock Interview Experience | Bangalore SDE II (L4)

Location
Bangalore
Posted
2 Apr 2025
332 reads

Summary

I had a Google mock interview for an SDE II (L4) role in Bangalore. The session focused on a core graph problem concerning organizational structure and employee scores, followed by two challenging follow-up questions on efficiently recomputing scores after individual or subtree team movements.

How it went

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());
}

Questions asked (3)

  1. 01

    Employee Score in Organizational Graph

    Data Structures & Algorithms

    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.

  2. 02

    Recompute Employee Scores on Individual Team Move

    Data Structures & Algorithms

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

    Recompute Employee Scores on Team Reorganization (Subtree Move)

    Data Structures & Algorithms

    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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!