## Amazon Interview Question for SDE1s

• 0

Country: United States
Interview Type: In-Person

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

Solution depends on the space and time complexity as asked by the interviewer.

1. 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

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

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.

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

@Another Aspirant

Yes, the lists need to be sorted even before they are compared.

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

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

Since A-U-K-B

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

@Another Aspirant -
Note the part about comparing entries and only incrementing one counter at a time.
i.e. if a[1] > b[1] then you only increment the b counter. You are essentially following the steps of creating a merged list, without the extra space.

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

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

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

you don't need else statement in 2nd for loop

``else table.put(x, 0);``

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

what's the ConnectedLeastFriends means?

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

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)

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

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.

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

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

What do you think is the complexity of List.contains() method?

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

@Dumbo - contains(obj) will take O(n) time

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

Start bfs from A as well as B on two threads and keep track already processed nodes

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

If we construct a graph whose edges are all of unit size (i.e., 1), indicating a contact connection between node A and node B, then BFS traversal from A to B will produce the shortest path between A and B. O(|V| + |E|).
Please correct me if I am wrong.

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.