Flipkart Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
// Lay off engine for Ace Shippping Corp
// Strategy: Use multiway tree to store organization hierarchy
// Also use a map to keep track of all nodes of the tree for
// easy access.
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
class Employee {
public:
typedef enum{
Manager,
IC // Individual Contributor
}Role;
Employee(int id, string name, int mgr_id, int rating, double salary, Role role=IC) {
this->id = id;
this->name = name;
this->mgr_id = mgr_id;
this->rating = rating;
this->salary = salary;
}
bool addDirectReports(Employee* emp) {
if(role != Manager) {
cout << "Can't add direct reports as role is not Manager\n";
return false;
}
directReports.push_back(emp);
return true;
}
bool removeDirectReports(Employee* emp) {
// TODO
return true;
}
int id;
int mgr_id;
string name;
int rating;
double salary;
Role role;
vector<Employee*> directReports;
};
bool CMP(Employee* e1, Employee* e2){
if(e1->rating != e2->rating) return e1->rating < e2->rating; // prioritize lesser rating
return e1->salary > e2->salary; // prioritize more salary if rating is same
}
int ComputeSavings(Employee* root, int k){
if(!root) {
return 0;
}
if(root->role == Employee::IC) return 0;
int savings=0;
std::sort(root->directReports.begin(), root->directReports.end(), CMP);
for(int i=0; i<root->directReports.size() && i<k; i++)
savings += root->directReports[i]->salary;
for(int i=0; i<root->directReports.size(); i++)
savings += ComputeSavings(root->directReports[i], k);
return savings;
}
int main() {
map<int, Employee*> empMap;
freopen("input.txt", "r", stdin);
// Read inputs
// Exit if id = 0
int id;
while(scanf("%d", &id), id) {
char name[100];
scanf("%s", name);
int mgr_id;
scanf("%d", &mgr_id);
int salary;
scanf("%d", &salary);
int rating;
scanf("%d", &rating);
Employee* emp = new Employee(id,string(name),mgr_id,rating,salary);
empMap[id]=emp;
}
// Fix role and add direct reports for managers
for(map<int, Employee*>::iterator it = empMap.begin(); it != empMap.end(); ++it){
if((it->second)->mgr_id != -1) {
empMap[(it->second)->mgr_id]->role = Employee::Manager;
empMap[(it->second)->mgr_id]->addDirectReports(it->second);
}
}
cout << "Savings: " << ComputeSavings(empMap[2], 1) << endl;
// Free memory
for(map<int, Employee*>::iterator it = empMap.begin(); it != empMap.end(); ++it){
Employee* emp = it->second;
delete emp;
}
return 0;
}
// Test case
// Format: Emp_id name manager_id salary rating
1 ROOT -1 -1 -1
2 CEO 1 100 5
3 VP1 2 10 3
4 VP2 2 20 2
5 A1 3 5 3
6 A2 3 6 3
7 B1 4 5 4
8 B2 4 8 2
0
A segment tree would give a better runtime. While adding employees to a manager, update the salary of employees recursively to the root. So that when we get rid of a node much closer to the root. We need not calculate the saving recursively under him.
- deegoy2 June 28, 2017