Interview Question for xyzs


Country: India
Interview Type: Written Test




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

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.

def uncover_hydra(communications, fury):
    messages = dict()
    
    for cmnt in communications:
        _parse_communication(cmnt, messages)
        
    print _find_hydra_agents(messages, fury)
    

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    


def _find_hydra_agents(agents_msg, fury):
    hydra, shield_agents, agents = set(), set(), [fury]
    
    while len(agents) > 0:
        # We get the next agent from the unvisited SHIELD agent set,
        # add him to the SHIELD list and then add all agents
        # this agent sent a message to to the unvisited SHIELD agent set.
        # We do this until there are no more SHIELD agents to visit.
        current = agents.pop()
        shield_agents.add(current)
        
        if current in agents_msg:
            for agent in agents_msg[current]:
                if agent not in shield_agents:
                    agents.append(agent)
    
    # We look for all agents in all communications and grab the ones
    # not in the SHIELD set.
    for sender in agents_msg.keys():
        if sender not in shield_agents:
            hydra.add(sender)
            
        for receiver in agents_msg[sender]:
            if receiver not in shield_agents:
                hydra.add(receiver) 
                
    return hydra
    
    
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")

- daniel.a.p February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Napster February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Chan February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Duplicate post.

- Chan February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Chan February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes
- Chan February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Chan February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can anyone explain me in python?

- reddygokul.i7 February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is simple implementation of DFS taking Nick Fury as the source.

- Anonymous February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right. More completely, any search (breadth or depth) originating in nick fury will find all the shield nodes. The rest would be the hydra nodes.

- gen-y-s February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi can any one give the algorithm please? dinakar

- reddygokul.i7 February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Chan February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we simply start with nick fury node and perform breadth or depth search to find all the shield nodes ( since all the shield nodes recieved an SOS that originated from nick fury, as the problem description specifies). The unvisited nodes after the search , are the hydra nodes.

- gen-y-s February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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")

- cshreyastech April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- gchauhan.blr September 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hitler is missing from your solution

- Shiv October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- PS September 08, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More