Amazon Interview Question Software Engineers
Country: United States
Interview Type: Written Test
We'll use the example in the question:
A: B,C,D
D: B,E,F
E: C,F,G
Start with element A. Insert it into the graph
node * A = new node("A"); //Data of a node is the character A
Insert B,C & D as its childern
A->addChild(B); A->addChild(C); ...
Then we will repeat the process for A's childern.
Take the next child(say D).
Search the entire file for D. Since file is not sorted its a linear time operation O(n)
Insert D into graph and repeat for its childern.
Since its linear search time for every node:
Complexity would be ~ O(n + n + n ....n times) ~ O(n ^2)
Sample node of a graph:
struct node{
int data;
vector <node *>childern; //A Linked List would be equally fine
bool isVisited; //during BFS, check if the node has been visited
};
With our data in place, we will perform a BFS on the graph.
Since we want level (of association), we will use two queues:
Q1: to hold graph nodes
Q2: to hold association levels
I cannot draw the graph here, so I will leave the drawing of the graph to your imagination. To traverse the graph:
Start with A:
Enqueue it to Q1 and enqueue level of association 0 into Q2
Then repeat the following till Q1 is empty:
- Dequeue a node(N) from Q1 and the level(L) from Q2
- Enqueue all unvisited childern of N into Q1 with association level of L+1 and mark them visited
A sample run would look like this:
Q1: A D,C,B C,D D F,E G,F G NULL
Q2: 0 1,1,1 1,1 1 2,2 3,2 3 NULL
o/p by level of association:
level 0: A
level 1: B,C,D
level 2: E,F
level 3: G
Complexity analysis:
Initially creating a graph out of the text file ~ O(n ^ 2)
BFS search ~ O(n). So we can produce linear time results if we spend initial time and create a graph.
The solution seems good except the fact that creation of graph. I was thinking an option where we can avoid it. All we need to maintain is a queue for BSF and read the data from file directly. In case we want to avoid the File IO time we can load all data in a Map just like Key and value as list or string. Map look up time would be O(1) and there would be extra space complexity of O(k) where k << n
I like your idea of using a STL Map. The one obvious advantage I see is while in graph to start with node A, you would have to traverse the graph to find the actual node A; in Map you can directly start with node A.
However, beyond this both would be an ~O(n) solution since we would have to examine each node in turn.
The space complexity might be a little less in a graph since we're not storing each node and its children individually.
public void printFriendsByAssociation(File f, String friend) {
Map<String, List<String>> friendMap = new HashMap<String, String[]>();
//-- Make Map of String to List of Strings
if (f != null) {
Scanner sc = new Scanner(f);
while (sc.hasNextLine()) {
String s = sc.nextLine;
String key = s.split(":")[0];
String[] values = (s.split(":")[1].trim()).split(",");
friendMap.put(key, values);
}
int lvl = 1;
boolean commaNeeded = false;
Set<String> printedFriends = new HashSet<String>();
Queue<String> q1 = new LinkedList<String>();
Queue<String> q2 = new LinkedList<String>();
pushArrayContentsToQueue(q1, friendMap.get(friend));
while (!q1.isEmpty()) {
System.out.println("Level " + lvl + " - ");
String nextFriend = q.dequeue();
if (!printedFriends.contains(nextFriend)) {
if (commaNeeded) {
System.out.print("," + printedFriend);
}
else {
System.out.print(printedFriend);
}
pushArrayContentsToQueue(q2, friendMap.get(nextFriend));
printedFriends.add(nextFriend);
commaNeeded = true;
}
if (q1.isEmpty()) {
lvl++;
q1 = q2;
}
}
}
}
private void pushArrayContentsToQueue(Queue q, String[] arr) {
if (arr != null) {
for (int i = 0; i < arr.length; i++) {
q.enqueue(arr[i]);
}
}
}
Thoughts?
Hi Mike,
Your code will not produce the output in the format as per the question. you have kept the printing of "level" inside the while loop. So, for each item in the queue , it will print "Level" in a new line. Also, you need to swap q1 and q2. not just q1 = q2. And, you have not considered the extreme case like, what happens if a friend name appears on the left as well as on the right, like:
A:B,C,D
D:X,A
it may result in an endless loop.
I have also submitted the answer. Please check and comment.
public void printFriendsByAssociation(File f, String friend) {
Map<String, List<String>> friendMap = new HashMap<String, String[]>();
//-- Make Map of String to List of Strings
if (f != null) {
Scanner sc = new Scanner(f);
while (sc.hasNextLine()) {
String s = sc.nextLine;
String key = s.split(":")[0];
String[] values = (s.split(":")[1].trim()).split(",");
friendMap.put(key, values);
}
int lvl = 1;
boolean commaNeeded = false;
Set<String> printedFriends = new HashSet<String>();
Queue<String> q1 = new LinkedList<String>();
Queue<String> q2 = new LinkedList<String>();
pushArrayContentsToQueue(q1, friendMap.get(friend));
while (!q1.isEmpty()) {
System.out.println("Level " + lvl + " - ");
String nextFriend = q.dequeue();
if (!printedFriends.contains(nextFriend)) {
if (commaNeeded) {
System.out.print("," + printedFriend);
}
else {
System.out.print(printedFriend);
}
pushArrayContentsToQueue(q2, friendMap.get(nextFriend));
printedFriends.add(nextFriend);
commaNeeded = true;
}
if (q1.isEmpty()) {
lvl++;
q1 = q2;
}
}
}
}
private void pushArrayContentsToQueue(Queue q, String[] arr) {
if (arr != null) {
for (int i = 0; i < arr.length; i++) {
q.enqueue(arr[i]);
}
}
}
public void printFriendsByAssociation(File f, String friend) {
Map<String, List<String>> friendMap = new HashMap<String, String[]>();
//-- Make Map of String to List of Strings
if (f != null) {
Scanner sc = new Scanner(f);
while (sc.hasNextLine()) {
String s = sc.nextLine;
String key = s.split(":")[0];
String[] values = (s.split(":")[1].trim()).split(",");
friendMap.put(key, values);
}
int lvl = 1;
boolean commaNeeded = false;
Set<String> printedFriends = new HashSet<String>();
Queue<String> q1 = new LinkedList<String>();
Queue<String> q2 = new LinkedList<String>();
pushArrayContentsToQueue(q1, friendMap.get(friend));
while (!q1.isEmpty()) {
System.out.println("Level " + lvl + " - ");
String nextFriend = q.dequeue();
if (!printedFriends.contains(nextFriend)) {
if (commaNeeded) {
System.out.print("," + printedFriend);
}
else {
System.out.print(printedFriend);
}
pushArrayContentsToQueue(q2, friendMap.get(nextFriend));
printedFriends.add(nextFriend);
commaNeeded = true;
}
if (q1.isEmpty()) {
lvl++;
q1 = q2;
}
}
}
}
private void pushArrayContentsToQueue(Queue q, String[] arr) {
if (arr != null) {
for (int i = 0; i < arr.length; i++) {
q.enqueue(arr[i]);
}
}
}
Thoughts?
graph = {'A':['B','C','D'],'D':['B','E','F'],'E':['C','F','G']}
def levelFrind(graph):
if graph==None:
return
output = []
count = 1
# currOutput = []
queue = sorted(graph.keys())
for key in queue:
currOutput = []
for value in graph[key]:
label = True
for i in range(len(output)):
if value in output[i] and label:
label = False
if label:
currOutput.append(value)
print 'the level is %d' % count
print currOutput
count +=1
output.append(currOutput)
return output
Ouput =levelFrind(graph)
print Ouput
Consider this a graph and complete a BFS. At each vertex/node, track whether the position has already been visited. Complexity O(nm), memory O(nm) where n is the number of vertices and m is the average number of 'friend' connections.
static class Person{
String name;
String Person[] friends;
String visited = false;
public Person(String name){
this.name = name;
}
public void setFriends(Person[] friends){
this.friends = friends;
}
public void setVisited(boolean visited){
this.visited = visited;
}
public String getName(){
return this.name;
}
public Person[] getFriends(){
return this.friends;
}
public boolean isVisited(){
return this.visited;
}
public int hashCode(){
return this.name.hashCode();
}
public boolean equals(Object o){
if(o instanceof Person){
return this.name.equals(o.name);
}
return false;
}
}
public static void printFriendLevels(File file, String personName){
HashMap<String, Person> personMap = new HashMap<String, Person>();
//build up the Person graph from the file
BufferedReader in = null;
try{
in = new BufferedReader(new FileReader(file));
String line = null;
while( (line = in.readLine) != null){
String name = line.substring(0, line.indexof(':'));
Person person = personMap.get(name);
if(person == null){
person = new Person(name);
personMap.put(name, person);
}
ArrayList<String> friendNames = getFriendNames(line);
Person[] friends = new Person[friendNames.size()];
for(int i = 0; i < friendNames.size(); i++){
String friendName = friendNames[i];
Person friend = personMap.get(friendName);
if(friend == null){
friend = new Person(friendName);
personMap.put(friendName, friend);
}
friends[i] = friend;
}
person.setFriends(friends);
}
}
catch(IOException e){
e.printStackTrace();
java.lang.System.err.println("Failed");
}
finally{
if(in != null){
try{
in.close();
}
catch(IOException e){
//do nothing
}
}
}
//do BFS search on the contents
ArrayList<Person> currentLevel = new ArrayList<Person>();
ArrayList<Person> nextLevel = new ArrayList<Person>();
ArrayList<Person> temp;
{
Person person = personMap.get(personName);
if(person == null){
return null;
}
currentLevel.add(person);
}
final StringBuilder line = new StringBuilder();
line.append("Level ");
final String dash = " -";
int count = 1;
while(!currentLevel.isEmpty()){
line.setLength(6);
line.append(count++);
line.append(dash);
for(Person person : currentLevel){
line.append(person.getName());
line.append(',');
for(Person friend : person.getFriends()){
if(!friend.isVisited()){
nextLevel.add(friend);
friend.setVisited(true);
}
}
}
java.lang.System.out.println(line.toString());
currentLevel.clear();
temp = currentLevel;
currentLevel = nextLevel;
nextLevel = currentLevel;
}
}
private static ArrayList<String> getFriendNames(String str){
int start = str.indexof(":") + 2;
ArrayList<String> names = new ArrayList<String>();
int pos = start;
while(pos < str.length()){
if(str.charAt(pos) == ','){
names.add(str.subString(start, pos));
start = pos + 1;
}
pos++;
}
return names;
}
Yes this is in fact a BFS traversal.
public static List<List<string>> GetFriendLevels(Dictionary<string, List<string>> friends, string person)
{
var q = new Queue<string>();
var hs = new HashSet<string>();
var result = new List<List<string>>();
q.Enqueue(friend);
q.Enqueue(null);
hs.Add(friend);
List<string> cl = new List<string>();
while(q.Count > 0)
{
string cur = q.Dequeue();
if(cur == null)
{
result.Add(cl);
cl = new List<string>();
if(q.Count != 0)
{
q.Enqueue(null);
}
}
else
{
cl.Add(f);
foreach(string f in friends[cur])
{
if(!hs.Contains(f)
{
q.Enqueue(f);
hs.Add(f);
}
}
}
}
// Removing the first level wish is itself
result.Remove(0);
return result;
}
package inhouse.project;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class FriendsAssociation {
public static void main(String[] args) {
File f = new File("c:\\Users\\amitabh\\Desktop\\friends.txt");
//calling method for calculating association
printFriendsByAssociationLevel(f,"A");
}
public static void printFriendsByAssociationLevel(File f, String friend){
if(f==null){
System.out.println("Unable to read");
}
else{
Map<String, String[]> fmap = new HashMap<String,String[]>();
Scanner scanHandle = null;
try {
scanHandle = new Scanner(f);
while(scanHandle.hasNext()){
String s = scanHandle.nextLine();
String[] kv = s.split(":");
String key = kv[0];
String[] values = kv[1].split(",");
fmap.put(key, values);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int level = 1;
boolean needComma = false;
Set<String> hasPrinted = new HashSet<String>();
hasPrinted.add(friend);
Queue<String> q1 = new LinkedList<String>();
Queue<String> q2 = new LinkedList<String>();
Queue<String> temp = new LinkedList<String>();
pushToQueue(q1,fmap.get(friend),hasPrinted);
System.out.println("Level:"+ level);
while(!q1.isEmpty()){
String aFriend = q1.remove();
if(!hasPrinted.contains(aFriend)){
if(!needComma){
System.out.print(aFriend);
needComma = true;
}
else{
System.out.print(","+aFriend);
}
pushToQueue(q2, fmap.get(aFriend),hasPrinted);
hasPrinted.add(aFriend);
}
if(q1.isEmpty()){
level++;
temp = q1;
q1 = q2;
q2 = temp;
needComma = false;
System.out.println();
if(!q1.isEmpty()){
System.out.println("Level:"+ level);
}
}
}
}
}
public static void pushToQueue(Queue<String> q,String[] s, Set<String> has){
if(s!=null){
for(int var = 0; var < s.length; var++ ){
if(!has.contains(s[var])){
q.add(s[var]);
}
}
}
}
}
This is an interesting question. At first glance, this is a graph search, either BFS or DFS. On another thought, the input stream seems already indexed, more like a NoSQL table input, or stream data in HDFS. Consider this is an Amazon question, you should consider this question as a big data question with inputs from distributed file systems.
The solution is just a simple key based inquiry with concurrent threads.
Implement using asynchronized tasks, then aggregate and deduplicate on the results returned from tasks based on the level of associations.
I believe this answer is what Amazon wants. If you go with the graph approach, you will enter the interviewer's trap, then he will follow up with memory limitation etc questions.
The first step to any interviewing question is to ask about the size of the data. At that point, you, as an interviewer, would know if this is a big data issue or not. Since there is no dialog in these questions and the question doesn't volunteer that information, it's reasonable to go with the strictly graphing approach.
Alternatively, you could demonstrate your supposed prowess and code up a complete and bug-free distributed graphing algorithm in 30-40 minutes like the average length of a technical interview.
public static void levelOrder (String start , Map<String,List<String>> graph){
Queue<String> q = new LinkedList<> ();
q.add(start) ;
HashSet<String> visited = new HashSet<> ();
int level = 1 ;
while (!q.isEmpty()) {
String cur = q.poll() ;
if (graph.containsKey(cur)) {
System.out.print("Level " + level + " - ");
for (int i = 0 ; i < graph.get(cur).size() ;++i) {
String next = graph.get(cur).get(i) ;
if (!visited.contains(next)) {
if (i != graph.get(cur).size() - 1) {
System.out.print(next + ",");
} else {
System.out.print(next);
}
visited.add(next) ;
q.add(next) ;
}
}
System.out.println();
level++;
}
}
}
Assuming parsing from the file is trivial i am avoiding that part. But other than that its basically processing an adjacencyList in a BFS fashion. Below is my solution.
public Map<Integer, List<String>> levelCalulator(Map<String, List<String>> adjacentMap, String root)
{
Map<Integer, List<String>> levelMap = new HashMap<>();
List<String> levelList = new ArrayList<>();
Set<String> visitedNode = new HashSet<>();
int level = 0;
levelMap.put(level, Arrays.asList(root));
levelList = levelMap.get(0);
visitedNode.add(root);
while (levelList.size() != 0)
{
levelList = constructNextLevelList(levelList, visitedNode, adjacentMap);
if(levelList.size() != 0)
{
level++;
levelMap.put(level, levelList);
}
}
return levelMap;
}
private List<String> constructNextLevelList(List<String> levelList, Set<String>visitedNode, Map<String, List<String>> adjacentMap)
{
List<String> resultList = new ArrayList();
for (String node : levelList) {
if(adjacentMap.containsKey(node))
{
for (String childNode : adjacentMap.get(node)) {
if(!visitedNode.contains(childNode))
{
resultList.add(childNode);
visitedNode.add(childNode);
}
}
}
}
return resultList;
}
public Map<Integer, List<String>> levelCalulator(Map<String, List<String>> adjacentMap, String root)
{
Map<Integer, List<String>> levelMap = new HashMap<>();
List<String> levelList = new ArrayList<>();
Set<String> visitedNode = new HashSet<>();
int level = 0;
levelMap.put(level, Arrays.asList(root));
levelList = levelMap.get(0);
visitedNode.add(root);
while (levelList.size() != 0)
{
levelList = constructNextLevelList(levelList, visitedNode, adjacentMap);
if(levelList.size() != 0)
{
level++;
levelMap.put(level, levelList);
}
}
return levelMap;
}
private List<String> constructNextLevelList(List<String> levelList, Set<String>visitedNode, Map<String, List<String>> adjacentMap)
{
List<String> resultList = new ArrayList();
for (String node : levelList) {
if(adjacentMap.containsKey(node))
{
for (String childNode : adjacentMap.get(node)) {
if(!visitedNode.contains(childNode))
{
resultList.add(childNode);
visitedNode.add(childNode);
}
}
}
}
return resultList;
}
Assuming the file parsing part is trivial, this is a straightforward solution of parsing the adjacencyList of a graph in a BFS fashion. Here is my soultion. surely can be better.
import java.util.*;
public class FriendLevelFinder{
public Map<Integer, List<String>> levelCalulator(Map<String, List<String>> adjacentMap, String root)
{
Map<Integer, List<String>> levelMap = new HashMap<>();
List<String> levelList = new ArrayList<>();
Set<String> visitedNode = new HashSet<>();
int level = 0;
levelMap.put(level, Arrays.asList(root));
levelList = levelMap.get(0);
visitedNode.add(root);
while (levelList.size() != 0)
{
levelList = constructNextLevelList(levelList, visitedNode, adjacentMap);
if(levelList.size() != 0)
{
level++;
levelMap.put(level, levelList);
}
}
return levelMap;
}
private List<String> constructNextLevelList(List<String> levelList, Set<String>visitedNode, Map<String, List<String>> adjacentMap)
{
List<String> resultList = new ArrayList();
for (String node : levelList) {
if(adjacentMap.containsKey(node))
{
for (String childNode : adjacentMap.get(node)) {
if(!visitedNode.contains(childNode))
{
resultList.add(childNode);
visitedNode.add(childNode);
}
}
}
}
return resultList;
}
public static void main(String[] args) {
FriendLevelFinder friends = new FriendLevelFinder();
Map<String, List<String>> adjMap = new HashMap<>();
adjMap.put("A", Arrays.asList("B", "C", "D"));
adjMap.put("D", Arrays.asList("B", "E", "F"));
adjMap.put("E", Arrays.asList("C", "F", "G"));
Map<Integer, List<String>> levels = friends.levelCalulator(adjMap, "A");
System.out.println(levels);
}
}
This is my source code.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Problem10 {
public static void main(String[] args) {
Map<String, List<String>> listRelationShip = new HashMap<String, List<String>>();
addRelationship(listRelationShip, "A: B,C,D ");
addRelationship(listRelationShip, "D: B,E,F ");
addRelationship(listRelationShip, "E: C,F,G ");
listRelation(listRelationShip, "A");
}
private static void listRelation(Map<String, List<String>> listRelationShip, String person){
Set<String> ignoreList = new HashSet<String>();
List<String> currentLevel = new ArrayList<String>();
List<String> nextLevel = new ArrayList<String>();
int level = 1;
nextLevel.add(person);
while(nextLevel.size()>0) {
currentLevel = new ArrayList<String>();
for (String str: nextLevel){
if(listRelationShip.get(str)!=null && listRelationShip.get(str).size()>0){
currentLevel.addAll(listRelationShip.get(str));
}
ignoreList.add(str);
}
boolean first = true;
for (String str: currentLevel) {
if (!ignoreList.contains(str)){
if(first) {
System.out.print("Level " + level +" -");
first = false;
}
System.out.print(str + ",");
}
}
System.out.println();
nextLevel = new ArrayList<String>();
for (String str: currentLevel){
if (!ignoreList.contains(str)){
nextLevel.add(str);
}
}
level++;
}
}
private static void addRelationship(Map<String, List<String>> listRelationShip, String value ){
String[] relation = value.split(":");
List<String> arrList = new ArrayList<String>();
String[] arr = relation[1].split(",");
for(String str:arr){
arrList.add(str.trim());
}
listRelationShip.put(relation[0], arrList);
}
}
This is my source code to solve this problem.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Problem10 {
public static void main(String[] args) {
Map<String, List<String>> listRelationShip = new HashMap<String, List<String>>();
addRelationship(listRelationShip, "A: B,C,D ");
addRelationship(listRelationShip, "D: B,E,F ");
addRelationship(listRelationShip, "E: C,F,G ");
listRelation(listRelationShip, "A");
}
private static void listRelation(Map<String, List<String>> listRelationShip, String person){
Set<String> ignoreList = new HashSet<String>();
List<String> currentLevel = new ArrayList<String>();
List<String> nextLevel = new ArrayList<String>();
int level = 1;
nextLevel.add(person);
while(nextLevel.size()>0) {
currentLevel = new ArrayList<String>();
for (String str: nextLevel){
if(listRelationShip.get(str)!=null && listRelationShip.get(str).size()>0){
currentLevel.addAll(listRelationShip.get(str));
}
ignoreList.add(str);
}
boolean first = true;
for (String str: currentLevel) {
if (!ignoreList.contains(str)){
if(first) {
System.out.print("Level " + level +" -");
first = false;
}
System.out.print(str + ",");
}
}
System.out.println();
nextLevel = new ArrayList<String>();
for (String str: currentLevel){
if (!ignoreList.contains(str)){
nextLevel.add(str);
}
}
level++;
}
}
private static void addRelationship(Map<String, List<String>> listRelationShip, String value ){
String[] relation = value.split(":");
List<String> arrList = new ArrayList<String>();
String[] arr = relation[1].split(",");
for(String str:arr){
arrList.add(str.trim());
}
listRelationShip.put(relation[0], arrList);
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Problem10 {
public static void main(String[] args) {
Map<String, List<String>> listRelationShip = new HashMap<String, List<String>>();
addRelationship(listRelationShip, "A: B,C,D ");
addRelationship(listRelationShip, "D: B,E,F ");
addRelationship(listRelationShip, "E: C,F,G ");
listRelation(listRelationShip, "A");
}
private static void listRelation(Map<String, List<String>> listRelationShip, String person){
Set<String> ignoreList = new HashSet<String>();
List<String> currentLevel = new ArrayList<String>();
List<String> nextLevel = new ArrayList<String>();
int level = 1;
nextLevel.add(person);
while(nextLevel.size()>0) {
currentLevel = new ArrayList<String>();
for (String str: nextLevel){
if(listRelationShip.get(str)!=null && listRelationShip.get(str).size()>0){
currentLevel.addAll(listRelationShip.get(str));
}
ignoreList.add(str);
}
boolean first = true;
for (String str: currentLevel) {
if (!ignoreList.contains(str)){
if(first) {
System.out.print("Level " + level +" -");
first = false;
}
System.out.print(str + ",");
}
}
System.out.println();
nextLevel = new ArrayList<String>();
for (String str: currentLevel){
if (!ignoreList.contains(str)){
nextLevel.add(str);
}
}
level++;
}
}
private static void addRelationship(Map<String, List<String>> listRelationShip, String value ){
String[] relation = value.split(":");
List<String> arrList = new ArrayList<String>();
String[] arr = relation[1].split(",");
for(String str:arr){
arrList.add(str.trim());
}
listRelationShip.put(relation[0], arrList);
}
}
//A simple javascript code
function findFriends(f){
var result = {},level = 1,i,j,k = [],af = [], nf = [],temp = [];
result['Level 1'] = friends[f];
af = af.concat(friends[f]);
temp = temp.concat(friends[f]);
while(temp.length != 0){
nf = temp.slice(0);
temp = [];
for (i = 0; i < nf.length; i++) {
if(friends[nf[i]]){
for(j = 0; j < friends[nf[i]].length; j++){
if(af.indexOf(friends[nf[i]][j]) == -1){
k.push(friends[nf[i]][j]);
}
}
}
}
af = af.concat(k);
temp = k;
if(k.length == 0){
continue;
}
level++;
result['Level' + level] = k;
k = [];
}
return result;
}
console.log(findFriends('A'));
console.log(findFriends('D'));
console.log(findFriends('E'));
//A simple javascript code
function findFriends(f){
var result = {},level = 1,i,j,k = [],af = [], nf = [],temp = [];
result['Level 1'] = friends[f];
af = af.concat(friends[f]);
temp = temp.concat(friends[f]);
while(temp.length != 0){
nf = temp.slice(0);
temp = [];
for (i = 0; i < nf.length; i++) {
if(friends[nf[i]]){
for(j = 0; j < friends[nf[i]].length; j++){
if(af.indexOf(friends[nf[i]][j]) == -1){
k.push(friends[nf[i]][j]);
}
}
}
}
af = af.concat(k);
temp = k;
if(k.length == 0){
continue;
}
level++;
result['Level' + level] = k;
k = [];
}
return result;
}
console.log(findFriends('A'));
console.log(findFriends('D'));
console.log(findFriends('E'));
package com.loadgeneral.projects;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Set;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.Queue;
import java.util.LinkedList;
public class FriendsGraph {
static class Node {
String name;
List<Node> friends = new ArrayList<Node>();
Node(String n) {
name = n;
}
}
Map<String,Node> graph = new HashMap<String,Node>();
FriendsGraph( String fileName ) {
String line;
try ( BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
while ( (line = rdr.readLine()) != null ) {
parseLine(line);
}
}
catch ( IOException ioe) {
System.err.println("error: " + ioe);
}
}
Node findNode(String name ){
Node n = graph.get(name);
if ( n == null ) {
n = new Node(name);
graph.put(name,n);
}
return n;
}
void parseLine(String line) {
int idx = line.indexOf(":");
String name = line.substring(0,idx).trim();
Node n = findNode(name);
String[] friends = line.substring(idx+1).split(",");
for( String f: friends) {
String friendName = f.trim();
Node friendNode = findNode(friendName);
n.friends.add(friendNode);
}
}
void processNode(Node node, Queue<Node> q, int level, Set<String> visited, Map<Integer, Set<String>> friendLevelMap){
for (Node n : node.friends) {
if ( ! visited.contains(n.name) ) {
Set<String> levelFriends = friendLevelMap.get(level);
if (levelFriends == null) {
levelFriends = new HashSet<String>();
friendLevelMap.put(level, levelFriends);
}
visited.add(n.name);
q.add(n);
levelFriends.add(n.name);
System.err.println(node.name + " adding: " + n.name);
}
}
}
Map<Integer, Set<String>> bfsFriends(Node node) {
int level = 1;
Map<Integer, Set<String>> friendLevelMap = new TreeMap<Integer, Set<String>>();
Set<String> visited = new HashSet<String>();
Queue<Node> q1 = new LinkedList<Node>();
Queue<Node> q2 = new LinkedList<Node>();
q1.add(node);
visited.add(node.name);
while ( !q1.isEmpty() || !q2.isEmpty() ) {
while ( !q1.isEmpty() ) {
node = q1.remove();
System.err.println("q1 removing node: " + node.name);
processNode(node, q2,level,visited,friendLevelMap);
}
++level;
while ( !q2.isEmpty() ) {
node = q2.remove();
processNode(node, q1,level,visited,friendLevelMap);
System.err.println("q2 removing node: " + node.name);
}
++level;
}
return friendLevelMap;
}
void printFriends ( String person ) {
Map<Integer,Set<String>> friendsLevel = bfsFriends( graph.get(person) ) ;
for ( Map.Entry<Integer,Set<String>> e: friendsLevel.entrySet() ) {
System.err.println( "Level " + e.getKey() + " - " + e.getValue() );
}
}
public static void main(String[] args) {
String fileName = args[0];
String person = args[1];
FriendsGraph g = new FriendsGraph(fileName);
g.printFriends(person);
}
}
I've figured out using hashtable and recursion concept.
private Map<Character, Integer> levels = new HashMap<>();
private Map<Character, char[]> friends = new HashMap<>();
public FindFriendship() {
friends.put('A', new char[] { 'B', 'C', 'D' });
friends.put('B', new char[] {});
friends.put('C', new char[] {});
friends.put('D', new char[] { 'B', 'E', 'F' });
friends.put('E', new char[] { 'C', 'F', 'G' });
}
public Map<Character, Integer> find(char text) {
buildFriendship(text, 1);
return levels;
}
private void buildFriendship(char text, int level) {
if (friends.containsKey(text)) {
for (char c : friends.get(text)) {
if (!levels.containsKey(c)) {
levels.put(c, level);
}
}
for (char c : friends.get((text))) {
buildFriendship(c, level + 1);
}
}
}
Oookay I think BFS traversal will work. However for that we would need to convert the file into a graph and then perform the BFS on it.
- puneet.sohi June 24, 2015