Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
#include <iostream>
#include <vector>
#include <utility>
#include <string>
using namespace std;
class prison{
private:
int rank;
string name;
int totalrank;
std::vector<prison> friends;
public:
void compute_rank();
prison(std::string name,int,std::vector<prison>);
//~prison();
inline std::string getName(){return this->name;}
inline int getRank(){return this->rank;}
inline int getTotal(){return this->totalrank;}
inline std::vector<prison> getFriends(){return this->friends;}
void print();
};
prison::prison(std::string name,int rank,std::vector<prison> friends){
this->name = name;
this->friends = friends;
this->rank = rank;
}
void prison::print(){
cout<<"Prisoner Name: "<<this->name<<" Rank: "<< this->rank<<endl;
cout<<"Prisoner Friends: \n"<<"Name\tRank: "<<endl;
for(auto f : this->friends){
cout<<f.name<<"\t"<< f.rank<<endl;
}
cout<<endl;
}
void prison::compute_rank(){
this->totalrank = this->rank;
for(auto e : friends){
totalrank+=e.rank;
}
}
void find_most_dangerous(std::vector<prison> p){
std::pair<int,std::string> mdp;
p[0].compute_rank();
mdp = make_pair(p[0].getTotal(), p[0].getName());
for(auto e : p){
e.compute_rank();
if(e.getTotal() > mdp.first){
mdp = make_pair(e.getTotal(),e.getName());
}else{
continue;
}
}
cout<<"Most Dangerous prisoner: " << mdp.second << " rank : "<<mdp.first<<endl;
}
int main(){
std::vector<prison> b;
prison a("A", 21, b);
b.push_back(a);
prison c("B", 44, b);
b.push_back(c);
prison d("D", 10, b);
b.push_back(d);
prison ds("DS", 10, b);
for(auto f : b){
f.print();
}
find_most_dangerous(b);
return 0;
}
Each prisoner`s rank can be represented by a node and his friends can be depicted by adjoining nodes.
- abhinav bansal February 12, 2015hashmap with key=prisoner : value = Danger rank
Do BFS
for each node hashmap[prisoner]= rank + rank of directly connected nodes
return hashmap
Now this will work only if graph is connected, which if we take kevin bacon`s consideration, every prisoner should be connected to every prisoner