Amazon Interview Question SDE1s
Country: United States
Interview Type: In-Person
Solution 2 : If used with two lists will lead to o(n^2) for comparison because if you increase pointer of both lists simultaneously, you might be missing some match which are not at the same place even in sorted list.
For o(nlogn) solution we can go for one merged list n sort them n compare if two consecutive entries are same at any point.
Your solution works for the common friends list not the connected friend list. This is the problem of graph. Using shortest path Algorithm can be solved this problem.
For eg: Suppose Alphabets represent person.
|A| - F-G-H-U-I
|U| - W-G-H-N-J-K-A
|k| - I-A-J-P-B-U
|P| - Q-G-J-K-B
|B| - K-O-L-M-Y
Answer should be U,K
Since A-U-K-B
void printConnectedFriends(Person A, Person B) {
List<Person> AsFriends = friendList(A);
List<Person> BsFriends = friendList(B);
Map<Person,Integer> table = new HashMap<Person,Integer>();
for (Person x: AsFriends) {
table.put(x,0);
}
boolean no_common_friends = true;
for (Person x: BsFriends) {
if ( table.get(x) != null ) {
System.out.println("Connected Friend: "+x);
no_common_friends = false;
}
else table.put(x, 0);
}
if ( no_common_friends ) {
System.out.println("NONE");
return;
}
}
Solution without using any extra data-structure space :
void printConnectedFriends(Person A, Person B) {
List<Person> friendsOfA = friendList(A);
List<Person> friendsOfB = friendList(B);
boolean connection_found = false;
for(Person person : friendsOfA) {
if(friendsOfB.contains(person) || friendsOfB.contains(A)) {
System.out.println(person);
connection_found = true;
}
}
if(!connection_found)
System.out.println("NONE");
}
Time Complexity = O(n)
Little Correction to my code posted above
void printConnectedFriends(Person A, Person B) {
List<Person> friendsOfA = friendList(A);
List<Person> friendsOfB = friendList(B);
//A & B may be connected. i.e A might be in B's friend list.
friendsOfA.add(A);
boolean connection_found = false;
for(Person person : friendsOfA) {
if(friendsOfB.contains(person) ) {
System.out.println(person);
connection_found = true;
}
}
if(!connection_found)
System.out.println("NONE");
}
Solution depends on the space and time complexity as asked by the interviewer.
- Murali Mohan July 08, 20131. A solution with O(n) space and time complexity is possible if the first list can be put into a hashmap and while traversing the second list, check if the friend is present in the hashmap and print it. If no common element is found print NONE in the end
2. If no extra space is to be used, sort both the lists- this results in time complexity of O(nlgn). Then check for common elements by comparing elements from both the lists and incrementing the pointers until either one of or both of the lists gets exhausted. If no common element is found print NONE in the end