Interview Question
xyzsCountry: India
Interview Type: Written Test
static Map<String,List<String>> _data = new HashMap<String,List<String>>();
static
{
_data.put("Nick Fury",Arrays.asList( "Tony Stark","Maria Hill","Norman Osborn"));
_data.put("Hulk",Arrays.asList("Tony Stark","HawkEye","Rogers"));
_data.put("Rogers",Arrays.asList("Thor"));
_data.put("Tony Stark",Arrays.asList("Pepper Potts","Nick Fury"));
_data.put("Agent 13",Arrays.asList("Agent-X","Nick Fury","Hitler"));
_data.put("Thor",Arrays.asList("HawkEye","BlackWidow"));
_data.put("BlackWidow",Arrays.asList("Hawkeye"));
_data.put("Maria Hill",Arrays.asList("Hulk","Rogers","Nick Fury"));
_data.put("Agent-X",Arrays.asList("Agent 13","Rogers"));
_data.put("Norman Osborn",Arrays.asList("Tony Stark","Thor"));
}
static Set<String> _shield = new HashSet<String>();
static Set<String> _hydra = new HashSet<String>();
public static void main(String[] args)
{
filterShieldAgents("Nick Fury");
filterHydraAgents();
System.out.println("Shield Agents----->"+_shield);
System.out.println("Hydra Agents----->"+_hydra);
}
public static void filterShieldAgents(String _rootAgent)
{
List<String> _agents = _data.get(_rootAgent);
if(_agents==null || _shield.contains(_rootAgent))
{
return;
}
_shield.add(_rootAgent);
for(int i=0;i<_agents.size();i++)
{
filterShieldAgents(_agents.get(i));
}
_data.remove(_rootAgent);
}
public static void filterHydraAgents()
{
Iterator<String> _msItr = _data.keySet().iterator();
while(_msItr.hasNext())
{
String _agent = _msItr.next();
_hydra.add(_agent);
List _agents = new ArrayList<String>(_data.get(_agent));
_agents.removeAll(_shield);
_hydra.addAll(_agents);
}
}
class Program
{
static void Main(string[] args)
{
string[] rawData = {"Nick Fury : Tony Stark, Maria Hill, Norman Osborn",
"Tony Stark: Pepper Potts, Nick Fury",
"Maria Hill : Hulk, Rogers, Nick Fury",
"Hulk : Tony Stark, HawkEye, Rogers",
"Norman Osborn: Tony Stark, Thor",
"Rogers : Thor",
"Agent 13 : Agent-X, Nick Fury, Hitler",
"Thor: HawkEye, BlackWidow",
"BlackWidow:Hawkeye",
"Agent-X : Agent 13, Rogers"
};
var agent = new AgentFilter(rawData, "Nick Fury");
Console.WriteLine(String.Join(",", agent.Hydra));
Console.Read();
}
}
public class AgentFilter
{
private IDictionary<string, IList<string>> data;
public AgentFilter(string[] rawData,string rootAgent)
{
Load(rawData);
GetAgentTrustedBy(rootAgent);
GetHydra();
}
private void Load(string[] rawData)
{
data = new Dictionary<string, IList<string>>();
foreach (var d in rawData)
{
string[] senderAndReceiver = d.Split(':');
IList<string> receiver = senderAndReceiver[1].Split(',');
if (!data.ContainsKey(senderAndReceiver[0].Trim()))
{
data.Add(senderAndReceiver[0].Trim(), receiver.Select(x=>x.Trim()).ToList<string>());
}
}
}
private void GetAgentTrustedBy(string agent)
{
if (!Shield.Contains(agent))
Shield.Add(agent);
else
return;
if (data.ContainsKey(agent)) {
foreach (var trustedAgent in data[agent])
GetAgentTrustedBy(trustedAgent);
data.Remove(agent);
}
}
private void GetHydra()
{
foreach (var sender in data)
foreach(var hydra in sender.Value)
if(!Shield.Contains(hydra))
Hydra.Add(hydra);
}
public IList<string> Shield = new List<string>();
public IList<string> Hydra = new List<string>();
}
class Program
{
static void Main(string[] args)
{
string[] rawData = {"Nick Fury : Tony Stark, Maria Hill, Norman Osborn",
"Tony Stark: Pepper Potts, Nick Fury",
"Maria Hill : Hulk, Rogers, Nick Fury",
"Hulk : Tony Stark, HawkEye, Rogers",
"Norman Osborn: Tony Stark, Thor",
"Rogers : Thor",
"Agent 13 : Agent-X, Nick Fury, Hitler",
"Thor: HawkEye, BlackWidow",
"BlackWidow:Hawkeye",
"Agent-X : Agent 13, Rogers"
};
var agent = new AgentFilter(rawData, "Nick Fury");
Console.WriteLine(String.Join(",", agent.Hydra));
Console.Read();
}
}
=============
public class AgentFilter
{
private IDictionary<string, IList<string>> data;
public AgentFilter(string[] rawData,string rootAgent)
{
Load(rawData);
GetAgentTrustedBy(rootAgent);
GetHydra();
}
private void Load(string[] rawData)
{
data = new Dictionary<string, IList<string>>();
foreach (var d in rawData)
{
string[] senderAndReceiver = d.Split(':');
IList<string> receiver = senderAndReceiver[1].Split(',');
if (!data.ContainsKey(senderAndReceiver[0].Trim()))
{
data.Add(senderAndReceiver[0].Trim(), receiver.Select(x=>x.Trim()).ToList<string>());
}
}
}
private void GetAgentTrustedBy(string agent)
{
if (!Shield.Contains(agent))
Shield.Add(agent);
else
return;
if (data.ContainsKey(agent)) {
foreach (var trustedAgent in data[agent])
GetAgentTrustedBy(trustedAgent);
data.Remove(agent);
}
}
private void GetHydra()
{
foreach (var sender in data)
foreach(var hydra in sender.Value)
if(!Shield.Contains(hydra))
Hydra.Add(hydra);
}
public IList<string> Shield = new List<string>();
public IList<string> Hydra = new List<string>();
}
class Program
{
static void Main(string[] args)
{
string[] rawData = {"Nick Fury : Tony Stark, Maria Hill, Norman Osborn",
"Tony Stark: Pepper Potts, Nick Fury",
"Maria Hill : Hulk, Rogers, Nick Fury",
"Hulk : Tony Stark, HawkEye, Rogers",
"Norman Osborn: Tony Stark, Thor",
"Rogers : Thor",
"Agent 13 : Agent-X, Nick Fury, Hitler",
"Thor: HawkEye, BlackWidow",
"BlackWidow:Hawkeye",
"Agent-X : Agent 13, Rogers"
};
var agent = new AgentFilter(rawData, "Nick Fury");
Console.WriteLine(String.Join(",", agent.Hydra));
Console.Read();
}
}
===============
public class AgentFilter
{
private IDictionary<string, IList<string>> data;
public AgentFilter(string[] rawData,string rootAgent)
{
Load(rawData);
GetAgentTrustedBy(rootAgent);
GetHydra();
}
private void Load(string[] rawData)
{
data = new Dictionary<string, IList<string>>();
foreach (var d in rawData)
{
string[] senderAndReceiver = d.Split(':');
IList<string> receiver = senderAndReceiver[1].Split(',');
if (!data.ContainsKey(senderAndReceiver[0].Trim()))
{
data.Add(senderAndReceiver[0].Trim(), receiver.Select(x=>x.Trim()).ToList<string>());
}
}
}
private void GetAgentTrustedBy(string agent)
{
if (!Shield.Contains(agent))
Shield.Add(agent);
else
return;
if (data.ContainsKey(agent)) {
foreach (var trustedAgent in data[agent])
GetAgentTrustedBy(trustedAgent);
data.Remove(agent);
}
}
private void GetHydra()
{
foreach (var sender in data)
foreach(var hydra in sender.Value)
if(!Shield.Contains(hydra))
Hydra.Add(hydra);
}
public IList<string> Shield = new List<string>();
public IList<string> Hydra = new List<string>();
}
HYPOTHESIS:
- Every agent can send message(s) to others
- A sender will send to only agent(s) who s/her trust.
=> Conclusion, if there is no one send a message to that agent s/he is considered as HYDRA.
Based on sample data we got the following tree of SHIELD:
-----------------------------
Nick Fury
|_Tony Stark
| |_Pepper Potts
| |_Nick Fury
|_Maria Hill
| |_Hulk
| | |_Tony Stark
| | |_HawkEye
| | |_Rogers
| | |_Thor
| | |_HawkEye
| | |_BlackWidow
| | |_Hawkeye
| |_Rogers
| |_Nick Fury
|_Norman Osborn
|_Tony Stark
|_Thor
List of agent not in a trusted tree (HYDRA):
-------------------------------------
Agent 13, Agent-X, Hitler
PROCESS STEPS:
- Get all agents from raw data.
- From root add trusted agent, based who s/he sent, to the tree.
- Filter out all trusted agent.
code using recreation to find members of hydra, I used daniel.a.p code for formatting the input data
def findSheldAgents(messages, shieldMember, shieldMembersSet):
if shieldMember in messages:
for agent in messages[shieldMember]:
if(agent not in shieldMembersSet):
shieldMembersSet.add(agent)
findSheldAgents(messages, agent, shieldMembersSet)
else:
return
return shieldMembersSet
def findHydraAgents(allMembersSet, shieldMembersSet):
print allMembersSet.difference(shieldMembersSet)
def uncover_hydra(communications, fury):
messages = dict()
for cmnt in communications:
_parse_communication(cmnt, messages)
shieldMembersSet = set()
shieldMembersSet = findSheldAgents(messages, fury, shieldMembersSet)
#print shieldMembersSet
allMembersSet = set()
for messageFromAgent in messages:
for agent in messages[messageFromAgent]:
allMembersSet.add(agent)
#print allMembersSet
findHydraAgents(allMembersSet, shieldMembersSet)
def _parse_communication(cmnt, messages):
msg = cmnt.split(':')
sender = msg[0].strip()
receivers = [ receiver.strip() for receiver in msg[1].split(',')]
# An adjacent list to be further used on the vertex navigation
messages[sender] = receivers
communication = [ "Nick Fury : Tony Stark, Maria Hill, Norman Osborn",
"Hulk : Tony Stark, HawkEye, Rogers",
"Rogers : Thor",
"Tony Stark: Pepper Potts, Nick Fury",
"Agent 13 : Agent-X, Nick Fury, Hitler",
"Thor: HawkEye, BlackWidow",
"BlackWidow:Hawkeye",
"Maria Hill : Hulk, Rogers, Nick Fury",
"Agent-X : Agent 13, Rogers",
"Norman Osborn: Tony Stark, Thor" ]
uncover_hydra(communication, "Nick Fury")
Very simple solution for this problem in python:
Just build adjacency around Nick Fury using recursive function:
communication = [ "Nick Fury : Tony Stark, Maria Hill, Norman Osborn",
"Hulk : Tony Stark, HawkEye, Rogers",
"Rogers : Thor",
"Tony Stark: Pepper Potts, Nick Fury",
"Agent 13 : Agent-X, Nick Fury, Hitler",
"Thor: HawkEye, BlackWidow",
"BlackWidow:Hawkeye",
"Maria Hill : Hulk, Rogers, Nick Fury",
"Agent-X : Agent 13, Rogers",
"Norman Osborn: Tony Stark, Thor" ]
prim_key = "Nick Fury";
abc = dict();
shield = [];
hydra =[];
for line in communication:
str = line.split(':');
keyval = str[0].strip()
abc[keyval] = str[1];
def addShields(key):
if key not in shield:
if key in abc.keys():
shield.append(key)
agents = abc[key].split(',')
for agent in agents:
agent = agent.strip()
addShields(agent)
def findHacker(prim):
addShields(prim)
for x in abc.keys():
if x not in shield:
hydra.append(x)
for hack in hydra:
print("HYDRA:", hack)
findHacker(prim_key)
Here's a Python Solution :
#Input stored in a Dictionary
dict = {'Nick Fury':['Tony Stark','Maria Hill','Norman Osborn'],
'Hulk':['Tony Stark','HawkEye','Rogers'],
'Rogers':['Thor'],
'Tony Stark':['Pepper Pots','Nick Fury'],
'Agent 13' : ['Agent-X', 'Nick Fury', 'Hitler'],
'Thor': ['HawkEye', 'BlackWidow'],
'BlackWidow':['HawkEye'],
'Maria Hill' : ['Hulk', 'Rogers', 'Nick Fury'],
'Agent-X' : ['Agent 13', 'Rogers'],
'Norman Osborn': ['Tony Stark', 'Thor']
}
def main():
tup = []
list_dict = []
flag = 0
'''creating an array of tuples for all the SHIELD members.
Every tuple has two elements : (SHIELD member name, Flag)
***Flag is set to 1 when the member name is visited i.e. becomes the key
in the dictionary such that its values are accessed'''
tup.append(('Nick Fury',1))
for el in dict['Nick Fury']:
tup.append((el,0))
for k,v in enumerate(tup):
if tup[k][1] == 0:
temp = list(tup[k])
temp[1] = 1
tup[k] = tuple(temp)
if tup[k][0] in dict.keys():
for el in dict[tup[k][0]]:
flag = 0
for item in tup:
if item[0] == el:
flag = 1
break
if flag == 0:
tup.append((el,0))
#Creating a list list_dict of all the unique SHIELD member names from the dictionary
for key in dict.keys():
for val in dict[key]:
if val not in list_dict:
list_dict.append(val)
#Extracting only names from the list of tuples into the list tup_names
tup_names, flag = zip(*tup)
tup_names = list(tup_names)
#Comparing the two lists and removing common names
for person in tup_names:
list_dict.remove(person)
print 'HYDRA MEMBERS:'
print list_dict
if __name__ == "__main__":
main()
This is a simple graph problem where each agent is a vertex. We will mark all vertexes that can be reached starting with Fury and whatever is left are the HYDRA agents.
- daniel.a.p February 28, 2015