## Amazon Interview Question for Software Engineers

Country: United States
Interview Type: Written Test

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

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.

``````So the solution would broadly comprise  of:
A) Convert the file into a graph. Its a one time operation, once done we won't need to do it again.
B) Starting with the appropriate node in the graph, perform a BFS(using queues)``````

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

We'll use the example in the question:
A: B,C,D
D: B,E,F
E: C,F,G

node * A = new node("A"); //Data of a node is the character A
Insert B,C & D as its childern

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

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

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:

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``````

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

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

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

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.

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

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

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

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.

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

This is a simple BFS search of the graph.

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

This is a simple BFS of the graph

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

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

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

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

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.

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

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

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

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

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

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

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

``````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``````

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

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
try{
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;
}
}
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()){
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) == ','){
start = pos + 1;
}
pos++;
}
return names;
}``````

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

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);
List<string> cl = new List<string>();

while(q.Count > 0)
{
string cur = q.Dequeue();
if(cur == null)
{
cl = new List<string>();

if(q.Count != 0)
{
q.Enqueue(null);
}
}
else
{
foreach(string f in friends[cur])
{
if(!hs.Contains(f)
{
q.Enqueue(f);
}
}
}
}

// Removing the first level wish is itself
result.Remove(0);

return result;
}``````

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

The problem description included taking the values from a File. Your code doesn't do that.

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

``````package inhouse.project;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.HashSet;
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){
}
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>();
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);
}

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])){
}
}
}
}
}``````

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

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.

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

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.

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

This was a written test. So they were looking for a well designed big free code that does the job.

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

``````public static void levelOrder (String start , Map<String,List<String>> graph){
Queue<String> q = new LinkedList<> ();
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);
}
}
}
System.out.println();
level++;
}
}``````

}

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

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

while (levelList.size() != 0)
{

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) {
{
for (String childNode : adjacentMap.get(node)) {
if(!visitedNode.contains(childNode))
{
}

}
}
}
return resultList;
}``````

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

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

while (levelList.size() != 0)
{

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) {
{
for (String childNode : adjacentMap.get(node)) {
if(!visitedNode.contains(childNode))
{
}

}
}
}
return resultList;
}``````

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

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

while (levelList.size() != 0)
{

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) {
{
for (String childNode : adjacentMap.get(node)) {
if(!visitedNode.contains(childNode))
{
}

}
}
}
return resultList;
}

public static void main(String[] args) {
FriendLevelFinder friends = new FriendLevelFinder();

Map<String, List<String>> adjMap = new HashMap<>();

Map<Integer, List<String>> levels = friends.levelCalulator(adjMap, "A");

System.out.println(levels);
}

}``````

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

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

while(nextLevel.size()>0) {
currentLevel = new ArrayList<String>();
for (String str: nextLevel){
if(listRelationShip.get(str)!=null && listRelationShip.get(str).size()>0){
}
}
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)){
}
}
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){
}
listRelationShip.put(relation[0], arrList);
}
}

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

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

while(nextLevel.size()>0) {
currentLevel = new ArrayList<String>();
for (String str: nextLevel){
if(listRelationShip.get(str)!=null && listRelationShip.get(str).size()>0){
}
}
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)){
}
}
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){
}
listRelationShip.put(relation[0], arrList);
}
}``````

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

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

while(nextLevel.size()>0) {
currentLevel = new ArrayList<String>();
for (String str: nextLevel){
if(listRelationShip.get(str)!=null && listRelationShip.get(str).size()>0){
}
}
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)){
}
}
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){
}
listRelationShip.put(relation[0], arrList);
}
}``````

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

``````//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'));``````

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

``````//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'));``````

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

``````package com.loadgeneral.projects;

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.io.IOException;
import java.util.Set;
import java.util.HashSet;

import java.util.TreeMap;
import java.util.Queue;

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

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

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

}``````

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

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

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.