## unknown Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can solve this as quickly as you can read the list of prisoners and the list of friends (O(n)).

Each prisoner has an individual danger score (ids) which is known and a net danger score (nds) which is unknown. Thus

``````class prisoner{
int ids
int nds
void prisoner(int danger){
ids=danger
nds=danger
}
}``````

Friendship is symmetric. Thus every time you find out "A is friends with B" you simply do A.nds+=B.ids and B.nds+=A.ids. Every time you do this, see if either A.nds or B.nds is greater than the current record for "highest nds.

Book-keeping note: The friendship list may contain redundant information. Eg finding out "A is friends with B and B is friends with A will cause you to add their scores twice. A fortiori if everything is redundantly listed then this algo will still find the most dangerous prisoner, but everyone's nds will be inflated 2x.

Comment hidden because of low score. Click to expand.
0

This is still O(n^2) with slight optimization

Comment hidden because of low score. Click to expand.
0

@Skor: this is essentially as fast as reading the list of prisoners and their friends. What maore do you want? And it's O(n), not O(n^2).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The time complexity is not actually O(n^2). Its O(VE) where V = # of vertices (or the prisoners in this case) and E = # of edges (friendship between prisoners). There is no better way that visiting each vertex(prisoner) and each edge(friendship) to solve this.

Comment hidden because of low score. Click to expand.
0

You mean it's O(V + E). Cause if it's O(VE) then there are better ways.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.