CareerCup

Seems like weighted graph is most suitable for data structure and finding max flow.

Time Complexity: O(n)

When some node is visted then compute net danger rank(NDR) and also add current node individual rank in the friend node net danger rank(NDR) then remove current node from the friendslist of friend .

for eg: if A has friends B and C
then acc to transitivity B also has friend A......
When you visit A then compute NDR of A with the help of its friends and also add A's IDR in B's NDR and remove A node from B's Friend List. So need of visiting A again while computing NDR for B.

public class PrisionerVO {
	
	private int idr;
	private int ndr;
	
	private List<Character> friendList;

	public int getNdr() {
		return ndr;
	}

	public void setNdr(int ndr) {
		this.ndr = ndr;
	}

	public int getIdr() {
		return idr;
	}

	public void setIdr(int idr) {
		this.idr = idr;
	}

	public List<Character> getFriendList() {
		return friendList;
	}

	public void setFriendList(List<Character> friendList) {
		this.friendList = friendList;
	}
	
	@Override
	public String toString() {
		
		return "\tIndividual Danger Rank:"+ idr +"\nNet Danger Rank:" + ndr+ "\nFriend List:"+ friendList+"\n---------------\n\n";
	}
	
}

public Character computerMaxDangerRank(Map<Character,PrisionerVO> prisionerMap){
		Set<Character> keySet = prisionerMap.keySet();
		
		int maxDR = 0;
		Character maxDRPrisioner = null;
		//key is prisionerName
		for(Character key:keySet){
			PrisionerVO currPrisioner = prisionerMap.get(key);
			List<Character> friendList = currPrisioner.getFriendList();
			
			//idr is individual danger rank
			int idr = currPrisioner.getIdr();
			
			//ndr is net danger rank of a prisioner
			int ndr = idr;
			if(friendList!=null && friendList.size()!=0)
			{
				for(Character friend:friendList){
					PrisionerVO friendPrisioner = prisionerMap.get(friend);	
					
					friendPrisioner.setNdr(friendPrisioner.getNdr()+idr);
					//adding friend idr current ndr
					ndr= ndr +  friendPrisioner.getIdr();
					//removing the current node from the friends list 
					friendPrisioner.getFriendList().remove(key);
					//i++;
				}
			}
			ndr = ndr + currPrisioner.getNdr();
			currPrisioner.setNdr(ndr);				
			
			if(ndr>maxDR){
				maxDR=ndr;
				maxDRPrisioner = key;
			}
		}
		
		return maxDRPrisioner;
	}

Use the following data structure:

HashMap prisoners;

Class Prisoner {
	int dangerValue;
	int dangerRank;
	ArrayList friends;
}

N is the number of prisoners and V is the average number of friends for each prisoner.

To update the danger value of a prisoner, we need to update danger rank of its friends which takes O(V^2).

To find the most dangerous prisoner we iterate through the prisoner's list and retrieve the maximum which can be done in O(N).

Another solution is to sort the prisoners list by their danger rank. In this case, update is O(V*log(n) + V^2). Finding the most dangerous prisoner is O(1).

isn't it a union-find data structure problem??

Seems like Google PageRank Algorithm

the question is somewhat flawed. if you dont have to recompute the danger value, then how can u assure the danger value is right as the graph is built