Sai
BAN USER- -1of 1 vote
AnswerYou're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (who also have danger ranks). You'll need to go through the prison and find out the prisoner who has the highest danger rank (his own + all his friends)
- Sai in United States| Report Duplicate | Flag | PURGE
Algorithm Problem Solving - -1of 1 vote
AnswersYou're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (who also have danger ranks). You'll need to go through the prison and find out the prisoner who has the highest danger rank (his own + all his friends)
- Sai in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Problem Solving - 0of 0 votes
AnswersYou're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (prisoners, who also have danger ranks). The guard has a list of prisoners with their corresponding danger ranks and he also has a list of the friends of each of the prisoners in the prison.
- Sai in United States
The danger rank is computed as follows: Prisoner 1 has a danger value of 5, his friends are Prisoner 2 and Prisoner 5, who have danger values of 3 and 4 respectively. So the danger value of Prisoner 1 is 5+3+4 = 12.
There could be any number of prisoners. Whichever prisoner has the highest value is the most dangerous(computed using the above method).
Friendship can be assumed to be symmetric.
Come up with an efficient algorithm to find the most dangerous prisoner?
The solution I came up with runs in quadratic time.
A hash table which has the Prisoner as Key and list of his friends as value
Compute the sum of danger rank of all friends one key at a Time. (n * N)
Maintain a max count and update it as necessary.
I believe there is a solution for this problem having better time complexity than O(N^2).| Report Duplicate | Flag | PURGE
unknown Algorithm Problem Solving Puzzle - 0of 0 votes
AnswersYou're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (prisoners, who also have danger ranks). The guard has a list of prisoners with their corresponding danger ranks and he also has a list of the friends of each of the prisoners in the prison.
- Sai in United States
The danger rank is computed as follows: Prisoner 1 has a danger value of 5, his friends are Prisoner 2 and Prisoner 5, who have danger values of 3 and 4 respectively. So the danger value of Prisoner 1 is 5+3+4 = 12.
There could be any number of prisoners. Whichever prisoner has the highest value is the most dangerous(computed using the above method).
Friendship can be assumed to be symmetric.
Come up with an efficient algorithm to find the most dangerous prisoner?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Repcoragkemmer, Data Scientist at Bankbazaar
Have years of experience to treating variety of outpatients with modalities such as massage, exercise, paraffin, joint mobilization, mechanical traction ...