unknown Interview Question
- 0of 0 votes
You'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 February 03, 2015 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
Open Chat in New Window