Amazon Interview Question Web Developers
Country: United States
@Nbob : ideally we should not maintain m_level in class...
we can print level by level without maintaining this also ..
push a dummy node each time u push all the friends of a member node.... while pop() ing, when ever we come across dummy node .. means we have covered a level ...
may be maintaing adjaceny list of Graph will be sufficient for this problem. so that we can print levels easily. correct me if I am wrong
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FBFriends {
/**
* @param args
*/
public static void main(String[] args) {
Member m = new Member(1,"A");
Member m1 = new Member(2,"B");
Member m2 = new Member(3,"C");
Member m3 = new Member(4,"D");
Member m11 = new Member(5,"E");
Member m22 = new Member(6,"F");
Member m33= new Member(7,"G");
Member m111 = new Member(8,"H");
Member m222 = new Member(9,"I");
Member m333= new Member(10,"J");
List<Member> l3 = new ArrayList<Member>();
List<Member> l2 = new ArrayList<Member>();
List<Member> l1 = new ArrayList<Member>();
l3.add(m111);
l3.add(m222);
l3.add(m333);
m11.setFriends(l3);
m22.setFriends(l3);
l2.add(m11);
l2.add(m22);
l2.add(m33);
m2.setFriends(l2);
m3.setFriends(l2);
l1.add(m1);
l1.add(m2);
l1.add(m3);
m.setFriends(l1);
System.out.print(" You ("+m.getNo()+","+m.getName()+") ");
printData(m.getFriends(), 0, 5);
}
public static void printData(List<Member> mem,int level,int n){
List<Member> nm = new ArrayList<Member>();
System.out.print("\n Level "+level+" [");
String sep = "";
Map<Member,List<Member>> nhMap = new HashMap<Member, List<Member>>();
for(Member m: mem){
System.out.print(sep+" Friend ("+m.getNo()+","+m.getName()+")");
if(m.getFriends() != null)
//nm.addAll(m.getFriends());
nhMap.put(m, m.getFriends());
sep = ",";
}
System.out.print("]\n");
level++;
if(level >= n || nhMap.size() == 0) return;
printNameData(nhMap, level, n);
}
public static void printNameData(Map<Member,List<Member>> hmap,int level, int n){
Map<Member,List<Member>> nhMap = new HashMap<Member, List<Member>>();
System.out.print("\n Level "+level+" [");
String sep = "";
for(Map.Entry<Member,List<Member>> mem:hmap.entrySet()){
System.out.print(sep+" Friends via ("+mem.getKey().getNo()+","+mem.getKey().getName()+")[");
sep = "";
for(Member m: mem.getValue()){
System.out.print(sep+" Friend ("+m.getNo()+","+m.getName()+")");
if(m.getFriends() != null)
nhMap.put(m, m.getFriends());
sep = ",";
}
System.out.print("]");
}
System.out.print("]\n");
level++;
if(level >= n || nhMap.size() == 0) return;
printNameData(nhMap, level, n);
}
}
Assuming this is done in Javascript, couldn't this be done by populating a 2D array with levels & names, then just printing off that list? Would this be too inefficient?
// Init levels listing & add top member
var levels = new Array();
levels[0] = new Array();
levels[0][0] = me.name;
function printFriendsByLevel(Member m) {
// Populate list recursively
populateLevels(1, m.friends);
// Print the list
for(var i=0; i<levels.length; i++) {
for(var j=0; j<levels[i].length; j++) {
print(levels[i][j])
}
print("</br>");
}
}
function populateLevels(level, friends) {
if(!levels[level]) {
levels[level] = new Array();
}
index = level.length;
for (var friend in friends) {
levels[level][index] = friend.name;
index = index + 1;
populateLevels(level + 1, friend.friends);
}
}
How about use a HashSet to track already seen friends so that you don't print a friend twice. And use two indices to track levels just like level tree order print. Let me know if this is wrong, I will really appreciate
//Breadth First Search Strategy but shouldn't print friends twice. Also print in levels
void printSocialGraph(Member m){
// Strategy: First Queue but add the already printed friends in HashSet so as not to repeat.
// We use two iterators to track levels.
if(m==null) return; //If m is null quit.
Queue<Memeber> q = new Queue<Member>();
HashSet<Member> printed = new HashSet<Member>();
q.push(m);
printed.add(m);
int level=1;
int friendsCurLevel=m.friends.size();
int friendsNxtLevel=0;
System.out.println("\n Level "+level+" Friends: ")
while(!q.isEmpty()){
Member tmpMember = q.pop();
List<Member> l = tmpMember.friends;
for (int i=0; i<l.size();i++){
tmpMember = l.get(i);
if (!printed.contains(tmpMember)){
printed.add(tmpMember);
System.out.println("Name:"+ tmpMember.name+", Email:" + tmpMember.email);
friendsCurLevel--;
addListQueue(tmpMember.friends, q)
friendsNxtLevel=friendsNxtLevel+tmpMember.friends.size();
}
}
if(friendsCurLevel==0)
{
level++;
System.out.println("\n Level "+level+" Friends:")
friendsCurLevel=friendsNxtLevel;
friendsNxtLevel=0;
}
}
}
void addListQueue(List<Member> l, Queue<Member> q){
for (int i=0;i<l.size();i++){
q.push(l.get(i));
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
/**
* Assume primitive Facebook. FB has Members.
*
* class Member {
* String name;
* String email;
* List<Member> friends;
* }
*
* Question A:
* Code printSocialGraph(Member m). Direct friends of m are Level 1 friends.
* Friends of friends are level 2 friends.....and so on. Print level 1
* friends first. Then print level 2 friends....and so on.
*
* Enumerate test cases to verify the implementation is correct.
*/
public class Facebook {
public static final int LEVELS = 10;
public static void main(String args[]) {
Member james = new Member("James", "james@email.com");
Member samita = new Member("Samita", "samita@email.com");
Member sreeja = new Member("Sreeja", "sreeja@email.com");
Member umesh = new Member("Umesh", "umesh@email.com");
Member shreya = new Member("Shreya", "shreya@email.com");
Member dipesh = new Member("Dipesh", "dipesh@email.com");
Member namrata = new Member("Namrata", "namrata@email.com");
Member deepna = new Member("Deepna", "deepna@email.com");
Member anjaan = new Member("Anjaan", "anjaan@email.com");
Member alien = new Member("Alien", "alien@email.com");
james.add(samita).add(sreeja).add(umesh).add(shreya).add(dipesh).add(namrata);
samita.add(james).add(sreeja).add(umesh).add(shreya).add(namrata);
sreeja.add(james).add(samita).add(umesh).add(shreya);
umesh.add(james).add(samita).add(sreeja).add(shreya);
shreya.add(james).add(samita).add(sreeja).add(umesh).add(dipesh);
dipesh.add(shreya).add(deepna);
namrata.add(james).add(samita);
deepna.add(anjaan);
anjaan.add(alien);
printSocialGraph(umesh, LEVELS);
}
public static void printSocialGraph(Member member, int level) {
if(member!=null && level>=1) {
Map<String, Map<String, Member>> map = new HashMap<String, Map<String, Member>>();
Map<String, Member> self = new HashMap<>();
self.put(member.getName(), member);
map.put("0", self);
printSocialGraph(member, level, 1, map);
}
}
private static void printSocialGraph(Member member, int level, int current, Map<String, Map<String, Member>> map) {
if(current<=level) {
Map<Member, String> members = new HashMap<Member, String>();
Map<String, Member> newMap = new HashMap<String, Member>();
if(current == 1) {
if(member.getFriends()!=null) {
for(Member m: member.getFriends()) {
newMap.put(m.getName(), m);
}
}
map.put("1", newMap);
} else {
for(int i=0; i<current; i++) {
for(Entry<String, Member> entry: map.get(""+i).entrySet()) {
members.put(entry.getValue(), "");
}
}
for(Entry<Member, String> em: members.entrySet()) {
if(em.getKey().getFriends()!=null){
for(Member network: em.getKey().getFriends()) {
if(members.get(network)==null) {
newMap.put(network.getName(), network);
}
}
}
}
map.put(""+current, newMap);
}
printSocialGraph(member, level, ++current, map);
} else {
for(int i=0; i<current; i++) {
System.out.println("\nLEVEL: "+i);
System.out.println("*********");
for(Entry<String, Member> entry: map.get(""+i).entrySet()) {
System.out.println(entry.getValue().getName());
}
}
}
}
}
class Member {
private String name;
private String email;
private List<Member> friends;
public Member(String name, String email) {
this.name = name;
this.email = email;
}
public Member add(Member member) {
if(this.friends==null) {
this.friends = new ArrayList<>();
}
this.friends.add(member);
return this;
}
public String getName() {
return this.name;
}
public String getEmail() {
return this.email;
}
public List<Member> getFriends() {
return this.friends;
}
}
---------- OUTPUT ----------
LEVEL: 0
*********
Umesh
LEVEL: 1
*********
James
Shreya
Sreeja
Samita
LEVEL: 2
*********
Dipesh
Namrata
LEVEL: 3
*********
Deepna
LEVEL: 4
*********
Anjaan
LEVEL: 5
*********
Alien
LEVEL: 6
*********
LEVEL: 7
*********
LEVEL: 8
*********
LEVEL: 9
*********
LEVEL: 10
*********
Using BFS on the constructed graph and maintaining a level value internally in the object on the fly.
- Nbob March 23, 2013#include <iostream> #include <stdlib.h> #include <vector> #include <queue> using namespace std; class Member { public: Member(string name, string email) { m_name = name; m_email = email; m_level = 0; } void AddFriend(Member* m) { m_friends.push_back(m); } int NumberOfFriends() { m_friends.size(); } void GetAllFriends(vector<Member*>& f) { f = m_friends; } int GetLevel() { return m_level; } string name() { return m_name; } void PrintSocialGraph() { queue<Member*> q; q.push(this); while (!q.empty()) { Member* m = q.front(); q.pop(); cout << "Level:" << m->GetLevel() << "--->" << m->name() << '\n'; vector<Member*> f; vector<Member*>::iterator it; m->GetAllFriends(f); int level = m->GetLevel(); for (it = f.begin(); it != f.end(); it++) { q.push(*it); (*it)->SetLevel(level+1); } } } void SetLevel(int level) { m_level = level; } private: vector<Member*> m_friends; string m_name; string m_email; int m_level; }; int main() { Member m1(string("A"), string("A@gmail.com")); Member m2(string("B1"), string("B1@gmail.com")); Member m3(string("C1"), string("C1@gmail.com")); Member m4(string("D1"), string("D1@gmail.com")); Member m5(string("E2"), string("E2@gmail.com")); Member m6(string("F2"), string("F2@gmail.com")); Member m7(string("G2"), string("G2@gmail.com")); Member m8(string("H2"), string("H2@gmail.com")); Member m9(string("I2"), string("I2@gmail.com")); Member m10(string("J2"), string("J2@gmail.com")); Member m11(string("K2"), string("K2@gmail.com")); Member m12(string("L2"), string("L2@gmail.com")); Member m13(string("M2"), string("M2gmail.com")); Member m14(string("N3"), string("N3@gmail.com")); Member m15(string("O3"), string("O3@gmail.com")); Member m16(string("P3"), string("P3@gmail.com")); Member m17(string("Q3"), string("Q3@gmail.com")); Member m18(string("R3"), string("R3@gmail.com")); // Add friends of M1. m1.AddFriend(&m2); m1.AddFriend(&m3); m1.AddFriend(&m4); // Add m2 firnds m2.AddFriend(&m5); m2.AddFriend(&m6); m2.AddFriend(&m7); // Add m3 friends m3.AddFriend(&m8); m3.AddFriend(&m9); m3.AddFriend(&m10); // Add m4 friends m4.AddFriend(&m11); m4.AddFriend(&m12); m4.AddFriend(&m13); // Add m5 friends m5.AddFriend(&m14); m5.AddFriend(&m14); m5.AddFriend(&m16); // Add m6 friends m6.AddFriend(&m17); m6.AddFriend(&m18); m1.PrintSocialGraph(); return 1; }